Chapter 2.2

Chapter 2 Sets and Functions Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-1 1 Section 2.2 Relations Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-2 2 In listing the elements of a set, the order is not important. So, {1, 3} = {3, 1}. When we wish to indicate that a set of two elements a and b is ordered, we enclose the elements in parentheses: (a, b). Then a is called the first element and b is called the second. The important property of ordered pairs is that (a, b) = (c, d ) iff a = c and b = d. Ordered pairs can be defined using basic set theory in a clever Essentially, we way. identify the two elements in the ordered pair and specify which one comes first.

Definition 2.2.1 The ordered pair (a, b) is the set whose members are {a, b} and {a}. In symbols we have (a, b) = {{a}, {a, b}}, where we have written the singleton set first. The acceptability of this definition depends on the ordered pairs actually having the property expected of them. This we prove in the following theorem. Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-3 3 Definition: Theorem 2.2.2: Proof: (a, b) = {{a}, {a, b}} and (c, d) = {{c}, {c, d}} (a, b) = (c, d) iff a = c and b = d.

If a = c and b = d, then {{c}, {c, d}} = (c, d). Conversely, suppose that (a, b) = (c, d). Then we have {{a}, {a, b}} = {{c}, {c, d}}. (a, b) = {{a}, {a, b}} = We wish to conclude that a = c and b = d. Consider two cases: when a = b and when a b. If a = b, then {a} = {a, b}, so (a, b) = {{a}}. Since (a, b) = (c, d), we then have {{a}} = {{c}, {c, d}}. The set on the left has only one member, {a}. Thus the set on the right can have only one member, so {c} = {c, d} and c = d. But then {{a}} = {{c}}, so {a} = {c} and a = c. Thus, a = b = c = d. On the other hand, if a b Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-4 4 Definition: Theorem 2.2.2: (a, b) =

{{a}, {a, b}} and (c, d) = {{c}, {c, d}} (a, b) = (c, d) iff a = c and b = d. On the other hand, if a then from the preceding argument it follows that c d. b, (a, b) = (c, d), we must have Since {a} {{c}, {c, d}}, which means that {a} = {c} or {a} = {c, d}. In either case, we have c {a}, so a = c. Again, since (a, b) = (c, d), we must have {a, b} {{c}, {c, d}}. Thus {a, b} = {c} or {a, b} = {c, d}. But {a, b} has two distinct members and {a, b} = {c, d}. {c} has only one, so we must have Now a = c, a b and b {c, d}, which implies that Copyright 2013, 2005, 2001 Pearson Education, Inc. b = d. Section 2.2, Slide 1-5 5 Definition 2.2.4 If A and B are sets, then the Cartesian product (or cross product) of A and B, written A B, is the set of all ordered pairs (a, b) such that a A and b B.

In symbols, A B = {(a, b) : a A and b B}. Example 2.2.5 If A and B are intervals of real numbers, then in the Cartesian coordinate system with A on the horizontal axis and B on the vertical axis, A B is represented by a rectangle. For example, if A is the interval [1, 4) and B is the interval (2, 4], then A B is the rectangle shown below: y [ 4 AB B ) 2 Note: The solid lines indicate the left and top edges are included. The dashed lines indicate the right and bottom edges are not included. [ 1 A

) 4 x Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-6 6 A relation between two objects a and b is a condition involving a and b that is either true or false. When it is true, we say a is related to b; otherwise, a is not related to b. For example, less than is a relation between positive integers. We have 1 < 3 is true, 2 < 7 is true, 5 < 4 is false. When considering a relation between two objects, it is necessary to know which object comes first. For instance, 1 < 3 is true but 3 < 1 is false. So it is natural for the formal definition of a relation to depend on the concept of an ordered pair. Definition 2.2.7 Let A and B be sets. A relation between A and B is any subset R of A B. We say that an element a in A is related by R to an element b in B if (a, b) R, and we often denote this by writing a R b. The first set A is referred to as the domain of the relation and denoted by dom R. If B = A, then we speak of a relation R A A being a relation on A.

Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-7 7 Example 2.2.8 Returning to Example 2.2.5 where A = [1, 4) and B = (2, 4], the relation a R b given by a < b is graphed as the portion of A B that lies to the left of the line x = y. y [ 4 R B ) 2 x=y AB [ 1 A

) 4 x=1 x x=3 For example, we can see that 1 in A is related to all b in (2, 4]. But 3 in A is related only to those b that are in (3, 4]. Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-8 8 Certain relations are singled out because they possess the properties naturally associated with the idea of equality. Definition 2.2.9 A relation R on a set S is an equivalence relation if it has the following properties for all x, y, z in S: (a) x R x (reflexive property) (b) If x R y, then y R x. (symmetric property)

(c) If x R y and y R z, then x R z. (transitive property) Example 2.2.10 Determine which properties apply to each relation. (a) Define a relation R on by x R y if x y. It is reflexive and transitive, but not symmetric. (b) Let S be the set of all lines in the plane and let R be the relation is parallel to. It is reflexive (if we agree that a line is parallel to itself), symmetric, and transitive. (c) Let S be the set of all people who live in Chicago, and suppose that two people x and y are related by R if x lives within a mile of y. It is reflexive and symmetric, but not transitive. Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-9 9 Given an equivalence relation R on a set S, it is natural to group together all the elements that are related to a particular element. More precisely, we define the equivalence class (with respect to R ) of x S to be the set Ex = { y S : y R x}. Since R is reflexive, each element of S is in some equivalence class. Furthermore, two different equivalence classes must be disjoint. That is, if two equivalence classes overlap, they must be equal. To see this, suppose that w Ex Ey. Ex

