Sheng Li (gmachine1729) wrote,
Sheng Li
gmachine1729

Rigorous construction and definition of the integers and proof of their basic properties

Originally published at 狗和留美者不得入内. You can comment here or there.

Definition 1.1 The Cartesian product of [公式] is

[公式]

Definition 1.2 A function [公式] defines a relation [公式] such that for all [公式] , the set [公式] is a singleton set. For a function [公式] , we say that [公式] iff [公式] . By definition, for each [公式] , there is exactly one value in [公式] , namely [公式] , which satisfies this [公式] relation, which is of course equivalent to [公式] .

We can, for example, define projection functions

[公式] Definition 1.3 For any function [公式], [公式] we define the preimage to be[公式] .

Definition 1.4 A function [公式] is injective or one-to-one iff for any [公式] , [公式] is the empty set or a singleton set. It is surjective or onto iff for any [公式] , [公式] . It is bijective iff it is both injective and surjective.

Definition 1.5 Let the set of functions from [公式] be denoted by [公式] . We define the function composition operator

[公式] via the map

[公式] such that

[公式] We will leave it to the reader to verify that this is well-defined or uniquely defined.

Proposition 1.6 The [公式] operator is associative. Formally, if [公式] , then

[公式] Proof: It suffices to show that for any [公式] ,

[公式] The LHS of the above is by definition of the function composition operator

[公式] As for the RHS,

[公式]

Equality of the two completes our proof. [公式]

Take singleton set [公式], some set [公式] , and a function [公式] . We require that [公式] is injective and that [公式] . Moreover, we define

[公式] Definition 1.7 A magma is a set [公式] matched with an operation, [公式] , which sends any two elements [公式] to another element [公式] . The codomain of [公式] defines its closure property. If the [公式] operation is associative, then its associated magma is a semigroup.

Proposition 1.8 Assuming that [公式] and that [公式] is associative, let [公式] denote the intersection of all magmas on [公式] containing [公式] , which we call the magma generated by [公式] . Then, [公式] is a semigroup on [公式].

Proof: [公式] is associative by hypothesis, and by Proposition 1.6, [公式] is associative. Thus, both the general and specific magmas given above are semigroups. The [公式] operator applied to two elements of [公式] necessarily yields an element of [公式] , which also contains [公式] . [公式]

Axiom 1.9 (Induction axiom of singly generated magmas) An element of [公式] that is not [公式] must be equal to [公式] for some [公式] . Morever, the process of replacing the arguments of any finite [公式] expression that are not [公式]per this cannot continue indefinitely.

If [公式] and [公式] implies [公式] , then for all [公式] , [公式] . Since the two hypotheses are trivially true, we indeed that have that every element of [公式] commutes with the generator [公式] . More generally, take any class of propositions which take in an arbitrary element of [公式] as its sole parameter. Formally, we have a function [公式] from [公式] to the universe of propositions. We let [公式] denote the universe of true propositions. The induction axiom states that if [公式] and [公式] , then [公式] .

Corollary 1.10 [公式] is a semigroup on some subset of [公式] (here, implicitly, [公式] ).

Proof: We simply apply Proposition 1.8 to show that it is a semigroup. Now we show that the set of the semigroup is necessarily subset of [公式] . If by contradiction [公式] contains an element outside [公式] , then by Axiom 1.9, either [公式] , or function composition of elements of [公式] escapes [公式] , which is clearly false. [公式]

We define function

[公式] and require [公式] to be defined such that [公式] is bijective. In other words, every different or new element of [公式] corresponds to another element of the set [公式] , the elements of which are per this bijection defined via [公式] . Moreover, the [公式] operation in the domain of [公式] becomes what we will denote with [公式] in [公式] . We will also define [公式] . This is an example of an isomorphism between two semigroups.

Theorem 1.11 [公式] is commutative, or equivalently, [公式] is commutative on [公式] . [公式] is also associative on [公式] .

Take two arbitrary elements [公式] . Axiom 1.9 tells that in the expression [公式] we can express [公式] in terms of [公式] , using only the [公式] operator. Once this is done, associativity of [公式] and commutativity with respect to [公式] tells us that we can swap [公式] with the [公式] to its right, maintaining equality, until there are no more elements to the right of [公式] . This yields [公式] .

The associativity of [公式] on [公式] follows directly from the associativity of [公式] (Proposition 1.6). [公式]

Definition 1.12 A semigroup [公式] which contains an element [公式] such that [公式] for all [公式] is a monoid. This element [公式] is the identity element.

Based on this, we can adjoin to [公式] the element [公式] such that for all [公式] , [公式] , which also ensures that adjoining [公式] does not introduce any new elements other than itself. The set [公式] is the set of the whole numbers.

Proposition 1.13 The identity element of a monoid is unique.

Proof: Suppose otherwise that there two identity elements [公式] . By the definition of identity element, [公式] . [公式]

No element [公式] except [公式] has any associated element [公式] such that [公式] . We introduce them. The resulting set is [公式] , the integers.

This [公式] unary operator has two properties, namely [公式] and [公式] . Based on this rule, we have extended [公式] to all of [公式] .

Proposition 1.14 The [公式] operator in [公式] is commutative and associative.

Proof: For associativity, we let [公式] correspond to [公式] , notice that by Axiom 1.9, adjoining this would generate all the elements corresponding to [公式] in our isomorphic space of functions, in which we can use Proposition 1.6 to demonstrate associativity.

For commutativity, we notice that any finite expression containing only [公式] can be expressed in terms of [公式] , wherein if both [公式] are contained, the two must be adjacent somewhere, in which case the two together equate to the identity function [公式] . Thus every element aside from [公式] is generated either by [公式] or [公式] , per the [公式] operator.

Now let [公式] be two arbitrary elements. If both are generated by the same element, Theorem 1.11 shows commutativity. If WLOG, [公式] is generated by [公式] and [公式] by [公式] , then in [公式] , we swap any [公式] in its expression that has to its left [公式] until this cannot be done anymore. This process keeps constant the number of occurrences of both [公式] and [公式] . Thus, the result upon termination is equal to [公式] . [公式]

Proposition 1.15 For any [公式] , [公式] .

Proof: Commutativity and associativity gives us

[公式] [公式]

[公式] , with endowment of inverse element, is an example of a group.

We now define the multiplication operator [公式] on [公式] such that [公式] is its identity, or formally, [公式] for all [公式] . In addition we stipulate that for all [公式] , [公式] and also that [公式] . One can easily check that this defines multiplication over all of [公式] .

Theorem 1.16 (Commutative and distributive properties) For all [公式] , [公式] . For all [公式] , [公式]

Proof: Take arbitrary [公式] and use Axiom 1.9 (induction) on the properties given above which define multiplication over all of [公式] . [公式]

Corrollary 1.17 Left distributive implies right distributive and vice versa.

Proof: Use Theorem 1.16 on the left distributive property to derive the other. [公式]

Proposition 1.18 For all [公式] , [公式] .

Proof: By the distributive property,

[公式] Proposition 1.13 then shows that [公式] . [公式]

