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

• If A and B are finite then B^A is finite.
• The finiteness of a set is equivalent to that of its powerset.

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|

Since S is injective among cardinals,
|E|+1+1 = |E|+1 ⇒ |E|+1 = |E|
So the class of Dedekind-finite sets is {0,S}-stable. ∎

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 quotient set K_E = ℘(E)/≈, whose {0,1,S,+}-structure (restriction of the one among cardinals) coincides with the quotient of the one of ℘(E). The natural surjection plays the role of the cardinality function

| |_E : ℘(E) ↠ K_E.

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

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

|E|_E ∈ Dom S_KE means E is Dedekind-infinite
|E|_E ∈ M_E means E is finite. ∎

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

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

For any sets E, F such that |E| ≤ |F|, there is a (unique) natural embedding j_E,F ∈ Mor_{0,1,+}(K_E,K_F) defined as "the identity on cardinals", i.e.

∀A⊂E, ∀f:E↪F, j_E,F(|A|_E) = |f[A]|_F ≤ |Im f|_F

{j_E,G , j_F,G⚬h} ⊂ Mor_{0,S}(K_E,K_G)
j_E,G = j_F,G⚬h
|E|_G = j_F,G(h(|E|_E)) ≤ |F|_G

Similarly if E is infinite, any h ∈ Mor_{0,S}(M_E,K_F) also preserves cardinals (j_F,G⚬h = j_{E,G |ME}).
But, the result does not extend to K_E with an infinite E. In details, h ∈ Mor_{0,S}(K_E,K_F) neither implies h ∈ Mor_{≤}(K_E,K_F) nor injectivity of h, nor Im h = ≤⃖(h(|E|_E)). Taking all these as additional hypotheses, to deduce |E| ≤ |F| and h = j_E,F also involves the use of the well-ordering theorem which is a difficult consequence of (equivalent to) the axiom of choice, out of scope at this stage.

So, the above essentially describes the cardinality concept as forming the unique meta-{0,S}-isomorphism from the class of finite cardinals, to the class of natural numbers conceived as synonymity classes of ground {0,S}-terms. Its inverse is explicitly given by the concept, already introduced in 2.3, of the family of sets (V_n)_n∈D defined for any fixed ground {0,S}-draft D with its strict order < (transitive closure of S_D), as

∀n∈D, V_n = <⃖(n)

∀n∈D, |V_n| ≃ n.

Under the axiom of infinity, the set of all finite subsets of ℕ is

F = ⋃_n∈ℕ ℘(V_n)

∀A∈F, ¬(0∈A ∧ ∀n∈A, Sn∈A))

Yet, this expression of arithmetic in finite set theory does not ensure all axioms of first-order arithmetic. Indeed, the schema of induction (obtained from (Ind) by second-order universal elimination) is normally meant to include the cases of subsets defined by formulas with quantifiers in ℕ, but these become open quantifiers when ℕ is not admitted as a set. To recognize the subsets so defined as sets in set theory, is the point of the axiom schema of specification, which we only introduced in 1.A without using it yet.

Cancellativity in finite monoids

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

Free commutative monoids

R = {(u,u⚬σ) | u∈M ∧ σ∈𝔖_l(u)}

Indeed, it is easy to check that R is a congruence containing commutativity, i.e. M/R is a commutative monoid.
Less trivial is to check the converse: that it has basis X in the category of commutative monoids. In other words, for any commutative monoid (E,e,•) and f∈Mor(M,E), let us prove by induction on n∈ℕ that

∀u∈Xⁿ, ∀σ∈𝔖_n, f(u) = f(u⚬σ)

∀σ∈𝔖_n+1, ∃a,b∈M, u⚬σ = a⋅x⋅b ∧ (a⋅b)Rv
f(u) = f(v)•f(x) = f(a⋅b)•f(x) = f(a)•(f(b)•f(x)) = f(a)•(f(x)•f(b)) = f(u⚬σ) ∎

• M' is the set or class of functions u : V → X where V is any finite set (possibly ranging among subsets of a fixed infinite set U). These are objects of a subcategory of an overcategory of the category of sets, namely 〈1_E〉_{0,+}/X.
• R' is the relation of (existence of an) isomorphism in that overcategory.

∑(v⚬u) = f(V)

Another construction of free commutative monoid with basis X with no more stuff meant to be quotiented away, consists in the submonoid ℕ^(X) of the product monoid ℕ^X, made of all h∈ℕ^X such that {x∈X | h(x) ≠ 0} is finite. Such h is said to have finite support.
The natural morphism (quotient) M' ↠ ℕ^(X) is given by defining the image h∈ℕ^(X) of u∈M' by

