4.1. Finiteness and countability

A set E is called finite if it is in bijection with the domain of S in some ground {0,S}-term. Otherwise it is called infinite.
A set E is called countable if there exists an injection from E to ℕ.

Countability of ℕ×ℕ

The sequence of triangular numbers can be defined using multiplication as 2Tn = n(n+1), or recursively by

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

From there we can define a bijection b2 from ℕ×ℕ to ℕ as b2(x,y)= Tx+y+y.
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:
b1=Id
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:

Axiom of infinity

In set theory with the powerset, for any language L, the existence of a ground term L-algebra is deducible from that of an injective L-algebra, by taking its minimal subalgebra. Then, the following statements are equivalent, forms of the axiom of infinity which means the existence of an infinite set:

  1. There exists an injective algebra whose language has at least a constant and a non-constant.
  2. There exists a set with a non-surjective injection into itself.
  3. There exists an injective {0,S}-algebra.
  4. There exists an infinite set.
  5. For any countable algebraic language there is a countable injective algebra
  6. Any consistent first-order theory with a countable language has a countable model

1. ⇒ 2. : given such an algebra E with a non-constant s, the function (ExsE(kx)) is a non-surjective injection of E into itself.
2. ⇔ 3. is obvious.

The proofs of 3. ⇒ 5. ⇒ 6. will be given in the section on the completeness theorem.

Let us show an easy converse :
If a language L is included in some universe U, even a "small" one only containing finite sets (model of a weak version of set theory, without axiom of infinity or even without powerset), then there exists an injective L-algebra.

Proof. If U is standard, LUU, thus (U, IdLU) is an injective L-algebra. Otherwise, use what plays the role of IdLU in U (expressed by its tuples definers). ∎

Assuming the axiom of infinity, the above definition of finiteness can be rephrased as follows : a set E is finite if there exists an integer n∈ℕ and a bijection from Vn = {x∈ℕ | x<n} to E.

Let us abbreviate in binders kVn as k<n.

Finite cardinalities

Let us now show 2. ⇒ 4. as such a set is infinite. Proving 2 on a given infinite set will need the axiom of choice, however 4. ⇒ 2. can still be proven by picking a different set.
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, this is easy to prove) and Im K = Q.
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: Equivalently, a set E is finite if there exists an integer n∈ℕ and a surjection from Vn to E. The smallest such n is the one for which this function is bijective, and is the number of elements of E.

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

We already gave two constructions for recursive sequences: one by terms and the other using minimal sub-algebras. Let us give a third one (somehow reformulating the first). Let HE be "as good as E in providing finite sequences", i.e.

n∈ℕ, ∀uH, ∀xE, ∃vH, vn=x ∧ ∀k<n, vk = uk

then it can be used instead of E to define the recursive sequence uE such that u0=a ∧ ∀n∈ℕ, un+1 = f(un) as

n∈ℕ, ∀xE, x = un ⇔ ∃vH, v0=avn=x ∧ ∀k<n, vk+1 = f(vk)

The interest of this definition is that if H is countable, then it can be written in the language of first-order arithmetic, without using the powerset. Still there is one difficulty : the simple candidate expressions of H as a countable set assume recursion, and thus cannot stand as a definition of recursion. To actually provide a definition of recursion that does not assume it, requires a different expression of an enumerated H. This was solved by Gödel who provided such a numbering for sequences (which actually does not coincide with ℕ(ℕ)) only using full first-order arithmetic (with addition and multiplication), thus proving that this arithmetic is able to express recursion (thus exponentiation, factorials, approximations of square roots and third roots... possibilities are so diverse that they cannot fit any nicely ordered description). Then he could build from there the needed tools to prove his famous incompleteness theorem.
We can still generalize recursion by taking recursive conditions of the form

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

Its existence and uniqueness can be proven either directly by adapting the above definition, or from the previous case by replacing E by the set of finite sequences in E.
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. Infinity and the axiom of choice
4.4. Non-standard models of Arithmetic
4.5. How theories develop
4.6. The Incompleteness Theorem