Discrete Mathematics· Note 02

Relations

Year 2 · Semester ILast updated

Jan 7

Relations

Intuitively, a relation is a way of “comparing” two elements

  1. <<, >>, ==, ≤\leq, ≥\geq, among numbers
  2. A=A= set of people, B=B= set of cities
    • We can define a relation to hold between person a∈Aa\in A and city b∈Bb\in B if aa lives in bb.
  3. A=A= set of people
    • We can define a relation to hold between person a1∈Aa_1\in A and person a2∈Aa_2\in A if they share a family connection.

Formal Definition:
Let A,BA,B be sets. A relation RR from AA to BB is a subset of A×BA\times B.

Yeah, that’s it. The relation doesn’t have to be anything meaningful. It’s just a subset of the Cartesian product of the two sets.

Examples of Relations

A={ 1,2 }A=\set{1,2}, B={ 1,2,3 }B=\set{1, 2, 3}

  1. “less than” relation: R={ (1,2),(1,3),(2,3) }R=\set{(1,2), (1,3), (2,3)}
  2. “greater than” relation: R={ (2,1),(3,1),(3,2) }R=\set{(2,1), (3,1), (3,2)}
  3. “arbitrary” relation: R={ (1,1),(1,3),(2,1) }R=\set{(1,1), (1,3), (2,1)}

A relation RR from AA to itself (i.e. R⊆A×AR\sseq A\times A) is called a relation on AA.

For example, see the third example in the intuitive definition above.

Simple Relations

  • Empty relation: R=ϕR=\phi
    • No pairs satisfy the relation
    • E.g, R∈N×N, (a,b)∈RR\in\N\times\N,\ (a,b)\in R iff a=−ba=-b
    • R=ϕR=\phi because there are no negative numbers in N\N
  • Complete relation: R=A×BR=A\times B
    • Every pair satisfies the relation
    • E.g, A={ 1,2,3 }A=\set{1,2,3}, B={ 4,5,6 }B=\set{4,5,6}, R=R= “less than”
    • R=A×BR=A\times B because every element of AA is less than every element of BB

The usual set operations can be applied to relations, e.g. union, intersection, complement, etc. since relations are just sets.

Inverse Relations

Definition:
Let RR be a relation from AA to BB. The inverse relation of RR (denoted R−1R^{-1}) is the relation from BB to AA defined by R−1={ (b,a)∣(a,b)∈R }R^{-1}=\set{(b,a)\mid(a,b)\in R}.

Examples of Inverse Relations

A={ 1,2 }A=\set{1,2}, B={ 1,2,3 }B=\set{1, 2, 3} R=R= “less than” = { (1,2),(1,3),(2,3) }\set{(1,2), (1,3), (2,3)}

R−1=R^{-1}= “greater than” = { (2,1),(3,1),(3,2) }\set{(2,1), (3,1), (3,2)}

Note that we just swapped the order of the elements in each pair.

Composition of Relations

Suppose R1⊆A×BR_1 \sseq A\times B and R2⊆B×CR_2 \sseq B\times C are relations.

Definition:
The composition of R1R_1 and R2R_2 (denoted R1∘R2R_1\of R_2) is the relation from AA to CC defined by R1∘R2={ (a,c)∣∃b∈B s.t. (a,b)∈R1 and (b,c)∈R2 }R_1\of R_2=\set{(a,c)\mid\exists b\in B\text{ s.t. }(a,b)\in R_1\text{ and }(b,c)\in R_2}.

Compositions explained in English

A composition of relations R1R_1 and R2R_2 is a new relation R1∘R2R_1\of R_2 that contains all pairs (a,c)(a,c) where there exists some bb such that (a,b)∈R1(a,\boldsymbol{b})\in R_1 and (b,c)∈R2(\boldsymbol{b},c)\in R_2.

Examples of common composed relations

A,B,CA,B,C are sets of people
R1⊆A×BR_1\sseq A\times B is relation “is a brother of” (i.e. (a,b)∈R1(a,b)\in R_1 iff aa is a brother of bb)
R2⊆B×CR_2\sseq B\times C is relation “is a parent of” (i.e. (b,c)∈R2(b,c)\in R_2 iff bb is a parent of cc)

