Relations and Properties of Relations

Relations (Chapter 8)

Two-Place Predicates

• Two-place predicates, like $B(x, y)$ where $x$ is the brother of $y$, are fundamental in mathematics.

• They help describe basic concepts.

• Examples:

  • $G(x, y)$: $x$ is greater than or equal to $y$ (magnitude comparison).

  • $P(x, y)$: $x$ has the same parity as $y$ (parity comparison of integers).

  • $S(x, y)$: $x$ has square equal to $y$ (relates a value to its square).

What are Relations?

• Two-place predicates are also called relations.

• Definition: If $P(x, y)$ is a two-place predicate with domain of discourse $A$ for $x$ and $B$ for $y$, then $P$ is a relation from $A$ to $B$.

  • $A$ is called the domain of the relation.

  • $B$ is called the codomain of the relation.

Specifying Relations

• Verbal Description: Providing a verbal description (e.g., $E(x, y)$: The word $x$ ends with the letter $y$).

  • Domain: Words in English.

  • Codomain: Letters of the alphabet.

  • Example: (cat, t) satisfies $E$, but (dog, w) does not.

• Listing Ordered Pairs: Explicitly listing the ordered pairs that satisfy the relation.

  • Example: If $A = {1, 2, 3, 4}$ and $B = {a, b, c, d}$, a relation $R$ from $A$ to $B$ could be $R = {(1, b), (2, c), (4, c)}$.

• Notation: $aRb$ is often used in place of $(a, b) \in R$.

  • For example, $G(3, 2)$ is true, or $(3, 2) \in G$, or $3G2$.

Representing Relations with Graphs

• Relations can be represented using graphs.

• Bipartite Graph: A diagram with vertices (dots) and edges (lines).

  • Create a column of dots for elements of $A$ and label them.

  • Create a column of dots for elements of $B$ and label them.

  • Connect vertex $a \in A$ to vertex $b \in B$ with an edge if $(a, b) \in R$.

• Example 8.1: Let $A = {1, 2, 3, 4}$, $B = {a, b, c, d}$, and $R = {(1, a), (2, b), (3, c), (3, d), (4, d)}$. A bipartite graph represents $R$.

Relations on a Set

• If $R$ is a relation from $A$ to $A$, then $R$ is a relation on $A$.

  • Relations on a set can be represented using a digraph.

• Digraph (Directed Graph): Edges have a direction indicated by an arrowhead.

  • Each element of $A$ labels a single point.

  • An arrow connects vertex $s$ to vertex $t$ if $(s, t) \in R$.

  • An edge of the form $(s, s)$ is called a loop.

• Example 8.2: Let $A = {1, 2, 3, 4, 5}$ and $R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)}$. A digraph visually represents $R$.

Representing Relations with Matrices

• A 0-1 matrix is used to represent a relation, handy for computer encoding.

• An $m \times n$ matrix is a rectangular array with $m$ rows and $n$ columns.

  • Entries are indexed by row and column: $a<em>{i,j}$ or $a</em>{ij}$ represents the entry in the $i^{th}$ row and $j^{th}$ column.

• For finite sets $A$ and $B$ with $m$ and $n$ elements respectively, use elements of $A$ and $B$ to index rows and columns.

• Matrix of R, $M_R$: The entry in the row labeled by $a$ and the column labeled by $b$ is 1 if $aRb$ and 0 otherwise.

• Example 8.3: Let $A = {1, 2, 3, 4}$ and $B = {a, b, c, d}$, and $R = {(1, a), (1, b), (2, c), (4, c), (4, a)}$.

  • The 0-1 matrix representing $R$ is:
    $M_R = \begin{bmatrix} 1 &amp; 1 &amp; 0 &amp; 0 \ 0 &amp; 0 &amp; 1 &amp; 0 \ 0 &amp; 0 &amp; 0 &amp; 0 \ 1 &amp; 0 &amp; 1 &amp; 0 \end{bmatrix}$

  • The matrix appearance depends on the order of elements in $A$ and $B$.

Set Operations on Relations

• Relations as sets of ordered pairs allow set operations.

• Bit-wise operations on 0-1 matrices represent these operations.

  • $M<em>{R \cup S} = M</em>R \lor M_S$

  • $M<em>{R \cap S} = M</em>R \land M_S$

• $M \subseteq N$ means that wherever $N$ has a 0 entry, $M$ also has a 0.

  • $R \subseteq S$ means the same as $M<em>R \subseteq M</em>S$.

