Доказательство равенства двух множеств

[Nogin Anton]

Подскажите пожалуйста, как продолжить доказательство:

$((A\cup B)\circ C)^{-1}=(A\circ C)^{-1}\cup (B\circ C)^{-1}$

Начал преобразовывать правую часть с раскрытия операции "объединение":

$\forall <x,y>\in [(A\circ C)^{-1} \cup (B\circ C)^{-1}] \to$

$\to <x,y>\in (A\circ C)^{-1} \vee <x,y>\in (B\circ C)^{-1} \to$ [теперь раскрываю инверсию]

$\to <y,x>\in (A\circ C)\vee <y,x>\in (B\circ C) \to$ [теперь раскрываю композицию]

$\to (\exists m)(<y,m>\in A\& <m,x>\in C)\vee (\exists k)(<y,k>\in B\& <k,x>\in C)$

И на этом месте ступор...

[Sonic86]

Так. Во-первых вместо $\to$ удобно использовать сразу $\Leftrightarrow$, чтоб в обратную сторону не доказывать. Во-вторых, кванторов не нужно вообще.
И вот это:

Ногин Антон писал(а):

$\to <x,y>\in (A\circ C)^{-1} \vee <x,y>\in (B\circ C)^{-1} \to$ [теперь раскрываю инверсию]
$\to <y,x>\in (A\circ C)\vee <y,x>\in (B\circ C) \to$

Что за странные переход? $a \in X^{-1} \to a \in X$? М.б. наоборот ?

[Nogin Anton]

Ну я же просто раскрыл инверсию.. то есть поменял местами элементы кортежа.. я неверно сделал?

[Sonic86]

Nogin Anton писал(а):

Ну я же просто раскрыл инверсию.. то есть поменял местами элементы кортежа.. я неверно сделал?

Так. Кажется я затупил. $A,B,C$ - множества? Что такое $X \circ Y$? Что такое $X^{-1}$?

-- Чт июн 23, 2011 20:59:11 --

Нашел определения здесь:
http://rusnauka.narod.ru/lib/program/fu ... tions.html
Если Вы имели ввиду под инверсией то, что написано там, то имейте ввиду, что чаще это называется дополнением множества, обозначается $\bar X$ и определяется как: $x \in X \Leftrightarrow x \not \in X$. И тогда я Вам правильно написал .

Что такое "композиция множеств" не нашел.

[Nogin Anton]

$A,B,C$ - множества

$X\circ Y$ - это композиция двух множеств:

$X\circ Y=\{<x,y>|x\in X \& y\in Y\}$

$X^{-1}$ - это инверсия множества $X$. То есть, если $X=\{<x,y>\}$, то $X^{-1}=\{<y,x>\}$

[Sonic86]

(определения)

Nogin Anton писал(а):

$X\circ Y$ - это композиция двух множеств:
$X\circ Y={<x,y>|x\in X \& y\in Y}$

Ясно. Декартово произведение $X \times Y$.
$(x,y)$ - стандартное обозначение пары.

Значит Вы как-то неправильно композицию преобразовали. Правильно так:
$(x,y) \in X \times Y \Leftrightarrow x \in X \& y \in Y$.

[Nogin Anton]

то есть так?

[раскрываю инверсию] $ \Leftrightarrow (y,x)\in (A\circ C)\vee (y,x)\in (B\circ C)\Leftrightarrow y\in A \& x\in C\vee y\in B\& x\in C$..

[Sonic86]

Угу. Дальше Вы сможете

[AD]

Nogin Anton в сообщении #461511 писал(а):

$A,B,C$ - множества

$X\circ Y$ - это композиция двух множеств:

$X\circ Y=\{<x,y>|x\in X \& y\in Y\}$

$X^{-1}$ - это инверсия множества $X$. То есть, если $X=\{<x,y>\}$, то $X^{-1}=\{<y,x>\}$

По-моему, Ваша тема называется "бинарные отношения", и вместо слова "множество" нужно всюду поставить "отношение", ну и там "композиция отношений", "обратные отношения", и Вы при этом немножко путаетесь в определениях либо чего-то не понимаете. Потому что "композиция множеств" и "обратное множество" - это какая-то лютая дикость. Если это не так - заранее извиняюсь.

[Nogin Anton]

Скорее всего не понимаю)))

$ \Leftrightarrow (y,x)\in (A\circ C)\vee (y,x)\in (B\circ C)\Leftrightarrow y\in A \& x\in C\vee y\in B\& x\in C$

[далее $x\in C$ вынес за скобки] $\Leftrightarrow (y\in A\vee y\in B)\& x\in C \Leftrightarrow$ (y\in A\cup B)\& x\in C\Leftrightarrow

$\Leftrightarrow (y,x)\in ((A\cup B)\circ C)\Leftrightarrow (x,y)\in [(A\cup B)\circ]^{-1}$

Ч.т.д.

[AD]

Nogin Anton в сообщении #461568 писал(а):

Скорее всего не понимаю)))

Ну вот лучше уточните на всякий случай, а то если я прав, то всё неправильно. Композицией отношений $A\subset X\times Y$ и $B\subset Y\times Z$ обычно называется отношение $A\circ B=\{(x,z)\in X\times Z: \exists y\in Y, (x,y)\in A, (y,z)\in B\}$. Было такое?

[Nogin Anton]

Вы правы!