h = (X∋x ↦ |u_•(x)|).

∑(v⚬u) = ∑_x∈X v(x)⋅h(x)
∏(v⚬u) = ∏_x∈X v(x)^h(x)

∀i∈I, δ_ik = (i=k ? Id_Ei : 0_ik) ∈ Mor (E_i,E_k)

This can be seen as a construction of the coproduct of the E_i as a role given to P, by letting the j_i take value in P by composition with δ

∀i∈I, j_i = ⊓_k∈I δ_ik ∈ Mor (E_i,P)

∀x∈P, g(x) = ∑_i∈I f_i(x_i)

Numbers of injections

P(|Y|,|X|) = |Inj(X,Y)|

P(n,0) = 1
P(n,1) = n
∀k∈ℕ, n<k ⇒ P(n,k) = 0

∀g∈ Inj(A,Y), π_A•(g) ≈ Inj(B, Y\Im g)

∀n,k,i ∈ℕ, P(n+i, k+i) = P(n,k)⋅P(n+i, i)

P(n+1, k+1) = P(n,k)⋅(n+1)
P(n+i, i+1) = n⋅P(n+i, i)

∀n,k ∈ℕ, P(n,k+1) = (n−k)⋅P(n,k)

∀n∈ℤ,∀k∈ℕ, P(n,k) = ∏_i<k (n−i)

The above formulas keep validity for negative n except that P(n,k) ≠ 0. Namely, it is conveniently expressed there by the rising factorial

∀n∈ℤ,∀k∈ℕ, P⁺(n,k) = ∏_i<k (n+i) = P(n+k−1,k)
P(-n,k) = P⁺(n,k)⋅(-1)^k

∀n∈ℕ, n! = |𝔖_n| = P(n,n) = P⁺(1,n) >0

n!⋅P⁺(n+1, k) = n!⋅P(n+k,k) = (n+k)!

Numbers of combinations

∀n∈ℤ,∀k∈ℕ, k!⋅C(n,k) = P(n,k)

C⁺(n,k) = C(n+k−1,k)
C(-n,k) = C⁺(n,k)⋅(-1)^k

As 0! = 1! = 1 we generally have C(n,0) = C⁺(n,0) = 1 and C(n,1) = n.
As A ↦ ∁_X A defines a bijective correspondence between k-combinations and n-combinations of V_n+k,

∀n,k∈ℕ, C(n+k,k) = C(n+k,n) = C⁺(n+1,k) = C⁺(k+1,n)

Given n=|X| and k,l∈ℕ, the number of possible data of disjoint A,B ⊂X with |A| = k and |B| = l, can be expressed in 3 ways according to which of A, B or A∪B is chosen first. This gives the following double equality (its validity for all n∈ℤ follows either by relating cases of negative n to those of positive n, or by deducing the general formula from numerical definitions after multiplication by k!⋅l!) :

∀n∈ℤ,∀k,l∈ℕ, C(n−k,l)⋅C(n,k) = C(n−l,k)⋅C(n,l) = C(k+l,l)⋅C(n,k+l)

In particular when l = 1

∀n∈ℤ,∀k∈ℕ, (n−k)⋅C(n,k) = n⋅C(n−1,k) = (k+1)⋅C(n,k+1)

From there follows

∀n∈ℤ,∀k∈ℕ*, C(n,k) = C(n−1,k−1) + C(n−1,k)

n⋅C(n−1,k) = (n−k)⋅C(n,k) = n⋅(C(n,k) − C(n−1,k−1))
(n−k)⋅C(n−1,k) = n⋅C(n−1,k) − k⋅C(n−1,k) = (n−k)⋅(C(n,k) − C(n−1,k−1))

The number of strictly monotone g:V_k → V_n is C(n,k).
Proof : g bijectively matches the k-combination Im g of V_n. ∎

The number of monotone f:V_k → V_n is C⁺(n,k).
Proof : f bijectively matches strictly monotone g:V_k → V_n+k−1 by g(x) = f(x) + x. ∎

Monotone f:V_k → V_n+1, monotone g:V_n → V_k+1, and k-combinations A of V_n+k, are so bijectively related by

∀x<k, ∀y<n, f(x) ≤ y ⇔ x < g(y) ⇔ x < |A∩V_x+y+1|

The number of h:V_n → ℕ such that ∑h ≤ k is C⁺(n+1,k).
Proof : they are bijectively h = h'_|Vn for h':V_n+1 → ℕ such that ∑h' = k. ∎

Related wikipedia pages:

Binomial coefficient
Combination
Multiset