relation

cartesian product

Cartesian product

The cartesian product of two sets $A$ and $B$, denoted by $A\times B$, is the set of all possible ordered pairss $(a,b)$ where $a\in A$ and $b\in B$:
$A\times B:=\{(x,y):x\in A\wedge y\in B\}$
$B\times A:=\{(y,x):x\in A\wedge y\in B\}\ne A\times B$
e.g.: $A=\{1,2,3\}$ and $B=\{a,b\}$, then $A\times B=\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}$

The cartesian product is not commutative: $A\times B\ne B\times A$

Taking the cartesian product of mutiple sets:
$A_1\times A_2\times \cdots \times A_n=\{(a_1,a_2,\dots a_n)\mid \forall i:a_i\in A_i\}$

The cardinality of the cartesian product is the product of the cardinalities of the individual sets:
$|A\times B|=|A|\cdot |B|$
So the cartesian product of a set with the empty set is the empty set: $|A\times \varnothing |=|A|\cdot 0=0⟹A\times \varnothing =\varnothing$

Link to original

Relation

$A,B$ are sets, $R\subseteq A\times B$ is a relation between $A$ and $B$.
In words: A relation is a subset of all possible ordered pairs of elements from two sets.

Binary relation

$A=B\to$ binary relation on $A$.
$R\subseteq A\times A=\{(x,y)\mid x\in A,y\in A\}$ (or $R\subseteq A^2$) is a binary relation on $A$ (a subset of the cartesian product).
$xRy:⟺(x,y)\in R$ (common notation)
$x/Ry:⟺(x,y)\notin R$

Illustrating relations

EXAMPLE

$A=\{1,2,3\}$, $B=\{x,y\}$
$R\subseteq A\times B$
$R=\{(1,x),(1,y),(2,y),(3,x)\}$

Binary relations can be represented as a graph

$A=\{1,2,3\}$
$R=\{(1,1),(1,2),(2,2),(2,1),(2,3),(3,2)\}$

Properties of relations

Reflexive

$\forall x\in A:xRx$ … every element is related to itself … $a=a$.

Link to original

Symmetric relation

$\forall x,y\in A:xRy⟹yRx$

Link to original

Antisymmetric

$\forall x,y\in A:xRy\wedge yRx⟹x=y$ … if two elements are related both ways, they are the same element.
E.g.: $x\le y\wedge y\le x⟹x=y$ (which is not symmetric, e.g. $1\le 2$ but not $2\le 1$, and different from asymmetric, which is the opposite of symmetric $xRy⟹\neg (yRx)$).

Link to original

Transitive

$\forall x,y,z\in A:xRy\wedge yRz⟹xRz$

Link to original

Partial order (Halbordnung)

The relation $R\subseteq A\times A$ is a partial order on $A$ if it is: reflexive, antisymmetric, transitive.

Link to original

Total/linear order (Totalordnung)

Additional to being a partial order, if a relation is total, i.e. $\forall x,y\in A:xRy\vee yRx$, then any two elements are comparable – the hasse-diagram always looks like a chain).

Link to original

equivalence relation

Equivalence relation

$R\subseteq A\times A$ is an equivalence relation on $A$ if it is:

• reflexive, i.e. $\forall x\in A:xRx$ (every element is related to itself … a = a)
• symmetric, i.e. $\forall x,y\in A:xRy⟹yRx$
• transitive, i.e. $\forall x,y,z\in A:xRy\wedge yRz⟹xRz$

The relationship in the example above is not an equivalence relation (3 would need a self-loop and 1,3 would need to be connected symmetrically).

Equivalence relations

Let $A$ be any set, $xRy:⟺x=y$ → “Equality relation” on $A$ (the resulting set is the diagonal of the cartesian product).

Let $A$ be any set, $\forall x,y\in A:xRy$ → “Universal relation” on $A$ (the resulting set is the entire cartesian product).
The equality relation can also be though of as partitioning each different element into its own set, and the universal relation as a single set containing all elements.

