nyuuzyou/wikis huggingface dataset:
Natural Numbers under Addition form Commutative Semigroup

== Theorem ==
The algebraic structure $\struct {\N, +}$ consisting of the set of natural numbers $\N$ under addition $+$ is a commutative semigroup.
== Proof ==
By Naturally Ordered Semigroup Exists, there exists a naturally ordered semigroup.
Consider the natural numbers $\N$ defined as the naturally ordered semigroup.
From the definition of the naturally ordered semigroup, $\struct {\N, +}$ is a semigroup.
By Naturally Ordered Semigroup Axioms imply Commutativity, it follows that $\struct {\N, +}$ is a commutative semigroup.
== Also see ==
* Natural Numbers under Addition form Commutative Monoid
Category:Natural Number Addition
Category:Examples of Commutative Semigroups
Natural Numbers under Addition form Inductive but not Strictly Inductive Semigroup

== Theorem ==
Let $\struct {\N, +}$ denote the algebraic structure consisting of the set of natural numbers $\N$ under addition $+$.
Then $\struct {\N, +}$ forms an inductive semigroup, but not a strictly inductive semigroup
== Proof ==
Recall the definition of inductive semigroup:
Recall the definition of strictly inductive semigroup:
The natural numbers $\N$ can be considered as a naturally ordered semigroup.
From Naturally Ordered Semigroup is Unique, $\struct {\N, +}$ is unique up to isomorphism.
Hence from Naturally Ordered Semigroup forms Peano Structure, $\N$ is a Peano structure.
Let $S$ be a subset of $\N$.
Then by :
:$\paren {0 \in S \land \paren {\forall z \in S: z + 1 \in S} } \implies S = \N$
The latter condition is that which defines an inductive semigroup, where $0$ is identified with $\alpha$ and $1$ with $\beta$.
However, there is no element in $\struct {\N, +}$ which can be identified with $\beta$ in the definition of strictly inductive semigroup.
Indeed, the element $0$ can be expressed in the form $x \circ 1$ for any $x$.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.9 \ \text {(c)}$
Category:Natural Number Addition
Category:Inductive Semigroups
Category:Strictly Inductive Semigroups
Natural Numbers under Min Operation forms Total Semilattice

== Theorem ==
Let $\struct {\N, \wedge}$ denote the set of natural numbers $\N$ under the min operation:
:$\forall a, b \in \N: a \wedge b := \min \set {a, b}$
Then $\struct {\N, \wedge}$ forms a total semilattice.
== Proof ==
Taking the semilattice axioms in turn:
=== ===
We have that:
:$\min \set {a, b} = \begin {cases} a & : a \le b \\ b : b \le a \end {cases}$
Hence if $a, b \in \N$ then $a \wedge b \in \N$.
Thus $\struct {\N, \wedge}$ is closed.
=== ===
Thus $\wedge$ is associative.
=== ===
Thus $\wedge$ is commutative.
=== ===
Thus $\wedge$ is idempotent.
All the semilattice axioms are thus seen to be fulfilled, and so $\struct {\N, \wedge}$ is a semilattice.
=== Totality ===
Let $T \subseteq S$.
Let $a, b\ in T$.
From Min Operation Equals an Operand:
:$\forall a, b \in \N: \min \set {a, b} \in \set {a, b}$
Hence by definition of subset:
:$\min \set {a, b} \in T$
Hence by definition $\struct {\N, \wedge}$ is a total semilattice.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.22 \ \text {(d)}$
Category:Total Semilattices
Category:Natural Numbers
Category:Min Operation
Natural Numbers under Multiplication do not form Group

== Theorem ==
The algebraic structure $\struct {\N, \times}$ consisting of the set of natural numbers $\N$ under multiplication $\times$ is not a group.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Example $7.2$
Category:Natural Number Multiplication
Category:Examples of Groups
Category:Natural Numbers under Multiplication do not form Group
Natural Numbers under Multiplication do not form Group/Proof 1

== Theorem ==
== Proof ==
 that $\struct {\N, \times}$ is a group.
