A ≈ B ⇔ ∃f∈B^{A}, f : A ↔ B
Equinumerous sets are said to "have the same cardinal". For our needs, the cardinal |A| of any set A, intuitively meant as the equivalence class of A by ≈ in the class of all sets, can be formalized as A itself, where any direct or indirect use of "equality" between cardinals (never mixed with other elements) actually refers to the use of ≈.|A| ≺ |B| ⇔ ∃f:A↪B, Im f ≠ B
ASB ⇔ ∃x∈B, A = B\{x}.
ASB ⇒ |A| ≺ |B| ⇒ |A| ≤ |B| ⇔
(|A| ≺ |B| ∨ A ≈ B).
|A| ≺ ℘(A)
Im f ⊂ A ∨ (D = f_{⋆}A ⇒ (DSC ∧ f_{|D}:D↪A ∧ Im f_{|D} ≠ A)) ∎
Then for any sets A,B,C,D,(ASB ∧ CSD) ⇒ (A≈C ⇔ B≈D)
This can deduced (simpler than done elsewhere) from the above, either by Cantor-Bernstein, or by noting that the constructed injections are bijective here.(f(x) y)_{D}⚬f_{|A} = (A ∋ z ↦ (f(z) = y ? f(x) : f(z))) : A ↔ C
because f^{ -1}(y) ∈ A ⇔ f(x) ≠ y ⇔ f(x)∈ C.
In K_{E}, the relation S is both functional and injective thanks to the above result.
Let us complete this into a structure with language Σ = {0,S} first
introduced to define ℕ, by interpreting 0 as {∅}.
Then as a Σ-system, K_{E} is functional, surjective and injective, and
Dom S_{KE} ∪ {|E|} = K_{E}.
If F⊂E then the natural injection from K_{F} to K_{E} is a Σ-embedding (like any injective morphism from a surjective system to an injective one). As each K_{E} plays the role of a set of cardinals (namely those less than |E|), such natural injections can be conventionally seen as inclusions (K_{F} ⊂ K_{E}).
On the "class" of cardinals, operators of addition, multiplication and exponentiation are naturally defined from the relevant operations between sets,
|A| + |B| = |A⊔B|
|A| ⋅ |B| = |A×B|
|A|^{|B|} = |A^{B}|
1 = |{•}|
A subset A ⊂ E will be called finite if, equivalently,
Proof. 4.⇒1.⇒2. is obvious.
2.⇒3. : in the Σ-draft D = Min_{Σ} K_{E}, S is injective
and its transitive closure T is irreflexive (by well-foundedness), thus
T⃖ ∈ Mor_{Σ}(D,℘(D))
Denoting V_{n} = T⃖(n), the function n↦|V_{n}| forms a Σ-morphism from D to K_{E∪D}.3.⇒4. : T⃖ defines a Σ-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.∎
To prove it comes down to proving that any cardinal |F| outside the ground Σ-term X with root |E| is greater than |E|, which can be conveniently done in two possible ways.
One way involves a distinction of cases.
If F is
infinite, from Dom S_{KF} ∪ {|F|} = K_{F} we deduce
Min_{Σ} K_{F} ⊂ Dom S_{KF},
thus Min_{Σ} K_{F} is a ground term Σ-algebra, i.e. a copy of ℕ,
thus contains all finite cardinals: any finite cardinal is lower than any infinite one.
If F is finite then |E|, |F| both belong to
Min_{Σ} K_{E∪F}. There, any two elements are comparable
by ⌈S⌉ because, by the proof from 4.5, any nonempty subset
of Min_{Σ} K_{E∪F} has a least element for ⌈S⌉.
Then they are also comparable by ≤ as ⌈S⌉ ⊂ ≤.
The other way uses 0 ≤ |F| and
∀(x,y)∈S_{X}, |F| ≠ x ≤ |F| ⇒ x ≺ |F| ⇒ y ≤ |F| ∎
Proposition. For any set E, |E| ≺ |E| ⇔ |ℕ| ≤ |E| which implies that E is infinite.Proof. If f:E↪E and x ∈ ∁_{E} Im f then
〈{x}〉_{f} ≈ ℕ (as a unary {f}-term algebra), and
Conversely, if ℕ ⊂ E then the extension of S_{ℕ} by Id_{E\ℕ}
is an injective, non-surjective transformation of E.∎
(The missing converse, that |ℕ| ≤ |E| for any infinite E, cannot be proven without
the axiom of choice, as will be discussed in 5.5)
The first two are the statements of existence of
More equivalent statements will be reviewed in the next section.
In particular, if A and B are finite then A⊔B, A×B and A^{B} are finite. Indeed these can be successively deduced by induction as follows: for a given finite A, the fininess holds for B = ∅, and if BSB' then the finiteness of the result from (A,B) implies that from (A,B'), because, respectively,
(A⊔B)S(A⊔B')
A×B' ≈ A ⊔ A×B
A^{B'} ≈ A × A^{B}
∎
A union A∪B of finite sets is also finite. This can be seen as A∪B ≈ A⊔(B\A), where B\A is finite because B is. From this, follows by induction that any finite union of finite sets is finite. Then, any term is finite (the set of roots of infinite sub-terms of a draft is empty thanks to well-foundedness, when all symbols have finite arities).
As V_{2}^{B} ⥬ ℘(B), the finiteness of B implies that of ℘(B), and both are equivalent since |B| < ℘(B).
If there is a surjection f : A ↠ B and A is finite then
B is finite, |B| ≤ |A|, and
There are two main ways to prove it:
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.∎
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). ∎
Obviously for any A ⊂ X we have●[u] = ●[u_{|A}] • ●[u_{|X\A}] = ●[u_{|X\A}] • ●[u_{|A}].
Our proof from which this result is inferred, only used commutativity between elements of Im u. So, this implicitly contains or repeats the proof from 3.5 that a monoid generated by a commutative subset is also commutative.(to be completed)