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

[provincialka]

Хм... А может, использовать для представления отношений графы? Правда, их тут рисовать замучаешься...
alf1234, вы знаете, как связаны бинарное отношение и ориентированный граф? А как выглядит граф транзитивного отношения?

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

1) $(a,a)$ и $(b,b)$, не получится построить транзитивное отношение.

Ох! Вы, наверное, имеете в виду, что здесь нет пар вида $(a,b), (b,c)$, для которых можно проверять условие транзитивности? Ну, на нет и суда нет! Значит, требуемое условие выполняется. Ведь не нарушается же оно!

[alf1234]

mihaild в сообщении #1142060 писал(а):

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

$$\{\}, \{(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$ двойных отношений на двухэлементном множестве рефлексивны?

Спасибо!
Транзитивны первые 6, затем 10, 12, 13, 14, 15.
Правильно ли?

А вот рефлексивность не понимаю -- как проверять, потому как не очевидно как пары связывать отношением $R$.

ТО есть как проверить, напимер верно ли $(a,a)R(a,a)$? Вот не очевидно это...

Если бы в качестве элементов множества рассматривались не пары чисел, а просто числа и было бы известно, что за отношение $R$, тогда очевидно.

-- 05.08.2016, 00:07 --

provincialka в сообщении #1142086 писал(а):

Хм... А может, использовать для представления отношений графы? Правда, их тут рисовать замучаешься...
alf1234, вы знаете, как связаны бинарное отношение и ориентированный граф? А как выглядит граф транзитивного отношения?

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

1) $(a,a)$ и $(b,b)$, не получится построить транзитивное отношение.

Ох! Вы, наверное, имеете в виду, что здесь нет пар вида $(a,b), (b,c)$, для которых можно проверять условие транзитивности? Ну, на нет и суда нет! Значит, требуемое условие выполняется. Ведь не нарушается же оно!

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

[provincialka]

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

не очевидно как пары связывать отношением $R$.

А не надо их связывать. Они уже связаны. Или нет.
Например, на множестве $\{a,b\}$ отношение $R_1=\{(a,a),(a,b),(b,b)\}$ рефлексивно, потому что связывает $a$ с $a$ и $b$ с $b$.
А отношение $R_2=\{(a,a),(a,b),(b,a)\}$ не рефлексивно, потому что не связывает $b$ с $b$.

-- 05.08.2016, 00:16 --

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

бинарные отношения -- это ребра ориентированные,

Уж лучше сказать "бинарнОЕ отношенИЕ -- это ребра ориентированные". Вернее, набор таких ребер. Одно отношение = все входящие в него пары, все ребра.

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

Граф транзитивного отношения, наверное, просто ориентированный пусть, соединяющий три вершины....

Вы имели в виду "путь"? Все равно неверно. Вернее, бессмысленное высказывание.

Граф транзитивного отношения -- это граф обладающий неким свойством. А не "путь".

[mihaild]

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

Транзитивны первые 6, затем 10, 12, 13, 14, 15.

Почему, например, вы считаете $\{(a, b), (a, a)\}$ нетранзитивным? А $\{(a, b), (a, a), (b, a)\}$?

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

А вот рефлексивность не понимаю -- как проверять, потому как не очевидно как пары связывать отношением $R$.

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

[alf1234]

Я вроде как исправился, не знаю -- насколько верно. Но насчет пустого отношения под пунктом 1 -- не знаю, вроде бы если ничего нет, то любые свойства выполняются, в том числе рефл, симм, транзитивность.

1) $\{\}$

2) $\{(a,a)\},$ рефлексивное, симметричное, транзитивное

3) $\{(b,a)\}$, нерефлексивное, несимметричное, транзитивное

4) $ \{(a,b)\}$ нерефлексивное, несимметричное, транзитивное

5) $ \{(b,b)\}$ рефлексивное, симметричное, транзитивное

6) $ \{(b,a),(b,b)\}$, нерефлексивное, несимметричное, транзитивное

7) $ \{(a,b),(b,b)\}$, нерефлексивное, несимметричное, транзитивное

