2014 dxdy logo

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

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




 
 Найти число эпиморфизмов между конечными множествами
Сообщение22.10.2013, 16:50 
Аватара пользователя
Не получается строго доказать формулу.

Пусть $\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 неизбежно терпят крах.

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение22.10.2013, 17:52 
Вам нужно вывести из формулы $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$ (не очень легко, но ничего принципиально сложного нет), получите тождество. Значит все понятно...

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

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение23.10.2013, 12:12 
Аватара пользователя

(Lyssa)

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

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение23.10.2013, 12:36 

(Someone)

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

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение23.10.2013, 13:33 
Аватара пользователя

(Sonic86)

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

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

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

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение25.10.2013, 20:24 
Lyssa в сообщении #780150 писал(а):
Я всегда считала, что слова вроде «сюръекция», «эпиморфизм» или «отображение на» абсолютно синонимичны, и могут быть использованы вне зависимости от наличия на множестве той или иной алгебраической структуры. Разве это не так?
Не так.
Эпиморфизм в алгебре - это сюрьективный гомоморфизм.
Мономорфизм - это инъективный гомоморфизм.
Гомоморфизм $\varphi: G\to H$ - отображение, сохраняющее операции: $\varphi(xy)=\varphi(x)\varphi(y)$ (или отношения)

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение25.10.2013, 20:27 
Аватара пользователя
Lyssa в сообщении #780150 писал(а):
Я всегда считала, что слова вроде «сюръекция», «эпиморфизм» или «отображение на» абсолютно синонимичны, и могут быть использованы вне зависимости от наличия на множестве той или иной алгебраической структуры. Разве это не так?
Нет. В алгебре и теории категорий термин "эпиморфизм" имеет другое определение, нежели "сюръекция", и не всегда является сюръективным. С другой стороны, в алгебре термин "эпиморфизм" предполагает отображение, согласованное с алгебраической структурой, в то время как "сюръекция" не обязана сохранять какие-либо структуры.
Термины "сюръекция" и "отображение на" являются синонимами (второе есть просто русскоязычный вариант первого).

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

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение25.10.2013, 20:34 
Someone в сообщении #780155 писал(а):
В алгебре и теории категорий термин "эпиморфизм" имеет другое определение, нежели "сюръекция", и не всегда является сюръективным.
Как так эпиморфизм не всегда сюръективен?

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

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

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение25.10.2013, 21:42 
Lyssa в сообщении #780161 писал(а):
Следовательно, если структуры нет, то гомоморфизмом можно называть абсолютно любое отображение множеств. Почему это некорректно?
Ха, прикольно, действительно :D Обычно народ бурбакизмами просто не увлекается. С другой стороны, если меня в задаче просят доказать, что данное отображение - гомоморфизм, то звучит это обычно, а на Ваш язык как переводится?

 
 
 
 Re: Найти число эпиморфизмов между конечными множествами
Сообщение25.10.2013, 21:50 
Аватара пользователя
Lyssa в сообщении #780161 писал(а):
Следовательно, если структуры нет, то гомоморфизмом можно называть абсолютно любое отображение множеств. Почему это некорректно?
Формально можно, но фактически не называют. Вероятно, потому, что в алгебре "чистые" множества рассматривать не интересно, а там, где такие множества рассматривают, принят термин "сюръекция" или его перевод на соответствующий язык.

Lyssa в сообщении #780161 писал(а):
И можно пример, где именно в алгебре под эпиморфизмом понимается что-то отличное от «отображение на, сохраняющее структуру»?
Эпиморфизм колец $\mathbb Z\to\mathbb Q$ не является отображением на всё множество рациональных чисел $\mathbb Q$.

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group