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 X⊂E and any
x∈〈X〉_{L} in E there exists a draft
(D,D) where x∈D⊂E, D⊂E and
V_{D}⊂X.
It makes no difference to fix V_{D}=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
D⊂E.
Let (s,x,y)∈E such that Im x ⊂B. By finite choice
there exists a tuple of ground drafts
(D_{i},D_{i})_{i<ns}
such that ∀i<n_{s}, x_{i}∈D_{i} ∧ D_{i}⊂E.
Let D = ⋃_{i<ns} D_{i}.
Let us check that Ψ = (D ∋ z ↦ Ψ_{i}(z) for the smallest
i such that z∈D_{i}), defines a ground draft.
For any nonempty A⊂D, take the smallest i
such that A∩D_{i} ≠ ∅.
∃z∈A∩D_{i},
∅ = A∩D_{i}∩ Im l_{i,z} =
A ∩ Im l_{i,z} because
Im l_{i,z} ⊂ D_{i}.
Ψ(z) = Ψ_{i}(z) because i
is also smallest such that z∈D_{i},
thus l_{z} = l_{i,z}.
We conclude ∃z∈A, A ∩ Im l_{z} = ∅,
thus Ψ defines a ground draft on D.
Then either y∈D, 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 0_{P} = {∅} and
S_{P} = {(A,B)∈P^{2}
∃x∈B, A=B\{x}}.
We define the set of finite subsets of E as Min_{K}℘(E).
A set is finite if it is a finite subset of itself (otherwise it is infinite).
For any sets E⊂F, (E is finite) ⇔ (E is a finite subset of F). Proof :
 ⇒ : Id_{℘(E)} = Mor_{K'}(℘(E), ℘(F)).
 ⇐ : ∀A∈Sub_{K}℘(E), A∪(℘(F)\℘(E)) ∈ Sub_{K}℘(F).
Equivalently, a set E is finite if it has a bijection to the graph of S in
a ground Kterm n (which can be seen as a unary {S}term). This may
as well be seen as a bijection to its domain {0,...,n1} 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
Kdraft is either ∅ or a ground Kterm or a ground term
Kalgebra (only two other languages have this property, apart from those with no constant).
A set is called countable if, equivalently,
 It has an injection to a condensed ground Kdraft
 It has a bijection with a condensed ground Kdraft
 A condensed ground Kdraft 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: A≈B ⇔ ∃f : A ↔ B.
The quotient
structure on Q=P/≈, seen as a graph
G⊂(^{{0,S}}Q)×Q is functional both ways (both it and
its transpose are functional), and Im G = Q.
Indeed:
 ∀(A,B),(A',B') ∈S_{P},
A≈A' ⇔ B≈B'. The converse for x∈B\A,
x'∈B'\A' and f : B ↔ B' is by A ∋
y ↦ (f(y)=x' ? f(x):f(y)) ∈A'.
 ∀A∈P, A≈∅ ⇔ A=∅ ⇔ A ∉ Im S_{P}.
Axiom of infinity
In set theory with the powerset, the
following statements are equivalent expressions of the axiom of infinity:
 There exists an injective algebra whose language has at least a constant and a
nonconstant.
 There exists a nonsurjective injection of a set to itself; equivalently an
injective {0,S}algebra, or a set ℕ.
 There exists an infinite set.
 For any countable algebraic language there is a (countable)
injective algebra
 Any consistent firstorder theory with a countable language
has a (countable) model
4. ⇒ 2. ⇒ 1.; for 1. ⇒ 2. : from a nonconstant operation s there,
x↦s(k↦x)
is an injective, nonsurjective 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 Lalgebra. If such a model U is standard, this takes the form
^{L}U ⊂ U, making (U, Id_{LU})
an injective Lalgebra. ∎
The infinity of ℕ easily implies the uniqueness of the
number of elements of a finite set, as its nonuniqueness 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 E∈P 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 nontrivial),
through the fact that (Dom K)∪{(S,e)} = (^{{0,S}}Q)
to prove that things fall into either case:
 If E is finite, e∈ Min Q, and Q is a ground term with
root e representing the number of elements of E ;
 If E is infinite, e∉ Min Q, and Min Q is a ground term algebra
(thus a model of arithmetic), whose preimage is the set of all finite subsets of E.
Assuming the axiom of infinity, the finiteness of a set E is equivalent to the existence of a
number n∈ℕ and a bijection from
V_{n} = {x∈ℕ  x<n} to
E; or a surjection from V_{n} 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) E^{E} 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 ? x⋅x + y : y⋅y +
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
b_{2} :
ℕ×ℕ → ℕ
is defined as
b_{2}(
x,
y) =
T_{x+y}+
y
from the sequence (
T_{n}) of
triangular numbers
defined by
2⋅T_{n} = n⋅(n+1) (see
properties of parity) or equivalently by
T_{0}=0 ∧ ∀
n∈ℕ,
T_{n+1}=
T_{n}+
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 b_{2}^{1}(z), where
x+y is the only n such that
T_{n}≤z<T_{n+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 x∈E its smallest preimage by f.
Fixing a bijection b_{2} from ℕ^{2} to ℕ,
for any integer n>0 we can recursively define a
bijection b_{n}:ℕ^{n}→ℕ, for
example:
b_{1}=Id_{ℕ}
∀n>0,∀u∈ℕ^{n},
b_{Sn}(u) =
b_{2}(b_{n}(u),u_{n})
(which gives back b_{2} as the particular case of
b_{n} for n=2).
Also the set ℕ^{(ℕ)} = {u∈ ℕ^{ℕ} 
∃k∈ ℕ, ∀n>k, u_{n}=0} is countable.
There are different ways to see it:
 A sequence of bijections h_{n} : ℕ↔
E_{n}, gives a surjection ∐_{n∈ℕ}
E_{i} ≈ ℕ×ℕ →
U=⋃_{n∈ℕ} E_{n}
so that taking E_{n}=ℕ^{n} we find that
U=ℕ^{(ℕ)} is countable.
 With the decomposition in prime numbers
 As the binary representation maps ℕ to the set 2^{(ℕ)} of finite
subsets of ℕ, it also maps ℕ^{(ℕ)}
to the set 2^{(ℕ×ℕ)} of finite subsets of ℕ×ℕ.
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. Nonstandard models of Arithmetic
4.4. How theories develop
4.5. Secondorder logic
4.6. Wellfoundedness
4.7. Ordinals and cardinals
4.8. Undecidability of the axiom of
choice
4.9. Secondorder
arithmetic
4.10. The Incompleteness
Theorem