4.1. Finiteness and countability

To review equivalent forms of the axiom of infinity, we need to work without assuming it. Let us start with a technical result.

Covering of stable subsets by terms

For any L'-system (E,E), any XE and any x∈〈XL in E there exists a draft (D,D) where xDE, DE and VDX.
It makes no difference to fix VD=X, or X=∅ by adding it as a set of constants to the language.

Proof, fixing X=∅ to simplify.
Let us show the stability of the union B of the D such that there exists a ground draft (D,D) with DE.
Let (s,x,y)∈E such that Im xB. By finite choice there exists a tuple of ground drafts (Di,Di)i<ns such that ∀i<ns, xiDiDiE.
Let D = ⋃i<ns Di.
Let us check that Ψ = (Dz ↦ Ψi(z) for the smallest i such that zDi), defines a ground draft.
For any nonempty AD, take the smallest i such that ADi ≠ ∅.
zADi, ∅ = ADi∩ Im li,z = A ∩ Im li,z because Im li,zDi.
Ψ(z) = Ψi(z) because i is also smallest such that zDi, thus lz = li,z.
We conclude ∃zA, A ∩ Im lz = ∅, thus Ψ defines a ground draft on D.
Then either yD, or adding it there with (s,x,y) gives a ground draft that fits.∎

Thus independently of the axiom of infinity (existence of term algebras) anyway all elements of a minimal algebra are values of ground terms.

Finiteness

Let K={0,S}.
For any set E, let us give its powerset P=℘(E) the K'-structure defined by 0P = {∅} and SP = {(A,B)∈P2| ∃xB, A=B\{x}}.

We define the set of finite subsets of E as MinK℘(E). A set is finite if it is a finite subset of itself (otherwise it is infinite).
For any sets EF, (E is finite) ⇔ (E is a finite subset of F). Proof :

Equivalently, a set E is finite if it has a bijection to the graph of S in a ground K-term n (which can be seen as a unary {S}-term). This may as well be seen as a bijection to its domain {0,...,n-1} or to its image {1,...,n}.
Proof. From a finite set E, the above theorem gives a term with root E included in ℘(E)...

Countable sets

It is easy to check that any condensed ground K-draft is either ∅ or a ground K-term or a ground term K-algebra (only two other languages have this property, apart from those with no constant).
A set is called countable if, equivalently,

  1. It has an injection to a condensed ground K-draft
  2. It has a bijection with a condensed ground K-draft
  3. A condensed ground K-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.

Finite cardinalities

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 G⊂({0,S}⋆QQ is functional both ways (both it and its transpose are functional), and Im G = Q.
Indeed:

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

Finite cardinalities

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 ℕ×ℕ
y\x
0
1
2
3
4
0
0
1
4
9
16
1
2
3
5
10
17
2
6
7
8
11
18
3
12
13
14
15
19

A natural bijection between ℕ×ℕ and ℕ is defined by (x,y) ↦ (y < x ? xx + y : yy + x + y).
y\x
0
1
2
3
4
0
0
1
3
6
10
1
2
4
7
11
2
5
8
12
3
9
13
Another bijection b2 : ℕ×ℕ → ℕ is defined as b2(x,y) = Tx+y+y from the sequence (Tn) of triangular numbers defined by 2⋅Tn = n⋅(n+1) (see properties of parity) or equivalently by T0=0 ∧ ∀n∈ℕ, Tn+1=Tn+n+1. This makes ℕ×ℕ a ground term (0,S)-algebra where
0=(0,0)
S(0,y)=(y+1,0)
S(x+1,y)=(x,y+1)
which recursively defines b2-1(z), where x+y is the only n such that Tnz<Tn+1.

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:

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
4.7. Ordinals and cardinals
4.8. Undecidability of the axiom of choice
4.9. Second-order arithmetic
4.10. The Incompleteness Theorem