Бинарное отношение. Транзитивность.

[supermelon]

Пусть есть некоторое отношение $$ {R} \subset {{X} \times {X}} известно, что оно транзитивно и больше ничего не известно. Есть какие-нибудь следствия из транзитивности R?
Что собой представляет транзитивность отношения? Перефразирую: какой PROFIT можно извлечь если отношение транзитивно?

[Mathusic]

supermelon в сообщении #887312 писал(а):

Что собой представляет транзитивность отношения? Перефразирую: какой PROFIT можно извлечь если отношение транзитивно?

Дополнительная информация, возможность делать некоторые выводы. Определение знаете?

[supermelon]

Цитата:

Определение знаете?

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

[Xaositect]

supermelon в сообщении #887502 писал(а):

Я просто не могу найти общего между параллельностью прямых и, допустим, равенства, подобия фигур (в евклидовой), хотя оба отношения транзитивны.

Эти отношения не только транзитивны, но еще рефлексивны и симметричны. Такие отношения называются отношениями эквивалентности. Такие отношения возникают тогда, когда хочется выразить тот факт, что какие-то объекты похожи между собой.
Они очень часто встречаются повсюду в математике и позволяют делить некоторое множество на классы эквивалентности. Если две прямые параллельны третьей, то они параллельны между собой. Если две фигуры подобны заданной, то они подобны между собой. Таким образом, все множество прямых можно разбить на части, в каждой из которых прямые параллельны, а в разных частях - не параллельны. Эти части можно назвать направлениями. Точно так же все фигуры можно разбить на классы подобия. Если мы рассматриваем равенство, то каждый класс будет состоять из одного элемента. В школе, когда изучают дроби, вводят равенство дробей: $\frac a b = \frac c d$, если $ad = bc$. На строгом математическом языке это формулируется так: на множестве дробей вводится отношение эквивалентности $\frac a b \sim \frac c d \Leftrightarrow ad = bc$, и множество дробей разбивается на классы эквивалентных между собой дробей. Эти классы называются рациональными числами.

Еще транзитивностью обладают отношения (частичного) порядка, такие как отношение "одно число меньше другого", "одна фигура содержится в другой", "одно число делится на другое". Эти отношения транзитивны и антисимметричны, они для любых двух различных элементов задают порядок - либо один элемент "больше" другого, либо "меньше", либо они не сравнимы между собой. (например, числа $4$ и $9$ не сравними по делимости).

Общее транзитивное отношение в некоторых местах имеет свойства эквивалентности, а в некоторых - порядка. То есть, в любом транзитивном отношении $prec$ можно для каждого элемента выделить все те, которые относятся к нему с обоих сторон (то есть $x\prec x'$ и $x'\prec x$), и между такими классами отношение будет устанавливать порядок - если $x_1$ и $x_2$ относятся к одному классу, а $y_1$ и $y_2$ - к другому, то либо всегда $x_i\prec y_j$ (все иксы "меньше" игреков), либо наоборот, либо никакие иксы и игреки между собой не соотносятся.

Если что-то непоянтно, спрашивайте, я попробую объяснить как-нибудь еще.

[supermelon]

Огромное спасибо за ответ, но есть одно но - мне это все известно и понятно. Я видимо никогда не научусь задавать правильные вопросы. То есть транзитивность нигде кроме отношения эквивалентности и отношения порядка не используется, я правильно понимаю?

[Xaositect]

Ну, как я написал, произвольное транзитивное рефлексивное отношение $\preceq$ однозначно задается этношением эквивалентности $x\sim y \Leftrightarrow x\preceq y \mathop{\&} y\preceq x$ и отношением порядка между классами эквивалентности. Так что достаточно рассмотреть эти два частных случая по отдельности, и мы сможем рассматривать и произвольные транзитивные отношения - они "раскладываются" на эти два случая (рефлексивность - это чисто техническая вещь, ее всегда можно добавить или убрать).

[Oleg Zubelevich]

