?

Log in

No account? Create an account

Previous Entry Share Next Entry
Моему другу Павлику про отношения -- равно человеческие и математические
tilir
ris-d

Отношения -- это то, что действительно заботит людей (в том числе -- математиков и программистов) и, особенно, весной. Многие теряют в них и свою голову и себя, и нужен действительно критичный ум, чтобы подойти к этой проблеме честно и беспристрастно. Я надеюсь, ты помнишь нашу небольшую беседу, посвящённую этой теме, основные мысли которой я хотел бы развить и изложить письменно (потому что есть вещи с которыми сложно справиться устно и экспромтом).



В процессе своего развития, человеческий разум приходит к понятию равенства, одинаковости, идентичности. Всё это -- разные слова для одного и того же сложно выразимого фундаментального понятия. В своей общности оно сравнимо с понятиями "объекта", "процесса", "совокупности" или, скажем "выбора" -- все эти понятия непосредственно следуют из нашей интуиции и естественного языка и не определяются. Равными или неравными между собой мы можем назвать два предмета окружающего нас мира, выделив признак по которому они сравниваются: у двух людей может быть одинаковый цвет кожи, в двух чашках может быть поровну чая, у двух людей может быть равная любовь к искусству.  При этом строгое измерение может показать, что цвет кожи немного отличается, но мы говорим "равен" не смотря на это. Строгое измерение же любви к искусству просто невозможно -- и это нам тоже не мешает.

Таким образом, наше сравнение распространяется как на то, что Лейбниц называл "истины разума", так и на то, что он называл "истины факта" -- и распространяется абсолютно однородно. Лао-Цзы писал, что счастье и несчастье следуют из сравнения, которое есть добровольная пытка ума. Возможно это и так, возможно же это не пытка, а, напротив, наслаждение. Впрочем, это тоже лишь вопрос соотнесения (видишь как изящно захлопываются двери той тюрьмы в которой разум подвергают этой пытке).

Но, что мы точно можем утверждать, так это то, что любые два объекта могут быть соотнесены друг с другом неким бинарным соотношением (ведь если мы попробуем сказать 'a не связано никаким бинарным отношением с b', то 'не быть связанным никаким отношением' -- само по себе будет бинарным отношением между 'a' и 'b', что приводит нас к логическому противоречию, следующему из устройства нашего разума и языка).

И вот, возникает желание навести некий порядок, классифицировав те бинарные отношения, которые возможны в этом мире (возможно более патриотично было бы говорить "в нашем мире") и сведя их к набору возможно более простых свойств. Разумеется ни я ни ты -- не первые люди, которые обращают внимание на этот вопрос. Классификация бинарных отношений основывается на трёх основных их свойствах -- рефлективности, симметричности и транзитивности, определение которых выглядит так: 

Пусть дано отношение R, связывающее x и y как xRy. Оно:
  • Рефлективно, если истинно, что xRx
  • Симметрично, если из xRy следует yRx
  • Транзитивно, если из xRy и yRz следует xRz.

Каждое из этих свойств имеет и свою обратную форму. Отношение не рефлективно, если неверно, что xRx. Обратная форма симметричности несколько сложнее. Дело в том, что если мы назовём асимметричным отношение, в котором из xRy не следует yRx, и подставим y равным x, то мы получим что оно ещё и не рефлективно по определению. Поэтому, чтобы их не смешивать обычно говорят, что симметричность определяется только для разных объектов, в случае же если они равны, их свойства определяются рефлективностью.
И наконец транзитивность обращается так, что из xRy и yRz не следует xRz.

Ты можешь заметить на этом месте, что каждое из рассмотренных свойств можно обратить не меньше, чем двумя способами. Первый способ (на примере симметричности) -- мягкое обращение -- сказать, что из xRy просто не следует yRx (но и не запрещается по совпадению). Второй способ -- строгое обращение -- сказать что из xRy следует что никогда не yRx. Очевидно, что строгое обращение это всегда лишь частный случай мягкого обращения (когда мы запрещаем все случайные совпадения), а значит далее я буду вести речь о мягком обращении, обращаясь к его строгой форме как к частному случаю.

