Ch. 7: Relations 7.1 Relations and their Properties

Ch. 7: Relations 7.1 Relations and their Properties

Ch. 8: Relations 8.1 Relations and their Properties Functions Recall ch. 1: Functions Def. of Function: f:AB assigns a unique element of B to each element of A

Functions- Examples and Non-Examples Ex: students and grades Function Ex Ex: A={1,2,3,4,5,6}, B={a,b,c,d,e,f} {(1,a),(2,c),(3,b),(4,f),(5,b),(6,c)} is a subset of AxB

Also show graphical format. Relations Relations are also subsets of AxB, without the above uniqueness requirement of functions. Def. of Relations: Let A and B be sets. A binary relation from A to B is a subset of AxB.

Special Case: A relation on the set A is a relation from A to A. Examples of relations Flights Review of AxB Recall that AxB={(a,b)|a A and b B}

For A={1,2,3} and B={x,y}, find AxB Find AxA Functions and Relations Do a few examples of students and grades and determine if they are functions and/or relations

Notations for Relations Notations: Graphical Tabular Ordered pairs aRb later: matrices and digraphs

Properties for a relation A relation R on a set A is called: reflexive if (a,a) R for every a A symmetric if (b,a) R whenever (a,b) R for a,b A antisymmetric : (a,b) R and (b,a) R only if a=b for a,b A transitive if whenever (a,b) R and (b,c) R, then (a,c) R for a,b,c A

Alternative notation A relation R on a set A is called:

reflexive if aRa for every a A symmetric if bRa whenever aRb for every a,b A antisymmetric : aRb and bRa only if a=b for a,b A transitive if whenever aRb and bRc, then aRc for every a, b, c A Question What does RST show?

RAT? Ex: Consider the following relations R on the set A of all people. Determine which properties (RSAT) hold:circle if so: 1. R={(a,b)| a is older than b } RSAT 2. R={(a,b)| a lives within 10 miles of b }

RSAT 3. R={(a,b)| a is a cousin of b } RSAT 4. R={(a,b)| a has the same last name as b } RSAT More examplesR on the set A of all people. 5. R={(a,b)| as last name starts with the same letter as bs }

RSAT 6. R={(a,b)| a is a (full) sister of b } RSAT Let A=set of subsets of a nonempty set 7. R={(a,b)| a is a subset of b } RSAT

Let A={1,2,3,4} 8. R={(a,b)| a divides b } R={(1,1),(1,2),(1,3),(1,4),(2,2),} RSAT 9. R={(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1),

(4,4)} RSAT Let A=Z (integers) 10. R={(a,b)| a b } 11. R={(a,b)| a=b+1 } 12. R={(1,1), (2,2), (3,3) }

RSAT RSAT RSAT Number of relations-questions How many relations are there on a set with 4 elements?

AxA has ___ elements. So number of subsets is ___ How many relations are there on a set with n elements? ___ Number of reflexive relations on a set with n elements The other ___may or may not be in. So ___ reflexive relations. Number of relations- Answers

How many relations are there on a set with 4 elements? AxA has 4^2=16 elements. So number of subsets is 2 16 How many relations are there on a set with n elements? 2n^2 Number of reflexive relations on a set with n elements The other n(n-1) may or may not be in. So 2n(n-1) reflexive relations.

Combining Relations Ex: sets A={1,2,3}, B={1,2,3,4}; Relations: R={(1,1),(2,2), (3,3)}, S={(1,1), (1,2), (1,3), (1,4)} RS RS RS SR

Def. of Composite Let R be a relations from A to B and S a relations from B to C. The composite of R and S: S R = {(a,c)| a A, c C, and there exists b B such that (a,b) R and (b,c) S}

Composite example Ex 1: R from {0,1,2,3,4} to {0,1,2,3,4}, S from {0,1,2,3,4} to {0,1,2,3,4} R={(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)} S={(1,0), (2,0), (3,1), (3,2), (4,1)} Find S R Find R S

