And in this case we define the equivalence class [x] of x to be the set of
all y ∈ X being equivalent to x, that is [x] := { y ∈ X | x ∼ y }. And
the set of all equivalence classes is denoted by X/∼ := { [x] | x ∈ X }.
Example: if f : X → Y is any function then we obtain an equivalence
relation ∼ on X by letting x ∼ y :⇐⇒ f (x) = f (y). And the
equivalence class of x ∈ X is just the fiber [x] = f −1 (f (x)).
• Consider a nonempty set X 6= ∅ once more. Then a family of subsets
P ⊆ P(X) is said to be a partition of X, iff for any P , Q ∈ P we
obtain the statements
[
X = P
P 6= ∅
P 6= Q =⇒ P ∩Q=∅
Example: if ∼ is an equivalence relation on X, then X/∼ is a partition
of X. Conversely if P is a partition of X, then we obtain an equivalence
relation ∼ on X by letting x ∼ y :⇐⇒ ∃ P ∈ P : x ∈ P and y ∈ P .
Hence there is a one-to-one correspondence between the equivalence
relations on X and the partitions of X given by ∼ 7→ X/∼.
• Consider any nonempty set I 6= ∅, then a relation ≤ on I is said to be
a parial order on I, iff it is reflexive, transitive and anti-symmetric.
Formally that is for any i, j and k ∈ I we get
i=j =⇒ i≤j
i ≤ j, j ≤ k =⇒ i≤k
i ≤ j, j ≤ i =⇒ i=j
And ≤ is said to be a total or linear order iff for any i, j ∈ I we
also get i ≤ j or j ≤ i (that is any two elements contained in I can
be compared). Example: for any set X the inclusion relation ⊆ is a
partial (but not linear) order on P(X). If now ≤ is a linear order on
I, then we define the minimum and maximum of i, j ∈ I to be
½ ½
i if i ≤ j j if i ≤ j
i ∧ j := i ∨ j :=
j if j ≤ i i if j ≤ i
• Now consider a partial order ≤ on the set X and a subset A ⊆ X.
Then we define the set A∗ of minimal respectively the set A∗ of max-
imal elements of A to be the following
A∗ := { a∗ ∈ A | ∀ a ∈ A : a ≤ a∗ =⇒ a = a∗ }
A∗ := { a∗ ∈ A | ∀ a ∈ A : a∗ ≤ a =⇒ a = a∗ }
11
And an element a∗ ∈ A∗ is said to be a minimal element of A. Likewise
a∗ ∈ A∗ is said to be a maximal element of A. Note that in general
it may happen that A has several minimal (or maximal) elements or
even none at all (e.g. N∗ = { 0 } and N∗ = ∅). For a linear order
minimal (and maximal) elements are unique however.
• Finally ≤ is said to be a well-ordering on the set X, iff ≤ is a linear
order on X such that any non-empty subset A ⊆ X has a (already
unique) minimal element. Formally that is
∀ ∅ 6= A ⊆ X ∃ a∗ ∈ A such that ∀ a ∈ A : a∗ ≤ a
• Let X be any set, then the cardinality of X is defined to be the class
of all sets that correspond bijectively to X. Formally that is
|X| := { Y | ∃ ω : X → Y bijective }
Note that most textbooks on set theory define the cardinaltity to be
a certain representant of our |X| here. However the exact definition is
of no importance to us, what matters is comparing cardinalities: we
define the following relation ≤ between cardinals:
|X| ≤ |Y | :⇐⇒ ∃ ι : X → Y injective
⇐⇒ ∃ π : Y → X surjective
|X| = |Y | :⇐⇒ ∃ ω : X → Y bijective
⇐⇒ |X| ≤ |Y | and |Y | ≤ |X|
Note that the first equivalency can be proved (as a standard excercise)
using equivalency relations and a choice function (axiom of choice).
The second equivalency is a rather non-trivial statement called the
equivalency theorem of Bernstein. However these equivalencies grant
that ≤ has the properties of a partial order, i.e. reflexivity, transitivity
and anti-symmetry.
• (♦) We will introduce and use several different notions of substruc-
tures and isomorphy. In order to avoid eventual misconceptions, we
emphasise the kinds of structures regarded by applying subscripts to
the symbols ≤ and £ of substructures and ∼ = of isomorphy. E.g. we
will write R ≤r S to indicate, that R is a subring of S, a £i R to
indicate that a is an ideal of R and R ∼ =r S to indicate that R and S
are isomorphic as rings. Note that the latter is different from R ∼
=m S
(R and S are isomorphic as modules). And this did make sense, since
R ≤r S and hence R and S can be regarded as R-modules. We will
use the same subscripts for generated algebraic substructures, i.e. h• ir
for rings, h• ii for ideals and h• im for modules.
12