supermelon в сообщении #887312 писал(а):

Пусть есть некоторое отношение $$ {R} \subset {{X} \times {X}} известно, что оно транзитивно и больше ничего не известно. Есть какие-нибудь следствия из транзитивности R?
Что собой представляет транзитивность отношения? Перефразирую: какой PROFIT можно извлечь если отношение транзитивно?

нарисуйте множество $R$ на плоскости

[supermelon]

Xaositect
А вот сейчас мое понимание поплыло куда-то. Мне вот эта строка непонятна $x \sim y \leftrightarrow x \preceq {y} \wedge {y} \preceq x$ -это ж посылка антисимметрии, то есть когда отношение эквивалентности и когда каждый элемент сравним с любым, так?

Oleg Zubelevich
Как я его нарисую если о нем ничего неизвестно кроме транзитивности и что является подмножеством декартова квадрата Х.

[Xaositect]

supermelon в сообщении #887537 писал(а):

Xaositect
А вот сейчас мое понимание поплыло куда-то. Мне вот эта строка непонятна $x \sim y \leftrightarrow x \preceq {y} \wedge {y} \preceq x$ -это ж посылка антисимметрии, то есть когда отношение эквивалентности и когда каждый элемент сравним с любым, так?

Нет, если у нас есть транзитивное рефлексивное отношение $\preceq$, то на его основе мы можем определить отношение эквивалентности: $x\sim y$ тогда и только тогда, когда $x\preceq y$ и $y\preceq x$.

[supermelon]

Xaositect
Я не могу понять откуда взялось $x \preceq y $ и $ y \preceq x$ b и что это. Есть версия что это отсюда $aRb \rightarrow bRa$, но в более строгом варианте.

[Xaositect]

Так.
Пусть у нас есть некоторое отношение $R$. Для любых двух элементов $x$ и $y$ возможны 4 случая - либо оба $xRy$ и $yRx$ неверны, либо верно, что $xRy$, но неверно $yRx$, либо наоборот, либо оба $xRy$ и $yRx$ верны. Можно построить новое отношение $E$, задав его таким образом, что оно будет верно только в 4 случае: $xEy$ тогда и только тогда, когда $xRy$ и $yRx$. Это просто определение.
Это действительно связано с симметричностью. Отношение $E$, построенное таким образом, всегда будет симметрично.
Кроме того, если исходное отношение $R$ транзитивно или рефлексивно, то построенное $E$ сохраняет эти свойства. Отсюда, если $R$ - это предпорядок (транзитивное рефлексивное отношение), то $E$ будет отношением эквивалентности.

[Oleg Zubelevich]

supermelon в сообщении #887537 писал(а):

Как я его нарисую если о нем ничего неизвестно кроме транзитивности и что явля

ну а Вы порисуйте для случая $X=\mathbb{R}$, посмотрите, что значит транзитивность с точки зрения геометрии этого множества, уже полезная информация

[supermelon]

Xaositect
Еще раз огромное спасибо за разъяснения. Вроде относительно разобрался.

Oleg Zubelevich
Я уже рисовал. Геометрически походит на композицию отображений.

-- 17.07.2014, 20:07 --

Косяяк, композиция ж транзитивна. Вот опять замкнутый круг.

[Oleg Zubelevich]

вопрос бессмысленен с самого начала. какой профит можно извлечь из транзитивности? на любом множестве дофига транзитивных отношений, начиная с "=" Каккой профит? -- ни какого.

[supermelon]

Oleg Zubelevich
"ни какого" - в этом то я и хотел убедиться. Пусть $R \subset X \times X $, то из транзитивности $R$ следует, что $R \circ R \subset R$ и обратно. Банально, но я не сразу додумался.

Увы, но Зорич не исчерпывающе пишет и объясняет "очевидные" вещи, поэтому приходится подключать к его курсу огромную кучу литературы, интернет и то не всегда понятно, что ты делаешь правильно, а что нет. Проблемы самообразования у меня такие.