×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

10

0

43

# DISCRETEMATHEMATICS MATH245

SDSU
GPA 3.64

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
43
WORDS
KARMA
25 ?

## Popular in Mathematics (M)

This 43 page Class Notes was uploaded by Miss Gladys Lubowitz on Tuesday October 20, 2015. The Class Notes belongs to MATH245 at San Diego State University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/225273/math245-san-diego-state-university in Mathematics (M) at San Diego State University.

×

## Reviews for DISCRETEMATHEMATICS

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/20/15
Math 245 Discrete Mathematics Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations Lecture 14 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminusSDSUEDU httpterminusSDSUEDU Id lectureitexv 1 5 20061205 005229 blomgren Exp Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 143 Relations Introduction Mathematical Relations Examples Two logical expressions can be said to be related if they have the same truth tables A set A can be said to be related to a set B if A g B A real number a can be said to related to y if a lt y An integer n can be said to related to m if An integer n can be said to related to m if n and m are both odd Etc etc etc We are going to study mathematical relations on sets their properties and representations Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 243 Relations Introductory Example 1 of 2 Let A 012 and B 1 23 The relation Let an element a E A be related to an element y E B if and only if x lt y Notation x R y E x is related to y x B y E x is not related to y We have the following relations 0R1 since 0 lt 1 1 R 1 since 1 7i 1 0R2 since 0 lt 2 2 R 1 since 2 7i 1 0R3 since 0 lt 3 2 R 2 since 2 7i 2 1R2 since 1 lt 2 1R3 since 1 lt 3 2R3 since 2 lt 3 Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 343 Relations Introductory Example 2 of 2 Relations and Cartesian Products The Cartesian product A X B of two sets A and B is the set of all ordered pairs whose first element is in A and second elements in B AXBxyleAandyEB In our example A x B 01 02 03 1 1 12 13 21 22 23 The elements of some ordered pairs 01 072 073 172 173 273 are considered to be related others are not Knowing which ordered pairs are in this set is equivalent to knowing which elements are related Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 443 Relations Formal Definition Definition Binary Relation Let A and B be sets A binary relation R from A to B is a subset of A X B Given an ordered pair 33 6 A x B x is related to y by R written ny if and only if 33 6 R Symbolic Notation ny ltgt xy E R MW e xyyWR The term binary is used in the definition to indicate that the relation is a subset of the Cartesian product of two sets Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 543 Illustration Relations AXB Figure Given 2 sets A and B we Figure The Relation R is a subset of form the Cartesian product A X B A X B If and only if 3631 E Rwe 11 y E Agtlt B E 1 E A and y E say that 1 is related to y by R symbol B ically 1 By The subset R g A X B can be specified 1 Directly Explicitly by indicating what pairs xy E R This is only feasible when A and B are finite and small sets 2 By specifying a rule for what elements are in R eg by saying that xy E R if and only if x yz Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 643 Example Congruence Modulo 2 Relation 1 of 2 We generalize the previous example to the set of all integers Z ie forall mm 6 Z X Z mRn ltgt m n is even Questions a is 4R0 2R6 3R 3 5R2 b List 5 integers that are related by R to 1 c Prove that if n is odd then nR 1 Answers ai Yes 4R0 since 4 0 4 is even aii Yes 2 R6 since 2 6 4 is even aiii Yes 3R 3 since 3 3 6 is even aiv No 5 R 2 since 5 2 3 is odd Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 743 Example Congruence Modulo 2 Relation b There are infinitely many examples eg 1 11 111 1111 11111 C since 1 1 0 since 11 1 10 since 111 1 110 since 1111 1 1110 since 11111 1 11110 integer k By substitution Hence Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 843 nR1Vn odd D is even is even is even is even is even Proof Suppose n is any odd integer Then n 2k 1 for some n 12k1 12kiseven Representation Arrow Diagrams for Relations Let A 123 and B 135 Figure Arrow diagram representation of Figure Arrow diagram representation of the relation the relation forall 3631 E A X B R 21 25 11yE R ltgt 1 lt 3 Notes i It is possible to have an element that does not have an arrow coming out of it ii It is possible to have several arrows coming out of the same element of A pointing in different directions iii It is possible to have an element in B that does not have an arrow pointing to it Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 943 Relation from A to A Directed Graph of a Relation Definition A binary relation on a set A is a binary relation from A to A In this case we can modify the arrow diagram to be a directed graph instead of representing A twice we only represent it once and draw arrows from each point of A to each related point eg g there is an arrowfrom xtoy ltgt XRy ltgt Xy E R Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1043 Example Directed Graph of a Relation Let A 34 5 6 78 and define a binary relation R on A Rx7y EAXA 2lx y Figure We notice that the graph must be symmetric since if 2n then 2 n Since 2O there is a loop at every node in the graph Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1143 Properties of a Binary Relation on One Set A Recall Definition A binary relation on a set A is a binary relation from A to A In the context of a binary relation on a set we can name 3 properties Definition Let R be a binary relation on a set A 1 R is Reflexive if and only if Vx E A xRx 2 R is Symmetric if and only if Vx y E A if x Ry then y Rm 3 R is Transitive if and only if Vx y z E A if x Ry and sz then sz Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 1243 Reflexivity Formal R is Reflexive if and only if Vx E A xRx Functional R is Reflexive ltgt for all a E A x x E R Informal Each element is related to itself Graph Each point of the graph has an arrow looping around back to itself Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1343 Symmetry Formal Functional Informal Graph R is Symmetric if and only if Vxy E A if x Ry then y Rx R is Symmetric ltgt for all xy E A if 334 6 R then ya 6 R If one element is related to a second element then the second element is related to the first In all cases where there is an arrow going from one point to a second there is an arrow going from the second point back to the first gt Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1443 Transitivity Formal R is Transitive if and only if Vxyz E A if ny and sz then sz Functional R is Transitive ltgt for all xyz E A if 334 6 R and yz E R then xz E R Informal If one element is related to a second element and that second element is related to a third element then the first element is related to the third element Graph In all cases where there is an arrow going from one point to a second and from the second point to a third there is an arrow going from the first point to the third lt Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1543 NonReflexivity NonSymmetry and NonTransitivity If R is a binary relation defined on a set A then 1 R is not reflexive ltgt there is an element a E A such that x R x ie xx Q R 2 R is not symmetric ltgt there are elements xy E A such that ny but y R x ie xy E R but yx Q R 3 R is not transitive ltgt there are elements xy z E A such that ny and sz but x R z ie xy y z E R but x 2 Q R To show that a binary relation does not have one of the properties it is sufficient to find a counterexample Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1643 Example 1 of 5 Let A 0123 and define relations R S and T R 070 071 073 170 171 272 370 373 S 0707 07 2 073 273 T 0717 273 Fill in the table Reflexive Symmetric Transitive Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1743 Example The Relation R 2 of 5 We have A 0123 and R 0707 071 0 OJ 7 10 171 22 370 373 Q 0 221 32 R is reflexive since there is a loop at each point in the directed graph Gsg R is symmetric since in for every arrow going from one point to another there is an other arrow going back R is not transitive since 69 1 R0 and 0 R3 but 1 R 3 ie there is no shortcut arrow connecting 1 and 3 Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1843 Example The Relation S 3 of 5 We have A 0123 and S 0707 072 073 273 3lt 2 S is not reflexive since there are missing loops at 1 2 and 3 S is not symmetric the arrows from 2to0 3to0 and 3to2 are missing S is transitive since there is always a shortcut arrow so that if 11 y E S and 317 Z 6 Sthen1z E S Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 1943 Example The Relation T 4 Of 5 We have A 0123 and T 0717273 lo gt01 304 02 T is not reflexive since there are missing loops at 0 1 2 and 3 T is not symmetric the arrows from 1to 0 and 3to2 are missing T is transitive since it is not not transitive Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2043 Example The Relations R S and T 5 of 5 Let A 0123 and define relations R S and T R 070 071 073 170 171 272 370 373 S 07 0 07 2 07 3 27 3 T 071 23 Fill in the table Reflexive Symmetric Transitive R Yes Yes No No No Yes T No No Yes Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2143 lrreflexivity AntiSymmetry and lntransitivity Definition Let R be a binary relation on a set A 1 R is lrreflexive if and only if Vx E A x R x 2 R is Antisymmetric if and only if Vxy E A if x Ry then 3 R is lntransitive if and only if Vxyz E A if ny and sz then x R z o R can be reflexive nonreflexive or irreflexive o R can be symmetric nonsymmetric or antisymmetric o R can be transitive nontransitive or intransitive Think about these definitions Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 2243 lrreflexivity Formal R is lrreflexive if and only if Vx E A X R X Functional R is lrreflexive ltgt for all x E A X X if R Informal No element is related to itself Graph No point of the graph has an arrow looping around back to itself Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2343 AntiSymmetry Formal Functional Informal Graph R is Anti Symmetric if and only if Vxy E A if ny then y R X R is AntiSymmetric ltgt for all xy E A if 334 6 R then yX e R If one element is related to a second element then the second element is NOT related to the first In all cases where there is an arrow going from one point to a second there is no arrow going from the second point back to the first Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2443 lntransitivity Formal R is lntransitive if and only if Vxyz E A if ny and sz then X R 2 Functional R is lntransitive ltgt for all xyz E A if xy E R and yz E R then Xz e R Informal If one element is related to a second element and that second element is related to a third element then the first element is not related to the third element Graph In all cases where there is an arrow going from one point to a second and from the second point to a third there is never an arrow going from the first point to the third no shortcut exist anywhere 2 O lt 0 Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 2543 Example Equality on R Let A R the set of real numbers and define the relation R x Ry ltgt x y Properties R is reflexive R is reflexive if and only if Vx E R xRx Here this means x x ie Vx E R x x This statement is certainly true every real number equals itself R is symmetric This is true since ifx y then y x hence x y E R and y x E R R is transitive This is true since if x y and y 2 then x 2 Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2643 Example Less Than lt on R Let A R the set of real numbers and define the relation R x Ry ltgt x lt y Properties R is irreflexive If x R x then x lt x but that is nevertrue hence x R x Vx E R R is antisymmetric If x By then x lt y which means y 7 x ie y R x R is transitive This is true since if x lt y and y lt 3 then x lt 3 Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2743 Example Congruence Modulo 3 on Z We define a relation R on Z as follows Vmn E Z mRn ltgt 3lm n R is reflexive Suppose m is an integer Now m m 0 and 3l0 since 0 3 0 so by definition of R we have m Rm D R is symmetric Suppose m n E Z such that mRn By definition of R we have3lm n ltgtm n 3 kforsomek E Z Multiplying both sides by 1 gives 71 m 3 which shows 3i n hence n Rm D R is transitive Suppose m n p E Z such that m R n and n Rp We have 3i m n and 3ln p and we can write m n 3r and n p 35 for some 7quot s E Z Adding the two gives m n i n p m p 3r i s which shows that 3i m p Hence m Rp and it follows that R is transitive D Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 2843 Equivalence Relations Different but the Same Idea We are going to group elements that look different but really are the same Example Think about the rational numbers there are several ways of writing the same fraction eg 1 1 2 4711 2 2 4 9422 We can define a relation on Q X Q where Q is the set of all rational numbers Rx7yEQXQxy now 3 6 R i e R e R etc Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 2943 A Relation Induced by a Partition Recall Definition A collection of nonempty sets A1A2 An is a partition of a set A if and only if 1 AA1UA2UUAn 2 A1A2 An are mutually disjoint Definition Given a partition of a set A the binary relation induced by the partition R is defined on A as follows Vx y E A x Ry ltgt there is a set Ai of the partition such that both x 6 Ai and y 6 Ai We need an example to make sense out of this definition Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3043 Example Relation Induced by a Partition Let A 0 1 2 3 4 and consider the following partition of A A1 034 A2 1 A3 2 Now two elements xy E A are related if and only if they belong to the same subset of the partition 0H Hence Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 3143 Equivalence Relations Theorem Let A be a set with a partition and let R be the relation induced by the partition Then R is reflexive symmetric and transitive Definition Equivalence Relation Let A be a nonempty set and R a binary relation on A R is an equivalence relation if and only if R is reflexive symmetric and transitive Example By the theorem the relation induced by a partition is an equivalence relation Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 3243 Notation Congruence Modulo n Notation Let m n d E Z with d gt 0 The notation m E 71 mod d is read m is congruent to n modulo dquot and means that dlm n Symbolically m E n mod d ltgt dlm n Recall the QuotientRemainder Theorem Theorem Given any integer n and a positive integer d there exist unique integers q the quotient and r the remainder such that ndqr and O rltd Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3343 Equivalence Relation Congruence Modulo 3 Let R be the relation R E Z X Z m nmod We show that this is an equivalence relation Reflexivity Let m e Z then 3lm m since 0 3 0 and it follows that mRm Symmetry Let mn E Z so that mRn We have 3lm n ltgt m n3kforsomekEZltgt n m3 k ltgt 3ln m ltgt an Transitivity Let mnp E Z so that mRn and an We have 3m n ltgt m n3r rEZ 3n p ltgt n p3ssEZ add m p3rs Hence 3m p and we have me D Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3443 Equivalence Classes Suppose we have a set A and an equivalence relation R on A Given a particular element a E A it is natural to ask the question what elements are related to a 7quot All the elements that are related to a form a subset of A and this subset is called the equivalence class of x Definition Suppose A is a set and R is an equivalence relation on A For each element a E A the equivalence class of x denoted x and called the class of a for short is the set of all elements y E A such that y Rx Symbolically 93 y 6 Al yRCU Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3543 Example Equivalence Classes 1 of 2 Let A 01234 and define a binary relation R on A R 00 04 11 13 7 272 371 373 470 474 N 9 c Figure The array diagram directed graph corresponding to the relation By quick inspection we see that R is reflexive symmetric and transi tive hence an equivalence relation Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3643 Example Equivalence Classes 2 of 2 30 gt lt gt lt 3 E The equivalence classes are 0 x E AlxRO 04 1 xEAlle 13 2 xEAlxR2 2 3 xEAlxR3 13 4 x E AlxR4 04 Note that 0 4 and 1 hence the distinct equivalence classes are 04 13 Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 3743 Equivalence Classes A Theorem The following theorem tells us that an equivalence relation induces a partition Theorem If A is a nonempty set and R is an equivalence re lation on A then the distinct equivalence classes of R form a partition of A ie the union of the equivalence classes is all of A and the intersection of any two distinct classes is empty Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3843 Example Equivalence Classes of Congruence Module 3 1 of 3 Let R be the relation of congruence modulo 3 on the set Z ie VmnEZ mRn ltgt 3lm n ltgt mEnmod3 We describe the equivalence classes For each integer a the class of ais a xEleRa 6Zl3l a xEle a3kkEZ xEle3kakEZ In particular 0xEle3kkEZ 03 36 69 9 1xEle3k1kEZ 14 27 510 8 2xEle3 2 kEZ 25 18 411 7 Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 3943 Example Equivalence Classes of Congruence Module 3 2 of 3 Wehave 0xEle3kkEZ 03 36 69 9 1xEle3k1kEZ 14 27 510 8 2xEle3 2 kEZ 25 18 411 7 By lemma1 Hence the distinct equivalence classes are xEle3 kEZ xEle3k l 1kEZ xEle3 2 kEZ Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 4043 Example Equivalence Classes of Congruence Module 3 3 of 3 The distinct equivalence classes are xEle3 kEZ xEle3k l 1kEZ xEle3 2 166 The class of 0 can also be called the class of 3 or the class of 96 but the class is the set x E le 3 k k E Z Definition Suppose R is an equivalence relation on a set A and S is an equivalence class of R A representative of the class 8 is any element a E A such that a S Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 4143 Notes o It is possible to define multiplication and addition of the equiva lence classes corresponding to the rational numbers previous ex ample The rational numbers can be defined as equivalence classes of ordered integers o It can be shown that all integers negative zero and positive can be defined as equivalence classes of ordered pairs of positive integers o Frege and Peano showed late 19th century that the positive in tegers can be defined entirely in terms of sets 0 Dedekind 1848 1916 showed that all real numbers can be defined as sets of rational numbers 0 All together these results show that the real numbers can be defined using logic and set theory alonel Relations on Sets Reflexivity7 Symmetry and Transitivity Equivalence Relations 7 p 4243 Homework 12 Not Due Final Version Eppv30 1011 1015 1017 10115 10123 101251023 1024 10212 10214 10237 1033 10317 10319 10340 Eppv20 1011 1015 1017 10115 10123 101251023 1024 10212 10214 10237 1032 10314 10316 10335 Relations on Sets Reflexivity Symmetry and Transitivity Equivalence Relations 7 p 4343

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com