Непринуждённо об отношениях

[arseniiv]

(Оффтоп)

«…ибо едино в трёх лицах: эквивалентность, разбиение и каноническая проекция».

UPD. Или всё же лучше факторотображение. Канонической проекцией много чего зовут…

[Ktina]

Mikhail_K в сообщении #1350433 писал(а):

Ktina в сообщении #1350421 писал(а):

Не рефлексивно, да симметрично и да транзитивно, поскольку из ложного утверждения следует любое (если Луна зелёная, то все тараканы - кошки).

Вопрос Вам: а ещё бывают отношения, симметричные и транзитивные, но при этом не рефлексивные, кроме пустого?

Не знаю. Четыре, наверное.

[Mikhail_K]

Ktina в сообщении #1350595 писал(а):

Не знаю.

Выше Вы (ошибочно) утверждали, что из симметричности и транзитивности следует рефлексивность.
Причём Вы имели в виду какое-то доказательство этой гипотезы.
А напишите это своё доказательство сейчас, с указанием того, в каком месте в нём содержится ошибка.
Все три свойства записывайте при этом аккуратно, с кванторами.
Возможно, это поможет с поиском контрпримеров.

-- 31.10.2018, 18:03 --

Ktina в сообщении #1350595 писал(а):

Четыре, наверное.

что четыре?
(Вашего израильского юмора - если это он - увы, не понимаю.)

[statistonline]

Mikhail_K в сообщении #1350433 писал(а):

а ещё бывают отношения, симметричные и транзитивные, но при этом не рефлексивные, кроме пустого?

Тогда, видимо, ответ "не бывает". Похоже, если у нас выполняется нерефлексивность и транзитивность, то придется признать, что симметричность выполняться не может:
Пусть R - отношение между элементами. Имеем

$ 1) \overline{xRx}$

$ 2) xRy, yRz \Rightarrow xRz$

Тогда $ xRy, yRx \Rightarrow xRx$ противоречит $1)$, а значит R - несимметрично. Так?

[eugensk]

statistonline
А почему найдется $y$ такое, что $xRy, yRx$ для данного $x$ ?

[Mikhail_K]

statistonline в сообщении #1350703 писал(а):

Тогда $ xRy, yRx \Rightarrow xRx$ противоречит $1)$, а значит R - несимметрично. Так?

А что такое здесь $y$? Откуда оно взялось и почему существует? Вы делаете выводы из утверждения $xRy$, не указав, что такое $y$, и не доказав его существование.

statistonline в сообщении #1350703 писал(а):

Тогда, видимо, ответ "не бывает".

Не-а, бывают.

[statistonline]

Mikhail_K в сообщении #1350706 писал(а):

А что такое здесь $y$? Откуда оно взялось и почему существует?

Элемент из того же множества, отличный от $x$.

[Mikhail_K]

statistonline в сообщении #1350728 писал(а):

Элемент из того же множества, отличный от $x$.

Но если Вы возьмёте любой элемент из того же множества, отличный от $x$, то утверждение $xRy$ вовсе не обязано быть верным. А Вы из него делаете дальнейшие выводы.
Вам нужен в качестве $y$ не любой элемент из того же множества, а какой?

[statistonline]

Mikhail_K в сообщении #1350730 писал(а):

Вам нужен в качестве $y$ не любой элемент из того же множества, а какой?

Чего-то я затупил... Наверное $y$ должен быть из того же подмножества, что и $x$, на котором определено $R$.

[Mikhail_K]

statistonline в сообщении #1350774 писал(а):

из того же подмножества

Что за подмножество, скажите более внятно.

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

[arseniiv]

Можно, кстати, записать рефлексивность как $I\subset R$ ($I$ — тождественное отношение), симметричность как $R^t\subset R$, транзитивность как $R\circ R\subset R$ и попробовать алгеброй бинарных отношений (не реляционной алгеброй вообще, она сложнее и не нужна здесь) получить условия на $R$ с нужным сочетанием свойств. Правда, это потребует лемм (о связи транспозиции, композиции и всего остального) и, видимо, через выражения с конкретными элементами носителя получается всё-таки быстрее.

[statistonline]

Mikhail_K в сообщении #1350827 писал(а):

Что за подмножество, скажите более внятно.

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

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

Можно, кстати, записать рефлексивность как $I\subset R$ ($I$ — тождественное отношение), симметричность как $R^t\subset R$, транзитивность как $R\circ R\subset R$ и попробовать алгеброй бинарных отношений (не реляционной алгеброй вообще, она сложнее и не нужна здесь) получить условия на $R$ с нужным сочетанием свойств. Правда, это потребует лемм (о связи транспозиции, композиции и всего остального) и, видимо, через выражения с конкретными элементами носителя получается всё-таки быстрее.

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

[Mikhail_K]

statistonline в сообщении #1351089 писал(а):

Скажите тогда, какой учебник можно почитать по этим вопросам?