By the definition of the number $0 \in \N$:
:$\forall n \in \N: n \times 0 = 0 = 0 \times n$
Thus $0$ is a zero in the abstract algebraic sense.
From Group with Zero Element is Trivial, $\struct {\N, \times}$ is the trivial group.
But $\N$ contains other elements besides $0$.
From this contradiction it follows that $\struct {\N, \times}$ is not a group.
Category:Natural Numbers under Multiplication do not form Group
Natural Numbers under Multiplication do not form Group/Proof 2

== Theorem ==
== Proof ==
 that $\struct {\N, \times}$ is a group.
We have that $1 \times 1 = 1$ and so is idempotent.
From Identity is only Idempotent Element in Group it follows that $1$ is the identity of $\struct {\N, \times}$.
Let $x \in \N$ such that $x \ne 0$ and $x \ne 1$.
There exists no $y \in \N$ such that $x \times y = 1$
Hence $\struct {\N, \times}$ does not fulfil .
Hence by Proof by Contradiction $\struct {\N, \times}$ is not a group.
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 3$: Examples of Infinite Groups: $\text{(i)}$
Category:Natural Numbers under Multiplication do not form Group
Natural Numbers under Multiplication form Monoid

== Theorem ==
The set of natural numbers under multiplication $\struct {\N, \times}$ is a monoid.
== Proof ==
Taking the monoid axioms in turn:
=== ===
From Natural Number Multiplication is Closed, $\struct {\N, \times}$ is a closed algebraic structure.
=== ===
From Natural Number Multiplication is Associative, $\struct {\N, \times}$ is an associative algebraic structure.
=== ===
From Identity Element of Natural Number Multiplication is One, $\struct {\N, \times}$ has an identity element $1$.
All the monoid axioms are thus seen to be fulfilled, and so $\struct {\N, \times}$ is a monoid.
== Sources ==
* 
* 
Category:Natural Number Multiplication
Category:Examples of Monoids
Natural Numbers under Multiplication form Ordered Commutative Semigroup

== Theorem ==
Let $\N$ be the natural numbers.
Let $\times$ be multiplication.
Let $\le$ be the ordering on $\N$.
Then $\struct {\N, \times, \le}$ is an ordered commutative semigroup.
== Proof ==
By Natural Numbers under Multiplication form Semigroup, $\struct {\N, \times, \le}$ is a semigroup.
By Natural Number Multiplication is Commutative, $\times$ is commutative.
By Ordering on Natural Numbers is Compatible with Multiplication, $\le$ is compatible with $\times$.
The result follows.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Theorem $16.13$: Corollary
Category:Natural Number Multiplication
Category:Examples of Commutative Semigroups
Category:Examples of Ordered Semigroups
Natural Numbers under Multiplication form Semigroup

== Theorem ==
Let $\N$ be the set of natural numbers.
Let $\times$ denote the operation of multiplication on $\N$.
The structure $\struct {\N, \times}$ forms a semigroup.
== Proof ==
=== ===
We have that Natural Number Multiplication is Closed.
That is, $\struct {\N, \times}$ is closed.
=== ===
We have that Natural Number Multiplication is Associative.
Thus the criteria are fulfilled for $\struct {\N, \times}$ to form a semigroup.
== Sources ==
* : $\S 29$. Semigroups: definition and examples: $(1)$
* 
* 
Category:Natural Number Multiplication
Category:Examples of Semigroups
Natural Numbers under Multiplication form Subsemigroup of Integers

== Theorem ==
Let $\struct {\N, \times}$ denote the set of natural numbers under multiplication.
Let $\struct {\Z, \times}$ denote the set of integers under multiplication.
Then $\struct {\N, \times}$ is a subsemigroup of $\struct {\Z, \times}$.
== Proof ==
We have from Natural Numbers under Multiplication form Semigroup that $\struct {\N, \times}$ forms a semigroup.
We have from Integers under Multiplication form Semigroup that $\struct {\Z, \times}$ forms a semigroup.
From Natural Numbers are Non-Negative Integers, we have that $\N \subseteq \Z$.
From the definition of integer multiplication it follows that $\times: \Z \to \Z$ is an extension of $\times: \N \to \N$.
Hence the result.
== Sources ==
* : $\S 32$ Identity element and inverses
Category:Examples of Subsemigroups
Category:Natural Number Multiplication
Category:Integer Multiplication
Natural Numbers under Subtraction do not form Magma