Inverse of a Relation

• Reversing all ordered pairs in $R$ gives the inverse relation, denoted $R^{-1}$.

  • $R^{-1} = {(b, a) | (a, b) \in R}$

• The bipartite graph for $R^{-1}$ is obtained by interchanging columns of vertices with edges.

• The matrix for $R^{-1}$ is the transpose of the matrix for $R$.

  • $M<em>{R^{-1}} = M</em>R^T$

Composition of Relations

• If $S$ is a relation from $A$ to $B$ and $R$ is a relation from $B$ to $C$, then the composition of $S$ by $R$ is $R \circ S$.

  • $R \circ S = {(a, c) | a \in A, c \in C \text{ and } \exists b \in B, \text{ such that } (a, b) \in S \text{ and } (b, c) \in R}$

• Example 8.4: Let $A = {1, 2, 3, 4}$, $B = {\alpha, \beta}$, and $C = {a, b, c}$. Further, let $S = {(1, \alpha), (1, \beta), (2, \alpha), (3, \beta), (4, \alpha)}$ and $R = {(\alpha, a), (\alpha, c), (\beta, b)}$.

  • Since $(1, \alpha) \in S$ and $(\alpha, a) \in R$, it follows that $(1, a) \in R \circ S$.

  • $R \circ S = {(1, a), (1, b), (1, c), (2, a), (2, c), (3, b), (4, a), (4, c)}$.

• Composition can be determined using bipartite graphs: $R \circ S$ has a two-edge path from $x$ to $y$.

Boolean Product of Matrices

• If $M<em>S$ is the $m \times k$ matrix of $S$ and $M</em>R$ is the $k \times n$ matrix of $R$, then the matrix $M_{R \circ S}$ represents the composition.

  • The Boolean product of $M<em>S$ and $M</em>R$ is the matrix $M_R S$ of the composition.

• Given an $m \times k$ 0-1 matrix $M$ and a $k \times n$ 0-1 matrix $N$, $M \odot N$ is an $m \times n$ 0-1 matrix where the $(i, j)$ entry is $(m<em>{i,1} \land n</em>{1,j}) \lor (m<em>{i,2} \land n</em>{2,j}) \lor … \lor (m<em>{i,k} \land n</em>{k,j})$.

• The ordinary matrix product is computed the same way as the boolean product where multiplication and addition have been replaced with and and or, respectively.

• Example: For the relations in the example above:
  $MR S = \begin{bmatrix} 1 &amp; 1 &amp; 1 \ 1 &amp; 1 &amp; 1 \ 0 &amp; 0 &amp; 1 \ 1 &amp; 1 &amp; 1 \end{bmatrix} = \begin{bmatrix} 1 &amp; 1 &amp; 0 \ 1 &amp; 0 &amp; 0 \ 0 &amp; 1 &amp; 0 \ 1 &amp; 0 &amp; 0 \end{bmatrix} \odot \begin{bmatrix} 1 &amp; 0 &amp; 1 \ 0 &amp; 1 &amp; 0 \ 0 &amp; 0 &amp; 0 \end{bmatrix} = MS MR$

Properties of Relations (Chapter 9)

Reflexive Relations

• A relation $R$ on $A$ is reflexive if for all $a \in A$, $aRa$.

  • Every element in the domain is related to itself.

• Example: $S(m, n)$: $m + n$ is even on the set of integers.

• Symbolic logic: $\forall a \in A, aRa$

• Digraph: Has a loop at every vertex.

• Matrix: All entries on the main diagonal are 1s.

Irreflexive Relations

• A relation $R$ on $A$ is irreflexive if $aRa$ is false for all $a \in A$.

  • No element of $A$ is related to itself.

• Digraph: Contains no loops.

• Matrix: All 0s on the main diagonal.

• Symbolic logic: $\forall a \in A, a \cancel{R} a$

Domain Specificity

• Whether a relation is reflexive or irreflexive depends on the domain.

• Example: $S(x, y)$: The square of $x$ is greater than or equal to $y$.

  • Reflexive on $N$ (natural numbers), as $n^2 \ge n$ for all $n \in N$.

  • Not reflexive on $R$ (real numbers), as \left( \frac{1}{2} \right)^2 = \frac{1}{4} < \frac{1}{2}.

Symmetric Relations

• A relation $R$ on $A$ is symmetric if $(a, b) \in R \implies (b, a) \in R$.

  • $R = R^{-1}$

  • If $a$ is related to $b$, then $b$ is related to $a$.

