Задача о конечных множествах - элементарное рассмотрение

[gefest_md]

Имеются два конечных множества с одинаковой мощностью (cardinal): $|A|=|B|=n$. Некоторая функция $f\colon A\stackrel{1-1}{\longrightarrow}B$ т.е. инъективна. Показать, что $f$ сюръективна. Из указаний лишь вопрос "что если функция не съюректнивна?" (Странная подсказка, чуть бы по подробнее ). Можем выбрать $y\in B$ такой, что $\forall x\in A(y\not= f(x))$. Ничего кроме общих рассуждений придумать не могу.

[Dan B-Yallay]

gefest_md в сообщении #466616 писал(а):

Можем выбрать $y\in B$ такой, что $\forall x\in A(y\not= f(x))$. Ничего кроме общих рассуждений придумать не могу.

Следовательно множество значений функции $f$ состоит из максимум $(n-1)$ элементов .
Тут сразу приходит на ум задачка с 10-ю кроликами и 9-ю клетками.

[JMH]

На самом деле сюрьективность следует из определения мощности множества и инъективности $f$.

[gefest_md]

Dan B-Yallay в сообщении #466623 писал(а):

Следовательно множество значений функции $f$ состоит из максимум $(n-1)$ элементов.

Из иньективности $f$ и $|A|=|B|$ следует равенство $|\mathrm{Rng}f|=|B|$. А дальше как доказать, что последнее равенство противоречит допущению $y\in B\wedge\forall x\in A(y\not=f(x)).$ Тем, что $B\subseteq\mathrm{Rng}f$???

[Null]

Тут как-то надо воспользоваться конечностью множеств, для бесконечных утверждение не верно.

[Someone]

Значит, так. У нас есть два конечных множества $A$ и $B$, причём, равномощных, то есть, существует биекция $\varphi\colon A\xrightarrow{\text{на}}B$ (я написал "на", чтобы подчеркнуть, что $\varphi A=B$, хотя в определении биекции это уже сказано). С другой стороны, есть какое-то инъективное отображение $f\colon A\to B$. И мы хотим доказать, что $fA=B$. Ну давайте предположим, что $fA\neq B$, то есть, существует элемент $x_1\in B\setminus fA$.

Null в сообщении #467762 писал(а):

Тут как-то надо воспользоваться конечностью множеств, для бесконечных утверждение не верно.

Правильно. Вот и давайте построим бесконечную последовательность попарно различных элементов $x_1,x_2,x_3,\ldots$, принадлежащих множеству $B$ (рассуждение проходит, правда, не только для конечных множеств, но и для множеств, конечных по Дедекинду)

[gefest_md]

Dan B-Yallay в сообщении #466623 писал(а):

Тут сразу приходит на ум задачка с 10-ю кроликами и 9-ю клетками.

Разобрался с этой задачей. Я хотел найти путь через уже доказанные утверждения к решению данной задачи. Выше я использовал утверждение: "Если $f\colon A\to B$ инъективное отображение то $|A|=|\bathrm{Rng}f|.$"
Другое доказанное утверждение: "Если $|A|=m$, $|B|=n$ и $A\cap B=\varnothing$, то $|A\cup B|=m+n.$" Следовательно, $|\mathrm{Rng}f\cup\{y\}|=n+1$. И конечно $|B\cup\{y\}|=|B|=n.$ Противоречие. ($1\not=0$ беру как одно из основных истинных свойств $\mathbb{R}.$)

[gefest_md]

(Оффтоп)

Ошибся кажется. Если кто-нибудь знает решение, прошу помочь. Это единственный мой вопрос по теме конечных множеств.

[Someone]

