4.1. Finiteness and countability

To review equivalent formulas for the axiom of infinity, we need to work without assuming the existence of ℕ nor of other term algebras.
Let us start with a technical result:
For any subset A of an L'-system E and any x∈〈AL of E there exists a draft (D,D) where xDE, DE and VDA. Thus if E is an L-algebra then x is the value of an L-term with variables interpreted in A (namely the term with root x in D interpreted by IdD)
(proof : to be developed...)
It is easy to check that any condensed ground {0,S}-draft is either ∅ or a ground {0,S}-term or a ground term {0,S}-algebra (only two other languages have this property, apart from those with no constant).
A set is called finite if it has an injection to a ground {0,S}-term (i.e. a unary {S}-term). Otherwise it is called infinite.
A set is called countable if, equivalently,
  1. It has an injection to a condensed ground {0,S}-draft
  2. It has a bijection with a condensed ground {0,S}-draft
  3. A condensed ground {0,S}-draft has a surjection to it
1.⇒2. by restricting the order, once condensed ground {0,S}-drafts are described from their order structure; another method is given below.
2.⇒(1.∧ 3.) ; 3.⇒1. without AC, by picking the smallest element of each preimage.

So, countable sets are either finite or in bijection with ℕ. The latter, on which there exists a possible structure of ground term {0,S}-algebra, will be called countably infinite. However we still need to prove that they are indeed infinite.

Axiom of infinity

In set theory with the powerset, the following statements are equivalent expressions of the axiom of infinity:
  1. There exists an injective algebra whose language has at least a constant and a non-constant.
  2. There exists a non-surjective injection of a set to itself; equivalently an injective {0,S}-algebra, or a set ℕ.
  3. There exists an infinite set.
  4. For any countable algebraic language there is a (countable) injective algebra
  5. Any consistent first-order theory with a countable language has a (countable) model

4. ⇒ 2. ⇒ 1.; for 1. ⇒ 2. : from a non-constant operation s there, xs(kx) is an injective, non-surjective transformation.

We shall prove 2. ⇔ 3. below (finite cardinalities), and 2. ⇒ 4. ⇒ 5. in the section on the completeness theorem.

We may regard 5. ⇒ 4. as relative to the natural assumption that the concept of injective algebra forms a consistent theory. This theory is essentially the part of set theory which describes tuples. So, if a language L is included in a model of that simple part of set theory, then there exists an injective L-algebra. If such a model U is standard, this takes the form LUU, making (U, IdLU) an injective L-algebra. ∎
The infinity of ℕ easily implies the uniqueness of the number of elements of a finite set, as its non-uniqueness would give that set a strict injection into itself, and thus an injection of ℕ into it.

Finite cardinalities

2. ⇒ 3. will come from the infinity of ℕ.
For 3. ⇒ 2. we shall pick a different set, as the existence of an injective {0,S}-algebra structure on any infinite set would need the axiom of choice.

For any set E, let us give its powerset P=℘(E) the {0,S}-structure defined by 0P = {∅} and SP = {(A,B)∈P2| ∃xB, A=B\{x}}.
Let ≈ be the equivalence relation of equinumerosity on P, defined as existence of a bijection: AB ⇔ ∃f : AB.
The quotient structure on Q=P/≈, seen as a graph K⊂({0,S}⋆QQ is functional both ways (both it and its transpose are functional), and Im K = Q.
Indeed: Now denoting e the image of EP in Q, these definitions allow to "measure the size" of E (finding whether it is finite or infinite, and what is its number of elements if it is finite), by making it easy (but still non-trivial), through the fact that (Dom K)∪{(S,e)} = ({0,S}⋆Q) to prove that things fall into either case:

Assuming the axiom of infinity, the finiteness of a set E is equivalent to the existence of a number n∈ℕ and a bijection from Vn = {x∈ℕ | x<n} to E; or a surjection from Vn to E, which is then bijective precisely when n takes its smallest value (the number of elements of E).

Without ℕ, either ℘(℘(E)) or (with more work) EE can be used to express the finiteness of a set E, and to rebuild ℕ from E if E is infinite.

Any left cancellative element of a finite monoid is invertible. Thus any finite cancellative monoid is a group.
Proof: it acts as an injective transformation of a finite set, thus a permutation, by which the preimage of e is a right inverse, thus an inverse.

Countability of ℕ×ℕ

A rather natural bijection between ℕ×ℕ and ℕ is defined by (x,y) ↦ (x < y ? yy + x : xx + x + y)

The sequence (Tn) of triangular numbers is defined by 2⋅Tn = n⋅(n+1) (meaningful thanks to properties of parity), or recursively by

T0=0 ∧ ∀n∈ℕ, Tn+1=Tn+n+1

From this comes another bijection b2 : ℕ×ℕ → ℕ defined as b2(x,y) = Tx+y+y. Its inverse b2-1(z) is determined as x+y is the only n such that Tnz<Tn+1.
This corresponds to giving ℕ×ℕ the following stucture of ground term (0,S)-algebra (which recursively defines the inverse of b2)

Countability of finite sequences of integers

If there is a surjection f from ℕ to a set E then E is countable, as an inverse injection can be defined by associating to each xE its smallest preimage by f.

Fixing a bijection b2 from ℕ2 to ℕ, for any integer n>0 we can recursively define a bijection bn:ℕn→ℕ, for example:
n>0,∀u∈ℕn, bSn(u) = b2(bn(u),un)
(which gives back b2 as the particular case of bn for n=2).
Also the set ℕ(ℕ) = {u∈ ℕ | ∃k∈ ℕ, ∀n>k, un=0} is countable. There are different ways to see it:

But this construction of ℕ(ℕ)) and similarly simple candidate expressions of H as a countable set, assumes recursion, thus cannot be used to define recursion by the above method. To actually provide a definition of recursion that does not assume it, requires a different expression of an enumerated H. The representation of sequences which was used by Godel as a basis to define recursion, actually forms a different set.
Back to homepage : Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.6. Algebraic terms and term algebras
3.7. Integers and recursion
3.8. Arithmetic with addition
4. Model Theory
4.1. Finiteness and countability
4.2. The Completeness Theorem
4.3. Non-standard models of Arithmetic
4.4. How theories develop
4.5. Second-order logic
4.6. Well-foundedness and ordinals
4.7. Undecidability of the axiom of choice
4.8. Second-order arithmetic
4.9. The Incompleteness Theorem