relation and operations power point presentation

relation and operations power point presentation

1. Relations and Operations Prepared by: MARIELA A. CAMBA

2. Concepts of Relations Theory of relations is introduced by Augustus De Morgan. We deal with relational operators, namely, ≤, <, >, ≥, ≠, and = are commonly used defining the relations. In set theory, the concept subset represents the relationship between the two sets. DEFINITION 2.1: A relation R on a set S (more precisely, a binary relation on S, since it will be a relation between pairs of elements of S) is a subset of SxS.

3. Properties of Binary Operations R eflexive relation I rreflexive relation S ymmetric relation A ntisymmetric relation T ransitive relation

4. R eflexive relation A relation R on a set A is called reflexive if and only if ( a, a ) R for every element a of A. Example 1: The relation ≤ on the set of integers {1, 2, 3} is {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} and it is reflexive because (1, 1), (2, 2), (3, 3) are in this relation. As a matter of fact ≤ on any set of numbers is also reflexive. Similarly ≥ and = on any set of numbers are reflexive. However,( < or >) on any set of numbers is not reflexive. Example 2 : The relation ⃀ on the set of subsets of {1, 2} is and it is reflexive. In fact relation ⃀ on any collection of sets is reflexive.

5. I rreflexive relation A relation R on a set A is called irreflexive if and only if <a, a> R for every element a of A. Example 1: The relation > (or <) on the set of integers {1, 2, 3} is irreflexive. In fact it is irreflexive for any set of numbers. Example 2: The relation {(1, 1 ), (1, 2 ), ( 1, 3 ), ( 2, 3), ( 3, 3 ) } on the set of integers {1, 2, 3} is neither reflexive nor irreflexive.

