4.1. Finiteness and countability

To review equivalent conditions for the axiom of infinity, we need formulations which do not assume ℕ.
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 an injection to ℕ
  3. It has an bijection with a condensed ground {0,S}-draft
  4. A condensed ground {0,S}-draft has a surjection to it
1.⇔2. as any condensed ground {0,S}-draft has an injection to ℕ, itself a condensed ground {0,S}-draft
1.⇒3. by restricting the order, once condensed ground {0,S}-drafts are described from their order structure; another method is given below.
3.⇒(1.∧ 4.) ; 4.⇒2. without AC, by picking the smallest element of each preimage.

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. ∎

Finite cardinalities

For 2. ⇒ 3. we need to prove the infinity of ℕ, and thus the infinity of any set with a non-surjective injection to itself. This amounts to showing the uniqueness of the number of elements of a finite set (as its non-uniqueness would give a strict injection of a finite set to itself, in which ℕ could thus be found).
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.

Rebuilding recursion

Our first construction (justification of existence) of recursive sequences (fn(a))n∈ℕ, came from the general case of interpretations of drafts, assuming a set theoretical framework with the powerset. Let us reformulate it in first-order logic, to make it fit in first-order theories with weaker assumptions than set theory, and do it for a more flexible form of recursion : for any aE and any fEE×ℕ, there exists a unique sequence xE such that x0=a ∧ ∀n∈ℕ, xn+1 = f(xn,n).
Let us abbreviate in binders kVn as k<n.
Assume given a set HE, available in a given first-order theory as abbreviating a range of operations defined by a formula with parameters, "large enough" to provide "all finite sequences". This condition can be expressed as

n∈ℕ, ∀uH, ∀yE, ∃vH, vn=y ∧ ∀k<n, vk = uk

Now the above recursive sequence x satisfies

n∈ℕ, ∀yE, y = xn ⇔ ∃vH, v0=a ∧ (∀k<n, vk+1 = f(vk,n)) ∧ vn=y.

This way, any first-order theory able to express such an H can use it to express recursion by holding xn as abbreviation of "the only y satisfying the right side of this equivalence". The existence and uniqueness of this y, comes from the existence of v such that (v0=a ∧ ∀k<n, vk+1 = f(vk,n)) and the uniqueness of its restriction to numbers ≤ n, which are easy to prove by induction (the axiom schema of induction in the given theory). As in particular any finite sequence expressible in the theory will be represented in H, this definition of recursion turns out to be "the recursion which the theory can express" independently of the particular choice of H.
In fact, such an H cannot be found in Presburger arithmetic but Gödel found one in full first-order arithmetic, from which he could build the needed tools to prove his famous incompleteness theorem. From recursion, many operations can be defined: exponentiation, factorials, approximations of square roots and third roots... possibilities are so diverse that they cannot fit any nicely ordered description.
Still another justification of recursion, working for any term algebra, will later come using minimal subalgebras in products.
Another generalization of recursion, easy to insert in the above proof (or deducible by changing E), involves conditions of the form

n∈ℕ, un = f((uk)k<n).

Countability of ℕ×ℕ

One bijection between ℕ×ℕ and ℕ uses the sequence (Tn) of triangular numbers.
This sequence can be defined recursively by T0=0 ∧ ∀n∈ℕ, Tn+1=Tn+n+1, or using multiplication as 2Tn = n(n+1).
Then a bijection b2 from ℕ×ℕ to ℕ can be 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. Infinity and the axiom of choice
4.5. How theories develop
4.6. Second-order logic
4.7. The Incompleteness Theorem