Сколько отношений транзитивности на множестве?

[alf1234]

А почему же, поменялись ведь местами $a$ и $b$ в итоге, то есть разные следствия или нет? Просто я пока не понимаю -- в какую сторону думать.

[Anton_Peplov]

Так, прошу прощения, там уже я посмотрел невнимательно.

[alf1234]

А еще есть ли какие-то отношения транзитивности здесь или нет, вот чего не пойму...

[mihaild]

alf1234 в сообщении #1141837 писал(а):

Спасибо! Вот бинарные отношения: $(a,a)$, $(a,b)$, $(b,a)$, $(b,b)$.

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

Теперь, как транзитивность записывается в терминах бинарного отношения, как множества? Вида "если что-то принадлежит отношению, то и еще что-то ему принадлежит".

alf1234 в сообщении #1141847 писал(а):

Если $a\le b$ и $b\le a$, то $a\le b$

Нет, должно быть "Если $a\le b$ и $b\le a$, то $a\le a$".

[arseniiv]

Можно рисовать бинарные отношения над конечным множеством как квадратные таблицы, клетки которых закрашены или пустые. Рефлексивное отношение должно будет иметь закрашенную диагональ (главную). Симметричное — совпадать со своим отражением относительно диагонали. С транзитивным не всё так просто, но картинки, по крайней мере, могут быть удобны.

-- Ср авг 03, 2016 23:06:09 --

Это, конечно, должно быть очевидным после комментария Anton_Peplov про связь функций в $\{0,1\}$ и отношений, но лишним не будет.

-- Ср авг 03, 2016 23:08:28 --

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

[alf1234]

$\{(a,a),(a,b),(b,a),(b,b)\}$?

-- 03.08.2016, 21:13 --

Четыре пары?

[arseniiv]

Это только одно из них. Остальные — его подмножества.

[alf1234]

Всевозможные подмножества, которых 8 штук?

[mihaild]

1) сколько подмножеств у четырехэлементного множества?
2) все ли возможные бинарные отношения на двухэлементном множестве (которые как раз и являются всеми подмножествами выписанного вами множества) транзитивны?

[alf1234]

1) Думаю, что 16 все-таки.
2) Думаю, что не все...

-- 04.08.2016, 11:39 --

Мне бы понять, как транзитивность проверять хотя бы для одной пары...Дальше бы сам..

[Aritaborian]

Вам ведь уже подсказали:

arseniiv в сообщении #1141903 писал(а):

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

Можно ручками, а можно программку написать ;-)

[alf1234]

Я эту подсказку не очень понял. Как сделать замыкание двухэлементного множества?

-- 04.08.2016, 14:35 --

Вроде бы здесь $\{(a,a),(a,b),(b,a),(b,b)\}$ симметричное замыкание совпадает с самим множеством. А вот как строить транзитивное замыкание не представляю. Как узнавать -- какие клетки закрашивать, а какие -- нет? Мне изначальный принцип не очевиден. Вроде должна быть таблица вида из четырех строк и четырех столбцов.

-- 04.08.2016, 14:40 --

[mihaild]

Чтобы строить транзитивное замыкание по таблице - делаете таблицу 2х2, в которой по строкам и столбцам - элементы множества, а в ячейках - 1, если соответствующая пара (элемент из строки, элемент из столбца) принадлежит отношению, и 0 иначе.

Теперь, если в клетках $(i, j)$ и $(j, k)$ (какие-то из $i, j, k$ могут совпадать) стоят единицы, то и в клетку $j, k$ ставится единица.

Но ИМХО это не очень хорошее объяснение - лучше думать сразу о транзитивных множествах.
Формальной подстановкой в определение транзитивности всех возможных троек элементов из двухэлементного множества, получается $8$ условий. $6$ из них тождествено выполнены, остается $aRb \land bRa \Rightarrow aRa$ и $bRa \land aRb \Rightarrow bRb$. Это значит, что если в отношении (подмножестве четырехэлементного множества всех пар элементов) есть одновременно $(a, b)$ и $(b, a)$, то там должны быть и $(a, a)$ и $(b, b)$.
Соответственно, нам достаточно посмотреть, есть ли пары $(a, b)$ и $(b, a)$ одновременно - если нет, то мы можем брать или не брать $(a, a)$ и $(b, b)$ произвольно, а если есть - то обязаны эти две пары взять.

[alf1234]

Спасибо, вроде бы понятно. Если в отношении есть пары $(a, b)$ и $(b, a)$ , то мы сможем построить такие отношения транзитивности $aRb \land bRa \Rightarrow aRa$ и $bRa \land aRb \Rightarrow bRb$ (получается уже есть одно отношение).
Рассмотрим сначала одноэлементное подмножество множества пар элементов:
1) Есть в отношении только $(a,a)$, то мы отсюда сможем только построить вот такую ерунду я $aRa \land aRa \Rightarrow aRa$ (считается ли это транзитивностью?).
2) Если в отношении есть только $(b,b)$, то аналогично $(a,a)$ c точностью до переобозначения.
Если в отношении есть только $(a,b)$, то не получится построить транзитивность (с только $(b,a)$ аналогично).
Рассмотрим двухэлементное подмножество множества пар элементов:
1) $(a,a)$ и $(b,b)$, не получится построить транзитивное отношение.
2) $(a,a)$ и $(a,b)$ получится
3) $(a,a)$ и $(b,a)$ получится
4) $(b,b)$ и $(b,a)$ получится
5) $(b,b)$ и $(a,b)$ получится
Рассмотрим трехэлементное подмножество множества пар элементов:
1) $(a,a)$ и $(b,b)$ и $(a,b)$
В четырех случаях получится.
2) $(a,a)$ и $(b,b)$ и $(b,a)$
В четырех случаях получится.
3) Если есть $(b,a)$ и $(b,a)$, то не получится, потому как должно быть четыре элемента.

Правильно ли это или я бред пишу?

[mihaild]

Вам, кажется, нужно более аккуратно следить за терминологией.

Бинарное отношение $R$ на $X$ - некоторое множество пар элементов из $X$.
Оно может быть транзитивным, а может не быть.
Оно транзитивно, если выполнено утверждение $\forall x,y,z \in X: xRy \land yRz \Rightarrow xRz$.

Что значит "считается транзитивностью", "построить транзитивность" - непонятно.
Что имеется в виду "не получится построить транзитивное отношение" - тоже (при каких условиях не получится?).

Вот вам все бинарные отношения на двухэлементном множестве:

$$\{\}, \{(b,b)\}, \{(b,a)\}, \{(b,a),(b,b)\}, \{(a,b)\}, \{(a,b),(b,b)\}, \{(a,b),(b,a)\}, \{(a,b),(b,a),(b,b)\},$$

$$\{(a,b),(a,a)\}, \{(a,b),(a,a),(b,b)\}, \{(a,b),(a,a),(b,a)\}, \{(a,b),(a,a),(b,a),(b,b)\}, \{(a,a)\},$$

$$\{(a,a),(b,b)\}, \{(a,a),(b,a)\}, \{(a,a),(b,a),(b,b)\}$$

Какие из них транзитивны, какие нет? Для нетранзитивных - что нужно подставить вместо $x, y, z$ в условие транзитивности, чтобы получить неверную импликацию?

-- 04.08.2016, 18:31 --

Если вы не против, можно для начала попробовать решить аналогичную задачу с рефлексивностью вместо транзитивности (она попроще)
Отношение на $X$ рефлексивно, если $\forall x \in X: xRx$. Какие из $16$ двойных отношений на двухэлементном множестве рефлексивны?