u8Cu0

Discrete Mathematics Lecture 6 — Relations

University course in discrete mathematics for computer science and engineering.

Sep 28, 2021
Downloads ‐ HTML, Markdown, PDF
All Files ‐ Post Files

Relations

Def: A relation \(\mathrel{R}\) on a set \(A\) is a subset to \(A \times A\).

\[ \mathrel{R} \subseteq A \times A \]

\[ (a_1, a_2) \in \mathrel{R} \]

is written as \(a_1\mathrel{R}a_2\), “\(a_1\) is related to \(a_2\)”.

Terminology

  1. Reflexivity: \(a \mathrel{R} a \forall a \in A\)
  2. Symmetry: \(a_1\mathrel{R}a_2 \Leftrightarrow a_2 \mathrel{R} a_1\).
  3. Antisymmetric: \((a_1\mathrel{R}a_2) \land (a_2 \mathrel{R} a_1) \Rightarrow a_1 = a_2\).
  4. Transitivity: \((a\mathrel{R} b) \land (b \mathrel{R} c) \Rightarrow a \mathrel{R} c\).
  5. Equivalence: Reflexive, symmetric and transitive.
  6. Partial Order: Reflexive, antisymmetric, transitive.

Informal Examples

For all examples below, \(A = \text{the set of all people}\).

  1. \(a_1 \mathrel{R}_1 a_2\) if \(a_1\) knows \(a_2\).
  2. \(a_1 \mathrel{R}_2 a_2\) if \(a_1\) and \(a_2\) are friends.
  3. \(a_1 \mathrel{R}_3 a_2\) if \(a_1\) and \(a_2\) are full siblings.
  4. \(a_1 \mathrel{R}_4 a_2\) if \(a_1\) is a decendant to \(a_2\).
Ref Sym Antisym Trans Ekv P.O
\(\mathrel{R}_1\) true false false false false false
\(\mathrel{R}_2\) false true false false false false
\(\mathrel{R}_3\) true true false true true false
\(\mathrel{R}_4\) true false true true false true

Mathematical Examples (partial orders)

  1. \(A = \mathbb{R}\) (any subset of \(\mathbb{R}\) would work). \(a_1 \mathrel{R} a_2\) if and only if \(a1 \leq a_2\).
    • Reflexive: \(a \leq a \forall a\), is true
    • Antisymmetric: \((a \leq b) \land (b \leq a) \Rightarrow a = b\), is true.
    • Transitive: \((a \leq b) \land (b \leq c) \Rightarrow a \leq c\), is true.
  2. \(A = \mathbb{Z}_+\), \(a_1 \mathrel{R} a_2\) if and only if \(a_1 | a_2\).
    • Reflexive: \(a | a, a = a \cdot 1\), is true.
    • Antisym: \((a | b) \land (b | a) \Rightarrow a=b\), is true.
    • Trans: \((a | b) \land (b | c) \Rightarrow a | c\), is true. \((\exists m \in \mathbb{Z}_+, b=ma) \land (\exists n \in \mathbb{Z}_+, c=nb)\) and \(c = n(ma) = (nm)a\). Therefore it is true.

The first example is actually an example of a total order. That is to say a partial order where for every pair \(a_1, a_2 \in A\) either \(a_1 \mathrel{R} a_2\) or \(a_2 \mathrel{R} a_1\)i.

  1. Let \(X\) be a set. Let \(A = 2^X(=\wp(X)) = \text{the set that contains all subsets to } X\). Then \(S_1 \mathrel{R} S_2\) if and only if \(S_1 \subseteq S_2\).

Relation Graph

If you have two elements, \(a_1\) and \(a_2\). So that.

\[ a_1 \mathrel{R} a_2 \]

(img 1)

For symmetry

\[ (a_1 \mathrel{R} a_2) \land (a_2 \mathrel{R} a_1) \]

(img 2)

This can also be drawn as

(img 2.1)

with just a single edge.

Ex: \(A=\{1, 2, 3, 4, 5, 6\}\)

\(a_1 \mathrel{R} a_2\) if \(a_1 | a_2\)

(img 3)

Hasse diagram of a partial order

A more effective representation of a relation graph

Simplifications

  1. Do not draw the loops.
  2. If \(a_1 \mathrel{R} a_2\) then place $a_1 under \(a_2\) (don’t need arrows).
  3. You don’t need to draw all three sides of a triangle, the third side is always understood, therefore does not need to be drawn.

If we combine 2 and 3 then we can summerize this into that you only need to write edges bewteen so called closest neighbours.

(img 4)

Note, there are no triangles in diagram, if there are then you have drawn too many lines. The reason for why this is the natural way to draw the graph in this way. That is to say why 1 is at the bottom, (2, 3, 5) in the middle and (4, 6) at the top. You order the number by the amount of prime factors.

The divisibility relation is similar to the subset relation.

(img 5)

The only difference here is that we allow copies of the same element in the sets. Otherwise it is similar to the subset relation. This is also called a multiset.

A multiset is like a normal set but where you allow multiple copies of the same element. For example \(\{2, 2\}\), would be a multiset.

Equivalence Relations

  1. Geometric example

\(A\) is the set of all directional straight lines in \(R^2\).

(img 6)

Two straight lines are related if one is a parallel displacement of the other.

(img 7)

  1. Let \(n \in \mathbb{Z}_+\). We define a relation on \(\mathbb{Z}\) according to the following.

\[ a_1 \mathrel{R} a_2 \Leftrightarrow n \mid a_1 - a_2 \]

  • Reflexive: \(a-a=0 n \mid 0\), (\(0=0\cdot n\)) is true.
  • Symmetry: \(n \mid a - b \Leftrightarrow n \mid b - a\).
  • Transitivity: \((n \mid a - b) \land (n \mid b -c) \Rightarrow n \mid a - c\).

Equivalance Classes

Let \(\mathrel{R}\) be a equivalnce relation on a set \(A\). Let \(a \in A\). The equivalenceclass for \(a\) is per definition,

\[ [a] = \{b \in A \mid a \mathrel{R} b \} \]

Clause: Let \(a_1, a_2 \in A\) and det \(\mathrel{R}\) be a equivalence relation on \(A\). Then either \([a_1]=[a_2]\) or \([a_1] \cap [a_2] = \emptyset\).

Proof: Let \(a_1, a_2\) be two elements so that \([a_1] \cap [a_2] \neq \emptyset\). That is to say you have to prove that \([a_1] = [a_2]\).

The fact that \([a_1] \cap [a_2] \neq \emptyset \Rightarrow \exists b : (a_1 \mathrel{R} b) \land (a_2 \mathrel{R} b)\).

Now take a arbitrary \(c \in A\) so that \(a_1 \mathrel{R} c\). There remains to prove that \(a_2 \mathrel{R} c\).

We know that

\[ a_2 \mathrel{R} b \]

and we know that

\[ a_1 \mathrel{R} b \]

which is symmetric to

\[ b \mathrel{R} a_1 \]

\[ (a_1 \mathrel{R} b) \land (b \mathrel{R} a_1) \Rightarrow (a_2 \mathrel{R} a_1) \land (a_1 \mathrel{R} c) \Rightarrow a_2 \mathrel{R} c \]

References