Что такое изоморфизм и гомоморфизмы

Question

Я пытался понять изоморфизм и гомоморфизмы в контексте программирования, и мне нужна помощь.

В книге FPiS это объясняет:

Начнем с гомоморфизмов:

"foo".length + "bar".length == ("foo" + "bar").length

Здесь длина является функцией от String to Int это сохраняет моноидную структуру.

• Почему это гомоморфизмы?

• Почему оно сохраняет моноидную структуру?

• Есть например map на list функция гомоморфизмов?

Об изоморфизме у меня есть следующее объяснение, что я взял его из книги:

Изоморфизм моноидов между M и N имеет два гомоморфизма f и g, где f и тогда g и g и тогда f являются единичной функцией. Например, моноиды String и List[Char] с конкатенацией изоморфны. Два логических моноида (false, ||) и (true, &&) также изоморфны через! (отрицание) функция.

Зачем (false, ||), (true, &&) а также String and List[Char] monoids with concatenation такое изоморфизм?

Answer 1

Почему это гомоморфизмы?

По определению.

Почему оно сохраняет моноидную структуру?

Из-за == в выражении выше.

Является ли, например, функция map в списке гомоморфизмами?

Да. замещать "foo" а также "bar" по двум спискам, и .length от .map(f), Тогда легко увидеть (и доказать), что уравнение выполнено.

Почему (false, ||), (true, &&) и моноиды String и List[Char] с конкатенацией являются изоморфизмом?

По определению. Доказательство тривиально, оставлено в качестве упражнения. (Подсказка: возьмите определение изоморфизма, замените все абстрактные объекты конкретными объектами, докажите, что полученное математическое выражение верно)

---

Изменить: Вот несколько определений, которые вы просили в комментариях:

• Гомоморфизм: преобразование одного множества в другое, сохраняющее во втором множестве отношения между элементами первого. Формально f: A → B где обаA а также B иметь * операция такая, что f(x * y) = f(x) * f(y),

• Моноид: алгебраическая структура с одной ассоциативной бинарной операцией и единичным элементом. Формально (M, *, id) моноид если (a * b) * c == a * (b * c) && a * id == a && id * a == a for all a, b, c in M,

Answer 2

"foo".length + "bar".length == ("foo" + "bar").length

Чтобы быть точным, это говорит о том, что length является моноидным гомоморфизмом между моноидом строк с конкатенацией и моноидом натуральных чисел с сложением. То, что эти две структуры являются моноидами, легко увидеть, если приложить усилия.

Причина length является моноидным гомоморфизмом, потому что он обладает свойствами, которые "".length = 0 а также x.length ⊕ y.length = (x ⊗ y).length, Здесь я намеренно использовал два разных символа для двух моноидных операций, чтобы подчеркнуть тот факт, что мы применяем операцию сложения к результатам примененияlength vs операция объединения строк для двух аргументов перед применениемlength, К сожалению, в приведенном примере используется один и тот же символ. + для обеих операций.

Отредактировано, чтобы добавить: плакат с вопросом попросил некоторые дополнительные детали о том, что именно является гомоморфизмом моноидов.

Итак, предположим, у нас есть два моноида (A, ⊕, a) и (B, ⊗, b), что означает, что A и B являются нашими двумя носителями, ⊕: A × A → A и ⊗: B × B → B являются нашими два бинарных оператора, и a ∈ A и b ∈ B являются нашими двумя нейтральными элементами. Гомоморфизм моноидов между этими двумя моноидами является функцией f: A → B со следующими свойствами:

• f (a) = b, т.е. если вы примените f к нейтральному элементу A, вы получите нейтральный элемент B
• f (x ⊕ y) = f (x) ⊗ f (y), т. е. если вы примените f к результату оператора A для двух элементов, это то же самое, что применить его дважды, к двум элементам A, и затем объединяя результаты, используя оператор B.

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

Хорошо, вы просили примеры, вот несколько примеров!

• Один из приведенного выше примера: length является гомоморфизмом моноидов из свободного моноида (A, ·, ε) * в (ℕ, +, 0)
• Отрицание - это моноидный гомоморфизм из (Bool, ∨, false) в (Bool, ∧, true) и наоборот.
• exp - моноидный гомоморфизм из (ℝ, +, 0) в (ℝ\{0}, *, 1)
• На самом деле, любой групповой гомоморфизм также является, конечно, моноидным гомоморфизмом.