Тут вопрос на логику, никакие знания и учебники не нужны.
Ну вот, выше Вы написали доказательство, что из симметричности и транзитивности следует рефлексивность.
Это доказательство неверное, потому что, как минимум, пустое отношение является контрпримером.
Ну вот проследите своё доказательство от начала до конца, имея в виду, что $R$ в нём - это пустое отношение. И скажите, какой шаг в этом доказательстве неверен и почему. Когда контрпример известен (пустое отношение), это просто сделать.
А потом уже можно будет поискать другие контрпримеры (непустые отношения, тоже симметричные и транзитивные, но не рефлексивные).

Дальше, возражение к Вашему доказательству уже было. Вы пишете утверждение $xRy$ и делаете из него какие-то дальнейшие выводы. В итоге получаете $xRx$. Цепочка рассуждений тут верная. Но откуда взялось самое первое утверждение в этой цепочке? Что такое $y$, Вы не определили. Что такое $y$? Любой элемент из множества, на котором задано отношение? (Обозначим его $M$.) Любой элемент из множества $M$, состоящий в отношении с элементом $x$? Что-то ещё? Чтобы использовать $y$, Вы его вначале должны определить, и показать, что такие $y$ вообще существуют.

----------

Ещё важный момент. Просто "$xRx$", если выше не было явно указано, что такое $x$ - это не утверждение, а непонятно что. Доказательство рефлексивности (если бы оно было возможно) можно было бы строить так.
Пусть $R$ - симметричное и транзитивное отношение. Пусть $x$ - произвольный элемент множества $M$. <... рассуждения ...> Значит, $xRx$. Тем самым, мы доказали, что для любого $x\in M$ верно $xRx$. Это и означает рефлексивность отношения $R$. Значит, симметричные и транзитивные отношения обязательно рефлексивны.

Или так: Пусть $R$ - симметричное и транзитивное, но нерефлексивное отношение. Раз оно нерефлексивно, то существует $x\in M$ такой, что $xRx$ неверно. <... рассуждения ...> Приходим к противоречию. Значит, симметричные и транзитивные отношения обязательно рефлексивны.

То есть нужно указывать, что такое $x$, как-то его вводить.
(Вообще, не помешало бы научиться все утверждения записывать с кванторами, но хотя бы так вот словами.)

То есть план такой: вначале приводите своё доказательство в нормальный вид (чтобы в нём не было взявшихся ниоткуда $x$ и $y$), затем ищете в нём ошибку, пользуясь известным контрпримером (пустое отношение), указываете какой конкретно шаг ошибочный, а там наверное и станет понятно, какие ещё есть контрпримеры.

----------

Наконец. Уже было сказано, что искомый контрпример (непустого отношения, симметричного и транзитивного, но не рефлексивного) можно найти не очень сложным перебором всевозможных отношений на множестве из трёх элементов $a,b,c$. Так тоже можно попробовать.

[Munin]

Отношения рассматриваются в курсе алгебры (или в курсе "дискретной математики").

[arseniiv]

С алгеброй всё просто, никакой учебник не нужен, тут пара определений, которые в принципе должны быть в той же Википедии (лучше английской).

1. Пусть $R\subset A\times B$, тогда обратное отношение $R^t := \{(y, x)\mid (x, y)\in R\}$. Также оно обозначается $R^{-1}$.

2. Пусть $R\subset A\times B, S\subset B\times C$, тогда композиция $R\circ S := \{(x, z)\mid (x, z)\in A\times C\wedge\exists y\in B.\;(x, y)\in R\wedge (y, z)\in S\}$.

Остальное выводится. Например, $R\circ(S\cap T) = (R\circ S)\cap(R\circ T)$.

Теперь будем рассматривать отношения ${}\subset A^2$ и пусть $B \subset A$, $G = B^2$. Заметим, что $R\cap G$ симметрично, если симметрично $R$:

$$(R\cap G)^t = R^t\cap G^t\subset R\cap G;$$

транзитивно, если транзитивно $R$:

$$(R\cap G)\circ(R\cap G) = R\circ R\cap R\circ G\cap G\circ R\cap G\circ G\subset R\circ R\cap G\circ G\subset R\cap G;$$

и не рефлексивно, если $B\ne A$: пусть $H = (A\setminus B)^2$, тогда

$$(I\cap R\cap G)\circ H\subset (I\cap G)\circ H = I\circ H\cap G\circ H = H\cap\varnothing = \varnothing,$$

а для рефлексивного $X$ должно выполняться $I\cap X = I$, ну и для $I$ всегда $I\circ H = H$.

Ну тут я немного срезал углы и пользовался интуитивно очевидными вещами, а если всё выводить аккуратно, игра не будет стоить свеч. Она даже сейчас не стоит, проще разобраться не point-free.

Munin в сообщении #1351207 писал(а):

Отношения рассматриваются в курсе алгебры

Думается, очень редко — это как-то не в тему туда включать. Алгебраических структур очень много, все туда не включишь, так что, как понимаю, вводный курс алгебры (у некоторых — кроме линейной алгебры — единственный) обычно ограничивается структурами типа групп и колец. (А отношениям место там, где расписывают основные сведения о множествах, функциях, но отдельный предмет из этого ведь не делают?)