2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Бинарные отношения
Сообщение24.10.2014, 22:31 
Пусть $\Delta_X$ - диагональ множества $X^2$, $\Delta_Y$ диагональ множества $Y^2, \ R_1 \subset X \times Y, \  R_2 \subset Y \times X, \ R_2 \circ R_1 = \Delta_X,  \ R_1 \circ R_2 = \Delta_Y$. Требуется доказать, что отношения $R_1$ и $R_2$ - функциональны и являются взаимно обратными отображениями.

В целом интуитивно я понимаю, как доказывать, но при доказательстве таких вот утверждений, где требуется некоторая "логическая эквилибристика" порой путаюсь. Просьба проверить доказательство.
Условие $\ R_2 \circ R_1 = \Delta_X,  \ R_1 \circ R_2 = \Delta_Y$ можно переписать как:
$$(1) \quad \forall x_1, x_2 \in X \ (x_1 = x_2) \Leftrightarrow \exists y \in Y: (x_1, y) \in R_1 \ \wedge  \ (y, x_2) \in R_2$$
$$(2) \quad \forall y_1, y_2 \in Y \ (y_1 = y_2) \Leftrightarrow \exists x \in X: (y_1, x) \in R_2 \ \wedge \ (x, y_2) \in R_1$$
Тогда предположим, что $(x, y_1) \in R_1 \  \wedge \ (x, y_2) \in R_1$, но при этом $y_1 \neq y_2$, тогда из (2) следует, что $\forall x \in X \  (y_1, x) \notin R_2 \ \vee \ (x, y_2) \notin R_1$, но $(x, y_2) \notin R_1$ противоречит предположению, значит $\forall x \in X \ (y_1, x) \notin R_2 $, это означает, что $R_2 = \varnothing$, чего быть не может. Аналогично доказываем для $R_1$. Это и доказывает функциональность бинарных отношений. То что это взаимно обратные отображения напрямую следует из (1) и (2). Что и требовалось доказать.

 
 
 
 Re: Бинарные отношения
Сообщение25.10.2014, 00:14 
Аватара пользователя
main.c в сообщении #922734 писал(а):
значит $\forall x \in X \ (y_1, x) \notin R_2 $, это означает, что $R_2 = \varnothing$, чего быть не может.

$ (y_1, x) \notin R_2 $, без квантора, $x$ уже выбрали. Почему $R_2=\varnothing$? Мне кажется $X,\ Y$ могут быть и пустыми.

-- Пт окт 24, 2014 23:29:12 --

Пишите, что требуется доказать: $\forall x\in X\exists! y\in Y((x,y)\in R_1)$
Существование (Вы это пропустили) Пусть $x\in X$. Тогда $(x,x)\in\Delta_X.$ Тогда $(x,x)\in R_2\circ R_1$. Тогда можно выбрать такой $y\in Y$, что $(x,y)\in R_1$ и $(y,x)\in R_2$. Вот он существующий $y$ такой, что $(x,y)\in R_1$ ...

 
 
 
 Re: Бинарные отношения
Сообщение25.10.2014, 00:57 
gefest_md в сообщении #922755 писал(а):
Пишите, что требуется доказать: $\forall x\in X\exists! y\in Y((x,y)\in R_1)$
Существование (Вы это пропустили) Пусть $x\in X$. Тогда $(x,x)\in\Delta_X.$ Тогда $(x,x)\in R_2\circ R_1$. Тогда можно выбрать такой $y\in Y$, что $(x,y)\in R_1$ и $(y,x)\in R_2$. Вот он существующий $y$ такой, что $(x,y)\in R_1$ ...

... теперь предположим, что существует ещё $y_2 \in Y$, неравный $y$, такой, что $(x,y_2)\in R_1$, тогда из (2) следует, что $(y_2, x) \notin R_2$, так как $x$ мы выбирали произвольно, это означает, что не найдётся такого $x$, что $(y_2, x) \in R_2$, но $(y_2, y_2) \in \Delta_Y$, а значит по условию такой $x$ найдётся - пришли к противоречию.

 
 
 
 Re: Бинарные отношения
Сообщение25.10.2014, 01:31 
Аватара пользователя
Я бы не стал предполагать, что "неравный $y$". $\exists! x P(x)$ доказывается так
$\exists x (P(x)\wedge\forall y(P(y)\to y=x))$ или так
$\exists x P(x)\wedge\forall y\forall z(P(y)\wedge P(z)\to y=z)$
Видим, что в конце надо доказать равенство. А где в условиях есть равенство? В определении отношения $\Delta_X$: $\Delta_X=\{(x,y)\in X\times X\mid x=y\}.$
Если идти по первому варианту, то возьмём $(y,x)\in R_2$, полученное в доказательстве существования и также $(x,y_2)\in R_1.$ И почти готово. Посмотрите внимательно какие имеются условия.

 
 
 
 Re: Бинарные отношения
Сообщение25.10.2014, 01:44 
Немного подправил доказательство.
...теперь предположим, что существует ещё $y_2 \in Y$, неравный $y$, такой, что $(x,y_2)\in R_1$, тогда из (2) следует, что $(y, x) \notin R_2$ - пришли к противоречию.

 
 
 
 Re: Бинарные отношения
Сообщение25.10.2014, 02:08 
Аватара пользователя
main.c в сообщении #922763 писал(а):
... теперь предположим, что существует ещё $y_2 \in Y$, неравный $y$, такой, что $(x,y_2)\in R_1$, тогда из (2) следует, что $(y_2, x) \notin R_2$, так как $x$ мы выбирали произвольно, это означает, что не найдётся такого $x$, что $(y_2, x) \in R_2$, но $(y_2, y_2) \in \Delta_Y$, а значит по условию такой $x$ найдётся - пришли к противоречию.

От этого голова болит у меня.

main.c в сообщении #922775 писал(а):
Немного подправил доказательство.
...теперь предположим, что существует ещё $y_2 \in Y$, неравный $y$, такой, что $(x,y_2)\in R_1$, тогда из (2) следует, что $(y, x) \notin R_2$ - пришли к противоречию.

Правильно.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group