Ey x w y x We claim that Ex = Ey. For any x Ex we have x R x. But w Ex, so w R x and, by symmetry, x R w. Also, w Ey, so w R y. Using transitivity twice, we have x R y. This implies x Ey and Ex Ey. The reverse inclusion follows in a similar manner. Thus we see that an equivalence relation R on a set S breaks S into disjoint pieces in a natural way. These pieces are an example of a partition of the set. Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-10 10 Definition 2.2.12 artition of a set S is a collection P of nonempty subsets of S such that (a) Each x S belongs to some subset A P . (b) For all A, B P , if A B, then A B = . ember of P is called a piece of the partition.

Example 2.2.13 Let S = {1, 2, 3}. Then the collection P = {{1}, {2}, {3}} is a partition of S. The the collection P = {{1, 2}, {3}} is also a partition of S. S S 1 2 3 P = {{1}, {2}, {3}} 1 2 3 P = {{1, 2}, {3}} The collection P = {{1, 2}, {2, 3}} is not a partition of S because {1, 2} and {2, 3} are not disjoint. Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-11 11 Not only does an equivalence relation on a set S determine a partition of S, but the partition can be used to determine the relation.

Theorem 2.2.17 Let R be an equivalence relation on a set S. Then { Ex : x S} is a partition of S. The relation belongs to the same piece as is the same as R. Conversely, if P is a partition of S, let P be defined by x P y iff x and y are in the same piece of the partition. Then P is an equivalence relation and the corresponding partition into equivalence classes is the same as P . Proof: Let R be an equivalence relation on S. We have already shown that {Ex : x S} is a partition of S. Now suppose that P is the relation belongs to the same piece (equivalence class) as. Then xPy iff x, y Ez for some z S. iff x R z and y R z for some z S. iff x R z and z R y for some z S. iff xRy Thus, P and R are the same relation. Copyright 2013, 2005, 2001 Pearson Education, Inc.

Section 2.2, Slide 1-12 12 Not only does an equivalence relation on a set S determine a partition of S, but the partition can be used to determine the relation. Theorem 2.2.17 Let R be an equivalence relation on a set S. Then {Ex : x S} is a partition of S. The relation belongs to the same piece as is the same as R. Conversely, if P is a partition of S, let P be defined by x P y iff x and y are in the same piece of the partition. Then P is an equivalence relation and the corresponding partition into equivalence classes is the same as P . Proof: Conversely, suppose that P is a partition of S and let P be defined by x P y iff x and y are in the same piece of the partition. Clearly, P is reflexive and symmetric. To see that P is transitive, suppose that x P y and y P z. Then y Ex Ez. But this implies that Ex = Ez by the contrapositive of 2.2.12(b), so x P z. Finally, the equivalence classes of P correspond to the pieces of P because of the way P was defined. Copyright 2013, 2005, 2001 Pearson Education, Inc. Section 2.2, Slide 1-13 13

Recently Viewed Presentations

  • Introduction to Introduction to Database Systems

    Introduction to Introduction to Database Systems

    From Relational Algebra to the Structured Query Language Rose-Hulman Institute of Technology Curt Clifton
  • Health Trends Review - Institute and Faculty of Actuaries

    Health Trends Review - Institute and Faculty of Actuaries

    Derek Wanless April 2002 * ... effective links and communication between different parts of the services 'Comfortable hotel services' not the Ritz but not a hostel 'A patient-centred service' Not all patients are the same - not just income, gender...
  • How to write a Strong thesis! - elabuehler.weebly.com

    How to write a Strong thesis! - elabuehler.weebly.com

    Debatable. A good argumentative thesis is centered on a debatable topic. Back in the '80s, teens loved to say "that's debatable" about claims they didn't agree with (such as "you should clean your room" and "you shouldn't go to that...
  • The Seven Wonders of The World

    The Seven Wonders of The World

    Moisés & el Cruce del Mar Rojo ¿Verdad o Ficción?
  • Roma Mater - Bishop Ireton High School

    Roma Mater - Bishop Ireton High School

    Rome was the site of many famous temples, but one of the most impressive is the Pantheon with its enormous open dome. It still stands today, reconsecrated and redecorated as a church. Living in Rome. There were two basic types...
  • Plant Transport - Western Oregon University

    Plant Transport - Western Oregon University

    How would transpiration on these two days differ? W O R K T O G E T H E R Sugar Transport The trouble with phloem Phloem tissue is living tissue, unlike xylem. When scientists studying how it works cut...
  • The Trojan War

    The Trojan War

    Briseis is led from Achilles' tent to Agamemnon's. Reading packet: 281-82. Ajax. After Achilles, Ajax son of Telamon was the mightiest of the Greek heroes in the Trojan War. Ajax was a huge man, head and shoulders larger than the...
  • Programming Biological Cells - People

    Programming Biological Cells - People

    Programming Biological Cells Ron Weiss, George Homsy, Radhika Nagpal ... intercellular communication High Level Programming Requires a new paradigm colonies are amorphous cells multiply & die often expose mechanisms cells can perform reliably Microbial programming language example: pattern ...