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\}$

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)\}$

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

Link to original

partition

Sets that form a partition are mutually exclusive and collectively exhaustive.

Partition

$\{A_i\mid i\in I\}$ is a partition of $A$ if:

• $\forall i\in I:A_i\subseteq A\wedge A_i\ne \varnothing$ (all $A_i$ are non-empty and subsets of $A$)
• ${\bigcup }_{i\in I}{A}_i=A$ (the union of all $A_i$ is $A$ – they cover $A$)
• $\forall i,j\in I:i\ne j⟹A_i\cap A_j=\varnothing$ (all $A_i$ are pairwise disjoint)

$A_i$ are called the blocks of the partition.

Like a school: all students are in a single class, no classs is empty and all classes together make up the school.

Partitions for equivalence relations:
$P_R=\{[x{]}_R\mid x\in X\}$, $R\dots$ relation on $X$

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

If $E$ is the disjoint union of $\{A_j\}$, then $\{A_j\}$ is a partition of $E$.

Link to original

Link to original

$R\subseteq A\times A:x\in A,K(x):=\{y\in A:xRy\}$

$K(x)$ is the equivalence class of $x$. “Die von $x$ erzeugte Equivalenzklasse”

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)$
i

Partial order (Halbordnung)

$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 partial order:
$\forall x,y\in A:xRy\vee yRx$ (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{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.

= All possible subsets of $\{1,2,3\}$

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