Let $A=\mathbb{Z},m\in {\mathbb{Z}}^{+},aRb:⟺a\equiv b\mathrm{mod}m$
$\forall a\in \mathbb{Z}:a\equiv a\mathrm{mod}m$, since $m\mid \underset{0}{\underbrace{a-a}}$, since $\exists x\in \mathbb{Z},0=mx$ (reflexive: $✓$)
$\forall a,b\in \mathbb{Z}:a\equiv b\mathrm{mod}m⟹b\equiv a\mathrm{mod}m$
$a\equiv b\mathrm{mod}m⟺m\mid b-a⟺\exists x\in \mathbb{Z}:mx=b-a$
$⟹m(-x)=a-b⟺b\equiv a\mathrm{mod}m$ (symmetric: $✓$)
$\forall a,b,c\in \mathbb{Z}:a\equiv b\mathrm{mod}m,b\equiv c\mathrm{mod}m⟹\underset{\text{z.z.: }m\mid c-a}{\underbrace{a\equiv c\mathrm{mod}m}}$
$a\equiv \mathrm{mod}m⟺\exists x:mx=b-a$
$b\equiv c\mathrm{mod}m⟺\exists y:my=c-b$
$⟹m(x+y)=c-a$ (transitive $✓$)

Equivalence class

Let $R\subseteq A\times A:x\in A$

$$K(x):=\{y\in A:xRy\}$$

The set of all elements that are related to $x$ via $R$ – $K(x)$ – is the equivalence class of $x$.
“Die von $x$ erzeugte Equivalenzklasse”.

Equivalence Relations ↔ Partitions

Every equivalence relation induces a partition and every partition induces an equivalence relation:

Equivalence Relation → Partition:
Given equivalence relation $R$ on $A$, the equivalence classes $[x{]}_R=\{y\in A\mid xRy\}$ form a partition. Properties of $R$ ensure partition properties: reflexivity means blocks are non-empty ($x\in [x{]}_R$), symmetry and transitivity ensure blocks are disjoint ($[x{]}_R=[y{]}_R$ or $[x{]}_R\cap [y{]}_R=\varnothing$), and together they guarantee blocks cover $A$ (${\bigcup }_{x\in A}[x{]}_R=A$).

Partition → Equivalence Relation:
Given partition $\{A_i\mid i\in I\}$ of $A$, define $xRy:⟺\exists i\in I:x,y\in A_i$. Partition properties ensure equivalence relation properties: non-empty blocks give reflexivity, disjoint blocks give symmetry, and covering gives transitivity.

Like sorting items into boxes: Each item goes in exactly one box (partition), and two items are related if they’re in the same box (equivalence relation).

Link to original

Every equivalence relation induces a partition, and every partition induces an equivalence relation (they are the same).

(1) $R\subseteq A\times A$, equiv. relation $⟹K=\{K(a):a\in A\}$ is a partition (the set of equivalence classes is a partition of $A$)
(2) $\{A_i\mid i\in I\}$ is a partition of a, $x\in A:\tilde{K}(x):=$ the block $A_j$ containing $x⟹\tilde{K}$ is an equivalence relation on $A$.
$\forall x,y\in A:xRy⟺\tilde{K}(x)=K(y)⟹R$ is an equivalence relation. The equivalence classes of $R$ are $A_i,i\in I$:

Proof (1):
$\forall x:K(x)\subseteq A,xRx⟹x\in K(x)\ne \varnothing$
${\bigcup }_{x\in A}K(x)=A$
$x\in K(a)\cap K(b)⟹aRx,\underset{⟹xRb}{\mathrm{bRx}}⟹aRb$
$⟹K(a)=K(b)$ (if two classes have a nonempty intersection, they are the same – different classes have no intersection)

Proof (2):
$x\in \tilde{K}(x)⟹xRx$
$x,y\in A:\underset{xRy}{\underbrace{\tilde{K}=\tilde{K}(x)B}}⟹\underset{yRx}{\underbrace{\tilde{K}(y)=\tilde{K}(x)}}$ (symmetric)
$xRy,yRz⟹\tilde{K}(x)=\tilde{K}(y)=\tilde{K}(z)⟹xRz$ (transitive)
$\forall x:K(x)=\{y\in A\mid xRy\}=\{y\in A\mid \tilde{K}(x)=\tilde{K}(y)\}=\tilde{K}(x)$

Link to original

Partial order (Halbordnung)

The relation $R\subseteq A\times A$ is a partial order on $A$ if it is: reflexive, antisymmetric, transitive.

