4.6. Finiteness
Equinumerosity and cardinals
Given any small category with a set O of objects, one may consider its objects
"up to isomorphism", by taking the quotient of O by the relation ∼
of isomorphism. Precisely, an attribute may be attached to objects, by saying that two objects
have the same [something] if and only if they are isomorphic. This is formalized as a function
K from O to some other set, whose equivalence relation is ∼, while
no other detail of this function matters. But, the use of this function may as well
be seen as an abbreviation of, or simulated by, the use of objects themselves, where the formula
"K(A) = K(B)" means to abbreviate A ∼ B
(the existence of an isomorphism between
A and B), and more sophisticated uses follow from there (for example, an inclusion
X ⊂ Y ⊂ Im K can be reinterpreted with X ⊂ O, Y ⊂ O
as ∀A∈X, ∃B∈Y, A∼B).
This may be generalized to any category beyond the small ones, as justified
either in terms of that abbreviation/simulation, or by the context of use where
the non-smallness of the category has no impact, since objects are only handled
"some fixed set of them at a time", i.e. interpretable as the use of some small
category, no matter which one precisely. Another possible justification would be to change
the formalization of set theory to admit another primitive class of objects beyond sets and
functions; this would be an extension or development of set theory, in the sense further discussed in 4.11).
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∈BA, f : A ↔ B
Equinumerous sets are said to "have the same cardinal" : |A| = |B| ⇔ A ≈ B
where |A| denotes the cardinal of a set A.
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| = |AB|
with their famous equality properties deducible from the existences
of canonical bijections (2.8).
Cardinals are naturally ordered by : |A| ≤ |B| if there exists an injection from A to B.
Indeed it is obviously a preorder (composites of injections are injections),
while its antisymmetry is given by the Cantor-Bernstein theorem. For any sets A, B, C,
|A| + |B| = |C| ⇔
(∃D⊂C, |B| = |D| ∧ |A| = |C\D|)
⇒ (∃D⊂C, |A| + |D| = |C|) ⇔ |A| ≤ |C|
Also, |A| ≤ |℘(A)| because (A∋x↦{x}) : A ↪ ℘(A),
while |A| ≠ |℘(A)|
by Cantor's theorem (2.7).
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|. ∎
More generally, if |A| + 1 ≤ |B| + 1 then |A| ≤ |B|.
Indeed if |C| + |A| + 1 = |B| + 1 for some C, then also
|C| + |A| = |B|, i.e. |A| ≤ |B|. ∎
Another easy result is
|A| ≤ |B| ⇔ (|A| = |B| ∨ |A| + 1 ≤ |B|)
Finiteness
Let us give to any powerset ℘(E), the {0,1,S,+}-structure defined
by restriction of the natural meta-{0,1,S,+}-structure on the class of sets:
0 = {∅}
1℘(E) = 1E = {{x}|x∈E}
∀setA,B, ASB ⇔ ∃x∈B, A = B\{x}
∀setA,B,C,
+((A,B), C) ⇔ (A∩B = ∅ ∧ C = A∪B)
It forms a partial {0,+}-algebra, embedded in the product monoid ℕE (if ℕ exists),
namely identifiable to {h∈ℕE | Im h ⊂ {0,1}}.
Its component 0 may also be written as the constant 0 = ∅
when using the convention for algebras.
The cardinality function forms a {0,1,S,+}-morphism from ℘(E) to
the class of cardinals.
If +((A,B), C) then
∪⃗(A) ∈ MorS(℘(B),℘(C))
∅⌈SE⌉B ⇒ A⌈SE⌉C
⇒ (∅⌈SE⌉A ⇒ ∅⌈SE⌉C)
〈1E〉{0,+} ⊂
〈0〉S = Min{0,S}
℘(E) ⊂ Min{0,1,+}℘(E)
Tbe set 〈0〉S = Min{0,1,+}℘(E) = 〈1E〉{0,+} is the set
of finite subsets of E.
So, a set F⊂E is finite when
F ∈ Min{0,1,+}℘(E)
independently of the chosen E such that F⊂E:
(+((A,B), C) ∧ C⊂F)
⇒ (A⊂F ∧ B⊂F)
Min{0,1,+}℘(F) = ℘(F) ∩ Min{0,1,+}℘(E)
Finiteness only depends on cardinality, since any bijection between E and F
defines an {0,1,+}-isomorphism between ℘(E) and ℘(F).
For this reason, it will also qualify cardinals: a finite cardinal is a cardinal of finite sets.
If
F⊂E and E is finite then F is finite because
∩⃗(F) ∈ Mor{0,+}(℘(E),℘(F))
∩⃗(F)[1E] ⊂ 〈1F〉{0}
∩⃗(F)[〈1E〉{0,+}] ⊂
〈∩⃗(F)[1E]〉{0,+} ⊂ 〈1F〉{0,+} ∎
Any finite union of finite sets is finite. 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 Ax where E
and each Ax are finite, follows by
{F ⊂ E|⋃x∈F Ax ∈ Min{0,1,+}℘(U)}
∈ Sub{0,1,+}℘(E) ∎
Any term over a language where all symbols have finite arities, is finite.
The proof involves the stability of the set of roots of finite sub-terms.∎
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,
- f[A] is finite,
- |f[A]| ≤ |A|.
Proof:
- f[A] = ⋃x∈A {f(x)}
- The finite choice theorem then gives the existence of a section of f|A.
A section of f|A can also be explicitly defined when
A = Vn, by y ↦ min f•(y).
ℕ and finite cardinals
Let us keep working independently of the axiom
of infinity, and now bring tools to express equivalent forms of it.
A set E is called Dedekind-infinite if, equivalently
- |E|+1 ≤ |E|
-
|ℕ| ≤ |E|
- |E|+1 = |E|
Proof 1.⇒2. : |E|+1 ≤ |E| means there exists f:E↪E
and x ∈ ∁E Im f, which implies
〈{x}〉f ≈ ℕ (as a unary {f}-term algebra).
2.⇒3. : if ℕ ⊂ E then the {0,S}-structure of ℕ extended by IdE\ℕ
forms a bijection |E|+1 = |E|.∎
Dedekind-infinity implies infinity, i.e. ℕ is infinite.
Proof: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. ∎
But, the converse depends on a version
of the axiom of choice, as will be discussed in 5.5.
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
KE = ℘(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) ↠ KE.
Let ME = Min{0,S} KE the set of
finite cardinals of subsets of E (thanks to the formula ∀B⊂F, f⋆(B) = MinLE
⇒ B = MinLF from 4.2).
As {0,S}-systems, KE and ME are functional, surjective
and injective, and
KE =
Dom SKE ∪ {|E|E}
Dom SME = ME ∩ Dom SKE
ME ⊂ Dom SME ∪ {|E|E}
|E|E ∉ Dom SME
Proof of the last formula:
|E|E ∈ Dom SKE means E is Dedekind-infinite
|E|E ∈ ME means E is finite. ∎
Hence as noted in 4.3,
- If E is finite then ME = KE
is a ground {0,S}-term with root |E|E.
- Otherwise ME is a ground {0,S}-term algebra, i.e. isomorphic to ℕ.
Hence the equivalence between several expressions of the axiom of infinity:
- 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.
If it holds (in a given universe) then the range of finite cardinals is expressible as the set ℕ,
which may be identified with the ground {0,S}-term algebra ME for any infinite E.
Otherwise, namely in finite set theory, finite cardinals may still be identified as "natural numbers" conceived as synonymity classes
of {0,S}-terms, which form a model of arithmetic out of the given model of finite set theory, but with a
caveat explained below. Either case needs
some technical justifications by the following results.
For any sets E, F such that |E| ≤ |F|, there is a (unique) natural embedding
jE,F ∈ Mor{0,1,+}(KE,KF)
defined as "the identity on cardinals", i.e.
∀A⊂E, ∀f:E↪F, jE,F(|A|E) =
|f[A]|F ≤ |Im f|F
Conversely, if E is finite and h ∈
Mor{0,S}(KE,KF) then |E| ≤ |F| and
h = jE,F.
Proof. Denoting G = E ∪ F,
{jE,G , jF,G⚬h}
⊂ Mor{0,S}(KE,KG)
jE,G = jF,G⚬h
|E|G = jF,G(h(|E|E))
≤ |F|G
hence h = jE,F because jF,G is injective.∎
Similarly if E is infinite, any h ∈ Mor{0,S}(ME,KF)
also preserves cardinals (jF,G⚬h
= jE,G |ME).
But, the result does not extend to KE with an infinite E.
In details, h ∈ Mor{0,S}(KE,KF) neither implies
h ∈ Mor{≤}(KE,KF) nor injectivity of h, nor
Im h = ≤⃖(h(|E|E)). Taking all these as additional hypotheses,
to deduce |E| ≤ |F| and h = jE,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 (Vn)n∈D defined for any fixed ground
{0,S}-draft D with its strict order < (transitive closure of SD), as
∀n∈D, Vn = <⃖(n)
It is an {0,S}-embedding from D to ℘(D) (in particular, the
term with root n is embedded into ℘(Vn)).
Therefore by uniqueness of interpretations,
∀n∈D, |Vn| ≃ n.
Applying this to D = ME, shows that any finite
A ⊂ E is equinumerous with V|A|E. So, any finite
A is in bijection with Vn where n = |A| in ℕ
under the axiom of infinity, or anyway in some ground functional {0,S}-draft D
serving as a range of natural numbers.
Under the axiom of infinity, the set of all finite subsets of ℕ is
F = ⋃n∈ℕ ℘(Vn)
The proof is easy, using F ∈ Sub{0,1,+}℘(E).
On the other hand in finite set theory, ℕ is only
indirectly handled as seen above without being a set. Through such encoding,
the range of all its subsets available as sets, matches the above definition of F.
This still fills the role of ℕ, since the induction axiom (Ind) from 4.4 is actually
equivalent to the following restricted version (assuming some basic properties of the order):
∀A∈F, ¬(0∈A ∧ ∀n∈A, Sn∈A))
(Another short equivalent form of (Ind) is ∀A∈F,
∃n∈ℕ\A, Vn⊂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
Any left cancellative element of a finite monoid (M, e, •) is invertible.
Thus, any finite left cancellative monoid is a group.
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
After the concept of free monoid introduced in 4.3 and 4.4, let us introduce the concept of
free commutative monoid, defined as a commutative monoid with some basis X in the category
of commutative monoids. This is another use of the general concept of free modules,
differing from that of free monoids by expanding the axioms list (beyond the axioms of monoid),
which may be formalized by adding an element in the structure of an equational system representing
these axioms. Then, a free commutative monoid with basis X, is the quotient
of the free monoid M = ⋃n∈ℕ Xn with basis X,
by the congruence generated by, so to speak,
the interpretation of the commutativity axiom in M.
This congruence coincides with the equivalence relation R =
{(u,u⚬σ) | u∈M
∧ σ∈𝔖l(u)}
where 𝔖n is the symmetric group of Vn.
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∈Xn,
∀σ∈𝔖n, f(u) = f(u⚬σ)
For n=0 it is trivial. Assume it for a given n.
Any u∈Xn+1 can be written u = v⋅x for
some v∈Xn and x∈X.
Then
∀σ∈𝔖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⚬σ) ∎
The quotient from term algebras to free monoids formed a simplification on the structure of
{e,•}-terms: the axioms of associativity and identity respectively removed the parenthesis and
occurrences of the identity element from terms, turning them into strings u∈Xn.
Then the quotient M ↠ M/R from free monoids to free commutative
monoids, reduces this structure further : it removes the role of the order of the domain
Vn of the string, reducing it to a structureless set of n elements, and seeing
two functions from finite sets to X as expressing the same element of M if they
match by a bijection between their domains. In other words, M/R can be represented
by the set of isomorphism classes of the overcategory 〈1E〉{0,+}/X
of functions from finite sets V (say, any subsets of some infinite set U) to X, to
be interpreted in commutative monoids by {0,+}-morphisms from ℘(V).
Another presentation of M/R 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.
This quotient is given by defining the image h∈ℕ(X) of u∈M by
h=(X∋x ↦ |u•(x)|).
Back to homepage :
Set theory and foundations
of mathematics
1. First foundations of
mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry