Direct Products and Relations

The present unit is part of the following walks

Introduction

Please note that the text on this web page gives a summary of the Unit Unions and Intersections of Sets. A full text including the proofs is available as a separate pdf document at the end of this page.

The present unit deals with two important concepts of mathematics: The first concept is the direct product

$$
A \times B := \{ (a, b) \mid a \in A, \: b \in B \}
$$

of two sets $A$ and $B$.

The second concepts is the equivalence relation which plays a crucial role in almost all branches of mathematics. The present unit is organized as follows:

Ordered pairs:

A set $\{ a, b \}$ consists of two elements $a$ and $b$ where the order of the two elements $a$ and $b$ does not play any role. In fact, we have $\{ a, b \} = \{ b, a \}$.

The main property of an ordered pair $(a, b)$ is to introduce an order and to distinguish between the two pairs $(a, b)$ and $(b, a)$ if $a \neq b$. The challenge is to find a definition of the pair $(a, b)$ within the set-theoretical framework of Zermelo and Fraenkel (for details about this framework see Unit Universe).

A good solution for this problem is the definition

$$
(a, b) := \big\{ a, \{ a, b \} \big\}.
$$

See Definition [#nst-def-ordered-pair]. The main property of ordered pairs is the fact that

$$
(a, b) = (c, d) \mbox{ if and only if } a = c \mbox{ and } b = d.
$$

See Theorem [#nst-th-ordered-pair-elementary].

The direct product of two sets:

The direct product of two sets $A$ and $B$ is the set

$$
A \times B := \{ (a, b) \mid a \in A, \: b \in B \}.
$$

The formal definition is given in Definition [#nst-def-direct-product]. Elementary properties of the direct product are equations of the form

\begin{eqnarray*}
(A \cup B) \times C & = & (A \times C) \cup (B \times C) \mbox{ and} \\
(A \cap B) \times C & = & (A \times C) \cap (B \times C).
\end{eqnarray*}

which are explained in Proposition [#nst-prop-direct-product-union].

Relations:

Relations are used to express that two elements (or two sets) $x$ and $y$ are related by a property, for example $x < y$ or $y = x^2$ or $x \subseteq y$. In everyday life two persons $X$ and $Y$ may be related if $X$ is the father of $Y$ or if $X$ and $Y$ are brothers. For example, if we have

$$
A := \mathbb{N} \mbox{ and } B := \{1, 2, 3, 4, 5, 6\},
$$

the relation $a$ is a divisor of $b$ can be expressed by the following subset $R$ of the direct product $A \times B = \mathbb{N} \times \{1, 2, 3, 4, 5, 6\}$:

$$
R = \{ (1,1), (1, 2), (2, 2), (1, 3), (3, 3), (1, 4), (2, 4), (4, 4), (1, 5), (5, 5), (1, 6), (2, 6), (3, 6), (6, 6) \}.
$$

There are various types of relations. The most important are:

Functions: A function $f : A \rightarrow B$ is a relation $R$, that is, a subset of the direct product $A \times B$ such that for each element $x$ of the set $A$ there exists exactly one element $y$ of the set $B$ such that

$$
(x, y) \in R.
$$

We set $y := f(x)$. Functions are explained in detail in Unit Functions.

Order relations: Typical order relations are the subset relation $\subseteq$ on a set of sets or the relation $\leq$ on a set of numbers. They are discussed in detail in Unit Ordered Sets and the Lemma of Zorn.

Equivalence relations: They are discussed in detail in Section Equivalence Relations.

Equivalence relations and partitions:

Let us consider the following example: We have six balls, three of them are blue, two of them are red, and one ball is green.
Then we can partion our set of six balls into three pairwise disjoint sets of blue, red and green balls, respectively.

More generally, we have a set $A$ and a set $P$ of properties such that each element $x$ of the set $A$ has exactly one property $p(x)$ of the set $P$. This idea can be expressed via an equivalence relation: Two elements $x$ and $y$ (for example, two balls) are called equivalent if and only if they have the same property $p$ (for example, if they have the same color). The set of the elements with a same property $p$ (for example, all red balls) form a so-called equivalence class.

An equivalence relation can also be expressed without explicitly mentioning the property $p$. This is done as follows: For a set $A$ we call a relation $\sim$ between the elements of the set $A$ an equivalence relation if the following conditions are fulfilled:

The relation $\sim$ is reflexive, that is, we have $x \sim x$ for all elements $x$ of the set $A$.

The relation $\sim$ is symmetric, that is, the relation $x \sim y$ implies the relation $y \sim x$ for all elements $x$ and $y$ of the set $A$.

The relation $\sim$ is transitive, that is, the relations $x \sim y$ and $y \sim z$ imply the relation $x \sim z$ for all elements $x$, $y$ and $z$ of the set $A$ (see Definition [#nst-def-equivalence-relation]).

For an equivalence relation $\sim$ on a set $A$ and an element $x$ of the set $A$ the set

$$
A_x := \{ z \in A \mid z \sim x \}
$$

is called an equivalence class (Definition [#nst-def-equivalence-relation]).

Equivalence classes have the following two important properties:

$$
A_x = A_y \mbox{ or } A_x \cap A_y = \emptyset \mbox{ for all } x, y \in A \mbox{ and } A = \bigcup_{x \in A} A_x,
$$

as shown in Proposition [#nst-prop-equivalent-class]. In other words, the equivalence classes of an equivalence relation define a so-called partition (see Definition [#nst-def-partition]), and partitions define equivalence relations (Theorem [#nst-th-equivalence-relation-partition]).

This is explained in detail in Section Equivalence Relations. A good example for the use of equivalence classes is the definition of the rational numbers based on the integers. This is explained in Unit [Rational Numbers – in preparation].

Background

We will define direct products and relations within the framework of the axioms of Zermelo and Fraenkel. We suppose that the reader is familiar with the following results (for more details see Unit Universe and Unit Unions):

Remark. We recall the following axioms of Zermelo and Fraenkel:

(a) Axiom of extension: Two sets $A$ and $B$ are equal if and only if

$$
A \subseteq B \mbox{ and } B \subseteq A
$$

(see Unit Universe).

(b) Axiom of specification: Let $A$ be a set, and let $\varphi(x)$ be a sentence containing the variable $x$ (for the definition of a sentence see Unit Universe). Then the sets

$$
\{ x \in A \mid \varphi(x) \} \mbox{ and } \{ x \subseteq A \mid \varphi(x) \}
$$

exist (see Unit Universe).

(c) Axiom of pairing: Let $A$ and $B$ be two sets. Then the sets $\{A\}$ and $\{A, B\}$ exist (see Unit Unions).

(d) Axiom of unions: Let ${\cal A}$ be a set of sets. Then the union $A := \bigcup_{X \in {\cal A}} X$ exists (see Unit Unions).

(e) Axiom of power: Let $A$ be a set. Then the power set of the set $A$, that is, the set of all subsets of the set $A$ exists (see Unit Unions).

In addition, we will make use of the following result:

Proposition. (a) Let $A$ and $B$ be two sets. Then the union $A \cup B$ exists.

(b) Let $A$ and $B$ be two sets. Then the intersection $A \cap B$ exists.

(c) Let ${\cal A}$ be a non-empty set of sets. Then the intersection $A := \bigcap_{X \in {\cal A}} X$ exists.

Ordered Pairs

Definition of an Ordered Pair:

Definition. Let $a$ and $b$ be two sets.

The ordered pair $(a, b)$ is defined by $(a, b) := \big\{ \{a\}, \{a, b\} \big\}$.

French / German. Ordered pair = Paire ordonnée = Geordnetes Paar.

Note that the existence of the set $(a, b) := \big\{ \{a\}, \{a, b\} \big\}$ follows from the axiom of pairing (see Remark [#nst-rem-ax-zermelo]).

Elementary Properties of Ordered Pairs:

Proposition. Let $a$, $b$, $c$ and $d$ be some sets.

(a) If $\{a\} = \{b\}$, then we have $a = b$.

(b) If $\{a\} = \{b, c\}$, then we have $a = b = c$.

(c) If $\{a, b\} = \{c, d\}$, then we have $a = c$ and $b = d$ or $a = d$ and $b = c$.

(d) If $\big\{ \{a\}, \{a, b\} \big\} = \big\{ \{c\}, \{c, d\} \big\}$, then we have $a = c$ and $b = d$.

Theorem. Let $a$ and $b$ be two sets.

(a) If $a = b$, then we have $(a, b) = (a, a) = \big\{ \{a\} \big\}$.

(b) If $a \neq b$, then we have $(a, b) \neq (b, a)$.

(c) Let $a$, $a’$, $b$ and $b’$ be four sets. Then we have

$$
(a, b) = (a’, b’) \mbox{ if and only if } a = a’ \mbox{ and } b = b’.
$$

(d) Suppose that the sets $a$ and $b$ are elements of the sets $A$ and $B$, respectively. Then the ordered pair $(a, b)$ is an element of the set ${\cal P} \big( {\cal P} (A \cup B) \big)$.

Historical Note:

The use of ordered pairs goes back to analytical geometry where the pair $(x, y)$ is used to describe a point in the real plane by coordinates.

The definition of an ordered pair in the context of the axioms of Zermelo and Fraenkel (see Unit Universe) as stated in Definition [#nst-def-ordered-pair] is due to Casimir Kuratowski:

Nous terminons cette note par une remarque suivante sur la notion de paire ordonnée.

Soit $A$ un ensemble composé de deux éléments $a$ et $b$. Il n’existe que deux classes, qui établissnet un ordre dans $A$ à savoir:

$$
\big( (a, b), (a) \big) \mbox{ et } \big( (a, b), (b) \big).
$$

[…]

Definition V. La classe $\big( (a, b), (a) \big)$ est une paire ordonnée dont $a$ est le premier élément et $b$ le second.

See [Kuratowski-1921], p.171.

We close this note with the following remark about the notion of an ordered pair:

Let $A$ be a set consisting of two elements $a$ and $b$. There are only two classes which establish an order on $A$, namely:

$$
\big( (a, b), (a) \big) \mbox{ et } \big( (a, b), (b) \big).
$$

[…]

Definition V. The set $\big( (a, b), (a) \big)$ is called an ordered pair where $a$ is the first element and $b$ the second.

(Translation by the author.)

Note that Kuratowski uses the brackets $( \ldots )$ for $\{ \ldots \}$.

An earlier definition of an ordered pair in the same spirit is due to Felix Hausdorff:

Übrigens läßt sich, wenn man will, der Begriff des geordneten Paares $(a, b)$ auf den Mengenbegriff zurückführen. Sind 1, 2 zwei voneinander wie von $a$ und $b$ verschiedene Elemente, so hat das Paar von Paaren

$$
\big\{ \{a, 1\}, \{b, 2\} \big\}
$$

genau die formalen Eigenschaften des geordneten Paares $(a, b)$, nämlich die Unvertauschbarkeit von $a$ und $b$ im Falle der Verschiedenheit beider Elemente. […]

See [Hausdorff-1914], p. 32.

By the way, if you want, the notion of an ordered pair $(a, b)$ can be attributed to the notion of sets. If 1 and 2 are two different elements which are also different from $a$ and $b$, then the pair of pairs

$$
\big\{ \{a, 1\}, \{b, 2\} \big\}
$$

has exactly the formal properties of the ordered pair $(a, b)$, namely the non-commutativity of $a$ and $b$ if they are distinct. […]

(Translation by the author.)

The definition of Hausdorff has the small disadvantage that the elements 1 and 2 depend on the elements $a$ and $b$ due to the condition

$$
\{a, b\} \cap \{1, 2\} = \emptyset.
$$

The Direct Product of Two Sets

Definition of the Direct Product:

Definition. Let $A$ and $B$ be two sets. Set

$$
A \times B := \{ x \in {\cal P} \big( {\cal P} (A \cup B) \big) \mid \exists \: a \in A \: \exists \: b \in B \mbox{ s.t. } x = (a, b) \}.
$$

(a) The set $A \times B$ is called the direct product of the sets $A$ and $B$} or, equivalently, the Cartesian product of the sets $A$ and $B$.

(b) We write $A \times B := \{ (a, b) \mid a \in A \mbox{ and } b \in B \}$ for short.

French / German. Direct product = Produit direct = Direktes Produkt.

Note that it follows from Proposition [#nst-prop-ax-pairing] that the set $A \cup B$ exists. It follows from the axiom of powers (see Remark [#nst-rem-ax-zermelo]) that the power set ${\cal P} \big( {\cal P} (A \cup B) \big)$ exists. It follows from the axiom of specification (see Remark [#nst-rem-ax-zermelo]) that the set $A \times B$ exists for all sets $A$ and $B$. Finally, it follows from Theorem [#nst-th-ordered-pair-elementary] that the pairs $(a, b)$ are contained in the direct product $A \times B$.

Example. Let $A := \{a, b\}$ and $B := \{c, d\}$. Then we have

$$
A \times B = \{(a, c), (a, d), (b, c), (b, d)\}.
$$

When is $A \times B = \emptyset$?

Proposition. Let $A$ and $B$ be two sets.

(a) We have $A = \emptyset \mbox{ or } B = \emptyset \mbox{ if and only if } A \times B = \emptyset$.

(b) We have $A \neq \emptyset \mbox{ and } B \neq \emptyset \mbox{ if and only if } A \times B \neq \emptyset$.

Elementary Properties of the Direct Product:

Proposition. Let $A$, $B$, $C$ and $D$ be four sets, and suppose that we have $A \neq \emptyset$ and $B \neq \emptyset$. Then we have

$$
A \subseteq C \mbox{ and } B \subseteq D \mbox{ if and only if } A \times B \subseteq C \times D.
$$

Proposition. Let $A$, $B$, $C$ and $D$ be four sets.

(a) Suppose that the sets $A$, $B$, $C$ and $D$ are all non-empty. Then we have

$$
A \times B = C \times D \mbox{ if and only if } A = C \mbox{ and } B = D.
$$

(b) Suppose that $A = \emptyset$ or $B = \emptyset$. Then we have

$$
A \times B = C \times D \mbox{ if and only if } C = \emptyset \mbox{ or } D= \emptyset.
$$

Proposition. Let $A$, $B$, $C$ and $D$ be four sets.

(a) We have $(A \cup B) \times C = (A \times C) \cup (B \times C)$.

(b) We have $(A \cap B) \times C = (A \times C) \cap (B \times C)$.

(c) We have $(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D) = (A \times D) \cap (B \times C).$

(d) We have $(A \cup B) \times (C \cup D) = (A \times C) \cup (A \times D) \cup (B \times C) \cup (B \times D).$

(e) We have $(A \setminus B) \times C = (A \times C) \setminus (B \times C)$.

Historical Note:

The direct product of two sets has been defined by Georg Cantor (see the historical remark of Bourbaki in [Bourbaki-2006], p. E.IV 41, footnote 2):

Jedes Element $m$ einer Menge $M$ lässt sich mit jedem Elemente $n$ einer anderen Menge $N$ zu einem neuen Elemente $(m, n)$ verbinden; für die Menge aller dieser Verbindungen $(m, n)$ setzen wir die Bezeichnung $(M.N)$ fest. Wir nennen sie die Verbindungsmenge von $M$ und $N$.

See [Cantor-1895], p. 485.

Each element $m$ of a set $M$ can be combined with an element $n$ of another set $N$ to get a new element $(m, n)$; the set of all of these combinations $(m, n)$ is denoted by $(M.N)$. We call it the combination set of $M$ and $N$.

(Translation by the author.)

The combination $(M.N)$ is the direct product $M \times N$.

In his axiomatic foundation [Zermelo-1908b] Zermelo gives a definition of the direct product of two sets based on the existing axioms. So he needs a formal definition of the pair $(m, n)$ as a specific set whose existence is guaranteed by the existing axioms. His solution is to define the direct product of two sets $A$ and $B$ only if the sets $A$ and $B$ are disjoint. Then the definition $(a, b) := \{a, b\}$ fulfills the important property that

$$
(a, b) = (a’, b’) \mbox{ if and only if } a = a’ \mbox{ and } b = b’ \mbox{ for all } a, a \in A \mbox{ and } b, b’ \in B.
$$

Es sei nun $T$ eine Menge, deren Elemente $M, N, R, \ldots$ lauter (untereinander elementfremde) Mengen sein mögen, […]. Alle Untermengen $S_1 \in \mathfrak{S}T$ [$= \bigcup_{X \in T} X$], welche mit jedem Elemente von $T$ genau ein Element gemein haben, bilden also nach III [axiom of specification] die Elemente einer Menge $P = \mathfrak{P}T$, welche […] als das Produkt der Mengen $M, N, R, \ldots$ bezeichnet werden soll. […]

See [Zermelo-1908b], p. 266.

Now let $T$ be a set whose elements $M, N, R, \ldots$ are various (mutually disjoint) sets, […]. All subsets $S_1$ of $\mathfrak{S}T$ [$= \bigcup_{X \in T} X$] that have exactly one element in common with each element of $T$ then are, according to Axiom III [axiom of specification], the elements of a set $P = \mathfrak{P}T$, which […] will be called […] the product of the sets $M, N, R, \ldots$. […]

See [Zermelo-1908b-en], p. 204.

A definition of the direct product for not necessarily mutually disjoint sets is for example introduced in the Grundzüge der Mengenlehre of Felix Hausdorff [Hausdorff-1914], pp. 36 – 37, based on the ordered pairs defined by Hausdorff (see Historical notes of Section Ordered Pairs).

Relations

Definition of a Relation:

Definition. Let $A$ and $B$ be two sets.

(a) Every subset $R$ of the direct product $A \times B$ is called a relation on the direct product $A \times B$. More precisely, the set $R$ is called a binary relation.

(b) If $A = B$, a relation $R$ on the direct product $A \times B = A \times A$ is called a relation on the set $A$.

(c) Let $R \subseteq A \times B$ be a relation. Two elements $a$ of the set $A$ and $b$ of the set $B$ are called related with respect to the relation $R$ if the pair $(a, b)$ is contained in the set $R$.
If the elements $a$ and $b$ are related with respect to the relation $R$, we write $a \: R \: b$.

(d) Often we denote a relation $R$ by a symbol like $*$ or $\sim$. We then speak of the relations $*$ or $\sim$, and we write $x * y$ or $x \sim y$ if the elements $x$ and $y$ are related with respect to the relation $*$ or $\sim$, respectively.

French / German. Relation = Relation = Relation.

Relations are very common in everyday life: If $A$ and $B$ are two sets of persons, two persons $a$ and $b$ of the set $A$ and of the set $B$, respectively may be called related if they are friends, if they are married of if they belong to the same family.

Examples. Let $A$ and $B$ be two sets, and let $R$ be a relation on the direct product $A \times B$.

(a) If $R = \emptyset$, there are no two elements $a$ of the set $A$ and $b$ of the set $B$ that are related with respect to the relation $R$.

(b) If $R = A \times B$, any two elements $a$ of the set $A$ and $b$ of the set $B$ are related with respect to the relation $R$.

(c) Let $R := \{(a, b) \in A \times A \mid a = b \}$. Then we have

$$
a \: R \: b \mbox{ if and only if } a = b.
$$

(d) Let ${\cal P} := {\cal P}(A)$ be the power set of the set $A$, and let $R := \{(x, X) \in A \times {\cal P} \mid x \in X \}$. Then we have

$$
x \: R \: X \mbox{ if and only if } x \in X.
$$

(e) Let $X$ be a set, let ${\cal P} := {\cal P}(X)$ be the power set of the set $X$, and let

$$
R := \{(X, Y) \in {\cal P} \times {\cal P} \mid X \subseteq Y \}.
$$

Then we have

$$
X \: R \: Y \mbox{ if and only if } X \subseteq Y.
$$

Important Types of Relations:

Definition. Let $A$ be a set, and let $*$ be a relation on the set $A$.

(a) The relation $*$ is called reflexive if we have $x * x$ for all elements $x$ of the set $A$.

(b) The relation $*$ is called symmetric if we have $x * y$ if and only if $y * x$ for all elements $x$ and $y$ of the set $A$.

(c) The relation $*$ is called antisymmetric if $x * y$ and $y * x$ implies $x = y$ for all elements $x$ and $y$ of the set $A$.

(d) The relation $*$ is called transitive if for each three elements $x$, $y$ and $z$ of the set $A$ the relations $x * y$ and $y * z$ imply $x * z$.

French / German. Reflexive = Réflexive = Reflexif; Symmetric = Symétrique = Symmetrisch; Antisymmetric = Antisymétrique = Antisymmetrisch; Transitive = Transitive = Transitif.

Examples. We consider the relations introduced in Example [#nst-ex-relation].

(a) The relations $=$ and $\subseteq$ are reflexive.

(b) The relation $=$ is symmetric.

(c) The relation $\subseteq$ is antisymmetric.

(d) The relations $=$ and $\subseteq$ are transitive.

Historical Note:

An early example of an abstract definition of relations is contained in Guiseppe Peano’s Principles of Arithmetics:

2. Sint $x$, $y$ entia quaecumque; systema ex ente $x$ et ex ente $y$ compositum ut novum ens consideramus, et signo $(x, y)$ indicamus; similiterque si entium numerus maior fit. Sit $\alpha$ propositio indeterminata continens $x$, $y$; tunc $[(x, y) \varepsilon ] \alpha$ significat classem entibus $(x, y)$ constitutam, quae conditioni $\alpha$ satisfaciunt. […]

See [Peano-1899], p. xii.

2. Let $x$ and $y$ be any objects whatsoever; we consider as a new object the system composed of the object $x$ and of the object $y$, and we denote it by the sign $(x, y)$; and similarly if we have a greater number of objects. Let $\alpha$ be a proposition containing the indeterminates $x$ and $y$; then $[(x, y) \varepsilon ] \alpha$ means the class composed of the objects $(x, y)$ that satisfy the condition $\alpha$. […]

See [Peano-1899-en], p. 90.

In modern terminology the expression of Peano reads as follows:

$$
[(x, y) \varepsilon ] \alpha := \{ (x, y) \in X \times Y \mid \alpha(x, y) \}
$$

where $\alpha(x, y)$ is a sentence.

Equivalence Relations and Partitions

The most important relations are functions, equivalence relations and order relations. For functions see Unit Functions. For order relations see Unit Ordered Sets and the Lemma of Zorn.

Definition of Equivalence Relations:

Definition. Let $A$ be a non-empty set, and let $\sim$ be a relation on the set $A$.

(a) The relation $\sim$ is called an equivalence relation if it is reflexive, symmetric and transitive.

(b) Let $\sim$ be an equivalence relation, and let $x$ be an element of the set $A$. The set

$$
A_x := \{ y \in A \mid y \sim x \}
$$

is called an equivalence class with respect to the equivalence relation $\sim$.

(c) The quotient of the set $A$ with respect to the equivalence relation $\sim$ is the set

$$
\bar{A} := \{ A_x \mid x \in A \}.
$$

It is denoted by $\bar{A}$ or by $A / \sim$. The elements $A_x$ of the set $\bar{A} = A / \sim$ often are denoted by $\bar{x} := A_x$. We have

$$
\bar{A} = \{ \bar{x} \mid x \in A \}.
$$

French / German. Equivalence relation = Relation d’équivalence = Äquivalenzrelation.

Examples. Let $A := \{a, b, c, d\}$, and suppose that the elements $a$, $b$, $c$ and $d$ are pairwise distinct.

(a) Let $a \sim a$, $b \sim b$, $c \sim c$, $d \sim d$, $c \sim d$ and $d \sim c$. Then the relation $\sim$ is an equivalence relation with equivalence classes $A_a = \{a\}$, $A_b = \{b\}$ and $A_c = A_d = \{c, d\}$.

(b) Let $a \sim a$, $b \sim b$, $c \sim c$, $d \sim d$, $a \sim b$, $b \sim a$, $c \sim d$ and $d \sim c$. Then the relation $\sim$ is an equivalence relation with equivalence classes $A_a = A_b = \{a, b\}$ and $A_c = A_d = \{c, d\}$.

Remarks. (a) Note that an equivalence relation is only defined for a set $A$. The reason is that an equivalence relation is a relation on a set $A$, that is, a subset of the direct product $A \times A$.

(b) Note that the quotient $\bar{A}$ of a set $A$ with respect to an equivalence relation $\sim$ can be expressed as follows:

$$
\bar{A} = \big\{ Y \subseteq A \mid \exists \: x \in A \mbox{ such that } Y = A_x := \{ y \in A \mid y \sim x \} \big\}.
$$

By the axiom of specification (see Remark [#nst-rem-ax-zermelo]), the set $\bar{A}$ exists.

Elementary Properties of Equivalence Relations:

Proposition. Let $A$ be a set, and let $\sim$ be an equivalence relation on the set $A$. Let $x$ and $y$ be two elements of the set $A$, and let $A_x$ and $A_y$ be the equivalence classes of the elements $x$ and $y$, respectively.

(a) The element $x$ is contained in the set $A_x$.

(b) We have $x \sim y \mbox{ if and only if } A_x = A_y.$

(c) We have $A_x = A_y$ or $A_x \cap A_y = \emptyset$.

(d) We have $A = \bigcup_{x \in A} A_x$.

Definition of a Partition:

Definition. Let $A$ be a non-empty set, and let ${\cal C}$ be a set of non-empty subsets of the set $A$.

(a) The set ${\cal C}$ is called a partition of the set $A$ if the following conditions are fulfilled:

(i) We have $\bigcup_{C \in {\cal C}} C = A$.

(ii) We have $C \cap D = \emptyset$ for all elements $C$ and $D$ of the set ${\cal C}$ such that $C \neq D$.

(b) The union $A = \bigcup_{C \in {\cal C}} C$ is called a disjoint union.

French / German. Partition = Partition = Partition. Disjoint Union = Union disjointe = Disjunkte Vereinigung.

Example. Let $A := \{a, b, c, d\}$, and suppose that the elements $a$, $b$, $c$ and $d$ are pairwise distinct.

Then the sets
\begin{eqnarray*}
{\cal C} & := & \big\{ \{a\}, \{b\}, \{c, d\} \big\} \mbox{ and }\\
{\cal D} & := & \big\{ \{a, b\}, \{c, d\} \big\}
\end{eqnarray*}
are two partitions of the set $A$.

Equivalence Relations define Partitions and vice versa:

Theorem. Let $A$ be a non-empty set.

(a) Let $\sim$ be an equivalence relation on the set $A$. Then the equivalence classes of the set $A$ with respect to the relation $\sim$ form a partition of the set $A$.

(b) Let ${\cal C}$ be a partition of the set $A$. For two elements $x$ and $y$ of the set $A$, define $x \sim y$ if and only if there exists an element $C$ of the partition ${\cal C}$ containing both elements $x$ and $y$.
Then the relation $\sim$ is an equivalence relation on the set $A$.
The equivalence classes of the relation $\sim$ are exactly the sets of the partition ${\cal C}$.

Proposition. (a) Let $\sim$ be an equivalence relation on a set $A$, and let $B$ be a subset of the set $A$. Then the equivalence relation $\sim$ induces an equivalence relation on the set $B$.

(b) Let ${\cal C}$ be a partition of a set $A$, and let $B$ be a subset of the set $A$. Let

$$
{\cal D} := \{ X \cap B \mid X \subseteq A \mbox{ and } X \cap B \neq \emptyset \}.
$$

Then the set ${\cal D}$ is a partition of the set $B$.

Equivalence relations are one of the very powerful tools in mathematics. They often allow to reduce the complexity of the investigation of a set $A$ to the often less complex investigation of the set $\bar{A} := \{ A_x \mid x \in A \}$.

By the way, in everyday life equivalence relations do also play an important role. For example, the football players are grouped into football teams. We say that the French national football team has won the World Cup in 2018 which is much easier than to say that the team of the players … has won the World Cup.

Historical Note:

The history of equivalence relations and equivalence classes is rather complicated. In [Asghari-2019], Amir Asghari gives a detailed study of this history based on former research by David Fowler. We just recall a few points and recommend the lecture of Asghari’s article for further information.

Equivalence relations already appear implicitly in Euclid’s elements [Heath-1925]: A famous example is the parallelism of lines in an affine plane. However, Euclid did not introduce the concept of an equivalence relation, and he did not explicitly note that parallelism is reflexive or symmetric (which of course is trivial). However, Euclid has shown that parallelism is transitive:

Straight lines parallel to the same straight line are also parallel to one another.

See [Heath-1925] Section I, 30.

Another standard example, where equivalence relations are implicitly given, is the congruence of numbers: If $n$ is a natural number, we can define the equivalence relation $\sim$ on the integers by defining

$$
a \sim b : \Leftrightarrow n \mbox{ is a divisor of } a – b.
$$

According to Asghari the first abstract definition of an equivalence relation has been given by Philip Jourdain, but he called it an isoid relation:

I call a relation which is reflexive, symmetrical and transitive an isoid relation.

See [Jourdain-1912], p. 492.

The terminology of equivalence relations and equivalence classes has been introduced by Helmut Hasse in [Hasse-1926].

The word equivalence has already been used among others by Georg Cantor who calls two sets $A$ and $B$ equivalent ($ A \sim B$) if there exists a bijective mapping from the set $A$ onto the set $B$. He explicitly shows that the relation $\sim$ is reflexive, symmetric and transitive:

Zwei Mengen $M$ und $N$ nennen wir äquivalent und bezeichnen dies mit

(4) $M \sim N$ oder $N \sim M$,

wenn es möglich ist dieselben gesetzmäßig in eine deratige Beziehung zu einander zu setzen, dass jedem Element der einen von ihnen ein und nur ein Element der andern entspricht. […]

Jede Menge ist sich selbst äquivalent:

(5) $M \sim M$.

Sind zwei Mengen einer dritten äquivalent, so sind sie auch unter einander äquivalent:

(6) aus $M \sim P$ und $N \sim P$ folgt $M \sim N$.

See [Cantor-1895], p.482.

Two sets $M$ and $N$ are called equivalent which is denoted by

(4) $M \sim N$ or $N \sim M$

if it is possible to relate these two sets in a way that each element of one set corresponds to one and only one element of the other set. […]

Every set is equivalent to itself:

(5) $M \sim M$.

If two sets are equivalent to a third set, then they are also equivalent to each other:

(6) it follows from $M \sim P$ and $N \sim P$ that $M \sim N$.

(Translation by the author.)

Notes and References

I found a lot of interesting information in the book Théorie des ensembles of Bourbaki (see [Bourbaki-2006] or [Bourbaki-2004]). In particular, there are extensive historical notes.

A list of textbooks about set theory is contained in Unit [Literature about Set Theory].

[Asghari-2019] Asghari, Amir H. (2019). “Experiencing Equivalence but Organizing Order”. In: Educational Studies in Mathematics 71.3, pp. 219–234.

[Bourbaki-2004] Bourbaki, Nicolas (2004). Theory of Sets. Berlin, Heidelberg, and New York: Springer Verlag.
Translation of [Bourbaki-2006] into English.

[Bourbaki-2006] Bourbaki, Nicolas (2006). Théorie des ensembles. Berlin, Heidelberg, and New York: Springer Verlag.
This book is a reprint of the edition of 1970. The four chapters of this book have been first published separately in the years 1954 (Description de la mathématique formelle), 1939 and 1954 (Théorie des ensembles), 1956 (Ensembles ordonnés, cardinaux, nombres entiers) and 1956 (Structures).

[Cantor-1895] Cantor, Georg (1895). “Beiträge zur Begründung der transfiniten Mengenlehre”. In: Mathematische Annalen 46, pp. 481–512.

[Hasse-1926] Hasse, Helmut (1926). Höhere Algebra. Berlin: de Gruyter and Co.

[Hausdorff-1914] Hausdorff, Felix (1914). Grundzüge der Mengenlehre. Leipzig: Veit and Comp.
For a new edition see [Hausdorff 2002].

[Hausdorff-CW-2] Hausdorff, Felix (2002). Gesammelte Werke. Vol. 2: Grundzüge der Mengenlehre. Ed. by Brieskorn E. et al. Berlin, Heidelberg, and New York: Springer Verlag.
For the first edition see [Hausdorff 1914].

[Heath-1925] Heath, Thomas, ed. (1925). The thirteen Books of Euclid’s Elements. Cambridge: Cambridge University Press.
The first edition appeared in 1908.

[Jourdain-1912] Jourdain, Philip E. B. (1912). “On Isoid Relations and Theories of Irrational Number”. In: Proc. of the 5th International Congress of Mathematicians, Cambridge 2, pp. 492–496.

[Kuratowski-1921] Kuratowski, Casimir (1921). “Sur la Notion de l’Ordre dans la Théorie des Ensembles”. In: Fundamenta Mathematicae 2.1, pp. 161–171.

[Peano-1899] Peano, Giuseppe (1899a). Arithmetices Prinicipia – Nova Methodo Exposita. Romae and Florentiae: Augustae Taurinorum.

[Peano-1899-en] Peano, Giuseppe (1899b). “The Principles of Arithmetics – Presented by a new method”. In: From Frege to Gödel. A Source Book in Mathematical Logic, 1879 – 1931. Ed. by van Heijenoort, pp. 83– 97.
This article is a translation of [Peano 1899a] into English.

[Zermelo-1908b] Zermelo, Ernst (1908). “Untersuchungen über die Grundlagen der Mengenlehre I”. In: Mathematische Annalen 65, pp. 261–281.

[Zermelo-1908b-en] Zermelo, Ernst (1967). “Investigations in the Foundations of Set Theory I”. In: From Frege to Gödel. A Source Book in Mathematical Logic, 1879 – 1931. Ed. by van Heijenoort, pp. 199–215.
This article is a translation of [Zermelo 1908] into English.

Download

Direct Products and Relations

The pdf document is the full text including the proofs.

Change History

VersionDateChanges
1.0.0April 2020Creation
1.0.1April 2020Minor Corrections
1.0.2August 2020Minor Corrections