== Theorem ==
The set of natural numbers $\N$ under the operation of subtraction does not form a magma.
== Proof ==
Proof by Counterexample:
Recall the definition of magma:
:$\struct {S, \circ}$ is a magma $\forall a, b \in S: a \circ b \in S$:
That is, a magma is closed under its operation.
Recall that the operation of natural number subtraction of $n - m$ is defined as:
:$n - m = p$
where $p \in \N$ such that $n = m + p$.
But this is defined only when $n \ge m$.
Consider $4 - 7$.
Then there exists no $p \in N$ such that $4 = 7 + p$.
Thus $4 - 7$ is not defined on $\N$.
Thus the algebraic structure $\struct {\N, -}$ is not closed.
Hence the algebraic structure $\struct {\N, -}$ is not a magma by definition.
== Sources ==
* 
* 
Category:Natural Numbers
Category:Subtraction
Category:Examples of Magmas
Natural Numbers with Divisor Operation is Isomorphic to Subgroups of Integer Multiples under Inclusion

== Theorem ==
Let $\N_{>0}$ denote the set of strictly positive natural numbers.
For $n \in \N_{>0}$, let $n \Z$ denote the set of integer multiples of $n$.
Let $\struct {\Z, +}$ denote the additive group of integers.
Let $\mathscr G$ be the set of all subgroups of $\struct {\Z, +}$.
Consider the algebraic structure $\struct {\N_{>0}, \divides}$, where $\divides$ denotes the divisor operator:
:$a \divides b$ denotes that $a$ is a divisor of $b$
Let $\phi: \struct {\N_{>0}, \divides} \to \struct {\mathscr G, \supseteq}$ be the mapping defined as:
:$\forall n \in \N_{>0}: \map \phi n = n \Z$
Then $\phi$ is an order isomorphism.
=== Corollary ===
== Proof ==
We note that from Subgroups of Additive Group of Integers, the subgroups of $\struct {\Z, +}$ are precisely the sets of integer multiples $n \Z$, for $n \in \N_{>0}$.
For each $n \in \N_{>0}$, there is a unique $n \Z \in \mathscr G$.
Hence $\phi$ is a bijection.
It remains to be demonstrated that $\phi$ is order-preserving in both directions.
Thus:
Then:
Hence the result.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.21$
Category:Natural Numbers
Category:Additive Groups of Integer Multiples
Category:Divisors
Category:Examples of Order Isomorphisms
Natural Numbers with Divisor Operation is Isomorphic to Subgroups of Integer Multiples under Inclusion/Corollary

== Corollary to Natural Numbers with Divisor Operation is Isomorphic to Subgroups of Integer Multiples under Inclusion ==
Let $\N_{>0}$ denote the set of strictly positive natural numbers.
For $n \in \N_{>0}$, let $n \Z$ denote the set of integer multiples of $n$.
Let $\struct {\Z, +}$ denote the additive group of integers.
Let $\mathscr G$ be the set of all subgroups of $\struct {\Z, +}$.
Let $\struct {\mathscr G, \times_\PP, \supseteq}$ be the ordered structure such that the operation $\times_\PP$ is defined as:
:$\forall n \Z, m \Z \in \mathscr G: n \Z \times_\PP m \Z := \paren {n m} \Z$
Consider the ordered semigroup $\struct {\N_{>0}, \times, \divides}$, where:
:$\divides$ denotes the divisor operator:
::$a \divides b$ denotes that $a$ is a divisor of $b$
:$\times$ denotes integer multiplication.
Let $\phi: \struct {\N_{>0}, \times, \divides} \to \struct {\mathscr G, \times_\PP, \supseteq}$ be the mapping defined as:
:$\forall n \in \N_{>0}: \map \phi n = n \Z$
Then $\phi$ is an ordered semigroup isomorphism.
== Proof ==
Recall that from Non-Zero Natural Numbers under Multiplication with Divisibility forms Ordered Semigroup, $\struct {\N_{>0}, \times, \divides}$ is indeed an ordered semigroup.
From Natural Numbers with Divisor Operation is Isomorphic to Subgroups of Integer Multiples under Inclusion, we have that $\phi: \struct {\N_{>0}, \divides} \to \struct {\mathscr G, \supseteq}$ is an order isomorphism.
We need to ascertain that $\struct {\mathscr G, \times_\PP, \supseteq}$ is an ordered semigroup.
Then we need to establish that $\phi: \struct {\N_{>0}, \times} \to \struct {\mathscr G, \times_\PP}$ is a semigroup isomorphism.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Exercise $15.9$
Category:Natural Numbers
Category:Additive Groups of Integer Multiples
Category:Divisors
Category:Ordered Semigroup Isomorphisms
Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4

