Sets
Much of algebra can be done using only very little set theory; all that is needed is a
means of comparing infinite sets, and the axiom of choice in the form of Zorn's
lemma. These topics occupy Sections 1.1 and 1.2. They are followed in Section 1.3
by an introduction to graph theory. This is an extensive theory with many applica-
tions in algebra and elsewhere; all we shall do here is to present a few basic results,
some of which will be used later, which convey the flavour of the topic.
1.1 Finite, Countable and Uncountable Sets
Most of our readers will have met sets before; a set for us is a collection of objects, its
members or elements. These elements may themselves be sets; of course one has to be
careful to avoid situations like Russell's paradox: 'the set Q of all sets that are not
members of themselves'; this quickly leads to a contradiction when one asks if
Q E Q. There are several ways of resolving this paradox, but they will not concern
us here; all that is needed is some care in forming 'large' sets.
Given two sets, we may wish to compare them for size, i.e. the number of elements
in each. We can use the natural numbers to count the members, but this may not be
necessary. When Man Friday wanted to tell Robinson Crusoe that he had seen a boat
with 17 men in it, he did this by exhibiting another 17-element set, and he could do
this without being able to count up to 17. Even for a fully numerate person it may be
easier to compare two sets rather than to count each; e.g. in a full lecture room a
brief glance may suffice to convince us that there are as many people as seats.
This suggests that it may be easier to determine when two sets have the same
'number of elements' than to find that number. Let us call two sets equipotent if
there is a bijection (i.e. a one-one correspondence) between them. This relation of
equipotence is an equivalence relation on any given collection of sets; here we
avoid talking about the collection of all sets, as that would bring us dangerously
close to the paradox mentioned above.
A set S is said to be finite, of cardinal n, if S is equipotent to the set {I, 2, ... , n}
consisting of the natural numbers from 1 to n. By convention the empty set, having
no elements, is reckoned among the finite sets; its cardinal is 0 and it is denoted
by 0.
,2 Sets
It is clear that two finite sets are equipotent if they have the same cardinal, and this
may be regarded as the basis of counting. It is also true that sets of different finite
cardinalities are not equipotent. This may seem intuitively obvious; we shall
assume it here and defer to FA its derivation from the axioms for the natural
numbers. More generally, we shall assume that for any natural numbers m, n, if
there is an injective mapping from {I, 2, ... , m} to {I, 2, ... , n}, then m :::: n. Let
us abbreviate {l, 2, ... , n} by [n], for any n EN. It follows that if there is a
bijection between [mJ and [n], then m:::: nand n :::: m, hence m = n. Thus for
any finite set, the natural number which indicates its cardinal is uniquely deter-
mined. The contrapositive form of the above assertion states that if m > n, then
there can be no injective mapping from [mJ to [nJ. A more illuminating way of
expressing this observation is Dirichlet's celebrated
Box Principle (Schubfachprinzip). If n + 1 objects are distributed over n boxes, then
some box must contain more than one of the objects.
Although intuitively obvious, this principle is of great use in number theory and
elsewhere.
Having given a formal definition of finite sets, we now define a set to be infinite if
it is not finite. Until relatively recent times the notion of 'infinity' was surrounded by
a good deal of mystery and uncertainty, even in mathematics. Thus towards the
middle of the 19th century, Bernard Bolzano propounded as a paradox the fact
that (in modern terms) an infinite set might be equipotent to a proper subset of
itself. A closer study reveals the fact that every infinite set has this property, and
this has even been taken as the basis of a definition of infinite sets; it certainly no
longer seems a paradox. The work of Georg Cantor, Richard Dedekind and others
from 1870 onwards has dispelled most of the uncertainties, and though mysteries
remain, they will not hamper us in the relatively straightforward use we shall
make of the theory.
In order to extend the notion of counting to infinite sets, we associate with every
set X, finite or not, an object IXI called its cardinal or cardinal number, defined in
such a way that two sets have the same cardinal iff they are equipotent. Such a defi-
nition is possible because, as we have seen, equipotence is an equivalence relation on
any collection of sets.
A non-empty finite set has as its cardinal a natural number; the empty set has
cardinal o. All other sets are infinite; their cardinals are said to be transfinite or
infinite. In particular, the set N of all natural numbers is infinite; its cardinal is
denoted by ~o. The letter aleph, ~, the first of the Hebrew alphabet, is customarily
used for infinite cardinal numbers. A set of cardinal ~o is also said to be countable
(or enumerable); thus A is countable iff there is a bijection from N to A. If a set A
is countable, it can be written in the form
(1.1.1 )
where the aj are distinct. Such a representation of A is called an enumeration of A,
and a proof that a set is countable will often consist in giving an enumeration. Some-
times the term 'enumeration' is used for a set written as in (1.1.1) even if the aj
, 1.1 Finite, Countable and Uncountable Sets 3
are not all distinct; in that case we can always produce a strict enumeration by going
through the sequence and omitting all repetitions. The set so obtained is finite or
countable.
Many sets formed from countable sets are again countable, as our first result
shows:
Theorem 1.1.1. Any subset and any quotient of a countable set is countable or finite. If
A and B are countable sets, then the union A U B and Cartesian product A x Bare
again countable; more generally, the Cartesian product of any finite number of count-
able sets is countable. Further, a countable union of countable sets is countable and the
collection of all finite subsets of a countable set is countable.
We recall that a quotient set of A is the set of all blocks, i.e. equivalence classes, of
some equivalence on A.
Proof. Any countable set A may be taken in the form (1.1.1); if A' is a subset, we go
through the sequence ai, az, ... of elements of A and omit all terms not in A'to
obtain an enumeration of A'. If A" is a quotient set, and x I~ X is the natural
mapping from A to A", then {a I, az, ... } is an enumeration of A", possibly with
repetitions; hence A" is countable (or finite).
Next let A be given by (1.1.1) and let B = {bl, bz, ... }; then A U B may be enum-
erated as {ai, bl , a2, bz , ... }, where repetitions (which will occur if An B #- 0) may
be discarded. Similarly we can enumerate A x B as {(ai, bl ), (a" b2), (az, b l ),
(ai, b3), (az, bz ), (a3, bl ), ... } by writing A x B as a square table and going along the
finite diagonals. Now the result for a product of r countable sets follows by induction
on r. Ifwe have a countable family {An} of countable sets, say An = {ani}, then we can
enumerate the union U A = {and n, i E N} by writing the elements ani as a matrix and
going again along the diagonals.
Finally let A be any countable set and denote by AT for r = 1,2, ... the set of all
r-element subsets of A. Clearly AT is countable, for it may be mapped into the
Cartesian power AT by the rule
where iJ, ... , jT is the sequence ii, ... , iT arranged in ascending order. This provides
a bijection of AT with a subset of AT, and it follows that Ar is countable. Now the
earlier proof shows that the union U Ar is countable, and adding 0 as a further
member we still have a countable set. •
With the help of this result many sets can be proved to be countable which do not
at first sight appear to be so. Thus the set Z of all integers can be written as a union of
N = {I, 2, ... } and N' = to, -1, -2, ... }; both Nand N ' are countable hence so is
Z. The set Q+ of all positive rational numbers is countable, as the image ofNz under
the mapping (a, b) I~ ab- I • Now Q itself can be written as the union of the set of
all positive rational numbers, the negative rational numbers and 0; therefore Q is
countable. The set of all algebraic numbers (see Section 7.1 below) is countable:
Much of algebra can be done using only very little set theory; all that is needed is a
means of comparing infinite sets, and the axiom of choice in the form of Zorn's
lemma. These topics occupy Sections 1.1 and 1.2. They are followed in Section 1.3
by an introduction to graph theory. This is an extensive theory with many applica-
tions in algebra and elsewhere; all we shall do here is to present a few basic results,
some of which will be used later, which convey the flavour of the topic.
1.1 Finite, Countable and Uncountable Sets
Most of our readers will have met sets before; a set for us is a collection of objects, its
members or elements. These elements may themselves be sets; of course one has to be
careful to avoid situations like Russell's paradox: 'the set Q of all sets that are not
members of themselves'; this quickly leads to a contradiction when one asks if
Q E Q. There are several ways of resolving this paradox, but they will not concern
us here; all that is needed is some care in forming 'large' sets.
Given two sets, we may wish to compare them for size, i.e. the number of elements
in each. We can use the natural numbers to count the members, but this may not be
necessary. When Man Friday wanted to tell Robinson Crusoe that he had seen a boat
with 17 men in it, he did this by exhibiting another 17-element set, and he could do
this without being able to count up to 17. Even for a fully numerate person it may be
easier to compare two sets rather than to count each; e.g. in a full lecture room a
brief glance may suffice to convince us that there are as many people as seats.
This suggests that it may be easier to determine when two sets have the same
'number of elements' than to find that number. Let us call two sets equipotent if
there is a bijection (i.e. a one-one correspondence) between them. This relation of
equipotence is an equivalence relation on any given collection of sets; here we
avoid talking about the collection of all sets, as that would bring us dangerously
close to the paradox mentioned above.
A set S is said to be finite, of cardinal n, if S is equipotent to the set {I, 2, ... , n}
consisting of the natural numbers from 1 to n. By convention the empty set, having
no elements, is reckoned among the finite sets; its cardinal is 0 and it is denoted
by 0.
,2 Sets
It is clear that two finite sets are equipotent if they have the same cardinal, and this
may be regarded as the basis of counting. It is also true that sets of different finite
cardinalities are not equipotent. This may seem intuitively obvious; we shall
assume it here and defer to FA its derivation from the axioms for the natural
numbers. More generally, we shall assume that for any natural numbers m, n, if
there is an injective mapping from {I, 2, ... , m} to {I, 2, ... , n}, then m :::: n. Let
us abbreviate {l, 2, ... , n} by [n], for any n EN. It follows that if there is a
bijection between [mJ and [n], then m:::: nand n :::: m, hence m = n. Thus for
any finite set, the natural number which indicates its cardinal is uniquely deter-
mined. The contrapositive form of the above assertion states that if m > n, then
there can be no injective mapping from [mJ to [nJ. A more illuminating way of
expressing this observation is Dirichlet's celebrated
Box Principle (Schubfachprinzip). If n + 1 objects are distributed over n boxes, then
some box must contain more than one of the objects.
Although intuitively obvious, this principle is of great use in number theory and
elsewhere.
Having given a formal definition of finite sets, we now define a set to be infinite if
it is not finite. Until relatively recent times the notion of 'infinity' was surrounded by
a good deal of mystery and uncertainty, even in mathematics. Thus towards the
middle of the 19th century, Bernard Bolzano propounded as a paradox the fact
that (in modern terms) an infinite set might be equipotent to a proper subset of
itself. A closer study reveals the fact that every infinite set has this property, and
this has even been taken as the basis of a definition of infinite sets; it certainly no
longer seems a paradox. The work of Georg Cantor, Richard Dedekind and others
from 1870 onwards has dispelled most of the uncertainties, and though mysteries
remain, they will not hamper us in the relatively straightforward use we shall
make of the theory.
In order to extend the notion of counting to infinite sets, we associate with every
set X, finite or not, an object IXI called its cardinal or cardinal number, defined in
such a way that two sets have the same cardinal iff they are equipotent. Such a defi-
nition is possible because, as we have seen, equipotence is an equivalence relation on
any collection of sets.
A non-empty finite set has as its cardinal a natural number; the empty set has
cardinal o. All other sets are infinite; their cardinals are said to be transfinite or
infinite. In particular, the set N of all natural numbers is infinite; its cardinal is
denoted by ~o. The letter aleph, ~, the first of the Hebrew alphabet, is customarily
used for infinite cardinal numbers. A set of cardinal ~o is also said to be countable
(or enumerable); thus A is countable iff there is a bijection from N to A. If a set A
is countable, it can be written in the form
(1.1.1 )
where the aj are distinct. Such a representation of A is called an enumeration of A,
and a proof that a set is countable will often consist in giving an enumeration. Some-
times the term 'enumeration' is used for a set written as in (1.1.1) even if the aj
, 1.1 Finite, Countable and Uncountable Sets 3
are not all distinct; in that case we can always produce a strict enumeration by going
through the sequence and omitting all repetitions. The set so obtained is finite or
countable.
Many sets formed from countable sets are again countable, as our first result
shows:
Theorem 1.1.1. Any subset and any quotient of a countable set is countable or finite. If
A and B are countable sets, then the union A U B and Cartesian product A x Bare
again countable; more generally, the Cartesian product of any finite number of count-
able sets is countable. Further, a countable union of countable sets is countable and the
collection of all finite subsets of a countable set is countable.
We recall that a quotient set of A is the set of all blocks, i.e. equivalence classes, of
some equivalence on A.
Proof. Any countable set A may be taken in the form (1.1.1); if A' is a subset, we go
through the sequence ai, az, ... of elements of A and omit all terms not in A'to
obtain an enumeration of A'. If A" is a quotient set, and x I~ X is the natural
mapping from A to A", then {a I, az, ... } is an enumeration of A", possibly with
repetitions; hence A" is countable (or finite).
Next let A be given by (1.1.1) and let B = {bl, bz, ... }; then A U B may be enum-
erated as {ai, bl , a2, bz , ... }, where repetitions (which will occur if An B #- 0) may
be discarded. Similarly we can enumerate A x B as {(ai, bl ), (a" b2), (az, b l ),
(ai, b3), (az, bz ), (a3, bl ), ... } by writing A x B as a square table and going along the
finite diagonals. Now the result for a product of r countable sets follows by induction
on r. Ifwe have a countable family {An} of countable sets, say An = {ani}, then we can
enumerate the union U A = {and n, i E N} by writing the elements ani as a matrix and
going again along the diagonals.
Finally let A be any countable set and denote by AT for r = 1,2, ... the set of all
r-element subsets of A. Clearly AT is countable, for it may be mapped into the
Cartesian power AT by the rule
where iJ, ... , jT is the sequence ii, ... , iT arranged in ascending order. This provides
a bijection of AT with a subset of AT, and it follows that Ar is countable. Now the
earlier proof shows that the union U Ar is countable, and adding 0 as a further
member we still have a countable set. •
With the help of this result many sets can be proved to be countable which do not
at first sight appear to be so. Thus the set Z of all integers can be written as a union of
N = {I, 2, ... } and N' = to, -1, -2, ... }; both Nand N ' are countable hence so is
Z. The set Q+ of all positive rational numbers is countable, as the image ofNz under
the mapping (a, b) I~ ab- I • Now Q itself can be written as the union of the set of
all positive rational numbers, the negative rational numbers and 0; therefore Q is
countable. The set of all algebraic numbers (see Section 7.1 below) is countable:
