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

[alf1234]

Помогите, пожалуйста, разобраться.
Сколько отношений транзитивности на множестве?

1) $A=\{a,b\}$

2) $A=\{a,b,c\}$

3) $A=\{a_1,a_2,...,a_n\}$


1) Мне кажется, что нельзя построить, так как множество должно содержать хотя бы три элемента.

2) $6$

3) $6C_n^3$.

Верно ли это?

[Anton_Peplov]

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

1) Мне кажется, что нельзя построить, так как множество должно содержать хотя бы три элемента.

Приведите, пожалуйста, точное определение транзитивного отношения.

[mihaild]

А что такое "отношение транзитивности"? Может быть "транзитивное отношение"?
В этом предположении:
1 - неверно. Например, пустое отношение является транзитивным.
2 - неверно. Там одних только отношений эквивалентности $5$ штук, а есть еще например $\{<a, a>\}, \{<b, b>\}, \{<c, c>\}$.
3 - т.к. 2 было его частным случаем, то тоже неверно.

[arseniiv]

(Угловые скобки)

…лучше набирать как \langle и \rangle: $\{\langle a,a\rangle\}$.

[alf1234]

Спасибо, вот определение транзитивности:

Бинарное отношение ${\displaystyle R}$ на множестве $ X$ называется транзитивным, если для любых трёх элементов множества $\{a,b,c\}$ выполнение отношений $aRb$ и $ bRc$ влечёт выполнение отношения $aRc$.

Но если есть два элемента, то трех же не найдется? Как так. Или их можно повторять?

[arseniiv]

Можно. Вообще, если бы разными буквами должны были бы называться обязательно разные вещи, было бы бессмысленно писать формулы типа $x=y$. А они такие красивые, жалко как-то — так что да ну такое ограничение.

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

[Anton_Peplov]

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

Или их можно повторять?

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

[alf1234]

Спасибо, правильно ли я начал выписывать?

1) $aRb\land bRa\Rightarrow aRa$

$bRa\land aRb\Rightarrow bRb$

$aRa\land bRa\Rightarrow aRa$

$bRb\land bRa\Rightarrow bRb$

$aRa\land aRa\Rightarrow aRa$

$bRb\land bRb \Rightarrow bRb$




.

[mihaild]

alf1234, по модулю опечаток вроде

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

$bRb\land bRa\Rightarrow bRb$

(в левой части должно быть $bRa$) - правильно.
(плюс некоторые из выписанных формул - тавтологии, содержательны только первые две)

[alf1234]

Спасибо!!! А откуда модуль?) Получается, два отношения транзитивности?

[mihaild]

alf1234, "по модулю Х" в данном случае означает "если не учитывать Х" (выражение, по всей видимости, пошло от факторизации модулей над кольцами), никакого строгого смысла здесь нет.

Если под "отношением транзитивности" вы понимаете транзитивное отношение - то нет, не два. Откуда вы взяли это число?
Вы выписали условия, при котором отношение на двухэлементном множестве транзитивно (точнее, часть этих условий - т.к. переменных под кванторами всеобщности 3, а элементов 2, то формально получается 8 условий; но часть из них (включая все невыписанные) всё равно являются тавтологиями). Теперь вам нужно посчитать, сколько отношений, удовлетворяющих этим условиям.
Начнем с более простого - сколько всего бинарных отношений на двухэлементном множестве?

[alf1234]

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

$aRb\land bRa\Rightarrow aRa$

$bRa\land aRb\Rightarrow bRb$

Остальные получаются у меня тавтологии

[Anton_Peplov]

alf1234
Я что-то никак не могу сообразить, с какого конца Вы начали. Бинарное отношение - это фактически функция двух переменных во множество $\{0, 1\}$. То, что $a \varphi b$ и $\neg \ a\varphi c$, можно выразить как $\varphi(a, b) = 1$ и $\varphi(a, c) = 0$. Я бы попробовал применить комбинаторику. Легко написать полное число функций из множества $A$ с $n$ элементами во множество $\{0, 1\}$. Нам требуется отобрать из них все функции такие, что $\varphi(a, b) = 1 \wedge \varphi(b, c) = 1 \Rightarrow \varphi(a, c) = 1$. Я надеюсь, что можно найти формулу, которая выражает число таких функций в зависимости от $n$.

[alf1234]

Ну попробую так. Пусть наше бинарное отношение это $\le$

Если был бы третий элемент, то транз. выглядела бы так: если $a\le b$ и $b\le c$, то $a\le c$

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

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

Остальное тавтологии или не выполняется $\varphi(a, b) = 1 \wedge \varphi(b, c) = 1 \Rightarrow \varphi(a, c) = 1$

[Anton_Peplov]

удалено.