2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Бинарные отношения
Сообщение24.10.2014, 22:31 


22/07/12
560
Пусть $\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 
Аватара пользователя


01/12/06
697
рм
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 


22/07/12
560
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 
Аватара пользователя


01/12/06
697
рм
Я бы не стал предполагать, что "неравный $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 


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

 Профиль  
                  
 
 Re: Бинарные отношения
Сообщение25.10.2014, 02:08 
Аватара пользователя


01/12/06
697
рм
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