== Theorem ==
=== Construction ===
There exists a unique total ordering $\le$ on $M$ such that:
:the restriction of $\le$ to $\N$ is the given total ordering $\le$ on $\N$
:$0 < \beta < 1$
such that the algebraic structure:
:$\struct {M, +, \le}$
is an ordered semigroup which fulfils the axioms:
:
:
:
but:
:does not fulfil 
:$\struct {M, +}$ is not isomorphic to $\struct {\N, +}$.
== Proof ==
Recall the axioms:
Some lemmata:
=== Lemma 1 ===
=== Lemma 2 ===
=== Lemma 3 ===
=== ===
Let $S \subseteq M$ such that $\beta \notin S$.
Then:
:$S \subseteq \N$
By the Well-Ordering Principle, $\struct {\N, \le}$ is a well-ordered set.
Hence $S$ is well-ordered.
Hence by definition, $S$ has a smallest element
Let $T \subseteq M$ such that $\beta \in T$.
;Case $1$: $0 \in T$
Then as $0 < \beta$ we have that:
:$\forall x \in T: 0 \le x$
and so $T$ has a smallest element, that is, $0$.
;Case $2$: $0 \notin T$
From Lemma $2$ we have that $\le$ is a total ordering such that:
:$\forall x \in T: \beta \le x$
and so $T$ has a smallest element, that is, $\beta$.
Hence it has been shown that every subset of $M$ has a smallest element.
That is, $\struct {M, \le}$ is a well-ordered set.
Hence holds.
=== ===
By the construction of the natural numbers, $\struct {\N, +, \le}$ is a naturally ordered semigroup.
Hence holds for $\N$:
:$\forall m, n \in \N: m \le n \implies \exists p \in \N: m + p = n$
Hence:
:$\forall m, n \in M \setminus \set \beta: m \le n \implies \exists p \in \N: m + p = n$
Now consider $\beta \in M$.
;Case 1:
Let $m \in M: m \le \beta$.
Then either:
:$m = \beta$
in which case:
:$\exists \beta \in M: m + \beta = \beta$
or:
:$m = 0$
in which case also:
:$\exists \beta \in M: m + \beta = \beta$
;Case 2:
Let $n \in M: \beta \le n$.
Then:
:$\exists n \in \N: n + \beta = n$
and it is seen that holds.
=== ===
We have that:
:$0 \in M$
and:
:$1 \in M$
and trivially holds.
=== ===
We have that:
:$\forall n \in M \setminus \set 0: n + 0 = n + \beta = n$
but it is not the case that $0 = \beta$.
That is, $\struct {M, +, \le}$ does not fulfil .
Hence the result.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.2 \ \text{(c)}$
Category:Naturally Ordered Semigroup
Category:Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4
Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4/Construction

== Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4: Construction ==
Let $\N$ denote the set of natural numbers.
Let $\beta$ be an object such that $\beta \notin \N$
Let $M = \N \cup \set \beta$.
Let us extend the operation of natural number addition from $\N$ to $M$ by defining:
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.2$
Category:Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4
Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4/Lemma 1

