同构和同态是什么？

Question

我试着在编程中理解同构和同态，需要一些帮助。

在FPiS一书中，它解释道：

​

​

让我们从同态开始：

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

在这里，length是String to Int中的一个函数，它保留了一元结构。

• 为什么这是同态？
• 为什么它保留了一元结构？
• 例如，map on list函数是同态吗？

关于同构，我有如下解释，我是从一本书中摘取的：

M和N之间的单半群同构有两个同态f和g，其中f andThen g和g andThen f都是一个恒等函数。例如，串连的字符串和ListChar一元是同构的。两个布尔幺半群(false，x_x)和(true，&)也是同构的。(否定)函数。

为什么(false, ||), (true, &&)和String and List[Char] monoids with concatenation是同构的？

Answer 1

为什么这是同态？

从定义上来说。

为什么它保留了一元结构？

因为上面表达式中的==。

例如，列表函数上的映射是同态吗？

是。将"foo"和"bar"替换为两个列表，.length替换为.map(f)。这样就很容易看出(并证明)方程成立。

为什么连在一起的字符串和ListChar一元都是同构的(false，x-)，(true，&&)？

从定义上来说。这个证据是微不足道的，只是一个练习。(提示:采用同构的定义，用具体的对象替换所有抽象对象，证明得到的数学表达式是正确的)

编辑:以下是您在评论中问到的几个定义：

• 同态:将一组转换为另一组，在第二组中保留第一组元素之间的关系。形式上，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之前，我们要对两个参数应用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)，即，如果你对两个元素上的A算子的结果应用f，就等于将它两次应用在两个A元素上，然后用B的算子组合结果。

问题是，单样体同态是一种保持结构的映射(这就是同态的意思；把这个词分解到它的古希腊根，你就会发现它的意思是“同型-”)。

好的，你问的例子，这里有一些例子！

• 上面例子中的一个例子：length是从自由幺半群(A，·，ε)*到(ℕ，+，0)的单样同态。
• 否定是从(Bool，∨，false)到(Bool，∧，true)和反面的单面同态。
• 是一元同态从(ℝ，+，0)到(ℝ{0}，*，1)
• 事实上，每一个群同态当然也是一个单样同态。