Зорич Мат. анализ 1 том доказательство

[anderlo]

Ребята, пытаюсь сделать это упражнение. понял как доказать сюръекцию но проблема с доказательством инъекции отношений.
Смотрел на этом форуме аналогичное док-во, но там как раз второй части не понял.
Не понимаю как из выполнения $(y_1 R_2 x) и (y_2 R_2 x)$ следует равенство $y_1$ и $y_2$.? После доказательства первой части имею такую картину:

$R_2 \circ R_1 = \left\lbrace(x_1;x_1)|\exists y(x_1 R_1 y_1)\wedge(y_1 R_2 x_1)\right\rbrace$
$R_1 \circ R_2 = \left\lbrace(y_1;y_1)|\exists x(y_1 R_2 x_2)\wedge (x_2 R_1 y_1)\right\rbrace$

Нужно как-то прийти к равенству $ x_1 $ и $ x_2 $
Какие рассуждения помогают прийти к инъекции $ R_1 $ и $ R_2 $?

[Ellan Vannin]

anderlo в сообщении #1106659 писал(а):

Ребята

Здрасьте

anderlo в сообщении #1106659 писал(а):

пытаюсь сделать это упражнение. понял как доказать сюръекцию но проблема с доказательством инъекции отношений.

Во-первых отбросим всю теоретическую часть (пользоваться Зоричем как учебником по-моему невозможно). Во-вторых определим строго формально, что такое бинарное отношение. В-третьих сформулируем задание равносильное исходному: пусть $\mathcal{R}_2 \circ \mathcal{R}_1=\langle \Delta_x,X,X \rangle$ и $\mathcal{R}_1 \circ \mathcal{R}_2=\langle \Delta_y,Y,Y \rangle$. Утверждается, что $\mathcal{R}_1$ и $\mathcal{R}_2$ оба не только функциональны, не только функции, но ещё и (вы не поверите) обратимые функции

Это неверно: возьмем два бинарных отношения $\mathcal{R}_1=\langle \{\langle 0,1\rangle, \langle 0,2\rangle\},\{0\},\{1,2\} \rangle $ и $\mathcal{R}_2=\langle \{\langle 1,0\rangle, \langle 2,0\rangle\},\{1,2\},\{0\} \rangle $ и перемножим их. Получится:
$\mathcal{R}_1 \circ \mathcal{R}_2=\langle \{\langle 0,0\rangle\},\{0\},\{0\} \rangle $
$\mathcal{R}_2 \circ \mathcal{R}_1=\langle \{\langle 1,1\rangle, \langle 2,2\rangle\},\{1,2\},\{1,2\} \rangle $
При этом отношение $\mathcal{R}_1$ у нас даже не функционально.

Здесь у меня к вам два вопроса:
1. Это точно взято из книги Зорича?
2. Вы точно на картинку поместили всё упражнение целиком? Нигде ничего не пропало, по краям не обрезано?

В такой формулировке вы не сможете ничего доказать. На примере видно, что $\mathcal{R}_2$ инъекцией не является.

[anderlo]

Ellan Vannin в сообщении #1106684 писал(а):

1. Это точно взято из книги Зорича?

Гл. 1 стр 22.

Ellan Vannin в сообщении #1106684 писал(а):

2. Вы точно на картинку поместили всё упражнение целиком? Нигде ничего не пропало, по краям не обрезано?

Вот ссылка на тему в которой обсуждалось данное доказательство. Первая часть мне кажется убедительной.
topic60996.html.

-- 15.03.2016, 00:21 --

Я не совсем уловил ход ваших рассуждений основанный на взятии двух конкретных подмножеств и последующей их компоновке. Ведь если мы возьмем такие пары
${R_1 = \left\lbrace \left\lbrace 1;1\right\rbrace, \left\lbrace 2;2 \right\rbrace, \left\lbrace 3;3\right\rbrace \right\rbrace}$ и ${R_2= \left\lbrace\left\lbrace 1;1\right\rbrace , \left\lbrace 2;2 \right\rbrace, \left\lbrace 3;3\right\rbrace \right\rbrace}$ то проблем с функциональностью не возникает.

[svv]

Ellan Vannin в сообщении #1106684 писал(а):

Это неверно: возьмем два бинарных отношения $\mathcal{R}_1=\langle \{\langle 0,1\rangle, \langle 0,2\rangle\},\{0\},\{1,2\} \rangle $ и $\mathcal{R}_2=\langle \{\langle 1,0\rangle, \langle 2,0\rangle\},\{1,2\},\{0\} \rangle $ и перемножим их. Получится:
$\mathcal{R}_1 \circ \mathcal{R}_2=\langle \{\langle 0,0\rangle\},\{0\},\{0\} \rangle $
$\mathcal{R}_2 \circ \mathcal{R}_1=\langle \{\langle 1,1\rangle, \langle 2,2\rangle\},\{1,2\},\{1,2\} \rangle $
При этом отношение $\mathcal{R}_1$ у нас даже не функционально.