== Lemma for Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4 ==
=== Construction ===
The algebraic structure:
:$\struct {M, +}$
is a commutative monoid such that $0$ is the identity.
== Proof ==
=== Closure ===
It is directly apparent from the definition that $\struct {M, +}$ is closed.
=== Commutativity ===
We know from Natural Number Addition is Commutative that:
:$\forall a, b \in \N: a + b = b + a$
It is also seen from the definition that:
:$\forall a \in \N: a + \beta = \beta + a$
Thus $+$ is commutative on $M$.
=== Associativity ===
We know from Natural Number Addition is Associative that:
:$\forall a, b, c \in \N: \paren {a + b} + c = a + \paren {b + c}$
It remains to check the other cases.
In the below, $a$ and $b$ are arbitrary non-zero elements of $\N$.
Because of commutativity it is sufficient to test the various combinations of $a$, $b$ and $0$ with $\beta$.
So:
All combinations of $a$, $b$ and $0$ with $\beta$ have been verified for associativity.
Hence $+$ is associative on $M$.
=== Identity Element ===
We have that Identity Element of Natural Number Addition is Zero.
That is:
:$\forall a \in \N: a + 0 = a = 0 + a$
We also have that:
:$\beta + 0 = \beta = 0 + \beta$
and it is seen that $0$ is the identity element for $\struct {M, +}$.
Hence the result.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.2 \ \text{(a)}$
Category:Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4
Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4/Lemma 2

== Lemma for Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4 ==
=== Construction ===
There exists a unique total ordering $\preccurlyeq$ on $M$ such that:
:the restriction of $\preccurlyeq$ to $\N$ is the given total ordering $\le$ on $\N$
:$0 \prec \beta \prec 1$
This total ordering we will rename $\le$ to overload the notation for $\N$.
== Proof ==
We define $\preccurlyeq$ on $M$ as follows:
:$a \preccurlyeq b \iff \begin {cases} a, b \in \N: a \le b \\ a = 0, b = \beta \\ a = \beta, b \in \N_{>0} \\ a = \beta, b = \beta \end {cases}$
=== Existence ===
The restriction of $\preccurlyeq$ to $\N$ is seen to be the total ordering $\le$ on $\N$.
We have that:
:$0 \preccurlyeq \beta$ and $0 \ne \beta$
from which:
:$0 \prec \beta$
and:
:$\beta \preccurlyeq 1$ and $\beta \ne 1$
from which:
:$\beta \prec 1$
and:
:$\forall a \in \N_{>0}: \beta \preccurlyeq a$
Finally:
:$\beta = \beta$
and so:
:$\beta \preccurlyeq \beta$
This demonstrates that $\preccurlyeq$ is total.
Hence existence of the total ordering in question has been proven.
=== Uniqueness ===
Let $\preccurlyeq'$ be another total ordering on $M$ such that:
:the restriction of $\preccurlyeq'$ to $\N$ is the given total ordering $\le$ on $\N$
:$0 \prec' \beta \prec' 1$
We have by definition of $\le$ on $\N$ that:
:$\forall a, b \in \N: a \le b \implies a \preccurlyeq' b$
From $0 \prec' \beta \prec' 1$ we have:
:$0 \preccurlyeq' \beta$
:$\beta \preccurlyeq' 1$
Because $\beta \preccurlyeq' 1$ and an ordering is transitive:
:$\forall a \in \N: 1 \le a \implies \beta \preccurlyeq' a$
Then as an ordering is reflexive:
:$\beta \preccurlyeq' \beta$
Hence $\preccurlyeq'$ is defined as:
:$a \preccurlyeq' b \iff \begin {cases} a, b \in \N: a \le b \\ a = 0, b = \beta \\ a = \beta, b \in \N_{>0} \\ a = \beta, b = \beta \end {cases}$
which is seen to be exactly the same as $\preccurlyeq$.
Hence the result.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.2 \ \text{(b)}$
Category:Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4
Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4/Lemma 3

== Lemma for Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4 ==
=== Construction ===
The algebraic structure:
:$\struct {M, +}$
is not isomorphic to $\struct {\N, +}$.
== Proof ==
 there exists a (semigroup) isomorphism $\phi$ from $\struct {M, +}$ to $\struct {\N, +}$.
