Binary Relations • Definition ○ A binary relation R from a set A to a set B is a subset R⊆A×B. • Example ○ Let A={0,1,2} and B={a,b} ○ {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. ○ We can represent this relation graphically or using a table: • Note ○ Relations are more general than functions ○ A function is a relation where exactly one element of B is related to each element of A Binary Relation on a Set • Definition ○ A binary relation R on a set A is a subset of A×A or a relation from A to A. • Example 1 ○ Suppose that A={a,b,c} ○ Then R={(a,a),(a,b), (a,c)} is a relation on A • Example 2 ○ Let A={1, 2, 3, 4} ○ The ordered pairs in the relation R={(a,b)│a divides b} are ○ {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3),(4,4)} • Question: How many relations are there on a set A? ○ Because a relation on A is the same thing as a subset of A×A ○ We count the subsets of A×A. ○ Since A×A has n^2 elements when A has n elements ○ And a set with m elements has 2^m subsets ○ There are 2(|A|2 ) subsets of A×A. ○ Therefore, there are 2(|A|2 ) relations on a set A. • Example 3 ○ Consider these relations on the set of integers: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} § R_6={(a,b)│a+b≤3} ○ Note § These relations are on an infinite set and each of these relations is an infinite set § R_5 can be viewed as a function § Our definition of a function f:A→B is a subset of A×B § Therefore every function is a relation ○ Which of these relations contain each of the pairs § (1,1), (1, 2), (2, 1), (1, −1), and (2, 2)? ○ Solution § (1,1) is in R_1, R_3, R_4, and R_6 § (1,2) is in R_1 and R_6 § (2,1) is in R_2, R_5, and R_6 § (1, −1) is in R_2, R_3, and R_6 § (2,2) is in R_1, R_3, and R_4 Reflexive Relations • Definition ○ R is reflexive if and only if (a,a)∈R for every element a∈A ○ Written symbolically, R is reflexive if and only if ○ ∀x[x∈U→(x,x)∈R] • Note ○ If A = ∅ then the empty relation is reflexive vacuously. ○ That is the empty relation on an empty set is reflexive! • Example ○ The following relations on the integers are reflexive: § R_1={(a,b)│a≤b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following relations are not reflexive: § R_2={(a,b)│a b} (note that 3 ≯ 3) § R_5={(a,b)│a=b+1} (note that 3 ≠ 3 + 1) § R_6={(a,b)│a+b≤3} (note that 4+4≰3) Antireflexive Relations • Definition ○ R is antireflexive if and only if (a,a)∉R for every element a∈A ○ Written symbolically, R is antireflexive if and only if ○ ∀x[x∈U→(x,x)∉R] • Note ○ Antireflexive is different from not reflexive • Example ○ The following relations on the integers are antireflexive § R_2={(a,b)│a b} § R_5={(a,b)│a=b+1} ○ R_6={(a,b)│a+b≤3} is neither reflexive nor antireflexive Symmetric Relations • Definition ○ R is symmetric if and only if (b,a)∈R whenever (a,b)∈R,∀a,b∈A ○ Written symbolically, R is symmetric if and only if ○ ∀x∀y[(x,y)∈R→(y,x)∈R] • Example ○ The following relations on the integers are symmetric: § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_6={(a,b)│a+b≤3} ○ The following are not symmetric: § R_1={(a,b)│a≤b} (note that 3 ≤ 4, but 4 ≰ 3) § R_2={(a,b)│a b} (note that 4 3, but 3 ≯ 4) § R_5={(a,b)│a=b+1} (note that 4 = 3 + 1, but 3 ≠ 4 + 1) Antisymmetric Relations • Definition ○ R is antisymmetric if and only if a=b whenever (a,b),(b,a)∈R,∀a,b∈A ○ Written symbolically, R is antisymmetric if and only if ○ ∀x∀y[(x,y)∈R∧(y,x)∈R→x=y] • Note ○ For any integer, if a≥b and a≤b, then a=b • Example ○ The following relations on the integers are antisymmetric: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} ○ The following relations are not antisymmetric: § R_3={(a,b)│a=b or a=−b} (note that (1,−1),(−1,1)∈R_3) § R_6={(a,b)│a+b≤3} (note that (1,2),(2,1)∈R_6) Transitive Relations • Definition ○ R is transitive if and only if (a,c)∈R whenever (a,b),(b,c)∈R, ∀a,b,c∈A ○ Written symbolically, R is transitive if and only if ○ ∀x∀y∀z[(x,y)∈R∧(y,z)∈R→(x,z)∈R] • Note ○ For every integer, a≤b and b≤c, then b≤c • Example ○ The following relations on the integers are transitive: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following are not transitive: § R_5={(a,b)│a=b+1} (note that (3,2),(4,3)∈R_5, but (3,3)∉R_5), § R_6={(a,b)│a+b≤3} (note that (2,1),(1,2)∈R_6, but (2,2)∉R_6). Combining Relations • Given two relations R_1 and R_2 • We can combine them using basic set operations to form new relations • Example ○ Let A={1,2,3} and B={1,2,3,4} ○ The relations R_1 = {(1,1),(2,2),(3,3)} and R_2 = {(1,1),(1,2),(1,3),(1,4)} can be combined using basic set operations to form new relations: ○ R_1 ∪ R_2 ={(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)} ○ R_1 ∩ R_2 ={(1,1)} ○ R_1 − R_2 ={(2,2),(3,3)} ○ R_2 − R_1 ={(1,2),(1,3),(1,4)} Inverse • Definition ○ Let R be a relation from A to B ○ The inverse of R is the relation § R^(−1)={(a,b)│(b,a)∈R} • Proposition ○ R is symmetric if and only if R=R^(−1) Composition • Definition ○ Suppose § R_1 is a relation from a set A to a set B. § R_2 is a relation from B to a set C ○ Then the composition of R_2 with R_1 is a relation from A to C where § if (x,y) is a member of R_1 § and (y,z) is a member of R_2 § then (x,z) is a member of R_2∘R_1 • Example ○ R_2∘R_1={(b,x),(b,z)} Powers of a Relation • Definition ○ Let R be a binary relation on A ○ Then the powers R_n of the relation R can be defined inductively by: ○ Basis Step: R_1=R ○ Inductive Step: R_(n+1)=R_n∘R • The powers of a transitive relation are subsets of the relation • This is established by the following theorem: • Theorem 1 ○ The relation R on a set A is transitive iff R_n⊆R for n = 1,2,3… ○ (see the text for a proof via mathematical induction)