8) $\{(a,a),(b,b)\}$, рефлексивное, симметричное, транзитивное

9) $\{(a,b),(a,a)\}$, нерефлексивное, несимметричное, транзитивное

10) $ \{(b,a),(a,a)\}$, нерефлексивное, несимметричное, транзитивное

11) $ \{(b,a),(a,b)\}$, нерефлексивное, симметричное, нетранзитивное

12) $\{(a,b),(b,a),(b,b)\}$, нерефлексивное, симметричное, нетранзитивное

13) $\{(a,b),(a,a),(b,b)\}$, нерефлексивное, несимметричное, транзитивное

14) $\{(a,b),(a,a),(b,a)\}$, нерефлексивное, несимметричное, нетранзитивное

15) $\{(b,a),(a,a),(b,b)\}$, рефлексивное, несимметричное, транзитивное

16) $ \{(a,b),(a,a),(b,a),(b,b)\}$, рефлексивное, симметричное, транзитивное

-- 06.08.2016, 23:27 --

Получается, вроде бы 13 транзитивных отношений!

[provincialka]

(2) и (5) не рефлексивные. Сравните с (6) или (7), скажем.

Все читать как-то скучно... Попробуйте все-таки применить логику. Для такого маленького носителя проще перечислить нетранзитивные отношения.

Посмотрим на основное условие: $aRb, bRc \Longrightarrow aRc$.
В любой тройке $(a,b,c)$ какие-нибудь элементы совпадают.

Например, если в отношение входят пары $(a,a)$ и $(a,b)$, то в силу транзитивности должна входить и пара $(a,b)$, что, естественно, выполняется (здесь можно учитывать и случай $b=a$.) Аналогично рассматривается случай $(a,b)$ и $(b,b)$.

Единственный нетривиальный случай -- когда $R$ содержит $(a,b)$ и $(b,a)$. Тогда в силу транзитивности оно должно содержать и $(a,a)$ и $(b,b)$.

Теперь легко перечислить те отношения, для которых это свойство не выполняется. Действительно, их ровно 3.

-- 07.08.2016, 00:03 --

Хм... как вы будете такими методами решать второе, а тем более третье задание? Ну, ничего! Главное понять само свойство транзитивноси!

[mihaild]

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

Но насчет пустого отношения под пунктом 1 -- не знаю, вроде бы если ничего нет, то любые свойства выполняются

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

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

3) $\{(b,a)\}$, нерефлексивное, несимметричное, транзитивное

Вот например почему это отношение нерефлексивно, несимметрично, нетранзитивно? Какие элементы нужно подставить вместо переменных, чтобы получились ложные утверждения?

(Оффтоп)

provincialka в сообщении #1142487 писал(а):

Хм... как вы будете такими методами решать второе, а тем более третье задание? Ну, ничего! Главное понять само свойство транзитивноси!

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

[alf1234]

Хорошо, спасибо.
А как быть с $\{\}$?
Я не очень понимаю, что такое пустое отношение, видимо. Это как может быть?
Я понимаю, что бинарное отношение на множестве $A $— любое подмножество ${\displaystyle R\subseteq A^{2}=A\times A}$
Допустим, что есть пустое подмножество $A\times A$. Там нет элементов. Как же можем проверять на рефлексивность, если проверять нечего?

А почему $\{(a,a)\},$ нерефлексивное? Потому как не выполняется $bRb$? Но ведь подмножество $\{(a,a)\},$ не содержит элемент $b$ или я что-то не так понимаю?

[provincialka]

mihaild
Нет, что вы! Какие же "обвинения"? Просто сочувствую! Жалею, так сказать

-- 07.08.2016, 00:16 --

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

Допустим, что есть пустое подмножество $A\times A$. Там нет элементов. Как же можем проверять на рефлексивность, если проверять нечего?

И что? Зато в самом носителе $A$ элементы же есть? Вот для них и проверять!

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

Но ведь подмножество $\{(a,a)\},$ не содержит элемент $b$ или я что-то не так понимаю?

Опять путаете отношение и его носитель. Элемент $b$ принадлежит $A$, так ведь?

