﻿ Finiteness and countability

## 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 :
• ⇒ : Id℘(E) = MorK'(℘(E), ℘(F)).
• ⇐ : ∀A∈SubK℘(E), A∪(℘(F)\℘(E)) ∈ SubK℘(F).

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:
• ∀(A,B),(A',B') ∈SP, AA' ⇔ BB'. The converse for xB\A, x'∈B'\A' and f : BB' is by Ay ↦ (f(y)=x' ? f(x):f(y)) ∈A'.
• AP, A≈∅ ⇔ A=∅ ⇔ A ∉ Im SP.

### 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:
• 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 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:

• A sequence of bijections hn : ℕ↔ En, gives a surjection ∐n∈ℕ Ei ≈ ℕ×ℕ → U=⋃n∈ℕ En so that taking En=ℕ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