Link to original

Total/linear order (Totalordnung)

Additional to being a partial order, if a relation is total, i.e. $\forall x,y\in A:xRy\vee yRx$, then any two elements are comparable – the hasse-diagram always looks like a chain).

Link to original

EXAMPLE

Let $A=\mathbb{R},xRy⟺x\le y$ → total order
Let $A=\mathbb{R},xRy⟺x<y$ → partial order (not reflexive: $x\nless x$)

Let $A=\mathbb{N},xRy⟺x\mid y$ → partial order (e.g. $2\nmid 3,3\nmid 3$)

$A=2^M=\{x:x\subseteq M\}$, $YRY⟺X\subseteq Y$ → partial order, total order if $|M|\le 1$, since the empty set is comparable to the set with one element. But if there are two elements, we can put both into a set with a single element and then the two sets are not comparable.

$(\{R:R\subseteq A\times B\},\subseteq )$ → partial order (the set of all relations between two sets is partially ordered by inclusion)
$(\{R:R\subseteq A\times A\},\oplus )$ can be written as a pair $(A,R),R\subseteq A\times A$.

hasse-diagram

Hasse-Diagram

A hasse diagram is like a relation graph for partial orders, so we omit the reflexive edges for simplicty. Every edge signifies a relation.
There is a hierarchy: Lower elements are subsets of the upper ones, so we can omit the arrows.
Every set connected via multiple relations could be made in a single step (transitive), but we also omit those arrows.

$(2^{\{1,2,3\}},\subseteq )$ … a partial order.

$\mathcal{P}(\{1,2,3\})$ = power set = All possible subsets of $\{1,2,3\}$

It’s not a total order since for example $\{1\}$ and $\{2\}$ are incomparable (neither is a subset of the other).
For $(2^{\{1,2,3\}},\supseteq )$, we mirror the diagram along the horizontal axis.

The natural numbers $\mathbb{N}$ are a linear order.

Link to original

Link to original

$(H,R)$ (Grundmenge $H$, Relation auf der Menge $H$), $R\subseteq H\times H$

Chain: $K\subseteq H$ is a chain if $(K,R)$ is a linear order.

In words: A chain is a subset with linear order. The superset does not need to be a linear order.

Maximal element: $K\in H$ is a maximal element if $\forall x\in H\setminus K:(K\cup \{x\},R)$ is not a chain.

In other words: We cannot add any more elements to $K$ without breaking the chain property.

$(2^{\{1,2,3\}},\subseteq ):\{\varnothing ,\{2\},\{1,2,3\}\}$ is a non-maximal chain.

It is a chain since for every two elements, one is a subset of the other.
It is not maximal since we can add $\{1\}$ for example to the chain and it would still be a chain.

${\mathbb{N}}^{+},\mid :\{1,2,4,8,16\}$ is a maximal chain.

Any power of two is a multiple of any other multiple of two i.e the divisibility relation is true.
But we cannot add any other natural number, since we would have a prime factor $\ne$ 2.

Minimum: $S\subseteq H,m\in S$ is a minimum of $S$ if $\forall x\in S:mRx$

We write it as $m=\min S$
What the minimum is depends on the relation. For $\le$, the minimum is the smallest number, for $\subseteq$ it is the smallest set, for $\mid$ it is the smallest divisor which divides all elements of $S$… which doesn’t have to exist.

$(\mathbb{Z},\le ),\mathbb{N}\subseteq \mathbb{Z},\min \mathbb{N}=0$

$\mathbb{Z}\subseteq \mathbb{Z}:\nexists \min \mathbb{Z}$

There is no smallest element in the set of integers.

Well-ordered set (for linear orders) $(H,R):⟺(\forall S\subseteq H,S\ne \varnothing )⟹\exists \min S$

$(H,R)$ is well-ordered if every non-empty subset $S\subseteq H$ has a minimum.

EXAMPLE

$(\mathbb{Z},\le )$ → not well-ordered

$(\mathbb{N},\le )$ → well-ordered.

Finite total orders are always well-ordered, since every non-empty subset has a minimum.

$(R_0^{+},\le )$ → not well-ordered because there is always an even smaller number.

Transclude of transfinite-induction