Binary Relations

# Binary Relations ## Objectifs et prérequis This chapter introduces binary relations as a fundamental concept in discrete mathematics, building on set theory to formalize relationships between elements. Students will learn to define and manipulate ordered pairs, Cartesian products, and various types of relations (reflexive, symmetric, transitive, equivalence, and order relations). They will develop the ability to analyze properties of relations, construct equivalence classes, and distinguish between partial and total orders. Prerequisites include familiarity with set notation, union, intersection, complement, and basic logical operators (and, or, not, implies). ## Introduction In mathematics, we often need to describe how elements from one set are connected to elements from another set—or even within the same set. For instance, “is less than” connects numbers, “is a sibling of” connects people, and “is congruent to modulo n” connects integers. Binary relations provide a precise framework for such connections. This chapter begins with the foundational idea of ordered pairs and the Cartesian product, then progresses to defining binary relations and examining their key properties. We will explore equivalence relations, which partition sets into disjoint classes, and order relations, which allow us to compare elements in a structured way. Mastery of these concepts is essential for advanced topics in algebra, logic, and computer science. ## I. Ordered pairs and Cartesian product of two sets An ordered pair is a fundamental building block for defining relations. Unlike a set, where order does not matter, an ordered pair preserves the sequence of its components. > **Definition**: An ordered pair $(a, b)$ consists of two elements where the first component is $a$ and the second is $b$. Two ordered pairs $(a, b)$ and $(c, d)$ are equal if and only if $a = c$ and $b = d$. The Cartesian product of two sets generalizes this idea to all possible ordered pairs formed from elements of the two sets. > **Definition**: Given two sets $A$ and $B$, the Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ such that $a \in A$ and $b \in B$. Symbolically: > $$ > A \times B = \{ (a, b) \mid a \in A \land b \in B \} > $$ ### Examples **Example 1**: Let $A = \{1, 2\}$ and $B = \{x, y\}$. Then: $$ A \times B = \{ (1, x), (1, y), (2, x), (2, y) \} $$ Note that $B \times A = \{ (x, 1), (x, 2), (y, 1), (y, 2) \}$, which is different from $A \times B$ unless $A = B$. **Example 2**: If $A = \emptyset$ or $B = \emptyset$, then $A \times B = \emptyset$, since there are no elements to form pairs. **Example 3**: For $A = \mathbb{R}$ (the set of real numbers), $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ represents the Euclidean plane, where each point corresponds to an ordered pair $(x, y)$. ### Properties of Cartesian product - $A \times B \neq B \times A$ in general (non-commutative). - $A \times (B \cup C) = (A \times B) \cup (A \times C)$ - $A \times (B \cap C) = (A \times B) \cap (A \times C)$ - $A \times (B \setminus C) = (A \times B) \setminus (A \times C)$ - If $A \subseteq B$, then $A \times C \subseteq B \times C$ for any set $C$. ### Exercises d'application corrigés **Exercise 1**: Let $A = \{a, b, c\}$ and $B = \{1, 2\}$. Find $A \times B$ and $B \times A$. Are they equal? **Solution**: $A \times B = \{ (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) \}$ $B \times A = \{ (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) \}$ Since the ordered pairs differ in order (e.g., $(a,1) \neq (1,a)$), $A \times B \neq B \times A$. **Exercise 2**: If $A \times B = \{ (x, p), (x, q), (y, p), (y, q) \}$, deduce $A$ and $B$. **Solution**: The first components are $x$ and $y$, so $A = \{x, y\}$. The second components are $p$ and $q$, so $B = \{p, q\}$. **Exercise 3**: Show that $(A \cup B) \times C = (A \times C) \cup (B \times C)$. **Solution**: Let $(z, w) \in (A \cup B) \times C$. Then $z \in A \cup B$ and $w \in C$. So $z \in A$ or $z \in B$. If $z \in A$, then $(z, w) \in A \times C$; if $z \in B$, then $(z, w) \in B \times C$. Thus $(z, w) \in (A \times C) \cup (B \times C)$. Conversely, if $(z, w) \in (A \times C) \cup (B \times C)$, then either $(z, w) \in A \times C$ or $(z, w) \in B \times C$. In either case, $z \in A \cup B$ and $w \in C$, so $(z, w) \in (A \cup B) \times C$. Hence equality holds. ## II. Binary Relation and Properties of relations in a set 1 Having defined the Cartesian product, we now define a binary relation as a subset of such a product. This allows us to formalize any relationship between elements of two sets (or within one set). > **Definition**: A binary relation $R$ from a set $A$ to a set $B$ is a subset of $A \times B$. If $(a, b) \in R$, we write $a \, R \, b$ and say “$a$ is related to $b$ by $R$”. If $A = B$, we say $R$ is a relation on $A$. When $A = B$, we focus on relations on a single set, which allows us to study internal properties like reflexivity, symmetry, and transitivity. > **Definition (Reflexive)**: A relation $R$ on a set $A$ is reflexive if for every $a \in A$, $(a, a) \in R$. That is, $a \, R \, a$ for all $a \in A$. > **Definition (Symmetric)**: A relation $R$ on a set $A$ is symmetric if for all $a, b \in A$, if $(a, b) \in R$ then $(b, a) \in R$. Symbolically: $\forall a,b \in A, (a,b) \in R \implies (b,a) \in R$. > **Definition (Transitive)**: A relation $R$ on a set $A$ is transitive if for all $a, b, c \in A$, if $(a, b) \in R$ and $(b, c) \in R$ then $(a, c) \in R$. Symbolically: $\forall a,b,c \in A, ((a,b) \in R \land (b,c) \in R) \implies (a,c) \in R$. ### Examples **Example 1**: Let $A = \{1, 2, 3\}$ and define $R = \{ (1,1), (2,2), (3,3), (1,2), (2,1) \}$. - Reflexive? Yes, because $(1,1), (2,2), (3,3) \in R$. - Symmetric? Check: $(1,2) \in R \implies (2,1) \in R$ (yes); $(2,1) \in R \implies (1,2) \in R$ (yes); no other asymmetric pairs. So yes. - Transitive? Check: $(1,2) \in R$ and $(2,1) \in R \implies$ should have $(1,1) \in R$ (yes). $(2,1) \in R$ and $(1,2) \in R \implies (2,2) \in R$ (yes). No other chains. So transitive. Thus $R$ is reflexive, symmetric, and transitive. **Example 2**: Let $A = \mathbb{Z}$ (integers) and define $R$ by $a \, R \, b$ iff $a - b$ is even. - Reflexive? $a - a = 0$, which is even → yes. - Symmetric? If $a - b$ is even, then $b - a = -(a - b)$ is even → yes. - Transitive? If $a - b$ even and $b - c$ even, then $(a - b) + (b - c) = a - c$ is even → yes. So $R$ is an equivalence relation (we’ll see this formally later). **Example 3**: Let $A = \{1, 2, 3\}$ and $R = \{ (1,2), (2,3) \}$. - Reflexive? Missing $(1,1), (2,2), (3,3)$ → no. - Symmetric? $(1,2) \in R$ but $(2,1) \notin R$ → no. - Transitive? $(1,2) \in R$ and $(2,3) \in R \implies$ should have $(1,3) \in R$, but it’s not → no. So $R$ is none of the three. ### Exercises d'application corrigés **Exercise 1**: Let $A = \{x, y, z\}$ and $R = \{ (x,x), (y,y), (z,z), (x,y), (y,z) \}$. Determine if $R$ is reflexive, symmetric, transitive. **Solution**: - Reflexive: $(x,x), (y,y), (z,z) \in R$ → yes. - Symmetric: $(x,y) \in R$ but $(y,x) \notin R$ → no. - Transitive: $(x,y) \in R$ and $(y,z) \in R \implies$ need $(x,z) \in R$, but it’s absent → no. So $R$ is reflexive only. **Exercise 2**: On $A = \{1,2,3,4\}$, define $R$ by $a \, R \, b$ iff $a \leq b$. Check reflexivity, symmetry, transitivity. **Solution**: - Reflexive: $a \leq a$ for all $a$ → yes. - Symmetric: $1 \leq 2$ is true but $2 \leq 1$ is false → no. - Transitive: If $a \leq b$ and $b \leq c$, then $a \leq c$ → yes. So $R$ is reflexive and transitive, but not symmetric. **Exercise 3**: Prove that if $R$ is symmetric and transitive, then it is not necessarily reflexive. **Solution**: Counterexample: Let $A = \{1,2\}$ and $R = \emptyset$. - Symmetric: Vacuously true (no pairs to violate). - Transitive: Vacuously true. - Reflexive? $(1,1) \notin R$ and $(2,2) \notin R$ → not reflexive. Thus symmetry and transitivity do not imply reflexivity. ## III. Binary Relation and Properties of relations in a set 2 We continue examining properties of relations, focusing on antisymmetry and asymmetry, which are crucial for defining order relations. We also consider how properties combine and the implications for relation classification. > **Definition (Antisymmetric)**: A relation $R$ on a set $A$ is antisymmetric if for all $a, b \in A$, if $(a, b) \in R$ and $(b, a) \in R$, then $a = b$. Symbolically: $\forall a,b \in A, ((a,b) \in R \land (b,a) \in R) \implies a = b$. > **Definition (Asymmetric)**: A relation $R$ on a set $A$ is asymmetric if for all $a, b \in A$, if $(a, b) \in R$ then $(b, a) \notin R$. Symbolically: $\forall a,b \in A, (a,b) \in R \implies (b,a) \notin R$. Note: Asymmetry implies antisymmetry and irreflexivity (no $(a,a)$), but the converse is not true. ### Examples **Example 1**: Let $A = \{1,2,3\}$ and $R = \{ (1,2), (2,3), (1,3) \}$ (the “less than” relation on this set). - Antisymmetric? Check: No pair $(a,b)$ and $(b,a)$ both in $R$ unless $a=b$, but there are no such pairs (e.g., $(1,2) \in R$ but $(2,1) \notin R$). So the condition holds vacuously → yes. - Asymmetric? $(1,2) \in R \implies (2,1) \notin R$ (true); similarly for others → yes. - Reflexive? Missing $(1,1), (2,2), (3,3)$ → no. - Symmetric? $(1,2) \in R$ but $(2,1) \notin R$ → no. - Transitive? $(1,2) \in R$ and $(2,3) \in R \implies (1,3) \in R$ → yes. So $R$ is asymmetric, antisymmetric, and transitive. **Example 2**: Let $A = \{1,2,3\}$ and $R = \{ (1,1), (2,2), (3,3), (1,2), (2,1) \}$. - Antisymmetric? $(1,2) \in R$ and $(2,1) \in R$ but $1 \neq 2$ → violates antisymmetry → no. - Asymmetric? $(1,2) \in R$ but $(2,1) \in R$ → not asymmetric. - Reflexive? Yes. - Symmetric? Yes (as in earlier example). - Transitive? Yes (as before). So $R$ is reflexive, symmetric, transitive, but neither antisymmetric nor asymmetric. **Example 3**: Let $A = \mathbb{N}$ and define $R$ by $a \, R \, b$ iff $a$ divides $b$ (written $a \mid b$). - Reflexive? $a \mid a$ → yes. - Symmetric? $2 \mid 4$ but $4 \nmid 2$ → no. - Antisymmetric? If $a \mid b$ and $b \mid a$, then $a = b$ (for positive integers) → yes. - Transitive? If $a \mid b$ and $b \mid c$, then $a \mid c$ → yes. So $R$ is reflexive, antisymmetric, and transitive — a partial order. ### Exercises d'application corrigés **Exercise 1**: On $A = \{a,b,c\}$, let $R = \{ (a,a), (b,b), (c,c), (a,b), (b,c) \}$. Is $R$ antisymmetric? Asymmetric? **Solution**: - Antisymmetric: Check all pairs where both $(x,y)$ and $(y,x)$ exist. - $(a,b) \in R$ but $(b,a) \notin R$ → ok. - $(b,c) \in R$ but $(c,b) \notin R$ → ok. - No pair has both directions unless $x=y$ (the reflexive ones). So antisymmetric → yes. - Asymmetric: Requires that if $(x,y) \in R$ then $(y,x) \notin R$. - $(a,a) \in R$ but $(a,a) \in R$ → violates asymmetry (since $(a,a)$ implies $(a,a)$ should not be in $R$, but it is). So not asymmetric (because reflexive pairs break asymmetry). Thus $R$ is antisymmetric but not asymmetric. **Exercise 2**: Show that an asymmetric relation is always antisymmetric and irreflexive. **Solution**: Let $R$ be asymmetric on $A$. - Irreflexive: Suppose for contradiction that $(a,a) \in R$ for some $a$. Then by asymmetry, $(a,a) \in R \implies (a,a) \notin R$, contradiction. So no $(a,a)$ → irreflexive. - Antisymmetric: Suppose $(a,b) \in R$ and $(b,a) \in R$. By asymmetry, $(a,b) \in R \implies (b,a) \notin R$, but we assumed $(b,a) \in R$ → contradiction. So it cannot happen that both $(a,b)$ and $(b,a)$ are in $R$ unless the premise is false. Thus the implication $((a,b)\in R \land (b,a)\in R) \implies a=b$ holds vacuously (since the antecedent is always false). Hence $R$ is antisymmetric. **Exercise 3**: On $A = \{1,2,3,4\}$, define $R$ by $a \, R \, b$ iff $a < b$. List $R$ and check all five properties: reflexive, symmetric, antisymmetric, asymmetric, transitive. **Solution**: $R = \{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) \}$ - Reflexive? No $(1,1)$ etc. → no. - Symmetric? $(1,2) \in R$ but $(2,1) \notin R$ → no. - Antisymmetric? No pair has both $(a,b)$ and $(b,a)$ → condition holds vacuously → yes. - Asymmetric? If $(a,b) \in R$ then $a<b$, so $b>a$ → $(b,a) \notin R$ → yes. - Transitive? If $a<b$ and $b<c$ then $a<c$ → yes. So $R$ is asymmetric, antisymmetric, and transitive (but not reflexive or symmetric). ## IV. Equivalence relations An equivalence relation is a relation that is reflexive, symmetric, and transitive. It generalizes the notion of equality and allows us to partition a set into disjoint subsets where elements are considered “equivalent” under the relation. > **Definition**: A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive. The key consequence of an equivalence relation is that it partitions the set into equivalence classes. > **Definition (Equivalence class)**: Let $R$ be an equivalence relation on $A$. For any $a \in A$, the equivalence class of $a$ modulo $R$, denoted $[a]_R$ or simply $[a]$ when $R$ is clear, is the set: > $$ > [a] = \{ x \in A \mid x \, R \, a \} > $$ > That is, all elements related to $a$. The fundamental theorem states that the equivalence classes of an equivalence relation form a partition of $A$: they are non-empty, pairwise disjoint, and their union is $A$. ### Examples **Example 1**: Let $A = \mathbb{Z}$ and define $R$ by $a \, R \, b$ iff $a \equiv b \pmod{3}$ (i.e., $3 \mid (a-b)$). - Reflexive: $a - a = 0$, divisible by 3 → yes. - Symmetric: If $3 \mid (a-b)$, then $3 \mid (b-a)$ → yes. - Transitive: If $3 \mid (a-b)$ and $3 \mid (b-c)$, then $3 \mid ((a-b)+(b-c)) = (a-c)$ → yes. So $R$ is an equivalence relation. Equivalence classes: $[0] = \{ \dots, -6, -3, 0, 3, 6, \dots \}$ $[1] = \{ \dots, -5, -2, 1, 4, 7, \dots \}$ $[2] = \{ \dots, -4, -1, 2, 5, 8, \dots \}$ These three classes are disjoint and cover $\mathbb{Z}$. **Example 2**: Let $A$ be the set of all triangles in a plane, and define $R$ by $\triangle_1 \, R \, \triangle_2$ iff they are congruent. - Reflexive: Every triangle is congruent to itself → yes. - Symmetric: If $\triangle_1 \cong \triangle_2$, then $\triangle_2 \cong \triangle_1$ → yes. - Transitive: If $\triangle_1 \cong \triangle_2$ and $\triangle_2 \cong \triangle_3$, then $\triangle_1 \cong \triangle_3$ → yes. So $R$ is an equivalence relation. Equivalence classes: Each class consists of all triangles congruent to a given one (same size and shape). **Example 3**: Let $A = \{1,2,3,4,5,6\}$ and define $R$ by $a \, R \, b$ iff $a$ and $b$ have the same parity (both even or both odd). - Reflexive: Same parity as self → yes. - Symmetric: If $a$ and $b$ same parity, then $b$ and $a$ same → yes. - Transitive: If $a$ same parity as $b$, and $b$ same as $c$, then $a$ same as $c$ → yes. Equivalence classes: $[1] = [3] = [5] = \{1,3,5\}$ (odd numbers) $[2] = [4] = [6] = \{2,4,6\}$ (even numbers) Two disjoint classes whose union is $A$. ### Exercises d'application corrigés **Exercise 1**: Let $A = \{1,2,3,4\}$ and $R = \{ (1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3) \}$. Show $R$ is an equivalence relation and find the equivalence classes. **Solution**: - Reflexive: All $(a,a)$ present → yes. - Symmetric: $(1,2)\in R \implies (2,1)\in R$; $(3,4)\in R \implies (4,3)\in R$; others are self-pairs → yes. - Transitive: Check chains: - $(1,2)$ and $(2,1) \implies (1,1)\in R$ (yes) - $(2,1)$ and $(1,2) \implies (2,2)\in R$ (yes) - $(3,4)$ and $(4,3) \implies (3,3)\in R$ (yes) - $(4,3)$ and $(3,4) \implies (4,4)\in R$ (yes) - No cross chains like $(1,2)$ and $(2,3)$ because $(2,3)\notin R$ So transitive → yes. Thus $R$ is an equivalence relation. Equivalence classes: $[1] = \{ x \mid x\,R\,1 \} = \{1,2\}$ (since $1\,R\,1$, $2\,R\,1$) $[2] = \{1,2\}$ $[3] = \{3,4\}$ $[4] = \{3,4\}$ So classes: $\{1,2\}$ and $\{3,4\}$. **Exercise 2**: On $A = \mathbb{Z}$, define $R$ by $a \, R \, b$ iff $a - b$ is divisible by 4. Prove it’s an equivalence relation and find $[0]$, $[1]$, $[2]$, $[3]$. **Solution**: - Reflexive: $a-a=0$, divisible by 4 → yes. - Symmetric: If $4 \mid (a-b)$, then $4 \mid (b-a)$ → yes. - Transitive: If $4 \mid (a-b)$ and $4 \mid (b-c)$, then $4 \mid (a-c)$ → yes. Equivalence classes (residues mod 4): $[0] = \{ \dots, -8, -4, 0, 4, 8, \dots \}$ $[1] = \{ \dots, -7, -3, 1, 5, 9, \dots \}$ $[2] = \{ \dots, -6, -2, 2, 6, 10, \dots \}$ $[3] = \{ \dots, -5, -1, 3, 7, 11, \dots \}$ **Exercise 3**: Let $R$ be an equivalence relation on $A$. Prove that for any $a,b \in A$, either $[a] = [b]$ or $[a] \cap [b] = \emptyset$. **Solution**: Suppose $[a] \cap [b] \neq \emptyset$. Then $\exists c \in A$ such that $c \in [a]$ and $c \in [b]$, i.e., $c\,R\,a$ and $c\,R\,b$. By symmetry, $a\,R\,c$. By transitivity: $a\,R\,c$ and $c\,R\,b \implies a\,R\,b$. Now show $[a] \subseteq [b]$: Let $x \in [a]$, so $x\,R\,a$. Since $a\,R\,b$ and $x\,R\,a$, by transitivity $x\,R\,b$ → $x \in [b]$. Similarly, $[b] \subseteq [a]$: Let $y \in [b]$, so $y\,R\,b$. Since $b\,R\,a$ (from $a\,R\,b$ by symmetry) and $y\,R\,b$, transitivity gives $y\,R\,a$ → $y \in [a]$. Thus $[a] = [b]$. If $[a] \cap [b] = \emptyset$, the alternative holds. Hence either $[a] = [b]$ or $[a] \cap [b] = \emptyset$. ## V. Equivalence classes This section deepens the understanding of equivalence classes, emphasizing their role in partitioning sets and their practical use in constructing quotient sets. We also examine how to work with representatives and well-defined operations on classes. > **Definition (Quotient set)**: Let $R$ be an equivalence relation on a set $A$. The quotient set of $A$ by $R$, denoted $A/R$, is the set of all equivalence classes of $A$ under $R$: > $$ > A/R = \{ [a] \mid a \in A \} > $$ The quotient set inherits structure from $A$ when operations are well-defined on classes. ### Examples **Example 1**: Let $A = \mathbb{Z}$ and $R$ be congruence modulo 3. Then $A/R = \{ [0], [1], [2] \}$, which has three elements. We can define addition on $A/R$ by $[a] + [b] = [a+b]$. This is well-defined: if $[a] = [a']$ and $[b] = [b']$, then $a \equiv a' \pmod{3}$ and $b \equiv b' \pmod{3}$, so $a+b \equiv a'+b' \pmod{3}$, hence $[a+b] = [a'+b']$. **Example 2**: Let $A = \mathbb{R}^2$ (the plane) and define $R$ by $(x_1,y_1) \, R \, (x_2,y_2)$ iff $x_1^2 + y_1^2 = x_2^2 + y_2^2$ (same distance from origin). - Reflexive, symmetric, transitive → equivalence relation. - Equivalence class of $(x,y)$: all points on the circle centered at origin with radius $\sqrt{x^2+y^2}$. - Quotient set $A/R$: each class corresponds to a non-negative real number $r$ (the radius), so $A/R \cong [0, \infty)$. **Example 3**: Let $A$ be the set of all people, and define $R$ by “has the same birthday month as”. - Equivalence classes: 12 classes, one for each month (January-born, February-born, etc.). - Quotient set has 12 elements. ### Exercises d'application corrigés **Exercise 1**: Let $A = \{1,2,3,4,5,6\}$ and $R$ be defined by $a \, R \, b$ iff $a \equiv b \pmod{2}$. Find $A/R$ and verify that the operation $[a] \oplus [b] = [a+b]$ is well-defined. **Solution**: Equivalence classes: $[1] = [3] = [5] = \{1,3,5\}$ (odd) $[2] = [4] = [6] = \{2,4,6\}$ (even) So $A/R = \{ [\text{odd}], [\text{even}] \}$ — two elements. Check well-definedness of $\oplus$: Take $[a] = [\text{odd}]$, $[b] = [\text{even}]$. Then $a$ odd, $b$ even → $a+b$ odd → $[a+b] = [\text{odd}]$. Now suppose $[a] = [\text{odd}]'$ (e.g., $a=3$ instead of $1$), $[b] = [\text{even}]'$ (e.g., $b=4$). Then $a+b=7$ odd → $[7] = [\text{odd}]$. Similarly, if both odd: odd+odd=even → $[even]$; if both even: even+even=even → $[even]$. In all cases, the result depends only on the classes, not the representatives → well-defined. **Exercise 2**: On $A = \mathbb{Z}$, let $R$ be equivalence modulo 5. Compute $[7] + [3]$ in $A/R$ using the definition $[a]+[b]=[a+b]$. **Solution**: $[7] = [2]$ because $7 \div 5$ remainder 2. $[3] = [3]$. $[7] + [3] = [2] + [3] = [2+3] = [5] = [0]$ (since $5 \equiv 0 \pmod{5}$). So result is $[0]$. **Exercise 3**: Let $A$ be the set of all strings over $\{a,b\}$, and define $R$ by $s_1 \, R \, s_2$ iff $s_1$ and $s_2$ have the same length. Is $R$ an equivalence relation? Describe $A/R$. **Solution**: - Reflexive: Any string has same length as itself → yes. - Symmetric: If len($s_1$) = len($s_2$), then len($s_2$) = len($s_1$) → yes. - Transitive: If len($s_1$) = len($s_2$) and len($s_2$) = len($s_3$), then len($s_1$) = len($s_3$) → yes. So $R$ is an equivalence relation. Equivalence classes: For each $n \in \mathbb{N} \cup \{0\}$, the class of all strings of length $n$. Quotient set $A/R = \{ [\varepsilon], [a], [b], [aa], [ab], [ba], [bb], [aaa], \dots \}$ — one class for each possible length. Thus $A/R \cong \mathbb{N} \cup \{0\}$ (the set of non-negative integers).