Нестрогий частичный порядок. Бинарные отношения.

[PWT]

Здравствуйте! Помогите, пожалуйста, разобраться!

Сколько различных отношений нестрого частичного порядка можно задать на множестве из трех элементов?

Всего бинарных отношений на множестве из трех элементов будет $2^9=512$.
Среди них, насколько я понимаю, нужно выбрать те, что удовлетворяют следующим свойствам:

1) Рефлексивность: ${\displaystyle \forall x:xRx}$
2) Антисимметричность: ${\displaystyle \forall x,y:xRy\land yRx\Rightarrow x=y}$
3) Транзитивность: ${\displaystyle \forall x,y,z:xRy\land yRz\Rightarrow xRz}$ .

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

Но вся проблема в антисимметричности. Может быть я плохо понимаю -- что это?

Я знаю как проверить на антисимметричность отношение $\{(a,a),(b,b)\}$. Там посылка будет ложная, значит отношение транзитивно. Это в случае, если $a\ne b$ А так как нам не известно, равны ли они, то нельзя пользоваться равенством.

1) Элементы $a,b,c$ изначально подразумеваются попарно различными или нет?
Мне самому кажется, что это неизвестно -- может да, а может -- нет.
2) Вот рассмотрим мы отношение $\{(a,b),(b,a)\}$. Антисимметрично ли оно? Как узнать $a=b$ или $a\ne b$?

[Anton_Peplov]

PWT в сообщении #1144600 писал(а):

Я знаю как проверить на антисимметричность отношение $\{(a,a),(b,b)\}$. Там посылка будет ложная, значит отношение транзитивно. Это в случае, если $a\ne b$ А так как нам не известно, равны ли они, то нельзя пользоваться равенством.

Это какая-то слишком высокая поэзия, чтобы я что-то понял. Нельзя ли помедленнее?

[arseniiv]

PWT в сообщении #1144600 писал(а):

Но вся проблема в антисимметричности. Может быть я плохо понимаю -- что это?

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

PWT в сообщении #1144600 писал(а):

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

которое лежит в диагонали независимо от $a=b$. Отношение не антисимметрично тогда и только тогда, когда для каких-то $a\ne b$ оно содержит одновременно пары $(a,b)$ и $(b,a)$.

PWT в сообщении #1144600 писал(а):

1) Элементы $a,b,c$ изначально подразумеваются попарно различными или нет?
Мне самому кажется, что это неизвестно -- может да, а может -- нет.

Да, как и в прошлом обсуждении, всегда по умолчанию ничего не известно.

PWT в сообщении #1144600 писал(а):

2) Вот рассмотрим мы отношение $\{(a,b),(b,a)\}$. Антисимметрично ли оно? Как узнать $a=b$ или $a\ne b$?

Как узнать — из условия, наверное. Там, где встретились в первый раз эти $a,b$.

[Anton_Peplov]

PWT в сообщении #1144600 писал(а):

Элементы $a,b,c$ изначально подразумеваются попарно различными или нет?

Если по условию это множество ТРЕХ элементов, состоящее из $a$, $b$ и $c$ - то да, подразумеваются попарно различными. Иначе было бы множество "не более чем трех элементов".

[PWT]

Anton_Peplov в сообщении #1144608 писал(а):

PWT в сообщении #1144600 писал(а):

Элементы $a,b,c$ изначально подразумеваются попарно различными или нет?

Если по условию это множество ТРЕХ элементов, состоящее из $a$, $b$ и $c$ - то да, подразумеваются попарно различными. Иначе было бы множество "не более чем трех элементов".

Спасибо, а разве $\{a,a,b\}$ -- не множество из трех элементов?

-- 17.08.2016, 00:05 --

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

Как узнать — из условия, наверное. Там, где встретились в первый раз эти $a,b$.

А условие в стартпосте, но из него мне не очевидно, потому спрашиваю...

-- 17.08.2016, 00:10 --

Anton_Peplov в сообщении #1144603 писал(а):

PWT в сообщении #1144600 писал(а):

Я знаю как проверить на антисимметричность отношение $\{(a,a),(b,b)\}$. Там посылка будет ложная, значит отношение транзитивно. Это в случае, если $a\ne b$ А так как нам не известно, равны ли они, то нельзя пользоваться равенством.

Это какая-то слишком высокая поэзия, чтобы я что-то понял. Нельзя ли помедленнее?