R1∘R2R_1\of R_2 is relation “is an uncle of” (i.e. (a,c)∈R1∘R2(a,c)\in R_1\of R_2 iff aa is an uncle of cc)

Notation: R2=R∘RR^2=R\of R, R3=R∘R∘RR^3=R\of R\of R, etc.

Properties of Relations

  • Associative: (R1∘R2)∘R3=R1∘(R2∘R3)(R_1\of R_2)\of R_3=R_1\of(R_2\of R_3)

Equivalence Relations

Partitions

Definition:
Let AA be any set. A partition PP of AA is a set of subsets of AA:

P={ A1,A2,…,Ai,…,An }P=\set{A_1,A_2,\dots,A_i,\dots,A_n}

such that two conditions are met:

  1. For all i≠j:Ai∩Aj=ϕi\not=j:A_i\cap A_j=\phi
    • Subsets in PP are disjoint
  2. ∪inAi=A\cup_i^nA_i=A
    • Every element of AA is in some subset of the partition
Example of a partition

Let A={ 1,2,3,4,5,6,7 }A=\set{1,2,3,4,5,6,7}
Let A1={ 2,5 }A_1=\set{2,5}
Let A2={ 1,3,6 }A_2=\set{1,3,6}
Let A3={ 7 }A_3=\set{7}
Let A4={ 4 }A_4=\set{4}

Then the partition PP of AA looks like this:

Equivalence Relations

Definition:
Given a partition PP of AA, define a relation RR as follows:
(a,b)∈R(a,b)\in R whenever a,ba,b belong to the same subset in the partition PP.

In our above example, (1,6)∈R(1,6)\in R, (1,2)∈R(1,2)\in R, (7,7)∈R(7,7)\in R, (7,6)∉R(7,6)\not\in R.

Example of an Equivalence Relation

Let A={ 1,2,3,4 }A=\set{1,2,3,4}
Let the partition be defined as specified in this diagram:

Then, R={ (1,3),(3,1),(2,2),(4,4),(1,1),(3,3) }R=\set{(1,3),(3,1),(2,2),(4,4),(1,1),(3,3)}

RR is called an equivalence relation, and we say that RR is induced by the partition PP.

Any relation RR on AA is:

  • Reflexive
    • Every a∈Aa\in A belongs to the same “cell” as itself
  • Symmetric
    • If aa is in bb’s cell, then bb is in aa’s cell
  • Transitive
    • If aa is in bb’s cell, and bb is in cc’s cell, then aa is in cc’s cell

Equivalence Relation Theorem

Any relation RR on AA which is reflexive, symmetric, and transitive is an equivalence relation (induced by some partition of AA).

I.e., we can “work backwards” from a relation satisfying these three properties to find the partition which induced it.

Example of the Equivalence Relation Theorem

A=ZA=\Z
R⊆Z×ZR\subseteq \Z\times\Z
R={ (a,b)∣a−bmod  5=0 }R=\set{(a,b)\mid a-b \mod 5=0}
(3,−2)∈R,(5,0)∈R,(−7,3)∈R,(3,13)∈R(3,-2)\in R, (5,0)\in R, (-7,3)\in R, (3,13)\in R
(1,2)∉R,(4,0)∉R,(2,−7)∉R,(8,8)∈R(1,2)\not\in R, (4,0)\not\in R, (2,-7)\not\in R, (8,8)\in R

Claim: RR is reflexive, symmetric, and transitive.

Proof:

  1. ∀n∈Z,n−n=0=0⋅5\forall n\in\Z,n-n=0=0\cdot5; hence (n,n)∈R(n,n)\in R
  2. If a−b=5ka-b=5k then b−a=−5k=5⋅(−k)b-a=-5k=5\cdot(-k)
  • If (a,b)∈R(a,b)\in R then (b,a)∈R(b,a)\in R
  1. If a−b=5ka-b=5k and b−c=5lb-c=5l, then a−c=(a−b)+(b−c)=5k+5l=5(k+l)⇒(a,c)∈Ra-c=(a-b)+(b-c)=5k+5l=5(k+l)\Rightarrow(a,c)\in R

Therefore, RR is an equivalence relation.

Equivalence Classes

Definition:
The cells of a partition (which induces RR) are called the equivalence classes of RR.

