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

[alf1234]

Спасибо, это вроде бы ясно. А для трехэлементного у нас будет $2^9=512$ вариантов подмножеств. Получается, что нам проще найти случаи, когда транзитивность не выполняется. А это когда отношение содержит содержит $(a,b)$ и $(b,a)$, но не содержит $(a,a)$ и $(b,b)$, таких вариантов три. Это было с парой чисел $(a,b)$, еще три аналогичных варианта с парой чисел $(b,c)$, еще три варианта с парой чисел $(a,c)$. Значит всего транзитивных отношений будет $2^9-3\cdot 3$.

В случае с $n$ элементным множеством, вроде бы должно быть транзитивных отношений $2^{n^2}-3C_n^2$. Верно ли это?

[arseniiv]

Можно сравнить с последовательностью A006905 в OEIS, которую мне недавно показал Aritaborian. К сожалению, в комментариях к ней такой простой формулы не упомянуто. Это с большой вероятностью говорит о том, что формула не от той последовательности. Впрочем, тут это сразу ясно: там 171, а здесь получилось 503.

[mihaild]

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

отношение содержит содержит $(a,b)$ и $(b,a)$, но не содержит $(a,a)$ и $(b,b)$, таких вариантов три

Почему $3$? Вы зафиксировали $2$ элемента, еще про $2$ сказали, что хотя бы один из них не принадлежит отношению - осталось еще $5$, каждый из которых может принадлежать отношению, а может не принадлежать.

[alf1234]

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

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

отношение содержит содержит $(a,b)$ и $(b,a)$, но не содержит $(a,a)$ и $(b,b)$, таких вариантов три

Почему $3$? Вы зафиксировали $2$ элемента, еще про $2$ сказали, что хотя бы один из них не принадлежит отношению - осталось еще $5$, каждый из которых может принадлежать отношению, а может не принадлежать.

Получается $2^5$ вариантов?

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

Можно сравнить с последовательностью A006905 в OEIS, которую мне недавно показал Aritaborian. К сожалению, в комментариях к ней такой простой формулы не упомянуто. Это с большой вероятностью говорит о том, что формула не от той последовательности. Впрочем, тут это сразу ясно: там 171, а здесь получилось 503.

Насколько я понял, для $n$ элементного множества аналитической формулы не получить)

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

]посылка импликации ложна для любых элементов - значит вся импликация истинна

Все-таки поймал себя на мысли, что этого не понимаю.
Я понимаю, что если посылка импликации ложна, то из нее следовать может все что угодно, но почему же импликация все-таки истина. Может есть какое-то бытовое толкование этому или нет? Что-то я подвис...

[mihaild]

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

Получается $2^5$ вариантов?

Есть $9$ пар, про каждую надо решить, брать ее или не брать. Две из них мы уже решили брать. Еще из двух хотя бы одну брать нельзя. Осталось $5$, которые можно брать как угодно. Сколько способов в итоге получается?

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

но почему же импликация все-таки истина

Обсуждалось тут и тут - если вы про то, почему импликация с ложной посылкой истинна.
Посылка ложна: возьмем посылку из определения симметричности: $xRy$, и возьмем какие-нибудь элементы $A$ в качестве $x$ и $y$. Например, $x = y = a$. Получаем $(a, a) \in \varnothing$ - ложь.