How do I prove the correctness of this isomorphism relation?

38 Views Asked by At

I want to show that $$[m] \uplus [n] \cong [m+n]$$ but I don't get why this is true. I see that $[m] = \{0, 1, 2, ... m-1\}$ and $[n] = \{0, 1, 2, ... n-1\}$but I don't see how this could lead to $[m+n] = \{0, 1, .... m+n-1\}$. Why is this even true?


The same goes for a relationship like $[m] \times [n] \cong [m\cdot n]$ (as a side note, why must it be $\times$ and not a multiplication for this relation? Or is this isomorphism incorrect?

1

There are 1 best solutions below

0
On

This is only going to work if your symbol $\uplus$ refers to the disjoint union, not just the union. There's several ways to instantiate the disjoint union, with one of the easiest being:

$A \uplus B = (A \times \{0\}) \cup (B \times \{1\})$

This ensures that the elements coming from $A$ and the elements coming from $B$ don't coincide. See if you can make it work with that definition.

Comment: These relations are basically about reflecting the usual operations on the natural numbers in the context of the cardinalities of finite sets. The disjoint union of sets corresponds to addition and the Cartesian product of sets corresponds to multiplication.