Обозначив выполнение каждого из этих свойств за 1, а невыполнение за 0, мы получим восемь возможных сочетаний (которые удобно проиндексировать двоичными числами от 000b до 111b, где в старшем разряде мы поставим рефлективность, во втором симметричность, а в младшем -- транзитивность.

Давай же рассмотрим и соотнесём со здравым смыслом получившуюся у нас классификацию.

000. Доминирование

Отношение, которое не отвечает ни одному из свойств есть строгое непосредственное доминирование. Оно обозначается как (x `idom` y) и выражает непосредственное предшествование в направленном ациклическом графе. Рассмотри следующий направленный ациклический граф, чтобы понять его суть:

pic-ris1

Здесь верны утверждения:
  • x `idom` y
  • y `idom` a
  • y `idom` b

И неверны все прочие связи. В частности -- неверно, что x `idom` x, поскольку ни один узел не предшествует непосредственно сам себе, из того, что x `idom` y не следует, что y `idom` x (и даже больше того -- следует что y никогда не `idom` x) и аналогично с транзитивностью -- видно, что, хотя x и является дальним предком a и b, он не является их непосредственным предком.

Строгое обращение транзитивности мы получим если в направленном ациклическом графе запретим узлу иметь более одного непосредственного предка. То есть если такой граф как на следующем рисунке будет невозможен.

ris2

С точки зрения человеческих отношений, это отношение биологических отцов и детей. Действительно никто сам не является своим биологическим сыном, если ты являешься чьим-то сыном, он точно не является твоим сыном, и если ты являешься чьим-то сыном ты точно не сын того, кто является его отцом.

С точки зрения программирования, непосредственное доминирование в ациклическом направленном графе это отношение непосредственного наследования. Если обращение транзитивности понимается строго -- то ещё и с запретом множественного наследования.

001. Строгий порядок

Отношение, которое не является ни рефлексивным ни симметричным, но при этом транзитивно -- это строгий порядок. Например рассмотрим операцию над натуральными числами "строго меньше" (x < y). Очевидно, что никакое натуральное число не меньше самого себя, и из (x < y)  следует что никогда не (y < x). Но при этом это отношение транзитивно -- очевидно, что из (x < y) и (y < z) следует (x < z).

В связных ациклических графах, строгий порядок это простое предшествование (например на поиске в ширину).

ris-3-strict
Левый обход задаёт один порядок, правый -- другой, но оба отвечают тому же соотношению.

В человеческих отношениях способов задать строгий порядок это любая иерархия, какая тебе больше нравится (хотя я уверен, что тебе не нравятся иерархии).

В программировании отношение строгого порядка это отношение "быть базовым классом для".

010. Отличимость

Отличимость по какому-то признаку очевидно не рефлексивна -- никто не отличается по какому-то признаку от самого себя. И не обязательно транзитивна, как показывает следующий рисунок:

ris-3-1

Но отличимость всегда симметрична.

Предыдущий рисунок может вводить в заблуждение относительно того, что отличимость может идти только по собственным признакам -- например форме. Чтобы сделать отличимость по не собственным признакам (положению в структуре) наглядной, рассмотрим отношение "иметь различных непосредственных предшественников на направленном ацикличном графе" (обозначим его `pdiff`).

ris4-pdiff

На картинке выполняется только соотношение:
d `pdiff` f

Разумеется всякий узел имеет общего непосредственного предшественника с самим собой, и из того, что два (x, y), (y, z) попарно не имеют общего предшественника, не следует, что (x, z) не имеют общего предшественника.

ris-5-nocommon

e `pdiff` d
d `pdiff` f
но e и f имеют общего предшественника.

Итак, `pdiff` это частный случай отличимости.

Как сделать в этом отношении обращение транзитивности строгим? Это возможно (и оно строгое на структуре предыдущего рисунка, даже если мы будем бесконечно её расширять, вводя далее одного потомка для e и двух для f и так далее), но мне не удалось отыскать никакого смысла, который бы соответствовал бы такому построению (за исключением того, что в получившейся структуре количество листьев всегда будет равно количеству уровней последования -- поскольку на каждом уровне мы сокращаем их количество на два и увеличиваем на три).

В человеческих отношениях "у нас были разные учителя" или "нам нравятся разные фильмы" -- это всё отличимость с нестрого обращённой транзитивностью.

011. Частичное равенство

Это отношение -- первый достаточно крепкий орешек, с которым предстоит столкнуться. Всё дело в том, что выколоть рефлексивность строго -- невозможно. Если у нас есть пары (x, y) и (y, x), которые выполняются по симметричности, то по транзитивности должна выполнятся и (x, x).

Попробуем воспользоваться нестрогим обращением для построения такого отношения. Пусть дано множество X = {x} и операция R, такая, что не каждый элемент x удовлетворяет xRx. Построим множество всех таких элементов и назовём его Y = {x | xRx} = {y}. Тогда по определению yRx = xRy, а если мы теперь построим Z = {y | yRy} = {z}, то из xRy и yRz будет вытекать xRz.

На таком отношении основаны так называемые сетоиды -- интересные объекты в теории доказательств. Но их детальное обсуждение я склонен отложить на потом.

Если несколько ослабить транзитивность и считать, что не только в симметричности x, y -- разные элементы, но и в транзитивности x, y и z обязательно попарно различны, то такое отношение соответствует наличию ненулевого расстояния на решётке.

ris-7

И действительно: если расстояние между a и b ненулевое, верно и обратное, если же расстояние между a и b ненулевое и между b и c -- тоже, то либо a совпадает с c, либо расстояние между ними также ненулевое.

ris-7.1

Можно сказать, что множество {a} частично равно множеству {a, c, d}, достижимому из b за один шаг. Это и есть суть частичного равенства.

100. Ассоциация.

Не менее сложно выколоть рефлексивность и в другую сторону, так, чтобы она выполнялась, остальные же два свойства -- нет. Если мы предположим, что каждый человек любит себя (а это выглядит разумным предположением), то это отношение как раз и будет выражать любовь, в том смысле в каком она особенно понимается весной. Конечно каждый предпочёл бы наделить любовь ещё и симметричностью, но наш мир не идеален.

В объектно-ориентированном программировании, такими свойствами обладает ассоциация объектов по использованию методов друг друга (известное каждому программисту "А знает о B").

ris-8

Любой объект знает о самом себе. Тем не менее, если объект класса User знаект об объекте класса Proxy, обратное не обязательно (собственно объект класса User может быть вообще невидим для объекта класса Proxy), тем более если объект User знает о Proxy, а Proxy знает об Executor, отношения между User и Executor -- крайне туманны.

Подобным же образом устроено отношение "страница видна для" в социальных сетях. Действительно твоя страница вконтакте для тебя всегда видна, но ни коммутативности ни транзитивности этот сервис не предоcтавляет.

101. Нестрогий порядок

Этот случай напротив -- очень хорошо исследован. Пример нестрогого порядка с нестрогим же обращением симметричности -- операции сравнения, например (<=). Очевидно из a <= b не следует, что b <= a, это может случится только если b = a.

Ещё один пример -- логическая импликация. Если из того, что вчера птицы летали низко следует, что сегодня пойдёт дождь, то обратное неверно, рефлективное заключение тавтологично, а если что-то теперь следует из дождя, это следует и из птиц.

Самое наглядное, что тут можно придумать -- это существование пути в направленном графе.

ris-9

Путь от узла к нему самому тривиален. Путь от a к b не означает, что есть обратный путь (на рисунке его и нет). Но путь от a к b и от b к с вместе складываются в путь от a к c.

Ещё одна трактовка частичного порядка -- это порядок множеств по включению.

ris-C

Можно написать (используя теперь <= для обозначения включения), что C <= B <= A.

В программировании частичный порядок на иерархии классов задаётся принципом подстановки Лисков. Если на конкретной иерархии он выполнен, это означает, что любой базовый класс является "более общим" чем любой производный, который является "более частным". Итак отношения частного-общего это тоже частичный порядок.

Частичный порядок присущ и человеческим иерархиям, самый простой пример это "быть начальником" (если мы предположим что каждый человек начальник сам себе).

110. Близость

Соотношение, являющееся и рефлективным и симметричным можно назвать близостью в математическом смысле. Самый простой пример -- пространственная близость. В теории множеств это отношение -- пересечение множеств:

ris-A

Действительно каждое множество имеет с самим собой ненулевое пересечение, и пересечение множеств симметрично. При этом как видно из рисунка, транзитивности может и не быть -- множество A не пересекает C.

На направленных графах также можно промоделировать это отношение отношением "иметь общего предка".

Для людей такое отношение моделирует знакомство (в его более формальном виде: "мы с N представлены") или отношения "иметь общих друзей с", "иметь общие интересы с" и так далее.

111. Эквивалентность.

Самое известное из бинарных соотношений -- оно позволяет формализовать понятие равенства.

ris-B

Рисунок показывает эквивалентность на базе отношения "A относится к той же связной компоненте в графе что и B". Отнесение к одной и той же общности, классу, собственно равенство как мы его интуитивно понимаем -- всё это отношения эквивалентности.

Любое отношение эквивалентности обладает интересным свойством -- оно позволяет на множестве объектов выделить непересекающиеся классы эквивалентности. Если корзинки равны по количеству яблок в них, это бьёт множество всех корзинок на корзинки с одним яблоком, с двумя, с тремя.... Есть такой подход к определению натуральных чисел, когда натуральное число рассматривается как класс эквивалентности всего, что есть в мире в таком количестве. Скажем число "два" это класс в который входят два человека, два яблока, два вагона, две звезды. Именно это свойство эквивалентности позволяет нам говорить о том, что "в этой комнате столько же людей сколько торшеров" -- не будь число "два" классом эквивалентности, это утверждение было бы бессмысленным.

Важно понимать настоящую разницу между равенством с которой я начал этот рассказ и эквивалентностью, которой я его заканчиваю. Если у нас есть класс, то оператор сравнения для его объектов мы можем определить как угодно. Мы можем даже определить его так, что два  объекта которые мы интуитивно называем "одинаковыми" не будут такими. Мы можем определить его даже так, что объект будет сам с собой состоять в любом из перечисленных мной отношений. Но если мы (например) посчитаем и сравним хеш-коды от побитового представления объектов, то это отношение строго задаст отношение эквивалентности, поскольку хеш-коды это определённые числа, а разные числа, сопоставленные объектам, создают разные классы эквивалентности к которым этот объект относится. Причём даже два объекта, которые мы интутитивно называем "разными" случайно попав в один класс -- будут эквивалентны.

В этом и состоит та тонкая разница, которую я хотел тебе объяснить.



  • 1
Доработанная окончательная версия «Решения парадоксов»
ВЕТВЬ /противоречивых суждений/ развёртывается при не фиксировании момента смыслового изменения ВЕДОМОГО /понятия в рассматриваемом вопросе/ полагающегося при переходе из МАКСИМАЛЬНО ВОЗМОЖНОГО (МксВ-ого) к МИНИМАЛЬНО ВОЗМОЖНОМУ (МнмВ-ому) УРОВНЮ ЗАВИСИМОСТИ (УЗ-и) от смысла ВЕДУЩЕГО понятия полагающегося на переднем плане для рассмотрения - Вдщ1 - и, соответственно, из МнмВ-ого к МксВ-ому УЗ-и от смысла ВЕДУЩЕГО понятия оставшегося за кадром или же перешедшего на задний план – Вдщ2 /антонима Вдщ1/.


Смысл ВЕДОМОГО:
«Критянин» перешедшего из МксВ-ого УЗ-и от смысла Вдщ1 «лжецы» к
МксВ-ому УЗ-и от смысла Вдщ2 «не лжецы» стал антонимом прежнему;
«Я» … «ложь» к … «правда» …;


Есть также ВЕТВЬ мнимая, развёртывание которой не связана с «не фиксированием момента …», ибо смыслового изменения полагающего развёртывание ВЕТВИ здесь нет.

Смысл ВЕДОМОГО:
«Ахиллес» не перешедшего из МксВ-ого УЗ-и от смысла Вдщ1 «путь
пройденный черепахой» к МксВ-ому УЗ-и от смысла Вдщ2 «пути не
пройденной черепахой» не допускает обгона;
«Стрела» … «движущаяся» … «покоящаяся»
преподносится как смысл перешедшего к антониму;
«Мнение Платона о ложности последующего мнения Сократа» …
«ПОДТВЕРЖДЕНИЯ /Сократом этого мнения Платона/» … «не
ПОДТВЕРЖДЕНИЯ» ...;
«Времени затраченного» … «преодоления полпути» … «преодоление всего пути»
не допускает достижения конца намеченного пути;
«Буриданов осёл» … «НЕУМЕНИЕ /делать выбор между двумя одинаковыми
стогами сена/» … «УМЕНИЕ» обречёт животное на смерть от голода;
«Сюрпризная дата казни» … «определения надсмотрщика» … «оптимистического
размышления приговорённого» не отменяет его казни в следующей
неделе;
«Брадобрей» … «бреющих себя» … «не бреющих себя» не допускает небритого
вида для брадобрея.



«Куча», «Лысый», «Корабль Тесея», «Яйцо или курица» не полагают развёртываний в отношение к себе даже мнимых ВЕТВЕЙ.








  • 1