# Direct Products and Relations

- Introduction
- Ordered Pairs
- The Direct Product of Two Sets
- Relations
- Equivalence Relations and Partitions
- Notes and References
- Download

## Introduction

**In the following you will find a short summary of tis unit. For detailed information please see the full text or download the pdf document at the end of this page.**

The present unit is the third unit of the walk *The Axioms of Zermelo and Fraenkel*. In the previous units *The Mathematical Universe* and *Unions and Intersections of Sets* we have introduced the basic axioms of Zermelo and Fraenkel.

We will explain the following terms:

- Ordered Pair
- Direct Product
- Relation
- Reflexive, symmetric, antisymmetric and transitive relation
- Equivalence Relation
- Partition

The main results are

- Theorem [#nst-th-ordered-pair-elementary] about ordered pairs saying that we have $(a, b) = (a’, b’)$ if and only if $a = a$ and $b = b’$ and
- Theorem [#nst-th-equivalence-relation-partition] saying that each equivalence relation defines a partition and that each partition defines an equivalence relation.

## Ordered Pairs

We will introduce the definition of ordered pairs:

**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.

**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’)$ if and only if $a = a’$ 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)$.

## The Direct Product of Two Sets

The direct product of two sets is one of the basic tools in mathematics such as the union or the intersection of two sets.

**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.

**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)$.

## Relations

Relations are used to express a connection between two mathematical objects. Particularly important relations are equivalence relations (see below), functions (see Unit *Functions and Equivalent Sets*) and order relations (see Unit *Ordered Sets and the Lemma of Zorn*).

**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.

**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$ imply $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.

## Equivalence Relations and Partitions

Equivalence relations are used to group and often to identify similar elements of a set:

**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.

**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. ** 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.

**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}$.

## Notes and References

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

Do you want to learn more? In the framework of the axioms of Zermelo and Fraenkel functions are defined as relations with specific properties. This approach is explained in Unit *Functions and Equivalent Sets*.

## Download

### Direct Products and Relations

The pdf document is the full text including the proofs.

Current Version: 1.0.3 from October 2020