By definition of isomorphism:
:$\phi$ is a homomorphism
:$\phi$ is a bijection.
As $\phi$ is a fortiori a surjection, $\phi$ is also an epimorphism.
Hence from Epimorphism Preserves Identity:
:$\map \phi 0 = 0$
Let $a \in M$ such that $a \ne \beta$ and $a \ne 0$.
Then:
But then:
:$\map \phi \beta = \map \phi 0$
and so $\phi$ is not injective.
Hence, by definition, $\phi$ is not a bijection.
This contradicts our assertion that $\phi$ is an isomorphism.
Hence there can be no such semigroup isomorphism between $\struct {M, +}$ and $\struct {\N, +}$.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.2 \ \text{(d)}$
Category:Natural Numbers with Extension fulfil Naturally Ordered Semigroup Axioms 1, 3 and 4
Natural Numbers without 1 fulfil Naturally Ordered Semigroup Axioms 1, 2 and 4

== Theorem ==
Let $S \subseteq \N$ be the subset of the natural numbers defined as:
:$S = \N \setminus \set 1 = \set {0, 2, 3, 4, \ldots}$
Then the algebraic structure:
:$\struct {S, +, \le}$
is an ordered semigroup which fulfils the axioms:
:
:
:
but:
:does not fulfil 
:$\struct {S, +}$ is not isomorphic to $\struct {\N, +}$.
== Proof ==
Recall the axioms:
=== ===
By the Well-Ordering Principle, $\struct {\N, \le}$ is a well-ordered set.
We have that $S \subseteq \N$.
By definition of well-ordered set, $S$ itself is well-ordered.
Hence holds.
=== ===
By the construction of the natural numbers, $\struct {\N, +, \le}$ is a naturally ordered semigroup.
Hence holds for $\struct {\N, +, \le}$.
By Cancellable Element is Cancellable in Subset:
: holds also for $\struct {S, +, \le}$.
=== ===
We have that:
:$0 \in M$
and:
:$2 \in M$
and trivially holds.
=== ===
We have that:
Consider $2, 3 \in \N$.
We have that:
:$2 \le 3$
and:
:$3 = 2 + 1$
But $1 \ne S$.
Hence:
:$\exists 2, 3 \in S: \nexists p \in S: 2 + p = 3$
That is, $\struct {M, +, \le}$ does not fulfil .
=== Lack of Isomorphism ===
It remains to demonstrate that $S$ and $\N$ are not isomorphic.
 there exists a (semigroup) isomorphism $\phi$ from $\struct {\N, +}$ to $\struct {S, +}$.
By definition of isomorphism:
:$\phi$ is a homomorphism
:$\phi$ is a bijection.
We have that:
That is:
:$\forall n \in \N: \map \phi n = m n$
But let $p \in S: p = n + 1$.
Then:
:$\nexists r \in \N: \map \phi r = p$
and so $\phi$ is not a surjection.
Hence, by definition, $\phi$ is not a bijection.
This contradicts our assertion that $\phi$ is an isomorphism.
Hence there can be no such semigroup isomorphism between $\struct {S, +}$ and $\struct {\N, +}$.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.3$
Category:Naturally Ordered Semigroup
Naturality of Yoneda Lemma for Contravariant Functors

== Theorem ==
Let $C$ be a locally small category.
Let $\mathbf{Set}$ be the category of sets.
Let $[C^{\operatorname{op}}, \mathbf{Set}]$ be the contravariant functor category.
Let $C^{\operatorname{op}} \times [C^{\operatorname{op}}, \mathbf{Set}] $ be the product category.
Let $C^{\operatorname{op}} \times [C^{\operatorname{op}}, \mathbf{Set}] \to \mathbf{Set} : (A, F) \mapsto \operatorname{Nat}(h_A, F)$ be the covariant functor defined as the composition of the hom bifunctor and the product of the opposite of the covariant Yoneda functor $h_-$ and the identity functor $\operatorname{id}_{[C^{\operatorname{op}}, \mathbf{Set}]}$.
Let $\operatorname{ev} : C^{\operatorname{op}} \times [C^{\operatorname{op}}, \mathbf{Set}] \to \mathbf{Set} : (A, F) \mapsto F(A)$ be the contravariant functor evaluation functor.
Then $\Phi_{(A, F)} : \operatorname{Nat}(h_A, F) \to F(A) : \eta \mapsto \eta_A(\operatorname{id}_A)$ defines a natural isomorphism, where $\operatorname{id}_A$ is the identity morphism of $A$.
== Proof ==
== Also see ==
* Naturality of Yoneda Lemma for Covariant Functors
Category:Category Theory