Ну я Вам уже подсказывал направление поиска. Ещё немного подскажу.
Так как $\varphi\colon A\to B$ - биекция (заимно однозначное отображение), то существует обратное отображение $\varphi^{-1}\colon B\to A$, которое также является биекцией. Определим отображение $\psi\colon B\to B$ формулой $\psi x=f\varphi^{-1}x$ для всех $x\in B$.
1) Покажите, что $\psi$ инъективно.
2) Покажите, что $x_1\notin\psi B$.
3) Определим $x_2=\psi x_1$, $x_3=\psi x_2$,..., $x_{k+1}=\psi x_k$,... Докажите, что эти элементы все попарно различны.

[gefest_md]

Someone в сообщении #468718 писал(а):

Ну я Вам уже подсказывал направление поиска. Ещё немного подскажу.
Так как $\varphi\colon A\to B$ - биекция (заимно однозначное отображение), то существует обратное отображение $\varphi^{-1}\colon B\to A$, которое также является биекцией. Определим отображение $\psi\colon B\to B$ формулой $\psi x=f\varphi^{-1}x$ для всех $x\in B$.
1) Покажите, что $\psi$ инъективно.
2) Покажите, что $x_1\notin\psi B$.
3) Определим $x_2=\psi x_1$, $x_3=\psi x_2$,..., $x_{k+1}=\psi x_k$,... Докажите, что эти элементы все попарно различны.

Спасибо за отклик!
1. $\psi$ инъективно потому, что $f$ инъективно и $\varphi^{-1}$ инъективно.
2. $x_1\notin\psi B$ потому, что $x_1\notin fA$ (по схеме-рисунку)
3. С этим пунктом запутанее. Когда первый раз посмотрел на свой (динамический) рисунок, создалось впечатление, что получилось "незаконченное" противоречие с $2\not=1$ (может быть "недосказанное"?), Подумаю ещё.

(Оффтоп)

после кофе

[Someone]

Хорошо, ещё подсказка. Определим множества $B_0=B$ и $B_k=\psi B_{k-1}$, $k=1,2,3,\ldots$. Пункт 3) следует из двух утверждений:
4) $B_k\subset B_{k-1}$;
5) $x_k\in B_{k-1}\setminus B_k$.
Но дальше уже подсказывать, вроде бы, нечего, осталось только полное решение написать.

[Circiter]

Вот мне понравилась спекуляция участника Dan B-Yallay о клетках/кроликах. Но, имхо, его пост несколько ненаглядет (для меня :) ), из-за странного $n-1$... (Someone вообще пушку-индукцию приволок для стрельбы по воробьям. :) )

Можно по предложенной в первом же сообщении топикстартера схеме: если функция инъективна, то по-определению инъективности разные элементы переводятся в разные и все эти $n$ разных элементов области значений имеют прообразы; но если функция не является, на этот раз уже сюръективной, т.е. если найдется элемент без прообраза, то этот элемент будет лишним, а всего их теперь будет строго больше $n$, символьно, $|B|>n$, что противоречит условию $|B|=n$. Значит предположение о несюръективности неверно. Методом от противного... того... :)

P.S.: Фу как линейки некрасиво здесь смотрятся. :)

[Someone]

Circiter в сообщении #469088 писал(а):

если найдется элемент без прообраза, то этот элемент будет лишним, а всего их теперь будет строго больше $n$, символьно, $|B|>n$, что противоречит условию $|B|=n$.

Это подозрительно похоже на использование того самого утверждения, которое требуется доказать.

[Circiter]

Почему? Я просто предположил, что $f$ несюръективна и получил $|B|>n$... А условие $|B|=n$ уже дано...

[Someone]

Собственно, условие $|B|=n$ означает, что существует взаимно однозначное отображение отрезка натурального ряда $A=\{1,2,\ldots,n\}$ (или $A=\{0,1,\ldots,n-1\}$, если натуральный ряд начинать с нуля) на $B$. А доказать нужно, что не может быть взаимно однозначного отображения того же $A$ на собственное подмножество $B$, и, следовательно, не может быть одновременно $|B|>n$. То есть, Вы предлагаете использовать в доказательстве именно то, что требуется доказать.