For each a∈Aa\in A, [a][a] means the equivalence class of aa.
E.g., in the last example, [3]=[−12][3]=[-12] (because they are both two less than multiples of 5)

The set of all equivalence classes of AA in the relation RR is denoted A/RA/R (“AA modulo RR”) and is called the quotient set of RR.

In the last example, A/R={ [0],[1],[2],[3],[4],[5] }A/R=\set{[0],[1],[2],[3],[4],[5]}

Example of Quotient Sets

A=A= set of people
RR is a relation on AA: (a,b)∈R(a,b)\in R when a,ba,b share last names.

It’s easy to see that RR is reflexive, symmetric, and transitive, and hence is an equivalence relation.

It’s also easy to see that each equivalence class corresponds to a family name.

The quotient set A/RA/R is the set of all last names.

Jan 14

Order Relations

Definition:
An order relation generalizes the familiar “orders” like ≤ or ≥ on sets of numbers.

Formally, a relation RR on a set AA is an order relation if it has three properties:

Properties of Order Relations

  1. RR is reflexive
  2. RR is transitive
  3. RR is antisymmetric
    • i.e., if (a,b)∈R(a,b)\in R and (b,a)∈R(b,a)\in R, then a=ba=b
    • RR cannot hold between different elements in both directions
    • Note that this is not the same as being asymmetric
    • Formally, RR is antisymmetric iff R∩R−1⊆IAR\cap R^{-1}\subseteq I_A

If RR is an order relation, then we use the notation

a⩽Rba\leqslant_Rb

in place of using aRbaRb or (a,b)∈R(a,b)\in R.

Examples of order relations
  1. ≤,≥\leq,\geq on sets of numbers
  2. Lexicographic order of points on an Rn\R^n plane
  • Order by first point, if those are equal, order by the next point, etc…
  1. Let AA be any set and define the relation RR on P(A)\pset A by:
    A1 R A2A_1\ R\ A_2 iff A1⊆A2A_1\sseq A_2.
  2. Let A=NA=\N.
    Define RR on AA as: (a,b)∈R(a,b)\in R if a∣ba|b (aa divides bb).

Definition:
An order relation RR on a set AA is a total order if, for every a1,a2∈Aa_1,a_2\in A, either a1≤Ra2a_1\leq_Ra_2 or a2≤Ra1a_2\leq_Ra_1 (or both, if a=ba=b).
Otherwise, RR is called a partial order.

Examples 1 and 2 above are examples of total orders, and examples 3 and 4 above are partial orders.

Hasse Diagrams

A partial order RR on a set AA can be illustrated using a Hasse diagram.

For example, A=n∣1≤n≤20A={n|1≤n≤20}, and RR is the divisibility relation (example 3 from above)

Property of Hasse Diagrams

We can get from a1a_1 to a2a_2 by moving up edges iff then a1≤Ra2a_1\leq_Ra_2

Rules of HD
  1. All minimal elements go on the bottom.
    • (a1∈Aa_1 \in A is minimal if there does ∄b∈A\not\exists b\in A s.t. b≤Rab\leq_Ra)
    • If there is a single minimum element aa, then aa is called a minimum in RR.
    • In the above example, 11 is a minimum.
      • If we delete 11 from AA, then 2,3,5,7,11,13,17,192,3,5,7,11,13,17,19 are all minimal elements, but there is no minimum.
  2. An edge exists from a1a_1 “goes up” to a2a_2 if:
    1. a1≠a2a_1 \not= a_2
    2. a1≤Ra2a_1\leq_Ra_2
    3. ∄b∈A\not\exists b\in A s.t. a1≤Rba_1\leq_Rb and b≤Ra2b\leq_Ra_2
    • Under these conditions, we call a2a_2 a successor element of a1a_1.
      • E.g., in our example, 4,6,10,144,6,10,14 are successors of 22.
      • a1a_1 is called a predecessor of a2a_2.
      • An element can have multiple predecessors and/or successors.
    • An element with no successors is called maximal
      • E.g., in our example, 16,12,18,15,20,14,11,13,17,1916,12,18,15,20,14,11,13,17,19 are maximal.
      • If only one element is maximal, then it is called a maximum of RR.

The Hasse Diagram of a total order looks like a straight line: