Найти число эпиморфизмов между конечными множествами

[Lyssa]

Не получается строго доказать формулу.

Пусть $\pi(n,m)$ число сюръективных гомоморфизмов из $|X| = n$ на $|Y| = m$. Чтобы получить его в явном виде, нужно взять общее число гомоморфизмов (а всего их, как известно, $m^n$) и вычесть из него все несюръективные. Несюръективный гомомоморфизм для $Y$ является сюръективным для его некоторого собственного подмножества. Значит, у нас есть следующая рекуррентная формула:

$$\pi(n,m) = m^n - \sum^{m-1}_{k=1} C_m^k \cdot \pi(n,k)$$

Я подсчитала первые несколько значений:
$\pi(n,1) = 1$
$\pi(n,2) = 2^n - 2 $
$\pi(n,3) = 3^n - 3 \cdot 2^n + 3$
Из них угадывается общий вид нужной формулы:

$$\pi(n,m) = \sum^{m}_{k=1} (-1)^{m-k} \cdot C_m^k \cdot k^n$$

Однако попытки доказать ее индукцией по m неизбежно терпят крах.

[Sonic86]

Вам нужно вывести из формулы $m^n = \sum\limits^{m}_{k=1} C_m^k \cdot \pi(n,k)$ формулу $\pi(n,m) = \sum\limits^{m}_{k=1} (-1)^{m-k} \cdot C_m^k \cdot k^n$. По индукции можно так: пусть мы доказали формулу для для $\pi(n,r)$ для $r=1,...,m-1$, пытаемся доказать для $r=m$. Умножим $\pi(n,r)$ для $r=1,...,m$ на $C_m^r$ и просуммируем по $r$ - получим формулу $F$ (выпишите ее сами). Доказываемое соотношение для $r=m$ будет верно тогда и только тогда, когда верна $F$. Теперь просто упростите $F$ (не очень легко, но ничего принципиально сложного нет), получите тождество. Значит все понятно...

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

[Someone]

(Lyssa)

Lyssa, у Вас странная терминология. Гомоморфизм, эпиморфизм, мономорфизм, изоморфизм — это алгебраическая терминология, относящаяся к отображениям, согласованным с алгебраической структурой. У Вас множества наделены алгебраическими структурами? Если нет, то используются термины отображение (или функция), сюръекция, инъекция, взаимно однозначное отображение.

[Sonic86]

(Someone)

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

Lyssa, у Вас странная терминология. Гомоморфизм, эпиморфизм, мономорфизм, изоморфизм — это алгебраическая терминология, относящаяся к отображениям, согласованным с алгебраической структурой. У Вас множества наделены алгебраическими структурами? Если нет, то используются термины отображение (или функция), сюръекция, инъекция, взаимно однозначное отображение.

Это м.б. категорная терминология. У них там термины "эпиморфизм" и "мономорфизм" переопределены для всех категорий (как отображения, на которые можно сокращать справа и слева) и могут применяться, в частности, к категории множеств с морфизмами типа "просто отображения".
Хотя термин "гомоморфизм" мне неясно к чему.
ссылка на вики

[Someone]

(Sonic86)

Sonic86 в сообщении #779005 писал(а):

Это м.б. категорная терминология.

А, действительно. Теорией категорий никогда всерьёз не занимался, поэтому вовремя не вспомнил. Но "гомоморфизма" в теории категорий не припоминаю. Там, как будто бы, термин "морфизм" используется.

Но в данном-то случае "сюръективный гомоморфизм" явно на теорию категорий не намекает.

[Lyssa]

Я всегда считала, что слова вроде «сюръекция», «эпиморфизм» или «отображение на» абсолютно синонимичны, и могут быть использованы вне зависимости от наличия на множестве той или иной алгебраической структуры. Разве это не так?

[Sonic86]

Lyssa в сообщении #780150 писал(а):

Я всегда считала, что слова вроде «сюръекция», «эпиморфизм» или «отображение на» абсолютно синонимичны, и могут быть использованы вне зависимости от наличия на множестве той или иной алгебраической структуры. Разве это не так?

Не так.
Эпиморфизм в алгебре - это сюрьективный гомоморфизм.
Мономорфизм - это инъективный гомоморфизм.
Гомоморфизм $\varphi: G\to H$ - отображение, сохраняющее операции: $\varphi(xy)=\varphi(x)\varphi(y)$ (или отношения)

[Someone]

Lyssa в сообщении #780150 писал(а):

Я всегда считала, что слова вроде «сюръекция», «эпиморфизм» или «отображение на» абсолютно синонимичны, и могут быть использованы вне зависимости от наличия на множестве той или иной алгебраической структуры. Разве это не так?

Нет. В алгебре и теории категорий термин "эпиморфизм" имеет другое определение, нежели "сюръекция", и не всегда является сюръективным. С другой стороны, в алгебре термин "эпиморфизм" предполагает отображение, согласованное с алгебраической структурой, в то время как "сюръекция" не обязана сохранять какие-либо структуры.
Термины "сюръекция" и "отображение на" являются синонимами (второе есть просто русскоязычный вариант первого).

P.S. Пока писал, уже появилось объяснение.

[arseniiv]

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

В алгебре и теории категорий термин "эпиморфизм" имеет другое определение, нежели "сюръекция", и не всегда является сюръективным.

Как так эпиморфизм не всегда сюръективен?

[Lyssa]

Не поняла вашу мысль. Если на множестве существует алгебраическая структура (группа, кольцо, алгебра, векторное пространство и т.д.), то гомоморфизм ее сохраняет. Следовательно, если структуры нет, то гомоморфизмом можно называть абсолютно любое отображение множеств. Почему это некорректно?

И можно пример, где именно в алгебре под эпиморфизмом понимается что-то отличное от «отображение на, сохраняющее структуру»?

[Sonic86]

Lyssa в сообщении #780161 писал(а):

Следовательно, если структуры нет, то гомоморфизмом можно называть абсолютно любое отображение множеств. Почему это некорректно?

Ха, прикольно, действительно Обычно народ бурбакизмами просто не увлекается. С другой стороны, если меня в задаче просят доказать, что данное отображение - гомоморфизм, то звучит это обычно, а на Ваш язык как переводится?

[Someone]

Lyssa в сообщении #780161 писал(а):

Следовательно, если структуры нет, то гомоморфизмом можно называть абсолютно любое отображение множеств. Почему это некорректно?

Формально можно, но фактически не называют. Вероятно, потому, что в алгебре "чистые" множества рассматривать не интересно, а там, где такие множества рассматривают, принят термин "сюръекция" или его перевод на соответствующий язык.

Lyssa в сообщении #780161 писал(а):

И можно пример, где именно в алгебре под эпиморфизмом понимается что-то отличное от «отображение на, сохраняющее структуру»?

Эпиморфизм колец $\mathbb Z\to\mathbb Q$ не является отображением на всё множество рациональных чисел $\mathbb Q$.