[alf1234]

Все, понял про пустое отношение, спасибо. Оно нерефлексивно, симметрично, транзитивно.

Цитата:

3) $\{(b,a)\}$, нерефлексивное, несимметричное, транзитивное
Вот например почему это отношение нерефлексивно, несимметрично, нетранзитивно? Какие элементы нужно подставить вместо переменных, чтобы получились ложные утверждения?

Нерефлексивно, потому как не содержит элементов $(a,a)$ и $(b,b)$. Рефлексивное замыкание будет $\{(b,a),(a,a),(b,b)\}$

Несимметрично, потому как не содержит элемента $(a,b)$. Симметричное замыкание будет $\{(b,a),(a,b)\}$

Нетранзитивно, потому как нет элементов $(a,a)$ и $(b,b)$ (могу расписать подробнее, здесь я уверен). Транзитивное замыкание будет $\{(b,a),(a,a),(b,b), (a,b)\}$.

Правильно? Да, мне бы хоть на двухэлементном разобраться, для начала)) Но, вроде бы, начал что-то понимать.

-- 07.08.2016, 00:20 --

provincialka в сообщении #1142491 писал(а):

Опять путаете отношение и его носитель. Элемент $b$ принадлежит $A$, так ведь?

Точно-точно, вы правы. А раз отношение задано на множестве $A$, то проверяя рефлексивность, нужно проверять для каждого элемента множества $A$.

[mihaild]

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

Нетранзитивно, потому как нет элементов $(a,a)$ и $(b,b)$ (могу расписать подробнее, здесь я уверен).

Ну распишите. Вот определение транзитивности: $\forall x,y,z \in A: xRy \land yRz \Rightarrow xRz$. Что вы подставляете вместо $x, y, z$?
(и я при переписывании ухитрился вас переврать, а вы не заметили - вы сначала правильно написали, что оно транзитивно)

[provincialka]

Обычно я стараюсь рассказывать эту тему, используя нематематические, бытовые примеры. Но для рефлексивности этот метод не подходит: в естественно языке практически нет рефлексивных понятий... вот как-то не нужны они!
Например, понятие "сестра" на множестве женщин -- рефлексивное?

Цитата:

На стене висит портрет дочери моих родителей, но не моей сестры. Чей?

"Дочь/сын моих родителей" -- рефлексивное отношение. Но для него в языке нет термина.

Вообще, рефлексивное отношение-- то, которое содержит в себе равенство. Например,"равно", $\leqslant$, $\subset$ -- рефлексивны. Потому что для любого числа $a$ выполняется $a\leqslant a$, и для любого множества $X$ верно, что $X\subset X$

[alf1234]

Ой, это я напрасно был уверен. Ведь у нас есть только $(b,a)$.

Если выберем $x=b$, $y=a$, то пары $(y,z)$ не найдется, потому как в отношении $\{(b,a)\}$ нет просто пары, где бы первый элемент был бы $a$, а значит посылка будет ложной, а значит импликация верна, а значит отношение транзитивно.
Кстати, правильно ли я понимаю, что транзитивное замыкание будет $\{(b,a)\}$, то есть не обязательно чего либо добавлять?

[mihaild]

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

а значит импликация верна, а значит отношение транзитивно

Формально нужно проверить еще все остальные варианты подстановки элементов вместо переменных.

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

транзитивное замыкание будет $\{(b,a)\}$, то есть не обязательно чего либо добавлять?

Да. И не просто "не обязательно", а нельзя - транзитивное замыкание это минимальное транзитивное отношение, содержащее наше - и если отношение уже транзитивно, то его транзитивное замыкание с ним совпадает.

[provincialka]

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

мне бы хоть на двухэлементном разобраться, для начала)) Но, вроде бы, начал что-то понимать.

На самом деле двухэлементное множество позволяет разобрать трудную для новичка часть задания, в которой некоторые из элементов, упомянутых в условии, совпадают между собой. В "более крупных" множествах нужно будет только добавить проверку для троек различных элементов, а это проще. Интуитивно более понятно.