# 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.]

Tags:
• #### 中国姓氏的南北分布

有意思的是分布是很不均匀的，也就是说好多姓是南方比例远高于北方比例或相反。从这一点，你如果知道一个人的父母的姓氏，你就可以对他是北方人还是南方人有个有点统计显著的估计。 读者可以在包含大姓分布图的…

• #### Why I think Stanford professor James Landay's piece on computing in China in 2011 exposed his idiocy

I dittoed his blog post on my LiveJournal too, see https://gmachine1729.livejournal.com/175023.html. For the original, see…

• #### China Will Overtake the US in Computing…Maybe, Someday… by Stanford professor James Landay in 2011

Original at https://dubfuture.blogspot.com/2011/12/china-will-overtake-us-in.html. [note: the following is a rough draft — I appreciate…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic