Relations as Subsets of Cartesian Products

A relation describes a connection between elements in one or more sets. In set theory, a relation is defined as a subset of a Cartesian product.

 

 

Definition

If we have two sets \( \large A\) and \( \large B\), a relation \( \large R\) from \( \large A\) to \( \large B\) is a subset of \( \large A \times B\):

 

$$ \large R \subseteq A \times B $$

 

This means that a relation consists of selected ordered pairs \((a,b)\), where \( \large a \in A\) and \( \large b \in B\).

 

 

Examples

• Less-than relation: \( \large R = \{(a,b) \in \mathbb{N} \times \mathbb{N} \mid a < b\}\).
• Equality relation: \( \large R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a = b\}\).
• Divisibility: \( \large R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a \text{ divides } b\}\).

 

 

Properties of relations

 

Reflexive

A relation is reflexive if every element is related to itself:

 

$$ \large (a,a) \in R \quad \text{for all } a \in A $$

 

Example:

 

Let \( \large A = \{1,2,3\}\) and the relation \( \large R = \{(1,1),(2,2),(3,3)\}\).

This relation is reflexive because all elements are related to themselves.

 

 

Symmetric

A relation is symmetric if it works both ways:

 

$$ \large (a,b) \in R \;\Rightarrow\; (b,a) \in R $$

 

Example:

 

Let \( \large A = \{\text{Anna}, \text{Bo}\}\) and the relation \( \large R = \{(\text{Anna},\text{Bo}),(\text{Bo},\text{Anna})\}\).

This can be interpreted as the relation “is married to” and is symmetric, because if Anna is married to Bo, then Bo is also married to Anna.

 

 

Antisymmetric

A relation is antisymmetric if both pairs can only occur when the elements are the same:

 

$$ \large (a,b) \in R \;\wedge\; (b,a) \in R \;\Rightarrow\; a=b $$

 

Example:

 

Let \( \large A = \{1,2,3\}\) and the relation \( \large R = \{(1,1),(2,2),(3,3),(1,2)\}\).

Here there is no pair with both \((1,2)\) and \((2,1)\), so the relation is antisymmetric.

 

 

Transitive

A relation is transitive if it can be “chained together”:

 

$$ \large (a,b) \in R \;\wedge\; (b,c) \in R \;\Rightarrow\; (a,c) \in R $$

 

Example:

 

Let \( \large A = \{1,2,3\}\) and the relation \( \large R = \{(1,2),(2,3),(1,3)\}\).

Here transitivity holds, because from \((1,2)\) and \((2,3)\) it follows that \((1,3)\).

 

 

Example: equivalence relation

A relation that is reflexive, symmetric and transitive is called an equivalence relation. It partitions a set into equivalence classes, where all elements are mutually related.

 

Example: The relation "has the same remainder when dividing by 3" on \( \large \mathbb{Z}\):

 

$$ \large R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a \equiv b \pmod{3}\} $$

 

This divides \( \large \mathbb{Z}\) into three classes: numbers with remainder 0, remainder 1, and remainder 2.

 

 

Importance and applications

Relations are fundamental because they describe how objects can be connected. They are used in, among other things:

 

• Graphs, where edges are relations between nodes.
• Databases, where tables can be seen as relations between data fields.
• Mathematical logic, where relations express connections between statements.

 

Understanding relations is an important step towards working with functions, which are precisely special relations.