• Digraph: Every non-loop has a return edge.

• Matrix: $M = M^T$ (symmetric about the main diagonal).

• Symbolic logic: $\forall a, b \in A, aRb \implies bRa$

Antisymmetric Relations

• A relation $R$ on $A$ is antisymmetric if whenever $(a, b) \in R$ and $(b, a) \in R$, then $a = b$.

  • The only objects related to each other are the same object.

• Example: The $\le$ relation for integers.

• Digraph: All streets one-way except loops.

• Matrix: If $a<em>{i,j} = 1$ and $i \ne j$, then $a</em>{j,i} = 0$.

• Symbolic logic: $\forall a, b \in A, (aRb \land bRa) \implies (a = b)$

Transitive Relations

• A relation $R$ on $A$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

  • $R \circ R \subseteq R$.

• Example: The $\le$ relation on $N$.

• Digraph: If there's a directed path of length two from $a$ to $c$ through $b$, there's a direct link from $a$ to $c$.

• Matrix: $M \cdot M \subseteq M$.

• Symbolic logic: $\forall a, b, c \in A, (aRb \land bRc) \implies aRc$

Examples

• Example 9.1: The "lives within one mile of" relation is reflexive, symmetric, but not antisymmetric or transitive.

• Example 9.2: $aRb \iff a \le b$ is reflexive, transitive, and antisymmetric (an ordering relation).

• Example 9.3: aRb \iff a < b is irreflexive and transitive.

• Example 9.4: A reflexive, symmetric, and transitive relation on $A = {1, 2, 3, 4, 5, 6}$.

• Example 9.5: A relation that is not reflexive, irreflexive, symmetric, or transitive but is antisymmetric.

Equivalence Relations (Chapter 10)

Concept of Equivalence

• Equivalence captures the notion of "same kind".

• Properties:

  • (1) Reflexive: Every object is equivalent to itself.

  • (2) Symmetric: If $a$ is equivalent to $b$, then $b$ is equivalent to $a$.

  • (3) Transitive: If $a$ is equivalent to $b$ and $b$ is equivalent to $c$, then $a$ is equivalent to $c$.

Definition of Equivalence Relation

• A relation $E$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.

• If $(s, t) \in E$, then $s$ and $t$ are considered to be of the same kind.

Equivalence Class

• The equivalence class of $x$ (denoted as $[x]$) is the set of all elements in $A$ that are equivalent to $x$.

  • $[x] = {y \in A | yEx}$

Partitioning

• Equivalence classes partition the set $A$ into separate pieces.

• Example: Considering cards with the same rank splits a deck into 13 equivalence classes.

Examples of Equivalence Relations

• Example 10.1: Equality on $N$. $aRb \iff a = b$.

• Example 10.2: Logical equivalence on logical propositions. $pRq \iff p \equiv q$.

• Example 10.3: Same age on people. $aRb \iff a$ and $b$ are the same age.

• Example 10.4: Given by a matrix (from exercise 3, part a) of chapter 9).

• Example 10.5: Same parity on integers. $aPb \iff a$ and $b$ are both even or both odd.

• Example 10.6: The equivalence class of 2 for the same parity relation is the set of all even integers. $[2] = {\dots, -4, -2, 0, 2, 4, \dots}$.

Theorem 10.7

• Let $E$ be an equivalence relation on a set $A$, and let $a \in A$. Then there is exactly one equivalence class to which $a$ belongs.

• Proof: $E$ is reflexive, so $aEa$, and thus $a \in [a]$ is true. If $a \in [b]$ then $[b] = [a]$.

  • Need to show: If $c \in [a]$, then $c \in [b]$, and if $c \in [b]$, then $c \in [a]$.

  • Direct proof (part 2): If $c \in [b]$, then $cEb$. Since $a \in [b]$, $aEb$, and by symmetry, $bEa$. By transitivity, $cEa$, meaning $c \in [a]$.

Definition 10.8

• A partition of a set A is a collection of nonempty, pairwise disjoint subsets of A, so that A is the union of the subsets in the collection.

• A partition of a set $A$ is a collection of nonempty, pairwise disjoint subsets of $A$, such that $A$ is the union of the subsets in the collection.

Digraph and Matrix Representation

• Digraph: Every vertex in an equivalence class is connected to every other vertex in that class (including itself).

• Matrix: Can be arranged in block diagonal form with all-1s matrices on the diagonal.