Ex 2 Ex. 2: R and S on the set of all people: Let R={(a,b)| a is the mother of b} S={(a,b)|a is the spouse of b} Find S R Find R S Def of powers

Def: Let R be a relation on the set A. The powers Rn, n=1,2,3, are defined inductively by R1=R and Rn+1=Rn R Ex Ex: R={(1,1), (2,1), (3,2), (4,3)} R2= {(1,1), (2,1), (3,1), (4,2)} R3=

Show R4=R3 So Rn=R3 for n=4, .. Ex: R={(1,1), (1,2), (3,4), (4,5), (3,5)} R2 = {(1,1), (1,2), (3,5)} R3={(1,1), (1,2)} R4=R3 so Rn=R3

Thm. 1 Theorem 1: Let R be a transitive relation on a set A. Then Rn is a subset of R for n=1,2,3, Proof what method would work well? Proof

By Induction: N=1: trivially true Inductive Step: Assume Rn R where n Z+. Show: _______ Assume (a,b) R n+1. (Question: Show?____) Then, since R n+1 = R n R, ______________ Since ______, then ____ R. Since _____________ then ______ R.

Recently Viewed Presentations

  • Covers of Books Written by Elliot A. Tanis

    Covers of Books Written by Elliot A. Tanis

    Covers of Books Written by Elliot A. Tanis Hope College 1977-2014 Probability and Statistical Inference 1st edition & International - 1977 Probability and Statistical Inference 2nd edition - 1983, 3rd edition - 1988 Probability and Statistical Inference 4th edition -...
  • Figure 26.1 Reproductive organs of the male, sagittal

    Figure 26.1 Reproductive organs of the male, sagittal

    © 2014 Pearson Education, Inc. Figure 26.1 Reproductive organs of the male, sagittal view. Peritoneum. Seminal gland (vesicle) Ampulla of. ductus deferens
  • Chapter 6: Stress and Coping - City Tech OpenLab

    Chapter 6: Stress and Coping - City Tech OpenLab

    Stress. Stressful stimulus: An external event that provokes a response. Stressful response: Physical or emotional reaction to stimulus. 1) Acute time-limited stressors. 2) Brief naturalistic stressors. 3) Stressful event sequences. 4) Chronic stress (daily stressor build-up) 5) Distal stressors
  • Healing Through Stretching - San Francisco State University

    Healing Through Stretching - San Francisco State University

    Bedtime Stretches Relax your body and your mind is sure to follow! Do these stretches every night before you go to sleep and you will sleep like a baby. Healing Through Stretching The Benefits of Stretching and Example Routines Stretching...
  • Designing Effective Surveys with Qualtrics - 1 or 2 Hour Course

    Designing Effective Surveys with Qualtrics - 1 or 2 Hour Course

    Use Qualtrics to create a range of question types, including: Multiple Choice and Matrix Tables. Utilise survey logic to adjust survey flow and question content, as determined by earlier responses. Customise the Look & Feel of a survey. Distribute a...
  • Second Life @ DU - Update

    Second Life @ DU - Update

    On DU's island, "The Science School," are Olin Hall and a replica of DU's Meyer-Womble Observatory on Mt. Evans Physics - Continued Teamed up with with University Collge to form a new program for NRC Program Amme envisions helping students...
  • Physics 121C Mechanics

    Physics 121C Mechanics

    An air-track glider attached to a spring. The glider is pulled a distance A from its rest position and released. Fig. (b) shows a graph of the motion of the glider, as measured each 1/20 of a second. The graphs...
  • The CICE Consortium: A New Collaborative Paradigm for Sea-Ice ...

    The CICE Consortium: A New Collaborative Paradigm for Sea-Ice ...

    Department of Energy • Office of Science • Biological and Environmental Research. ESM. The CICE Consortium: A New Collaborative Paradigm for Sea-Ice Model Development . Sea-Ice Model Science. CICE—a preeminent model simulating the growth, melting, and movement of sea ice—is...