Если $R=\{(a,a),(b,b)\}$, то ${\displaystyle \forall x,y:xRy\land yRx\in \varnothing$ ? потому импликация выполняется ${\displaystyle \forall x,y:xRy\land yRx\Rightarrow x=y}$
Значит антисимметрично. Да, я описался, упомянув транзитивность. Впрочем, данное отношение транзитивно из похожих соображений.

[Anton_Peplov]

PWT в сообщении #1144619 писал(а):

Спасибо, а разве $\{a,a,b\}$ -- не множество из трех элементов?

Нет, это множество из двух элементов. Совпадающие элементы множества считаются одним его элементом, другими словами, каждый элемент множества входит в него ровно один раз. В множестве $\{1, 1, 1, 1, 0\}$ два элемента, это то же самое множество, что $\{0, 1\}$ и $\{1, 0\}$. В этом отличие множества от мультимножества (в которое элемент может входить многократно, т.е. $\{0, 1\}$ и $\{0, 0, 1\}$ - разные мультимножества), а также кортежей и последовательностей (где, помимо этого, учитывается еще и порядок вхождения).

[PWT]

Anton_Peplov, спасибо!

Правильно ли я понимаю, что

$\{(a,a),(b,b)\}$ антисимметрично

$\{(a,a),(a,b)\}$ антисимметрично

$\{(b,a),(a,b)\}$ не антисимметрично

$\{(a,a),(a,b),(a,c)\}$ антисимметрично

$\{(a,a),(a,b),(a,c), (c,a)\}$ не антисимметрично

$\{(a,a),(a,b),(a,c), (с,b)\}$ не антисимметрично

$\{(a,a),(a,b),(a,c), (b,c),(c,b)\}$ не антисимметрично


Отношений, в которых есть $(a,b)$, но нет $(b,a)$ будет $2^7$. Столько же отношений с $(b,a)$, но без $(a,b)$. Получается всего $2^8$. Среди них есть те, где есть $(b,c)$, но нет $(c,b)$ -- их половина от $2^8$, то есть $2^7$. Аналогично проделываем с $(b,c)$. Тогда ответ $2^6=64$.

Ответ: 64 отношения. Верно ли?

[Anton_Peplov]

PWT в сообщении #1144619 писал(а):

Если $R=\{(a,a),(b,b)\}$, то ${\displaystyle \forall x,y:xRy\land yRx\in \varnothing$ ?

Нет. Хотя отношение антисимметрично, это да. Боюсь, у Вас путаница с применением кванторов.
Давайте проще: антисимметрично ли отношение $R=\{(a,a)\}$? Почему?

[PWT]

Anton_Peplov в сообщении #1144624 писал(а):

PWT в сообщении #1144619 писал(а):

Если $R=\{(a,a),(b,b)\}$, то ${\displaystyle \forall x,y:xRy\land yRx\in \varnothing$ ?

Нет. Хотя отношение антисимметрично, это да. Боюсь, у Вас путаница с применением кванторов.
Давайте проще: антисимметрично ли отношение $R=\{(a,a)\}$? Почему?

Да, потому как $aRa\land aRa => a=a$

[Anton_Peplov]

Теперь вернемся к отношению $R=\{(a,a),(b,b)\}$. Антисимметрично ли оно? Почему? Думаю, в данном случае будет лучше записать это словами, а не обозначениями.

[PWT]

Anton_Peplov в сообщении #1144627 писал(а):

Теперь вернемся к отношению $R=\{(a,a),(b,b)\}$. Антисимметрично ли оно? Почему? Думаю, в данном случае будет лучше записать это словами, а не обозначениями.

Да, антисимметрично все-таки..

[Anton_Peplov]

Докажите.

[PWT]

${aRa\land bRb\in \varnothing}$ Так как это пустое множество, то из него может следовать все что угодно, а значит импликация верна.

[Anton_Peplov]

Напишите здесь словами, без значков, определение антисимметричного отношения.

[PWT]

Антисимметричное отношение на множестве $A$ -- это множество пар элементов множества $A$, таких, что если это множество пар содержит пары $(x,y)$ и $(y,x)$, то из этого следует, что $x=y$ для любых двух элементов $x,y$ множества $A$.

Может отношение $\{(a,a),(b,b)\}$ антисимметрично, потому что не содержит пар вида $(a,b)$ и $(b,a)$?