4.6. Finiteness

Equinumerosity and cardinals

In particular for the category of sets, the equivalence predicate ≈ of equinumerosity between sets, is defined by the existence of a bijection :

A ≈ B ⇔ ∃f∈B^A, f : A ↔ B

On the "class" of cardinals, structures of addition, successor, multiplication and exponentiation are naturally defined from the relevant operations between sets,

0 = |∅|
1 = |{x}| for any x
|A| + |B| = |A⊔B|
S(a,b) ⇔ a+1 =b
|A| ⋅ |B| = |A×B|
|A|^|B| = |A^B|

|A| + |B| = |C| ⇔ (∃D⊂C, |B| = |D| ∧ |A| = |C\D|) ⇒ (∃D⊂C, |A| + |D| = |C|) ⇔ |A| ≤ |C|

For any sets A, B, if |A| + 1 = |B| + 1 then |A| = |B|.

Proof (simpler than done elsewhere).

Let C such that |C| = |A| + 1 = |B| + 1.
Let x,y∈C such that |A| = |C\{x}| and |B| = |C\{y}|.
If x = y we conclude directly.
Otherwise |A| = |C\{x,y}| + 1 = |B|. ∎

Another easy result is

|A| ≤ |B| ⇔ (|A| = |B| ∨ |A| + 1 ≤ |B|)

Finiteness

0 = {∅}
1_℘(E) = 1_E = {{x}|x∈E}
∀_setA,B, ASB ⇔ ∃x∈B, A = B\{x}
∀_setA,B,C, +((A,B), C) ⇔ (A∩B = ∅ ∧ C = A∪B)

∪⃗(A) ∈ Mor_S(℘(B),℘(C))
∅⌈S_E⌉B ⇒ A⌈S_E⌉C ⇒ (∅⌈S_E⌉A ⇒ ∅⌈S_E⌉C)
〈1_E〉_{0,+} ⊂ 〈0〉_S = Min_{0,S} ℘(E) ⊂ Min_{0,1,+}℘(E)

(+((A,B), C) ∧ C⊂F) ⇒ (A⊂F ∧ B⊂F)
Min_{0,1,+}℘(F) = ℘(F) ∩ Min_{0,1,+}℘(E)

∩⃗(F) ∈ Mor_{0,+}(℘(E),℘(F))
∩⃗(F)[1_E] ⊂ 〈1_F〉_{0}
∩⃗(F)[〈1_E〉_{0,+}] ⊂ 〈∩⃗(F)[1_E]〉_{0,+} ⊂ 〈1_F〉_{0,+} ∎

Proof. In the binary case, the finiteness of A and B implies that of A∪B = A∪(B\A), where B\A ⊂ B is finite.
The general case of a union U = ⋃_x∈E A_x where E and each A_x are finite, follows by

{F ⊂ E|⋃_x∈F A_x ∈ Min_{0,1,+}℘(U)} ∈ Sub_{0,1,+}℘(E) ∎

Any finite product of finite sets is finite.

Proof. A product of two finite sets is a finite union of finite sets. The general case follows like for unions. ∎

In particular, the finiteness of a set is equivalent to that of its powerset.

The finite choice theorem (announced in 2.10) is deduced in the same way.

For any finite set A ⊂ Dom f,

1. f[A] is finite,
2. |f[A]| ≤ |A|.

1. f[A] = ⋃_x∈A {f(x)}
2. The finite choice theorem then gives the existence of a section of f_|A.

ℕ and finite cardinals

A set E is called Dedekind-infinite if, equivalently

1. |E|+1 ≤ |E|
2. |ℕ| ≤ |E|
3. |E|+1 = |E|

Any finite cardinal is comparable with any other cardinal, i.e. |E| ≤ |F| ∨ |F| ≤ |E| whenever E is finite.

Proof : for any fixed set F, the class of sets E such that |E| ≤ |F| ∨ |F| ≤ |E| is {0,S}-stable.∎

Such reasonings to deduce a property of any set E by stability in the class of sets (or of cardinals), are justified as implicit uses of stability in the system ℘(E).
Likewise, the class of cardinals ≤ |E| can be expressed as a set K_E = ℘(E)/≈, whose {0,1,S,+}-structure (restriction of the one among cardinals) coincides with the quotient of the one of ℘(E).
Let M_E = Min_{0,S} K_E the set of finite cardinals of subsets of E.

As {0,S}-systems, K_E and M_E are functional, surjective and injective, and

K_E = Dom S_KE ∪ {|E|}
Dom S_ME = M_E ∩ Dom S_KE
M_E ⊂ Dom S_ME ∪ {|E|}
|E| ∉ Dom S_ME

Hence as noted in 4.3,

• If E is finite then M_E = K_E is a ground {0,S}-term with root |E|.
• Otherwise M_E is a ground term {0,S}-algebra, i.e. isomorphic to ℕ.

• There exists a ground term {0,S}-algebra (one of which is called ℕ);
• There exists a Dedekind-infinite set, i.e. an injective {0,S}-algebra;
• There exists an infinite set.

Finite cardinals form a model of arithmetic, or at least a model of the variant of arithmetic where the induction axiom is replaced by

(Ind') ∀x∈ℕ, ∀A⊂V_x+1, (0∈A ∧ ∀n∈A, Sn∈A) ⇒ x∈A

Without assuming them to form a set ℕ, natural numbers can be conceived as synonymity classes of {0,S}-terms.

Here are equivalent conditions for the finiteness of a subset A ⊂ E :

1. A ∈ Min_{0,S} ℘(E), i.e. ∅⌈S_E⌉A
2. |A| ∈ Min_{0,S} K_E
3. A ≈ V_n for some natural number n
4. There is a B ⊂ ℘(E) that is a {0,S}-term with root A.

Proof. 4.⇒1.⇒2. is obvious.
2.⇒3. : in the {0,S}-draft D = Min_{0,S} K_E, S is injective and its transitive closure T is irreflexive (by well-foundedness), thus

T⃖ ∈ Mor_{0,S}(D,℘(D))

3.⇒4. : T⃖ defines a {0,S}-embedding from the term with root n into ℘(V_n) which is isomorphic to ℘(A) when A ≈ V_n.
Remaining details are left to the reader.∎

More results

Any left cancellative element of a finite monoid (M, e, •) is invertible. Thus, any finite cancellative monoid is a group.

Proof: for any x ∈ M, the transformation •⃗(x) is injective in a finite set, thus also surjective. Being both left invertible and right cancellative (a monic retraction), x is invertible.∎

Finite composition in commutative monoids

Let us prove this by induction on the cardinal of X. The composite in M of the empty function is the identity element e of M, obviously independently of a total order on the empty X.
Any total order on a nonempty X has a last element x ∈ X. Then denoting A = X\{x}, the value in M of the string it gives is a•u(x) where a ∈ M is the composite of u_|A (common value for all its total orders). What needs to be checked is that for all x,y ∈ X, denoting a, b ∈ M the respective composites of u_|A and u_|B where A = X\{x} and B = X\{y}, we have a•u(x) = b•u(y).
If x=y we are done. Otherwise, denoting c = •[u_|X\{x,y}] ∈ M (or the value it takes for any chosen order on X\{x,y}), we have

a•u(x) = c•(u(y)•u(x)) = c•(u(x)•u(y)) = b•u(y). ∎

●[u] = ●[u_|A] • ●[u_|X\A] = ●[u_|X\A] • ●[u_|A].

(to be completed)