Почему у Вас композиция $\mathcal{R}_2 \circ \mathcal{R}_1$ не включает пары $(1, 2)$ и $(2, 1)$?

[Ellan Vannin]

svv в сообщении #1106701 писал(а):

Почему у Вас композиция $\mathcal{R}_2 \circ \mathcal{R}_1$ не включает пары $(1, 2)$ и $(2, 1)$?

Да, простите, я заработался. Пора спать.

[anderlo]

мне кажется неверно в данном случае приводить какие-то контрпримеры, т.к. эти отношения $\mathcal{R}_1$ и $\mathcal{R}_2$ - их природа, скрыты от нас и проявляется в ходе рассуждения, которые должны отталкиваться от исходных посылок.

-- 15.03.2016, 00:37 --

Да ничего... все равно спасибо! Но вопрос остается открытым. Кто же мне поможет?)))

[Ellan Vannin]

anderlo в сообщении #1106659 писал(а):

Нужно как-то прийти к равенству $ x_1 $ и $ x_2 $

Ладно, тут такая ситуация. Если $\mathcal{R}_2=\langle G_R_2, X, Y \rangle$ инъективно, это в точности означает, что $x_1 \mathcal{R}_2 y \land x_2 \mathcal{R}_2 y \Rightarrow x_1=x_2$. Вот если удастся показать равенство иксов, то мы и получим решение вашей задачи. Но у $\mathcal{R}_2 $ есть обратное. Оно и левое и правое, а значит вообще обратное отношение, и называется оно $\mathcal{R}_1$. По определению обратное отношение связывает те же самые элементы, но в другом порядке, то есть $x_2 \mathcal{R}_2 y \equiv y \mathcal{R}_1 x_2$. Значит можно сделать замену. Подставляем, получаем: $x_1 \mathcal{R}_2 y \land x_2 \mathcal{R}_2 y \equiv x_1 \mathcal{R}_2 y \land y \mathcal{R}_1 x_2$. Отсюда следует (из-за наличия промежуточного $y$), что иксы связаны композицией $\mathcal{R}_2 \circ \mathcal{R}_1$. Тогда пара $\langle x_1,x_2 \rangle$ принадлежит диагонали, что влечет за собой равенство компонент.

Я сегодня что-то всё перепутал на ночь глядя Но, надеюсь, мне удалось объяснить общий ход рассуждений. Если все понятно, то вы можете сами закончить доказательство.

[anderlo]

Спасибо, но трудность тут в том, чтобы показать, что $\mathcal{R}_2$ действительно обратно $\mathcal{R}_1$. Дело в том, что, как мне кажется, если сказать: "Арбуз больше мандарины", а потом переставить арбуз и мандарину местами, из этого не следует, что между ними будет отношение "меньше", ведь вместо него там может быть "мандарина желтее арбуза". Вот если бы доказать что $\mathcal{R}_1$ и $\mathcal{R}_2$ - есть отношения эквивалентности...!! Вот, тогда, все встало бы на свои места. Но может я где-то ошибаюсь... От форумчан по прежнему жду помощи...

[Ellan Vannin]

anderlo в сообщении #1106751 писал(а):

Вот если бы доказать что $\mathcal{R}_1$ и $\mathcal{R}_2$ - есть отношения эквивалентности...!! Вот, тогда, все встало бы на свои места. Но может я где-то ошибаюсь... От форумчан по прежнему жду помощи...

Отношение эквивалентности бывает на множестве. Зачем оно нужно? У вас области $X$ и $Y$ не равны, а равномощны (вам по заданию именно это нужно доказать). Все встанет на свои места, когда вы приведете точное определение и расскажете, что и как с его помощью пытаетесь доказать.

[anderlo]

Ладно, видно проблемы с логикой). Спасибо что помогали...

[tolstopuz]

anderlo в сообщении #1106659 писал(а):

Не понимаю как из выполнения $(y_1 R_2 x) и (y_2 R_2 x)$ следует равенство $y_1$ и $y_2$?

Из того, что $\Delta_Y\subset\mathcal{R}_1\circ\mathcal{R}_2$, следует существование такого $x_1$, что $y_1\mathcal{R}_2x_1$ и $x_1\mathcal{R}_1y_1$. Первое из этих условий вам не нужно, а второе комбинируете с вашим $y_1\mathcal{R}_2x$ и используете $\mathcal{R}_2\circ\mathcal{R}_1\subset\Delta_X$. И останется совсем чуть-чуть.

[Ellan Vannin]

Мне здесь тоже не помешала бы помощь:

tolstopuz в сообщении #1107032 писал(а):

$\Delta_Y\subset\mathcal{R}_1\circ\mathcal{R}_2$

tolstopuz в сообщении #1107032 писал(а):

$\mathcal{R}_2\circ\mathcal{R}_1\subset\Delta_X$

Что у вас обозначает знак $\subset$ ? Если вы про графики композиций, то они по условию задачи равны соответствующим диагоналям. Не подмножества, а равны.

tolstopuz в сообщении #1107032 писал(а):