6. S ymmetric relation A relation R on a set A is called symmetric if and only if for any a, and b in A, whenever (a, b) R , <b, a> R . Example 1 : The relation = on the set of integers {1, 2, 3} is {(1, 1) , (2, 2) (3, 3) } and it is symmetric. Similarly, = on any set of numbers is symmetric. However, < (or >), ≤ (or ≥ on any set of numbers is not symmetric. Example 2: The relation "being acquainted with" on a set of people is symmetric.

7. A ntisymmetric relation A relation R on a set A is called antisymmetric if and only if for any a, and b in A, whenever <a, b> R , and <b, a> R , a = b must hold. Equivalently, R is antisymmetric if and only if whenever <a, b> R , and a b , <b, a> R . Thus, in an antisymmetric relation no pair of elements are related to each other. Example: The relation < (or >) on any set of numbers is antisymmetric. So is the equality relation on any set of numbers.

8. Transitive relation A relation R on a set A is called transitive if and only if for any a, b, and c in A, whenever <a, b> R , and <b, c> R , <a, c> R . Example: The relation on the set of integers {1, 2, 3} is transitive, because for (1, 2) and (2, 3) in ≤, (1, 3) is also in ≤ , for (1, 1) and (1, 2) in ≤, (1, 2) is also in ≤, and similarly for the others. As a matter of fact ≤ on any set of numbers is also transitive. Similarly ≥ and = on any set of numbers are transitive.

9. Equivalence Relations A binary relation R on a set A is an equivalence relation if and only if: (1) R is reflexive (2) R is symmetric, and (3) R is transitive.

10. The equality relation (=) on a set of numbers such as { 1, 2, 3 } is an equivalence relation. The congruent modulo m relation on the set of integers i.e. {<a, b>| a b (mod m)}, where m is a positive integer greater than 1, is an equivalence relation. Taking this discrete structures course together this semester is another equivalence relation. Examples Note that the equivalence relation on hours on a clock is the congruent mod 12, and that when m = 2, i.e. the congruent mod 2, all even numbers are equivalent and all odd numbers are equivalent. Thus the set of integers are divided into two subsets: evens and odds.

11. Equivalence relations can also be represented by a digraph since they are a binary relation on a set. For example, the digraph of the equivalence relation congruent mod 3 on {0, 1, 2, 3, 4, 5 , 6} is as shown below. It consists of three connected components. The set of even numbers and that of odd numbers in the equivalence relation of congruent mod 2, and the set of integers equivalent to a number between 1 and 12 in the equivalence relation on hours in the clock example are called an equivalence class.

12. Equivalence class For an equivalence relation R on a set A, the set of the elements of A that are related to an element, say a, of A is called the equivalence class of element a and it is denoted by [a]. where N is the set of natural numbers. There are altogether twelve of them.

13. Partition Let A be a set and let A1, A2, ..., An be subsets of A. Then {A1, A2, ..., An} is a partition of A, if and only if:

14. Theorem 1: The set of equivalence classes of an equivalence relation on a set A is a partition of A. Conversely, a partition of a set A determines an equivalence relation on A.

15. ORDERING IN SETS A set S will be said to be partially ordered (the possibility of a total ordering is not excluded) by a binary relation R if for arbitrary a, b, c S, ( i ) R is reflexive, a R a; (ii) R is anti-symmetric, a R b and b R a if and only if a = b; (iii ) R is transitive, a R b and b R c implies a R c.

16. (a) In the orderings of A of Figs. 2-1 and 2-2, the first element is 1 and the last element is 12. Also, 1 is a minimal element and 12 is a maximal element. (b) In Fig. 2-3, S 1⁄4 fa, b, c, d g has a first element a but no last element. Here, a is a minimal element while c and d are maximal elements. (c) In Fig. 2-4, S 1⁄4 fa, b, c, d, eg has a last element e but no first element. Here, a and b are minimal elements while e is a maximal element.

17. OPERATIONS A binary opertaion ‘‘o” on a non-empty set S is a mapping which associates with each ordered pair (a, b) of elements of S a uniquely defined element a o b of S. In brief, a binary operation on a set S is a mapping of S X S into S.

18. 1. Addition is a binary operation on the set of even natural numbers (the sum of two even natural numbers is an even natural number) but is not a binary operation on the set of odd natural numbers (the sum of two odd natural numbers is an even natural number). EXAMPLES 2. Neither addition nor multiplication are binary operations on S = {0, 1, 2, 3, 4} since, for example, 2 + 3 = 5 S and 2 . 3 = 6 S.

19. 3. The operation a o b = a is a binary operation on the set of real numbers. In this example, the operation assigns to each ordered pair of elements (a, b) the first element a. EXAMPLES 4. In Table 2-1, defining a certain binary operation on the set A = {a, b, c, d, e} is to be read as follows: For every ordered pair (x, y) of A x A, we find x o y as the entry common to the row labeled x and the column labeled y. For example, the encircled element is d o e (not e o d ).

20. Types of Binary Operations A binary operation on a set S is called commutative whenever x o y = y o x for all x, y S.

21. We take the set of numbers on which the binary operations are performed as X. The operations (addition, subtraction, division, multiplication, etc.) can be generalized as a binary operation is performed on two elements (say a and b) from set X. The result of the operation on a and b is another element from the same set X. Thus, the binary operation can be defined as an operation x which is performed on a set A. The function is given by x: A x A → A. So the operation  x  performed on operands  a  and  b  is denoted by a x b.

22. Let us show that addition is a binary operation on real numbers (R) and  natural numbers  (N). So if we add two operands which are natural numbers  a  and  b , the result will also be a natural number. The same holds good for real numbers. Hence, Let us show that multiplication is a binary operation on real numbers (R) and natural numbers (N). So if we multiply two operands which are natural numbers  a  and  b , the result will also be a natural number. The same holds good for real numbers. Hence, Examples

23. Let us show that subtraction is a binary operation on real numbers (R). So if we subtract two operands which are real numbers  a  and  b , the result will also be a real number. The same does not hold good for natural numbers. It is because if we take two natural numbers, 3 and 4 as  a  and  b , then 3 – 4 = -1, which is not a natural number. Hence, Similarly, the division cannot be defined on  real numbers . This is because / : R x R → R is given by (a, b)→ aa/b. Now if we take  b  as 0 here, a/b is not defined. Examples

24. Thank you