Сюръективное отображение инъективно.

[ellipse]

Как доказать, что сюръективное отображение конечного множества в себя инъективно?

[Виктор Викторов]

Как сюръективное отображение конечного множества может быть «в себя»? Если отображение сюръективно, то оно «на себя». И, конечно, оно биективно.
Отображение называется сюръективным, если образом области определения является всё множество значений.

[Gordmit]

Например, от противного: если у какого-нибудь элемента есть хотя бы два прообраза, то найдется элемент, которому прообраза не достанется.

-- Пт июн 19, 2009 21:26:10 --

Виктор Викторов в сообщении #223401 писал(а):

Как сюръективное отображение конечного множества может быть «в себя»? Если отображение сюръективно, то оно «на себя».

Сюрьективное отображение множества в себя $\equiv$ отображение множества на себя.
"Сюрьективное отображение множества на себя" - это уже, по-моему, какая-то тавтология терминологическая

[Виктор Викторов]

Gordmit в сообщении #223402 писал(а):

Виктор Викторов в сообщении #223401 писал(а):

Как сюръективное отображение конечного множества может быть «в себя»? Если отображение сюръективно, то оно «на себя».

Сюрьективное отображение множества в себя $\equiv$ отображение множества на себя.
"Сюрьективное отображение множества на себя" - это уже, по-моему, какая-то тавтология терминологическая

Так это всё тавтология: Сюрьективное отображение - "отображение на".
Смысл: если отображение сюръективно, то оно (отображение) «на».
Сюръективное отображение конечного множества в (на) себя взаимнооднозначное соответствие. Вопроса то нет.

[Профессор Снэйп]

Надо сослаться на "принцип Дирихле". Хотя, наверное, можно ещё использовать метод математической индукции...

А вообще-то есть разные определения конечного множества, они без аксиомы выбора не тождественны...

[Виктор Викторов]

Профессор Снэйп в сообщении #223459 писал(а):

Надо сослаться на "принцип Дирихле". Хотя, наверное, можно ещё использовать метод математической индукции...

Какое отношение этот вопрос имеет к "принципу Дирихле"? Мощности то равны.

Профессор Снэйп в сообщении #223459 писал(а):

А вообще-то есть разные определения конечного множества, они без аксиомы выбора не тождественны...

Простите, профессор, но здесь конечный случай. Для нетривиального использования аксиомы выбора Френкель очень настаивал на бесконечном переборе (да и Рассел тоже). Ведь таких отображений конечное множество для каждого n. Вас устроит определение: «множество F – конечно, если существование взаимнооднозначного отображения множества F на подмножество F’ множества F означает F’ = F.». Надеюсь, мы не будем влезать в разговор о нерефлексивных множествах.

[Профессор Снэйп]

Виктор Викторов в сообщении #223510 писал(а):

Какое отношение этот вопрос имеет к "принципу Дирихле"? Мощности то равны.

Ну а принцип Дирихле как формулируется?

-- Пн июн 22, 2009 18:56:28 --

Виктор Викторов в сообщении #223510 писал(а):

Вас устроит определение: «множество F – конечно, если существование взаимнооднозначного отображения множества F на подмножество F’ множества F означает F’ = F.».

Безусловно устроит.

Пусть $F$ конечно (согласно Вашему определению) и $\varphi : F \to F$ --- сюрьекция. Выберем для каждого $x \in F$ элемент $y_x$, такой что $\varphi(y_x) = x$. Рассмотрим множество $F' = \{ y_x : x \in F \}$. Отображение $x \mapsto y_x$ есть биекция $F$ на $F'$. Отсюда и из того, что $F$ конечно, получаем $F' = F$. Теперь если $z_1$ и $z_2$ --- элементы $F$, то они из $F'$ и, значит, равенство $\varphi(z_1) = \varphi(z_2) = x$ означает $z_1 = y_x = z_2$. Так что $\varphi$ действительно инъективно.

Что Вас не устраивает в этом доказательстве?

[Виктор Викторов]

Профессор Снэйп в сообщении #223969 писал(а):

Виктор Викторов в сообщении #223510 писал(а):

Какое отношение этот вопрос имеет к "принципу Дирихле"? Мощности то равны.

Ну а принцип Дирихле как формулируется?

Из Википедии:
«Предположим, некоторое число кроликов рассажены в клетках. Если число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.»

Профессор Снэйп в сообщении #223969 писал(а):

Виктор Викторов в сообщении #223510 писал(а):

Вас устроит определение: «множество F – конечно, если существование взаимнооднозначного отображения множества F на подмножество F’ множества F означает F’ = F.».

Безусловно устроит.

Пусть $F$ конечно (согласно Вашему определению) и $\varphi : F \to F$ --- сюрьекция. Выберем для каждого $x \in F$ элемент $y_x$, такой что $\varphi(y_x) = x$. Рассмотрим множество $F' = \{ y_x : x \in F \}$. Отображение $x \mapsto y_x$ есть биекция $F$ на $F'$. Отсюда и из того, что $F$ конечно, получаем $F' = F$. Теперь если $z_1$ и $z_2$ --- элементы $F$, то они из $F'$ и, значит, равенство $\varphi(z_1) = \varphi(z_2) = x$ означает $z_1 = y_x = z_2$. Так что $\varphi$ действительно инъективно.

Что Вас не устраивает в этом доказательстве?

А что, я где-то не согласился с этим доказательством?

Gordmit в сообщении #223402 писал(а):

Например, от противного: если у какого-нибудь элемента есть хотя бы два прообраза, то найдется элемент, которому прообраза не достанется.

Мне просто показалось, что это максимум затрат, которых этот вопрос стоит. Вам не кажется, что мы стреляем из пушки по воробьям?