Из того, что $\Delta_Y\subset\mathcal{R}_1\circ\mathcal{R}_2$, следует существование такого $x_1$, что $y_1\mathcal{R}_2x_1$ и $x_1\mathcal{R}_1y_1$.

Существование промежуточного икса такого, что $y_1\mathcal{R}_2x_1$ и $x_1\mathcal{R}_1y_1$ означает: $y_1\mathcal{R}_2 \circ \mathcal{R}_1y_1$. То есть получается у другой композиции в качестве графика та же диагональ. Может быть вы здесь используете обратный способ записи композиций?

[tolstopuz]

Ellan Vannin в сообщении #1107052 писал(а):

Если вы про графики композиций, то они по условию задачи равны соответствующим диагоналям. Не подмножества, а равны.

Равенство множеств означает, что каждое множество является подмножеством другого (Зорич не пользуется знаком $\subseteq$, так что $\subset$ означает нестрогое включение). Я разбиваю его на два отдельных условия, чтобы яснее было видно, чем именно мы пользуемся на каждом шаге.

Ellan Vannin в сообщении #1107052 писал(а):

Существование промежуточного икса такого, что $y_1\mathcal{R}_2x_1$ и $x_1\mathcal{R}_1y_1$ означает: $y_1\mathcal{R}_2 \circ \mathcal{R}_1y_1$.

По условию $\mathcal{R}_2\circ\mathcal{R}_1=\Delta_X$, так что слева и справа от этой композиции могут стоять только иксы. Посмотрите внимательно на определение композиции у Зорича - в левой и правой частях отношения стоят в разном порядке.

[Ellan Vannin]

tolstopuz, я так и предполагал, что здесь обратный порядок. Поскольку мне физически тяжело пользоваться такими обозначениями, можно я лучше сформулирую всё заново?

Даны отношения: $\mathcal{R}_2=\langle G_\mathcal{R}_2,X,Y \rangle$ и $\mathcal{R}_1=\langle G_\mathcal{R}_1,Y,X \rangle$. Композицией $\mathcal{R}_1 \circ \mathcal{R}_2$ будем считать тройку $\langle \{\langle y_1,y_2 \rangle \mid \exists x \ y_1 \mathcal{R}_1 x \land x \mathcal{R}_2 y_2 \},Y,Y \rangle$.

Задача. $\mathcal{R}_2 \circ \mathcal{R}_1=\langle \{\langle x, x \rangle \mid \exists y \ x \mathcal{R}_2 y \land y \mathcal{R}_1 x \},X,X \rangle=\langle \Delta_x,X,X \rangle$ и $\mathcal{R}_1 \circ \mathcal{R}_2=\langle \{\langle y, y \rangle \mid \exists x \ y \mathcal{R}_1 x \land x \mathcal{R}_2 y \},Y,Y \rangle=\langle \Delta_y,Y,Y \rangle$. Доказать, что, к примеру, $\mathcal{R}_1$ инъективно: $\forall y_1,y_2\in Y \; \forall x \in X \quad y_1 \mathcal{R}_1 x \wedge y_2 \mathcal{R}_1 x \Rightarrow y_1 = y_2 $.

Не могли бы вы мне подсказать с новыми обозначениями, какое условие не нужно и что с чем скомбинировать, чтобы получить доказательство?

[tolstopuz]

Ellan Vannin в сообщении #1107063 писал(а):

Поскольку мне физически тяжело пользоваться такими обозначениями, можно я лучше сформулирую всё заново?

Лучше не надо, потому что 1) это запутает ТС и 2) текущий порядок согласуется с определенной у Зорича композицией функций. Давайте я попробую объяснить подробнее в текущих обозначениях.

Запишем $\mathcal{R}_2\circ\mathcal{R}_1=\Delta_X$ в виде двух отдельных утверждений:

$$(1a)\qquad\forall x_1\forall x_2\forall y(x_1\mathcal{R}_1y\wedge y\mathcal{R}_2x_2\Rightarrow x_1=x_2),$$

$$(1b)\qquad\forall x\in X(\exists y\ x\mathcal{R}_1y\wedge y\mathcal{R}_2x).$$

Точно так же $\mathcal{R}_1\circ\mathcal{R}_2=\Delta_Y$ означает

$$(2a)\qquad\forall y_1\forall y_2\forall x(y_1\mathcal{R}_2x\wedge x\mathcal{R}_1y_2\Rightarrow y_1=y_2),$$

$$(2b)\qquad\forall y\in Y(\exists x\ y\mathcal{R}_2x\wedge x\mathcal{R}_1y).$$

И пусть нам дано

$$(3a)\qquad y_1\mathcal{R}_2x,$$

$$(3b)\qquad y_2\mathcal{R}_2x.$$

Из $(2b)$ получаем

$$(4)\qquad x_1\mathcal{R}_1y_1.$$

Подставляя $(4)$ и $(3a)$ в $(1a)$, имеем

$$(5)\qquad\ldots.$$

Подставляя $(\ldots)$ и $(\ldots)$ с учетом $(5)$ в $(2a)$, имеем

$$(6)\qquad y_2=y_1.$$