Math 541 – 4/16 Apr 18, 2018 Shawn Math 541 No comments yet Math 541 – 4/11 Apr 18, 2018 Shawn Math 541 No comments yet 9.1 Relations and Their Properties Apr 18, 2018 Shawn Math 240 No comments yet 7.1 An Introduction to Discrete Probability Apr 18, 2018 Shawn Math 240 No comments yet
![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)](https://shawnzhong.com/wp-content/uploads/2018/04/img_5ad75495a5325.png)
