This chapter presents the following content: Relations and their properties, n-ary relations and their applications (not currently included in overheads), representing relations, closures of relations (not currently included in overheads), equivalence relations, partial orderings. | Relations Chapter 9 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Relations and Their Properties n-ary Relations and Their Applications (not currently included in overheads) Representing Relations Closures of Relations (not currently included in overheads) Equivalence Relations Partial Orderings Relations and Their Properties Section Section Summary Relations and Functions Properties of Relations Reflexive Relations Symmetric and Antisymmetric Relations Transitive Relations Combining Relations 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 relations from a set A to a set B graphically or using a table: 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: Suppose that A = {a,b,c}. Then R = {(a,a),(a,b), (a,c)} is a relation on A. 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), and (4, 4). Binary Relation on a Set (cont.) Question: How many relations are there on a set A? Solution: 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 n2 elements when A has n elements, and a set with m elements has 2m subsets, there are subsets of A × A. Therefore, there are relations on a set A. Binary Relations on a Set (cont.) Example: Consider these relations on the set of integers: R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b}, R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1}, R3 = {(a,b) | a = b or a = −b}, R6 = {(a,b) | a + b ≤ 3}. Which of these . | Relations Chapter 9 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Relations and Their Properties n-ary Relations and Their Applications (not currently included in overheads) Representing Relations Closures of Relations (not currently included in overheads) Equivalence Relations Partial Orderings Relations and Their Properties Section Section Summary Relations and Functions Properties of Relations Reflexive Relations Symmetric and Antisymmetric Relations Transitive Relations Combining Relations 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 relations from a set A to a set B graphically or using a table: Relations are more general than functions. A function is a relation where exactly one element of B is