For [公式] , we now define the less than relation [公式]. If [公式], it holds iff [公式] can be generated by [公式] . If [公式] , [公式] iff

[Error: Irreparable invalid markup ('<img [...] https://www.zhihu.com/equation?tex>') in entry. Owner must fix manually. Raw contents below.]

<p><small>Originally published at <a href="https://gmachine1729.wpcomstaging.com/2021/04/20/rigorous-construction-and-definition-of-the-integers-and-proof-of-their-basic-properties/">狗和留美者不得入内</a>. You can comment here or <a href="https://gmachine1729.wpcomstaging.com/2021/04/20/rigorous-construction-and-definition-of-the-integers-and-proof-of-their-basic-properties/#comments">there</a>.</small></p><div class="RichText ztext Post-RichText"> <p><b>Definition 1.1</b> The <i>Cartesian product</i> of <img src="https://www.zhihu.com/equation?tex=X%2CY" alt="[公式]" eeimg="1" data-formula="X,Y"> is</p> <p><img src="https://www.zhihu.com/equation?tex=X+%5Ctimes+Y+%3D+%5C%7B%28x%2Cy%29+%3A+x+%5Cin+X%2C+y+%5Cin+Y%5C%7D.%5C%5C" alt="[公式]" eeimg="1" data-formula="X \times Y = \{(x,y) : x \in X, y \in Y\}.\\"> </p> <p><b>Definition 1.2</b> A <i>function</i> <img src="https://www.zhihu.com/equation?tex=f+%3A+X+%5Cto+Y" alt="[公式]" eeimg="1" data-formula="f : X \to Y"> defines a <i>relation</i> <img src="https://www.zhihu.com/equation?tex=R+%5Csubset+X+%5Ctimes+Y" alt="[公式]" eeimg="1" data-formula="R \subset X \times Y"> such that for all <img src="https://www.zhihu.com/equation?tex=z+%5Cin+X" alt="[公式]" eeimg="1" data-formula="z \in X"> , the set <img src="https://www.zhihu.com/equation?tex=%5C%7B%28x%2Cy%29+%5Cin+R+%3A+x+%3D+z%5C%7D" alt="[公式]" eeimg="1" data-formula="\{(x,y) \in R : x = z\}"> is a singleton set. For a function <img src="https://www.zhihu.com/equation?tex=f" alt="[公式]" eeimg="1" data-formula="f"> , we say that <img src="https://www.zhihu.com/equation?tex=z+%5Cmapsto+f%28z%29" alt="[公式]" eeimg="1" data-formula="z \mapsto f(z)"> iff <img src="https://www.zhihu.com/equation?tex=%5C%7B%28x%2Cf%28x%29%29+%5Cin+R+%3A+x+%3D+z%5C%7D+%3D+%5C%7B%28z%2C+f%28z%29%5C%7D" alt="[公式]" eeimg="1" data-formula="\{(x,f(x)) \in R : x = z\} = \{(z, f(z)\}"> . By definition, for each <img src="https://www.zhihu.com/equation?tex=z+%5Cin+X" alt="[公式]" eeimg="1" data-formula="z \in X"> , there is exactly one value in <img src="https://www.zhihu.com/equation?tex=Y" alt="[公式]" eeimg="1" data-formula="Y"> , namely <img src="https://www.zhihu.com/equation?tex=f%28z%29" alt="[公式]" eeimg="1" data-formula="f(z)"> , which satisfies this <img src="https://www.zhihu.com/equation?tex=%5Cmapsto" alt="[公式]" eeimg="1" data-formula="\mapsto"> relation, which is of course equivalent to <img src="https://www.zhihu.com/equation?tex=R" alt="[公式]" eeimg="1" data-formula="R"> .</p> <p>We can, for example, define projection functions</p> <p><img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bproj%7D_1+%3A+%28X%2CY%29+%5Cto+X%2C%5C%5C+%28x%2Cy%29+%5Cmapsto+x%2C%5C%5C+%5Cmathrm%7Bproj%7D_2+%3A+%28X%2CY%29+%5Cto+Y%2C%5C%5C+%28x%2Cy%29+%5Cmapsto+y.%5C%5C" alt="[公式]" eeimg="1" data-formula="\mathrm{proj}_1 : (X,Y) \to X,\\ (x,y) \mapsto x,\\ \mathrm{proj}_2 : (X,Y) \to Y,\\ (x,y) \mapsto y.\\"> <b>Definition 1.3</b> For any function <img src="https://www.zhihu.com/equation?tex=f+%3A+X+%5Cto+Y" alt="[公式]" eeimg="1" data-formula="f : X \to Y">, <img src="https://www.zhihu.com/equation?tex=V+%5Csubset+Y" alt="[公式]" eeimg="1" data-formula="V \subset Y"> we define the <i>preimage</i> to be<img src="https://www.zhihu.com/equation?tex=f%5E%7B-1%7D%28V%29+%3D+%5C%7B+x+%5Cin+X+%3A+f%28x%29+%5Cin+V%5C%7D" alt="[公式]" eeimg="1" data-formula="f^{-1}(V) = \{ x \in X : f(x) \in V\}"> .</p> <p><b>Definition 1.4 </b>A function <img src="https://www.zhihu.com/equation?tex=f+%3A+X+%5Cto+Y" alt="[公式]" eeimg="1" data-formula="f : X \to Y"> is <i>injective</i> or <i>one-to-one</i> iff for any <img src="https://www.zhihu.com/equation?tex=y+%5Cin+Y" alt="[公式]" eeimg="1" data-formula="y \in Y"> , <img src="https://www.zhihu.com/equation?tex=f%5E%7B-1%7D%28%5C%7By%5C%7D%29" alt="[公式]" eeimg="1" data-formula="f^{-1}(\{y\})"> is the empty set or a singleton set. It is <i>surjective</i> or <i>onto</i> iff for any <img src="https://www.zhihu.com/equation?tex=y+%5Cin+Y" alt="[公式]" eeimg="1" data-formula="y \in Y"> , <img src="https://www.zhihu.com/equation?tex=f%5E%7B-1%7D%28%5C%7By%5C%7D%29+%5Cneq+%5Cemptyset" alt="[公式]" eeimg="1" data-formula="f^{-1}(\{y\}) \neq \emptyset"> . It is <i>bijective </i>iff it is both injective and surjective.</p> <p><b>Definition 1.5</b> Let the set of functions from <img src="https://www.zhihu.com/equation?tex=X+%5Cto+Y" alt="[公式]" eeimg="1" data-formula="X \to Y"> be denoted by <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28X%2CY%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(X,Y)"> . We define the function composition operator</p> <p><img src="https://www.zhihu.com/equation?tex=%5Ccirc+%3A+%5Cmathcal%7BF%7D%28Y%2CZ%29+%5Ctimes+%5Cmathcal%7BF%7D%28X%2CY%29+%5Cto+%5Cmathcal%7BF%7D%28X%2CZ%29%2C%5C%5C" alt="[公式]" eeimg="1" data-formula="\circ : \mathcal{F}(Y,Z) \times \mathcal{F}(X,Y) \to \mathcal{F}(X,Z),\\"> via the map</p> <p><img src="https://www.zhihu.com/equation?tex=%28f%2C+g%29+%5Cmapsto+f+%5Ccirc+g%5C%5C" alt="[公式]" eeimg="1" data-formula="(f, g) \mapsto f \circ g\\"> such that</p> <p><img src="https://www.zhihu.com/equation?tex=%28f+%5Ccirc+g%29%28x%29+%3D+f%28g%28x%29%29.%5C%5C" alt="[公式]" eeimg="1" data-formula="(f \circ g)(x) = f(g(x)).\\"> We will leave it to the reader to verify that this is well-defined or uniquely defined.</p> <p><b>Proposition 1.6 </b>The <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> operator is associative. Formally, if <img src="https://www.zhihu.com/equation?tex=f+%5Cin+%5Cmathcal%7BF%7D%28Z%2CW%29%2C+g+%5Cin+%5Cmathcal%7BF%7D%28Y%2C+Z%29%2Ch+%5Cin+%5Cmathcal%7BF%7D%28X%2CY%29" alt="[公式]" eeimg="1" data-formula="f \in \mathcal{F}(Z,W), g \in \mathcal{F}(Y, Z),h \in \mathcal{F}(X,Y)"> , then</p> <p><img src="https://www.zhihu.com/equation?tex=f+%5Ccirc+%28g+%5Ccirc+h%29+%3D+%28f+%5Ccirc+g%29+%5Ccirc+h.%5C%5C" alt="[公式]" eeimg="1" data-formula="f \circ (g \circ h) = (f \circ g) \circ h.\\"> <i>Proof</i>: It suffices to show that for any <img src="https://www.zhihu.com/equation?tex=x+%5Cin+X" alt="[公式]" eeimg="1" data-formula="x \in X"> ,</p> <p><img src="https://www.zhihu.com/equation?tex=%5Bf+%5Ccirc+%28g+%5Ccirc+h%29%5D%28x%29+%3D+%5B%28f+%5Ccirc+g%29+%5Ccirc+h%5D%28x%29.%5C%5C+" alt="[公式]" eeimg="1" data-formula="[f \circ (g \circ h)](x) = [(f \circ g) \circ h](x).\\ "> The LHS of the above is by definition of the function composition operator</p> <p><img src="https://www.zhihu.com/equation?tex=%5Cbegin%7Beqnarray%7D+%5Bf+%5Ccirc+%28g+%5Ccirc+h%29%5D%28x%29+%26%3D%26+f%28%28g%5Ccirc+h%29%28x%29%29%2C%5C%5C+%26%3D%26+f%28g%28h%28x%29%29.+%5Cend%7Beqnarray%7D%5C%5C" alt="[公式]" eeimg="1" data-formula="\begin{eqnarray} [f \circ (g \circ h)](x) &amp;=&amp; f((g\circ h)(x)),\\ &amp;=&amp; f(g(h(x)). \end{eqnarray}\\"> As for the RHS,</p> <p><img src="https://www.zhihu.com/equation?tex=%5Cbegin%7Beqnarray%7D+%5B%28f+%5Ccirc+g%29+%5Ccirc+h%5D%28x%29+%26%3D%26+%28f%5Ccirc+g%29%28h%28x%29%29%2C%5C%5C+%26%3D%26+f%28g%28h%28x%29%29.+%5Cend%7Beqnarray%7D%5C%5C" alt="[公式]" eeimg="1" data-formula="\begin{eqnarray} [(f \circ g) \circ h](x) &amp;=&amp; (f\circ g)(h(x)),\\ &amp;=&amp; f(g(h(x)). \end{eqnarray}\\"> </p> <p>Equality of the two completes our proof. <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p>Take singleton set <img src="https://www.zhihu.com/equation?tex=%5C%7B0%5C%7D" alt="[公式]" eeimg="1" data-formula="\{0\}">, some set <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> , and a function <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%3A+%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D+%5Cto+%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}: \{0\} \cup \mathbb{N} \to \{0\} \cup \mathbb{N}"> . We require that <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> is injective and that <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29+%3D+%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}(\{0\} \cup \mathbb{N}) = \mathbb{N}"> . Moreover, we define </p> <p><img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D_%7B%7C%5C%7B0%5C%7D%7D+%3A+%5C%7B0%5C%7D+%5Cto+%5Cmathbb%7BN%7D%2C%5C%5C+%5Cmathrm%7Bsuc%7D_%7B%7C%5C%7B0%5C%7D%7C%7D%280%29+%3D+%5Cmathrm%7Bsuc%7D%280%29.%5C%5C" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}_{|\{0\}} : \{0\} \to \mathbb{N},\\ \mathrm{suc}_{|\{0\}|}(0) = \mathrm{suc}(0).\\"> <b>Definition 1.7</b> A <i>magma </i> is a set <img src="https://www.zhihu.com/equation?tex=M" alt="[公式]" eeimg="1" data-formula="M"> matched with an operation, <img src="https://www.zhihu.com/equation?tex=%2A+%3A+M+%5Ctimes+M+%5Cto+M" alt="[公式]" eeimg="1" data-formula="* : M \times M \to M"> , which sends any two elements <img src="https://www.zhihu.com/equation?tex=a%2C+b+%5Cin+M" alt="[公式]" eeimg="1" data-formula="a, b \in M"> to another element <img src="https://www.zhihu.com/equation?tex=a+%2A+b" alt="[公式]" eeimg="1" data-formula="a * b"> . The codomain of <img src="https://www.zhihu.com/equation?tex=%2A" alt="[公式]" eeimg="1" data-formula="*"> defines its closure property. If the <img src="https://www.zhihu.com/equation?tex=%2A" alt="[公式]" eeimg="1" data-formula="*"> operation is associative, then its associated magma is a <i>semigroup</i>.</p> <p><b>Proposition 1.8</b> Assuming that <img src="https://www.zhihu.com/equation?tex=m_1+%5Cin+M" alt="[公式]" eeimg="1" data-formula="m_1 \in M"> and that <img src="https://www.zhihu.com/equation?tex=%2A%3A+M+%5Ctimes+M+%5Cto+M" alt="[公式]" eeimg="1" data-formula="*: M \times M \to M"> is associative, let <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7Bm_1%5C%7D%2C+%2A%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{m_1\}, *)"> denote the intersection of all magmas on <img src="https://www.zhihu.com/equation?tex=M" alt="[公式]" eeimg="1" data-formula="M"> containing <img src="https://www.zhihu.com/equation?tex=m" alt="[公式]" eeimg="1" data-formula="m"> , which we call the magma generated by <img src="https://www.zhihu.com/equation?tex=%28%5C%7Bm_1%5C%7D%2C+%2A%29" alt="[公式]" eeimg="1" data-formula="(\{m_1\}, *)"> . Then, <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7Bm_1%5C%7D%2C+%2A%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{m_1\}, *)"> is a semigroup on <img src="https://www.zhihu.com/equation?tex=M" alt="[公式]" eeimg="1" data-formula="M">.</p> <p><i>Proof</i>: <img src="https://www.zhihu.com/equation?tex=%2A" alt="[公式]" eeimg="1" data-formula="*"> is associative by hypothesis, and by Proposition 1.6, <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> is associative. Thus, both the general and specific magmas given above are semigroups. The <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> operator applied to two elements of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> necessarily yields an element of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> , which also contains <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> . <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p><b>Axiom 1.9 (Induction axiom of singly generated magmas)</b> An element of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7Bm_1%5C%7D%2C+%2A%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{m_1\}, *)"> that is not <img src="https://www.zhihu.com/equation?tex=m_1" alt="[公式]" eeimg="1" data-formula="m_1"> must be equal to <img src="https://www.zhihu.com/equation?tex=n+%5Ccirc+m_1" alt="[公式]" eeimg="1" data-formula="n \circ m_1"> for some <img src="https://www.zhihu.com/equation?tex=n+%5Cin+%5Cmathcal%7BM%7D%28%5C%7Bm_1%5C%7D%2C+%2A%29" alt="[公式]" eeimg="1" data-formula="n \in \mathcal{M}(\{m_1\}, *)"> . Morever, the process of replacing the arguments of any finite <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> expression that are not <img src="https://www.zhihu.com/equation?tex=m_1" alt="[公式]" eeimg="1" data-formula="m_1">per this cannot continue indefinitely.</p> <p>If <img src="https://www.zhihu.com/equation?tex=m_1+%5Ccirc+m_1+%3D+m_1+%5Ccirc+m_1" alt="[公式]" eeimg="1" data-formula="m_1 \circ m_1 = m_1 \circ m_1"> and <img src="https://www.zhihu.com/equation?tex=n+%5Ccirc+m_1+%3D+m_1+%5Ccirc+n" alt="[公式]" eeimg="1" data-formula="n \circ m_1 = m_1 \circ n"> implies <img src="https://www.zhihu.com/equation?tex=n+%5Ccirc+%28m_1+%5Ccirc+n%29+%3D+%28m_1+%5Ccirc+n%29+%5Ccirc+n" alt="[公式]" eeimg="1" data-formula="n \circ (m_1 \circ n) = (m_1 \circ n) \circ n"> , then for all <img src="https://www.zhihu.com/equation?tex=m+%5Cin+%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bm_1%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="m \in \mathcal{M}(\{\mathrm{m_1}\}, \circ)"> , <img src="https://www.zhihu.com/equation?tex=m+%5Ccirc+m_1+%3D+m_1+%5Ccirc+m" alt="[公式]" eeimg="1" data-formula="m \circ m_1 = m_1 \circ m"> . Since the two hypotheses are trivially true, we indeed that have that every element of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bm_1%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{m_1}\}, \circ)"> commutes with the generator <img src="https://www.zhihu.com/equation?tex=m_1" alt="[公式]" eeimg="1" data-formula="m_1"> . More generally, take any class of propositions which take in an arbitrary element of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bm_1%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{m_1}\}, \circ)"> as its sole parameter. Formally, we have a function <img src="https://www.zhihu.com/equation?tex=p" alt="[公式]" eeimg="1" data-formula="p"> from <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bm_1%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{m_1}\}, \circ)"> to the universe of propositions. We let <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BT%7D" alt="[公式]" eeimg="1" data-formula="\mathcal{T}"> denote the universe of true propositions. The induction axiom states that if <img src="https://www.zhihu.com/equation?tex=p%28m_1%29+%5Cin+%5Cmathcal%7BT%7D" alt="[公式]" eeimg="1" data-formula="p(m_1) \in \mathcal{T}"> and <img src="https://www.zhihu.com/equation?tex=%5Cforall+m+%5Cin+%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bm_1%7D%5C%7D%2C+%5Ccirc%29%2C+p%28m%29+%5Cin+%5Cmathcal%7BT%7D+%5Cimplies+p%28m%5Ccirc+m_1%29+%5Cin+%5Cmathcal%7BT%7D" alt="[公式]" eeimg="1" data-formula="\forall m \in \mathcal{M}(\{\mathrm{m_1}\}, \circ), p(m) \in \mathcal{T} \implies p(m\circ m_1) \in \mathcal{T}"> , then <img src="https://www.zhihu.com/equation?tex=%5Cforall+m+%5Cin+%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bm_1%7D%5C%7D%2C+%5Ccirc%29%2C+p%28m%29+%5Cin+%5Cmathcal%7BT%7D" alt="[公式]" eeimg="1" data-formula="\forall m \in \mathcal{M}(\{\mathrm{m_1}\}, \circ), p(m) \in \mathcal{T}"> .</p> <p><b>Corollary 1.10 </b><img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5Cmathrm%7Bsuc%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\mathrm{suc}, \circ)"> is a semigroup on some subset of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> (here, implicitly, <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28X%29+%5Cequiv+%5Cmathcal%7BF%7D%28X%2CX%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(X) \equiv \mathcal{F}(X,X)"> ).</p> <p><i>Proof</i>: We simply apply Proposition 1.8 to show that it is a semigroup. Now we show that the set of the semigroup is necessarily subset of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> . If by contradiction <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bsuc%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{suc}\}, \circ)"> contains an element outside <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> , then by Axiom 1.9, either <img src="https://www.zhihu.com/equation?tex=m+%5Cnotin+%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="m \notin \mathcal{F}(\{0\} \cup \mathbb{N})"> , or function composition of elements of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> escapes <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BF%7D%28%5C%7B0%5C%7D+%5Ccup+%5Cmathbb%7BN%7D%29" alt="[公式]" eeimg="1" data-formula="\mathcal{F}(\{0\} \cup \mathbb{N})"> , which is clearly false. <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"></p> <p>We define function</p> <p><img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7BtoNatural%7D%3A+%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bsuc%7D%5C%7D%2C+%5Ccirc%29+%5Cto+%5Cmathbb%7BN%7D%2C%5C%5C+m_1+%5Cmapsto+m_1%280%29%2C%5C%5C" alt="[公式]" eeimg="1" data-formula="\mathrm{toNatural}: \mathcal{M}(\{\mathrm{suc}\}, \circ) \to \mathbb{N},\\ m_1 \mapsto m_1(0),\\"> and require <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> to be defined such that <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7BtoNatural%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{toNatural}"> is bijective. In other words, every different or new element of <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bsuc%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{suc}\}, \circ)"> corresponds to another element of the set <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> , the elements of which are per this bijection defined via <img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7Bsuc%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{suc}\}, \circ)"> . Moreover, the <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> operation in the domain of <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7BtoNatural%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{toNatural}"> becomes what we will denote with <img src="https://www.zhihu.com/equation?tex=%2B" alt="[公式]" eeimg="1" data-formula="+"> in <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> . We will also define <img src="https://www.zhihu.com/equation?tex=1+%5Cequiv+%5Cmathrm%7BtoNatural%7D%28%5Cmathrm%7Bsuc%7D%29" alt="[公式]" eeimg="1" data-formula="1 \equiv \mathrm{toNatural}(\mathrm{suc})"> . This is an example of an <i>isomorphism</i> between two semigroups.</p> <p><b>Theorem 1.11 </b><img src="https://www.zhihu.com/equation?tex=%5Cmathcal%7BM%7D%28%5C%7B%5Cmathrm%7B%5Cmathrm%7Bsuc%7D%7D%5C%7D%2C+%5Ccirc%29" alt="[公式]" eeimg="1" data-formula="\mathcal{M}(\{\mathrm{\mathrm{suc}}\}, \circ)"> is commutative, or equivalently, <img src="https://www.zhihu.com/equation?tex=%2B" alt="[公式]" eeimg="1" data-formula="+"> is commutative on <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> . <img src="https://www.zhihu.com/equation?tex=%2B" alt="[公式]" eeimg="1" data-formula="+"> is also associative on <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> .</p> <p>Take two arbitrary elements <img src="https://www.zhihu.com/equation?tex=m%2C+n" alt="[公式]" eeimg="1" data-formula="m, n"> . Axiom 1.9 tells that in the expression <img src="https://www.zhihu.com/equation?tex=m+%5Ccirc+n" alt="[公式]" eeimg="1" data-formula="m \circ n"> we can express <img src="https://www.zhihu.com/equation?tex=n" alt="[公式]" eeimg="1" data-formula="n"> in terms of <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> , using only the <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> operator. Once this is done, associativity of <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> and commutativity with respect to <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> tells us that we can swap <img src="https://www.zhihu.com/equation?tex=m" alt="[公式]" eeimg="1" data-formula="m"> with the <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> to its right, maintaining equality, until there are no more elements to the right of <img src="https://www.zhihu.com/equation?tex=m" alt="[公式]" eeimg="1" data-formula="m"> . This yields <img src="https://www.zhihu.com/equation?tex=n+%5Ccirc+m" alt="[公式]" eeimg="1" data-formula="n \circ m"> .</p> <p>The associativity of <img src="https://www.zhihu.com/equation?tex=%2B" alt="[公式]" eeimg="1" data-formula="+"> on <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> follows directly from the associativity of <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> (Proposition 1.6). <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p><b>Definition 1.12</b> A semigroup <img src="https://www.zhihu.com/equation?tex=%28S%2C+%2A%29" alt="[公式]" eeimg="1" data-formula="(S, *)"> which contains an element <img src="https://www.zhihu.com/equation?tex=e" alt="[公式]" eeimg="1" data-formula="e"> such that <img src="https://www.zhihu.com/equation?tex=e+%2A+a+%3D+a+%3D+a+%2Ae" alt="[公式]" eeimg="1" data-formula="e * a = a = a *e"> for all <img src="https://www.zhihu.com/equation?tex=a+%5Cin+S" alt="[公式]" eeimg="1" data-formula="a \in S"> is a <i>monoid</i>. This element <img src="https://www.zhihu.com/equation?tex=e" alt="[公式]" eeimg="1" data-formula="e"> is the <i>identity element</i>.</p> <p>Based on this, we can adjoin to <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N}"> the element <img src="https://www.zhihu.com/equation?tex=0" alt="[公式]" eeimg="1" data-formula="0"> such that for all <img src="https://www.zhihu.com/equation?tex=n+%5Cin+%5Cmathbb%7BN%7D" alt="[公式]" eeimg="1" data-formula="n \in \mathbb{N}"> , <img src="https://www.zhihu.com/equation?tex=n%2B0+%3D+n+%3D+0%2Bn" alt="[公式]" eeimg="1" data-formula="n+0 = n = 0+n"> , which also ensures that adjoining <img src="https://www.zhihu.com/equation?tex=0" alt="[公式]" eeimg="1" data-formula="0"> does not introduce any new elements other than itself. The set <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BN%7D+%5Ccup+%5C%7B0%5C%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{N} \cup \{0\}"> is the set of the <i>whole numbers</i>.</p> <p><b>Proposition 1.13</b> The identity element of a monoid is unique.</p> <p><i>Proof</i>: Suppose otherwise that there two identity elements <img src="https://www.zhihu.com/equation?tex=e_1%2C+e_2" alt="[公式]" eeimg="1" data-formula="e_1, e_2"> . By the definition of identity element, <img src="https://www.zhihu.com/equation?tex=e_2+%3D+e_1+%2A+e_2+%3D+e_1" alt="[公式]" eeimg="1" data-formula="e_2 = e_1 * e_2 = e_1"> . <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"></p> <p>No element <img src="https://www.zhihu.com/equation?tex=n+%5Cin+%5Cmathbb%7BN%7D+%5Ccup+%5C%7B0%5C%7D" alt="[公式]" eeimg="1" data-formula="n \in \mathbb{N} \cup \{0\}"> except <img src="https://www.zhihu.com/equation?tex=0" alt="[公式]" eeimg="1" data-formula="0"> has any associated element <img src="https://www.zhihu.com/equation?tex=-n" alt="[公式]" eeimg="1" data-formula="-n"> such that <img src="https://www.zhihu.com/equation?tex=n%2B%28-n%29+%3D+0" alt="[公式]" eeimg="1" data-formula="n+(-n) = 0"> . We introduce them. The resulting set is <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> , the <i>integers</i>.</p> <p>This <img src="https://www.zhihu.com/equation?tex=-" alt="[公式]" eeimg="1" data-formula="-"> unary operator has two properties, namely <img src="https://www.zhihu.com/equation?tex=-0+%3D+0" alt="[公式]" eeimg="1" data-formula="-0 = 0"> and <img src="https://www.zhihu.com/equation?tex=-%28n%2B1%29+%3D+-n+%2B%28-1%29" alt="[公式]" eeimg="1" data-formula="-(n+1) = -n +(-1)"> . Based on this rule, we have extended <img src="https://www.zhihu.com/equation?tex=%2B" alt="[公式]" eeimg="1" data-formula="+"> to all of <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> .</p> <p><b>Proposition 1.14</b> The <img src="https://www.zhihu.com/equation?tex=%2B" alt="[公式]" eeimg="1" data-formula="+"> operator in <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> is commutative and associative.</p> <p><i>Proof</i>: For associativity, we let <img src="https://www.zhihu.com/equation?tex=-1" alt="[公式]" eeimg="1" data-formula="-1"> correspond to <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}^{-1}"> , notice that by Axiom 1.9, adjoining this would generate all the elements corresponding to <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> in our isomorphic space of functions, in which we can use Proposition 1.6 to demonstrate associativity.</p> <p>For commutativity, we notice that any finite expression containing only <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%2C+%5Ccirc%2C+%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}, \circ, ^{-1}"> can be expressed in terms of <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%2C+%5Cmathrm%7Bsuc%7D%5E%7B-1%7D%2C+%5Ccirc" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}, \mathrm{suc}^{-1}, \circ"> , wherein if both <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%2C+%5Cmathrm%7Bsuc%7D%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}, \mathrm{suc}^{-1}"> are contained, the two must be adjacent somewhere, in which case the two together equate to the identity function <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bid%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{id}"> . Thus every element aside from <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bid%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{id}"> is generated either by <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> or <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}^{-1}"> , per the <img src="https://www.zhihu.com/equation?tex=%5Ccirc" alt="[公式]" eeimg="1" data-formula="\circ"> operator.</p> <p>Now let <img src="https://www.zhihu.com/equation?tex=f%2C+g" alt="[公式]" eeimg="1" data-formula="f, g"> be two arbitrary elements. If both are generated by the same element, Theorem 1.11 shows commutativity. If WLOG, <img src="https://www.zhihu.com/equation?tex=f" alt="[公式]" eeimg="1" data-formula="f"> is generated by <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> and <img src="https://www.zhihu.com/equation?tex=g" alt="[公式]" eeimg="1" data-formula="g"> by <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}^{-1}"> , then in <img src="https://www.zhihu.com/equation?tex=f+%5Ccirc+g" alt="[公式]" eeimg="1" data-formula="f \circ g"> , we swap any <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}^{-1}"> in its expression that has to its left <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> until this cannot be done anymore. This process keeps constant the number of occurrences of both <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}"> and <img src="https://www.zhihu.com/equation?tex=%5Cmathrm%7Bsuc%7D%5E%7B-1%7D" alt="[公式]" eeimg="1" data-formula="\mathrm{suc}^{-1}"> . Thus, the result upon termination is equal to <img src="https://www.zhihu.com/equation?tex=g+%5Ccirc+f" alt="[公式]" eeimg="1" data-formula="g \circ f"> . <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p><b>Proposition 1.15 </b>For any <img src="https://www.zhihu.com/equation?tex=m%2Cn+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="m,n \in \mathbb{Z}"> , <img src="https://www.zhihu.com/equation?tex=-%28m%2Bn%29+%3D+%28-m%29%2B%28-n%29" alt="[公式]" eeimg="1" data-formula="-(m+n) = (-m)+(-n)"> .</p> <p><i>Proof</i>: Commutativity and associativity gives us</p> <p><img src="https://www.zhihu.com/equation?tex=%5Cbegin%7Beqnarray%7D+-%28m%2Bn%29+%26%3D%26+-%28m%2Bn%29+%2B%5B%28m%2Bn%29%2B%28-n%29%2B%28-m%29%5D%5C%5C+%26%3D%26%5B-%28m%2Bn%29%2B%28m%2Bn%29%5D+%2B+%28-n%29%2B%28-m%29%5C%5C+%26%3D%26%28-n%29%2B%28-m%29%5C%5C+%26%3D%26%28-m%29%2B%28-n%29.+%5Cend%7Beqnarray%7D%5C%5C" alt="[公式]" eeimg="1" data-formula="\begin{eqnarray} -(m+n) &amp;=&amp; -(m+n) +[(m+n)+(-n)+(-m)]\\ &amp;=&amp;[-(m+n)+(m+n)] + (-n)+(-m)\\ &amp;=&amp;(-n)+(-m)\\ &amp;=&amp;(-m)+(-n). \end{eqnarray}\\"> <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p><img src="https://www.zhihu.com/equation?tex=%28%5Cmathbb%7BZ%7D%2C%2B%29" alt="[公式]" eeimg="1" data-formula="(\mathbb{Z},+)"> , with endowment of inverse element, is an example of a <i>group</i>. </p> <p>We now define the multiplication operator <img src="https://www.zhihu.com/equation?tex=%5Ccdot" alt="[公式]" eeimg="1" data-formula="\cdot"> on <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> such that <img src="https://www.zhihu.com/equation?tex=1" alt="[公式]" eeimg="1" data-formula="1"> is its identity, or formally, <img src="https://www.zhihu.com/equation?tex=a%5Ccdot+1+%3D+a+%3D+1+%5Ccdot+a" alt="[公式]" eeimg="1" data-formula="a\cdot 1 = a = 1 \cdot a"> for all <img src="https://www.zhihu.com/equation?tex=a+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a \in \mathbb{Z}"> . In addition we stipulate that for all <img src="https://www.zhihu.com/equation?tex=a%2C+b+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a, b \in \mathbb{Z}"> , <img src="https://www.zhihu.com/equation?tex=a%5Ccdot+b+%2B+a%5Ccdot+1+%3D+a%5Ccdot+%28b%2B1%29" alt="[公式]" eeimg="1" data-formula="a\cdot b + a\cdot 1 = a\cdot (b+1)"> and also that <img src="https://www.zhihu.com/equation?tex=b+%5Ccdot+a+%2B+1+%5Ccdot+a+%3D+%28b%2B1%29%5Ccdot+a" alt="[公式]" eeimg="1" data-formula="b \cdot a + 1 \cdot a = (b+1)\cdot a"> . One can easily check that this defines multiplication over all of <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> .</p> <p><b>Theorem 1.16 (Commutative and distributive properties)</b> For all <img src="https://www.zhihu.com/equation?tex=a%2C+b%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a, b\in \mathbb{Z}"> , <img src="https://www.zhihu.com/equation?tex=a%5Ccdot+b+%3D+b%5Ccdot+a" alt="[公式]" eeimg="1" data-formula="a\cdot b = b\cdot a"> . For all <img src="https://www.zhihu.com/equation?tex=a%2Cb%2Cc+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a,b,c \in \mathbb{Z}"> , <img src="https://www.zhihu.com/equation?tex=a%5Ccdot%28b%2Bc%29+%3D+a%5Ccdot+b+%2B+a%5Ccdot+c" alt="[公式]" eeimg="1" data-formula="a\cdot(b+c) = a\cdot b + a\cdot c"> </p> <p><i>Proof</i>: Take arbitrary <img src="https://www.zhihu.com/equation?tex=a%2C+b%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a, b\in \mathbb{Z}"> and use Axiom 1.9 (induction) on the properties given above which define multiplication over all of <img src="https://www.zhihu.com/equation?tex=%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="\mathbb{Z}"> . <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p><b>Corrollary 1.17 </b>Left distributive implies right distributive and vice versa.</p> <p><i>Proof</i>: Use Theorem 1.16 on the left distributive property to derive the other. <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"></p> <p><b>Proposition 1.18</b> For all <img src="https://www.zhihu.com/equation?tex=a+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a \in \mathbb{Z}"><b> , </b><img src="https://www.zhihu.com/equation?tex=a+%5Ccdot+0+%3D+0" alt="[公式]" eeimg="1" data-formula="a \cdot 0 = 0"> .</p> <p><i>Proof</i>: By the distributive property,</p> <p><img src="https://www.zhihu.com/equation?tex=a%2B0+%3D+a+%3D+a+%5Ccdot+1+%3D+a%5Ccdot%281%2B0%29+%3D+a%5Ccdot+1+%2B+a+%5Ccdot+0+%3D+a+%2B+a+%5Ccdot+0.%5C%5C" alt="[公式]" eeimg="1" data-formula="a+0 = a = a \cdot 1 = a\cdot(1+0) = a\cdot 1 + a \cdot 0 = a + a \cdot 0.\\"> Proposition 1.13 then shows that <img src="https://www.zhihu.com/equation?tex=0+%3D+a+%5Ccdot+0" alt="[公式]" eeimg="1" data-formula="0 = a \cdot 0"> . <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p>For <img src="https://www.zhihu.com/equation?tex=a%2C+b+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a, b \in \mathbb{Z}"> , we now define the less than relation <img src="https://www.zhihu.com/equation?tex=a+%3C+b" alt="[公式]" eeimg="1" data-formula="a < b">. If <img src="https://www.zhihu.com/equation?tex=a+%3D+0" alt="[公式]" eeimg="1" data-formula="a = 0">, it holds iff <img src="https://www.zhihu.com/equation?tex=b" alt="[公式]" eeimg="1" data-formula="b"> can be generated by <img src="https://www.zhihu.com/equation?tex=%281%2C%2B%29" alt="[公式]" eeimg="1" data-formula="(1,+)"> . If <img src="https://www.zhihu.com/equation?tex=a+%5Cneq+0" alt="[公式]" eeimg="1" data-formula="a \neq 0"> , <img src="https://www.zhihu.com/equation?tex=a+%3C+b" alt="[公式]" eeimg="1" data-formula="a < b"> iff <img src="https://www.zhihu.com/equation?tex=%28-a%29%2Bb+%3E+0" alt="[公式]" eeimg="1" data-formula="(-a)+b > 0&#8243;> , where <img src="https://www.zhihu.com/equation?tex=%3E" alt="[公式]" eeimg="1" data-formula=">&#8220;> , the greater than relations, signifies that neither <img src="https://www.zhihu.com/equation?tex=%3C" alt="[公式]" eeimg="1" data-formula="<"> nor <img src="https://www.zhihu.com/equation?tex=%3D" alt="[公式]" eeimg="1" data-formula="="> holds. <img src="https://www.zhihu.com/equation?tex=%5Cleq%2C+%5Cgeq" alt="[公式]" eeimg="1" data-formula="\leq, \geq"> denote less than or equal to and greater than or equal to respectively.</p> <p><b>Proposition 1.18 (Associativity of multiplication) </b>For all <img src="https://www.zhihu.com/equation?tex=a%2Cb%2Cc+%5Cin+%5Cmathbb%7BZ%7D" alt="[公式]" eeimg="1" data-formula="a,b,c \in \mathbb{Z}"> , <img src="https://www.zhihu.com/equation?tex=%28a%5Ccdot+b%29%5Ccdot+c+%3D+a+%5Ccdot+%28b%5Ccdot+c%29" alt="[公式]" eeimg="1" data-formula="(a\cdot b)\cdot c = a \cdot (b\cdot c)"> .</p> <p><i>Proof</i>: If <img src="https://www.zhihu.com/equation?tex=c+%3D+0" alt="[公式]" eeimg="1" data-formula="c = 0"> , associativity equates to <img src="https://www.zhihu.com/equation?tex=0+%3D+0" alt="[公式]" eeimg="1" data-formula="0 = 0"> , by Proposition 1.18. Now assume WLOG that <img src="https://www.zhihu.com/equation?tex=c+%3E+0" alt="[公式]" eeimg="1" data-formula="c > 0&#8243;> . For <img src="https://www.zhihu.com/equation?tex=c+%3D+1" alt="[公式]" eeimg="1" data-formula="c = 1"> , the definition of multiplicative identity gives that associativity equates to <img src="https://www.zhihu.com/equation?tex=a+%5Ccdot+b+%3D+a%5Ccdot+b" alt="[公式]" eeimg="1" data-formula="a \cdot b = a\cdot b"> . Assume associativity for fixed <img src="https://www.zhihu.com/equation?tex=c" alt="[公式]" eeimg="1" data-formula="c"> . Then,</p> <p><img src="https://www.zhihu.com/equation?tex=%5Cbegin%7Beqnarray%7D+%28a%5Ccdot+b%29%5Ccdot+%28c%2B1%29+%26%3D%26+a%5Ccdot+b+%5Ccdot+c+%2B+a%5Ccdot+b+%5Ccdot+1%5C%5C+%26%3D%26a%5Ccdot+%28b%5Ccdot+c%29%2B+a+%5Ccdot+%28b%5Ccdot+1%29%5C%5C+%26%3D%26+a%5Ccdot+%28b%5Ccdot+c+%2B+b%5Ccdot+1%29%5C%5C+%26%3D%26+a%5Ccdot+%28b%5Ccdot+%28c%2B1%29%29.+%5Cend%7Beqnarray%7D%5C%5C" alt="[公式]" eeimg="1" data-formula="\begin{eqnarray} (a\cdot b)\cdot (c+1) &amp;=&amp; a\cdot b \cdot c + a\cdot b \cdot 1\\ &amp;=&amp;a\cdot (b\cdot c)+ a \cdot (b\cdot 1)\\ &amp;=&amp; a\cdot (b\cdot c + b\cdot 1)\\ &amp;=&amp; a\cdot (b\cdot (c+1)). \end{eqnarray}\\"> </p> <p>Axiom 1.9 (induction) completes our proof. <img src="https://www.zhihu.com/equation?tex=%5Csquare" alt="[公式]" eeimg="1" data-formula="\square"> </p> <p>We have by now shown that <img src="https://www.zhihu.com/equation?tex=%28%5Cmathbb%7BZ%7D%2C%2B%2C%2A%29" alt="[公式]" eeimg="1" data-formula="(\mathbb{Z},+,*)"> is a <i>commutative ring</i>. Adjoining multiplicative inverses to all non-zero elements yields the <i>rational numbers</i>. A <i>field</i> is a commutative ring where <img src="https://www.zhihu.com/equation?tex=0+%5Cneq+1" alt="[公式]" eeimg="1" data-formula="0 \neq 1"> and all non-zero elements are invertible. That the <i>rational numbers</i>, in addition to being multiplicably invertible maintains all the commutative ring properties is rather trivial to prove. We leave this to the reader.</p> <hr> <h3>什么促使了我详细透彻地证明并写出如此显然的数字的定义和属性的证明,以及相关的想法</h3> <ul> <li>我最近一年基本没学或做任何纯数学,科学而言学的<a href="https://zhuanlan.zhihu.com/p/352414927" class="internal" rel="noreferrer">基本都是物理</a>,并且学的过程中有意地不少以数学的思维思考,注重物理现象和直觉,数学当做工具而已。</li> <li>我高中和大学的时候基本完全没有物理直觉或物理思维,对物理现象和实验的感觉或兴趣是偏低的。不过,当时的我纯数学的也不怎么样,虽然能解一些非常局部的问题,尤其竞赛题,但完全没有构建数学理论的能力。那时候的我写作能力偏差,不善于积累或整理信息,与现在截然不同。我对非常严谨的形式化的数学的掌握也比较不行,若大学的我看了我在该文写出的内容,会看了觉得 trivial,但若那时候教我自己写,我应该还会觉得蛮吃力的,主动提出大致的想法或规划并执行的能力就更不用谈了。可以说大学时的我学术上,智力上是很不程度,非常缺乏深度的。</li> <li>我把爱因斯坦标记搞熟练后,也基本<a href="https://zhuanlan.zhihu.com/p/363187198" class="internal" rel="noreferrer">完全弄清了 covariant derivative, metric tensor, Christoffel symbols 那套了</a>。但是广义相对论没啥用,我这个人根据学纯数和理论物理的标准还是讲究实用性的。然后我想到试试概率论,以了解些 stochastic calculus 和二战时创造了 Ito calculus 的伊藤清为长远目标。概率这种东西,若论做些计算,我感觉自己是几乎没学然后自然就会了,高中时概率密度函数的那套对我很简单。不过如果引入一套测度论和形式化,大学的时候是几乎超越了我的智力和数学成熟的范围。遗憾的是我再次学习测度论,试图自己证明其中的一些引理却明显失败了,而且感觉自己的分析或许都不如三年前的时候了。可能学物理的过程对我的思维和品味有了些影响吧。</li> <li>我当然晓得分析是很注重细节和技巧尤其与不等式相关的,也认识到这种技巧能力,处于其最顶端的包括 Terence Tao,是很重数学智商 (M) 的。我知道我的 M 大概率是永远没法跟那些真正顶端的人比。我也觉得现在与大学时不同,我的脑子是语言智商 (V) 更高的。抽象代数显然是更重 V 的,他的细节没那么复杂,对具体的不等式的估计的能力要求相对较低,但对抽象和非量化结构的关系的洞察显然更高。有意思的是我看到了有人写他看到一帮搞数学的人有一次一起吃花生酱,然后其中选了 crunchy 的基本都是搞代数或逻辑的,这个也比喻代数的结构是比较离散比较明确的。</li> <li>如果我没有分析的头脑,那不说明我的代数天分不行。我想到试试把 Galois 理论在少参考其它文献的情况下基本独立推导出来。稍微想了想 fixed field, minimal polynomial, primitive element 那套,主观觉得实现了一种前所未有的感觉。然后可能因为 Galois 理论一般的基域都是有理数,我也想到了有理数的构建。有理数当然也得从自然数和整数来构建。我当然也想到了用于定义实数的 Dedekind cut,再次想了想觉得用 Cauchy 序列的同等类构建实数挺妙的,显然也是自然的做法。这么思考显然也是偏代数偏 V 的思维。Dedekind 据我所知实变的工作之外最好的工作也是抽代的,比如我知道有 Dedekind domain。</li> <li>我想到自己独立地把微积分的最基本的定义自己独立证明一遍,从极限到导数到黎曼积分到微积分基本定理。如果成功,那说明我的数学成熟和数学能力的确有了较大的提高,因为本科时,我觉得不具备这个能力,更多是被动看书并非常局部地思考。当然,这么做也是得花些时间。我是否有这个耐心和自制力是另一个问题,至少我上大学的时候这方面是很差的。</li> <li>若要构建微积分并真正从第一原则出发,那必然得先定义实数,不然你对 epsilon delta 的认识也是处于薄弱的数学严谨或公理化的基础之上的。这么想就把 Galois 理论暂时放到一边了,然后写了这篇博文。</li> <li>我可能因为比较缺乏耐心或长时间做或写同一个东西的人,基本没用 LaTeX 写过什么长于 10 页的东西。我在博客上知乎上写的数学和物理也都没有长的文章,当然把我写的好多内容相关的文章贴到一起整理一下,也是能成为分为段的章,以及分为书的章的。只不过因为我自己基本些完了一段就发表到网了,而我想到好多真正搞数学的人是写了几十页的内容才发给任何其他人。我近三年都没写过任何 .tex 的文档,都是用博客和知乎写的。所以我想如果我去写初等实变或 Galois 理论的”书“,我一定要在计算机上用某个动态地同时显示代码和内容 LaTeX 的 IDE。我认识到一旦复杂了,定义,例子,引理,断言,定理,推论的标记数字动态生成调整是知乎或 WordPress 未有的功能。若要公布,直接上转 PDF 就完了。</li> <li>对成功写这篇文章,我或许感到有点欣慰,根本源于我开始能够独立地完整地条理地构建或重建数学理论了,而之前我不光学数学的思维过于局部,也过于依赖教科书,感觉从未基本独立于教科书做出或重推导出任何算的上非 trivial 的内容。做习题到了一定程度价值是有限的,很多因为习题比核心内容容易得多,你能解出来经常不说明啥,看到过核心的定理的证明然后能够自己从新证明它一般比做出习题要难得多。本科时候好多定理的证明我只能 follow,就 follow 完了然后不看书而讲出来都超出了我当时的智力。很典型的例子是 <a href="https://link.zhihu.com/?target=https%3A//gmachine1729.com/2018/02/19/implicit-function-theorem-and-its-multivariate-generalization/" class=" wrap external" target="_blank" rel="noreferrer noopener">Implicit function theorem and its multivariate generalization</a>,幸好大学之后我却独立地把这个向另一个人完整地讲了一下。</li> <li>成为有深度的理论的科学家更重要的还是 V,而非 M。V 很高的人是更能开创潮流,独立于已有的共识找到新方向的。V 对应 theory builder,而 M 更多表示技巧能力强,对应于 problem solver。Terence Tao 和 Shing-Tung Yau 显然都是分析超强的 problem solver 为主的人。解析数论是非常 problem solver 的方向,陈景润的论文我看过(当然没理解任何细节),计算和不等式估计超级繁琐,陈景润显然也是20世纪最超强的 problem solver 数学家之一。陈省身更多是个 problem solving 能力特别强的 theory builder,我认识的跟 SS Chern 讨论过数学的人却认为 Chern 真正 revolutionize 了数学,而 Yau 却没有,他认为 Yau 本质是 analyst&#8217;s geometer,强点在于具备砸开繁琐的几何分析的不等式的耐力,技巧和勤奋,而 Chern 是个 geometer&#8217;s geometer,比 Yau 明显更有 vision。中国的数学家更多是 problem solving 强。美国的 tenure 制度显然也更适合 problem solvers。</li> <li>Steve Hsu 在他的博客写道美国的 Study of Mathematically Precocious Youth 暗示的是智力超长的初中生中,M 高于 V 更多的倾向于数学,而 M 和 V 更均高的倾向于物理和化学,并且提到理论物理学家的综合智商看似比纯数学家的要高一点。我现在就好奇是不是纯数学家中的重代数的,如代数几何学家,代数拓扑学家,逻辑学家也同样是 V 不低于或高于 M。</li> <li>我认识到理论物理对不等式的要求不高,爱因斯坦标记,张量可以说难,但本质上还是离散的结构性关系,是个 V 高的人所擅长的。理论物理的复杂程度和技巧难度显然低于数学,尤其细节不等式非常复杂的分析,但从某种角度,它的深度和广度的更高的。与理论物理相比,纯数学要局部得多。我个人还是一个更全面的人,比如我对历史,政治也有所敏感,不太喜欢好多数学家的那种脱离现实的作风。</li> <li>我做过点函数编程,如 Haskell, Scala,也学过最基本的范畴论。写了这篇文章后对 Haskell 的 monoid 和 functor 有了些新的认识,自然也想到了类型与断言的对应 (Curry-Howard correspondence)。我在美国也见到过 V 明显高于 M 的搞编程语言或函数编程的牛人。他们在数学竞赛或编程算法竞赛远不如我,但是高中和大学的时候,他们的宏观和抽象思维明显是远高于我的。</li> </ul> </div>
Tags: uncategorized
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 0 comments