Антирефлексивность + Полутранзитивность = Антисимметричность

[ProPupil]

Есть отношение $P$ на некотором множестве, которое является
а) антирефлексивным, т. е. $\not\exists x: \, xPx$
б) полутранзитивным, т. е. $\forall x, y, z, t: \, xPy \wedge yPz \Rightarrrow = xPt \vee tPz$

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

С транзитивностью проблем нет:

Пусть $x, y и z$ произвольны, причём $xPy \wedge yPz$, поскольку полутранзитивность выполняется для всех $t$, то она выполняется и при $t=x$, соответственно мы имеем $xPx \vee xPZ$. Первое невозможно в силу антирефлексивности, значит, верно второе, а это в точности то, что нам надо для транизитивности.

С антисимметричностью у меня возникла небольшая проблема. Необходимо показать, что $xPy & yPx$ выполняется только когда $x=y$. Но в силу доказанной выше транзитивности мы получаем $xPx$ при всех $y$ в том числе, и при $x=y$. То есть получается, что $xPy&yPx$ вообще никогда не выполняется?

[iifat]

Получается, но это не ваше дело не имеет отношения к поставленной задаче. Из $xPy\wedge yPx$ следует $x=y$? Если да, то отношение антисимметрично, что б там ни выводилось далее из дополнительных фактов.

[ProPupil]

iifat в сообщении #1278505 писал(а):

Получается, но это не ваше дело не имеет отношения к поставленной задаче. Из $xPy\wedge yPx$ следует $x=y$? Если да, то отношение антисимметрично, что б там ни выводилось далее из дополнительных фактов.

Я пытался пойти от противного: пусть существуют $x_1$ и $x_2$ такие, что $x_1 \ne x_2$ и $x_1Px_2 \wedge x_2Px_1$. Тогда в силу доказанной транзитивности мы имеем $x_1Pxx_1$, что невозможно. Следовательно, наше противоречие ложно, и $x_1 = x_2$. То есть отношение антисимметрично.

То есть получается, что нам неважно, что отношение $x_1Px_1$ вообще не может быть выполнено и при $x_1=x_2$? Меня именно этот момент смущает.

[provincialka]

ProPupil в сообщении #1278509 писал(а):

То есть получается, что нам неважно, что отношение $x_1Px_1$ вообще не может быть выполнено и при $x_1=x_2$? Меня именно этот момент смущает.

Почему? Какое из отношений $<$ и $\leqslant$ вы считаете антисимметричным?

[ProPupil]

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

ProPupil в сообщении #1278509 писал(а):

То есть получается, что нам неважно, что отношение $x_1Px_1$ вообще не может быть выполнено и при $x_1=x_2$? Меня именно этот момент смущает.

Почему? Какое из отношений $<$ и $\leqslant$ вы считаете антисимметричным?

Второе: если $x\leq y$ и $y \leq x$ - отсюда сразу следует, что $x=y$.
А если $x < y$ и $y < x$ одновременно - это в принципе невозможно.

[provincialka]

Неверно! Они оба антисимметричны.

ProPupil в сообщении #1278528 писал(а):

А если $x < y$ и $y < x$ одновременно - это в принципе невозможно.

А это никак не противоречит определению. В математике, если логично -- то верно, даже если и кажется странным. К тому же вы неверно (неаккуратно) сформулировали определение:

ProPupil в сообщении #1278497 писал(а):

Необходимо показать, что $xPy \& yPx$ выполняется только когда $x=y$.

Но ведь не "тогда и только тогда"!

Лучше написать так: Из $xPy$ и $yPx$ следует, что $x=y$
Ну, а $x<y\&y<x$ -- невозможное событие, из него следует все что угодно.

[pcyanide]

ProPupil в сообщении #1278497 писал(а):

Необходимо показать, что $xPy & yPx$ выполняется только когда $x=y$. Но в силу доказанной выше транзитивности мы получаем $xPx$ при всех $y$ в том числе, и при $x=y$. То есть получается, что $xPy&yPx$ вообще никогда не выполняется?

Если $x=y$ , то в силу антирефлексивности $xPy$ и $yPx$ ложны, отсюда $xPy \wedge yPx$ ложно. Получается, что антисимметричность (в понимании «тогда и только тогда») всегда противоречит антирефлексивности

Может, «тогда и только тогда» не нужно? В этом случае утверждение следует как раз в силу того, что «из лжи следует что угодно». Во статьях Wikipedia а также Wolfram Mathworld антисимметричность понимается только в одну сторону.

[provincialka]

pcyanide в сообщении #1279349 писал(а):

Может, «тогда и только тогда» не нужно?

Не нужно. А кто сказал, что нужно? Нигде такого определения не видела!.
Смысл антисимметрии в том, что отношение не может выполняться "в обе стороны", кроме разве что отношения элемента с собой. Но это последнее тоже может не выполняться. Что там "на диагонали" -- никого не волнует.