For each of these relations on the set {1,2,3,4}, decide
whether it is reflexive, whether it is symmetric, whether
it is antisymmetric, and whether it is transitive.
a) {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}
b) {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}
c) {(2,4),(4,2)}
d) {(1,2),(2,3),(3,4)}
e) {(1,1),(2,2),(3,3),(4,4)}
f) {(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)}.
a) Transitive.
b) This is reflexive since it contains (a,a)∈R for every a∈A. It is also symmetric since (2,1) is in R when (1,2) is. It is not antisymmetric since (1,2) and (2,1) are in the relation. It is transitive since (1,2) and (2,1) are in the relation then (1,1) and (2,2) are in the relation as well.
c) Not reflexive, but it is symmetric. Not antisymmetric because (2,4) and (4,2) are in the relation. IT isn't transitive because (2,4) and (4,2) are in the relation but (2,2) is not.
d) Not reflexive or symmetrical. It is antisymmetric since there are no cases of (a,b) being in the relation when (b,a) is. It is not transitive since although (1,2) and (2,3) are in the relation, (1,3) is not.
e) Reflexive, symmetric, antisymmetric, and transitive (the only tyime the hypothesis ((a,b)∈R∧(b,c)∈R) is met is when a=b=c.
f) Not reflexive or symmetric or antisymmetric. It is not transitive, since (2,3) and (3,1) are in the relation, but (2,1) is not.
Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)∈R if and only if
a) everyone who has visited Web page a has also visitedWeb page b.
b) there are no common links found on both Webpage a and Web page b.
c) there is at least one common link onWeb page a andWeb page b.
d) there is a Web page that includes links to both Webpage a and Web page b.
a) It's reflexive (if you visited website a you have also visited website a..) It is not symmetric since there must exist a website a and b such that the set of people who visited a are a proper subset of b. If there exists two different web pages that have the same exact set of visitors, then R is not antisymmetric. R is transitive (if everyone who visited a visited b, and everyone who visited b visited c, then everyone who visited a has also visited c.
b) Not reflexive, any page a that has links on it, (a,a)∈/R. R is symmetric in its very definition. R is not antisymmetric because there are surely two different webpages a and b that have no common links in them. Lastly, R is not transitive since for webpages with no links in common, if they have links at all, give an example of a failure of the definition (a,b)∈R and (b,a)∈R, but (a,a)∈/R.
c)
d)
¶ Determine whether a relation is an equivalence relation (reflexive, symmetric, and transitive)
Let R be the relation ont he set N of positive integers defined by R={(a,b):a+bis even}. Is R an equivalence relation?
It is reflexive (a+a is even).
It is symmetric (if a+b is even then b+a is even).
It is transitive (if a+b is even and b+c is even then a+c is also even)
It is reflexive, symmetric, and transitive, so it is an equivalence relation.
Let S be the relation "is a blood relative of" on the set X of people. Is S an equivalence relation?
It is not reflexive (a person can't be a blood relative of themselves, that doesnt make sense. The book says this is reflexive, so they are considering a person a relative of themselves...).
It is symmetric (if a person a has a blood relative b, then person b is a blood relative of a).
It is not transitive (a person may have a cousin a through his mothers family and another cousin b through their fathers family, but a and c may not be blood relatives).
Let R={(1,1),(1,3),(3,1),(3,3)}. Is R an equivalence relation on A={1,2,3}? on B={1,3}?
For A, its not reflexive since its missing (2,2), so its not an equivalence relation.
For B, it is symmetric, reflexive, and transitive so it is an equivalence relation.
Let A be the set of all ordered pairs of positive integers (including zero). This means that A={(a,b)∣a,b≥0}. Let R be a relation defined on A such that R={[(a,b),(c,d)]∣ad=bc}. Determine whether or not R is an equivalence relation.
The relation is reflexive, i.e., [(a,b),(a,b)]∈R, since ab=ba.
The relation is symmetric. If [(a,b),(c,d)]∈R, we know that ad=bc. This implies that cb=da, i.e. [(c,d),(a,b)]∈R.
The relation is transitive. If [(a,b),(c,d)]∈R and [(c,d),(e,f)]∈R, we know that ad=bc and cf=de hold. This implies that a=dbc and f=cde and hence af=dbccde=be. This implies that [(a,b),(e,f)]∈R.
Since the relation is reflexive, symmetric, and transitive, it is in fact an equivalence relation.
Let A be the set of all ordered pairs of positive integers (including zero). This means that A={(a,b)∣a,b≥0}. Let R be
a relation defined on A such that R={[(a,b),(c,d)]∣a+c=b+d}. Determine whether or not R is an equivalence relation.
R is not an equivalence relation since its not reflexive or transitive. For reflexivity, consider [(1,2),(1,2)] is not in R since 1+1=2+2
The set P({w,x,y,z}) is partially ordered with respect to the "subset" relation ⊆. Find a chain of length 4 in P({w,x,y,z})
∅⊆{w}⊆{w,x}⊆{w,x,y}⊆{w,x,y,z}.
¶ Determine whether a relation is an equivalence relation (reflexive, symmetric, and transitive) and if applicable, how many and what equivalence classes are there
In each case, say whether or not R is an equivalence relation on A. If it is an equivalence relation, what are the equivalence classes and how many equivalence classes are there?
a) R::={(x,y)∈W×W∣ the words x and y start with the same letter } where W is the set of all words in the 2001 edition of the Oxford English dictionary.
b) R::={(x,y)∈W×W∣ the words x and y have at least one letter in common }
c) R={(x,y)∈W×W and the word x comes before the word y alphabetically }
d) R={(x,y)∈R×R and ∣x∣≤∣y∣}
e) R={(x,y)∈B×B, where Bis the set of all bit strings andxandy have the same number of 1s} .
a) This is an equivalence relation, being symmetric reflexive and transitive. The equivalence class is [x]R is the set of words y such that y has the same first letter as x. There are 26 equivalence classes, one for each letter of the alphabet.
b) Not an equivalence relation, since its not transitive. There can exist a word a that has letters in common with another word b, and word b can have letters in common with a word c, but a may have no letters in common with c.
c) Not an equivalence relation. A word can't come before itself alphabetically.
d) Its not symmetric, no equiv relation.
e) This is an equivalence relation. There is an equivalence relation for all positive integers with that number of ones.
¶ Show that a relation is an equivalence relation ( reflexive, symmetric, and transitive)
Show that the relation R=∅ on the empty set S=∅ is reflexive, symmetric, and transitive.
Each of the properties reflexive, symmetric, and transitive are universally quantified statements. Because the domain is empty, each of them is vacuously true.
A relation R on the set A is irreflexive if for every a∈A, (a,a)∈/R. That is, R is irreflexive if no element in A is related to itself.
Which relations from exercise 3 are irreflexive?
c, d, f are irreflexive.
Can a relation on a set be neither reflexive nor irreflexive?
Yes, a relation R may contain some pairs of (a,a) but not all of them.
Give an example of an irreflexive relation on the set of all people.
(a,b)∈R iff a weighs more than b. A person can't weigh more than themselves, so this is irreflexive.
Use quantifiers to express what it means for a relation to be asymmetric.
∀a∀b¬((a,b)∈R∧(b,a)∈R)
or
∀a∀b((a,b)∈R→(b,a)∈/R)
¶ Verify a relation is a partial order and possibly a total order
Verify that each of the following relations is a partial order by describing a function, g, such that the relation is defined by g according to the following definition:
A relation, R, on a set, A, is a partial order providing there is a function, g, from A to some collection of sets such that
a1Ra2 iff g(a1)⊂g(a2)
for all a1=a2∈A
For each, is it a total order?
a) The relation < on R
b) The superset relation ⊇ on P(B) for a set B.
c) The divides relation on N.
a) g(r)::={t∈R∣t<r}. It follows that
r1<r2 iff g(r1)⊂g(r2)
so < satisfies the condition a1Ra2 iff g(a1)⊂g(a2) on R that defines partial orders. Likewise the relation ≤ is a partial order because
r1≤r2 iff r1<r2
for all reals r1=r2. ■.
b) g(a)::=aˉ::=B−{a}, and note that for a1=a2∈P(B),
a1⊇a2 iff a1⊃a2 iff a1⊂a2 iff g(a1)⊂g(a2)(sincea1=a2)(basic set theory)(def of g)
c)
Let R be the set of all real numbers and define a relation R on R×R as follows: For every (a,b) and (c,d) in R×R,
(a,b)R(c,d)⇔ either a<c or both a=c and b≤d.
Is R a partial order relation? Prove or give a counterexample.
(Note, this is just the lexicographic ordering)
R is a partial order relation.
R is reflexive: Suppose (a,b)∈R×R. Then (a,b)R(a,b) because a=a and b≤b.
R is antisymmetric: Suppose (a,b) and (c,d) are ordered pairs of real numbers such that (a,b)R(c,d) and (c,d)R(a,b). Then
either a<c or both a=c and b≤d
and
either c<a or both c=a and d≤b.
Thus
a≤c and c≤a
and so
a=c
Consequently,
b≤d and d≤b
and so
b=d
Hence (a,b)=(c,d)
R is transitive: Suppose (a,b),(c,d), and (e,f) are ordered pairs of real numbers such that (a,b)R(c,d) and (c,d)R(e,f). Then
either a<c or both a=c and b≤d
and
either c<e or both c=e and d≤f.
Case 1 (a<c and c<e): Then by transitivity of <, a<e, and so (a,b)R(e,f) by definition of R
Case 2 (a<c and c=e): Then by substitution, a<e, and so (a,b)R(e,f) by definition of R.
Case 3 (a=c and c<e): Then by substitution, a<e and so (a,b)R(e,f) by definition of R.
Case 4 (a=c and c=e): Then by definition of R, b≤d and d≤f, and so by transitivity of ≤,b≤f. Hence a=e and b≤f, and so (a,b)R(e,f) by definition of R.
In each case, (a,b)R(e,f). Therefore, R is transitive. Since R is reflexive, antisymmetric, and transitive, R is a partial order relation.
Consider the "divides" relation defined on the set A={1,2,22,23,…,2n}, where n is a nonnegative integer.
a. Prove that this relation is a total order relation on A.
b. Draw the Hasse diagram for this relation for n=4
Show that the relation R on a set A is symmetric iff R=R−1, where R−1 is the inverse relation.
Since this is a bidirectional statement we need to prove that
- if a relation is symmetric, then R=R−1
and
- R=R−1 implies that the relation is symmetric.
For 1, we must show that R⊆R−1 and R−1⊆R. To do this, let (a,b)∈R. Since R is symmetric, this implies that (b,a)∈R. Since R−1. But since R−1 consists of all pairs (a,b) such that (b,a)∈R, this means that (a,b)∈R−1. Thus we have shown that R⊆R−1. Next let (a,b)∈R−1. By definition this means that (b,a)∈R. Since R is symmetric, this implies that (a,b)∈R as well. Thus we have show that R−1⊆R.
For 2, We let (a,b)∈R and try to show that (b,a) is also necessarily an element of R. Since (a,b)∈R, the definition tells us that (b,a)∈R−1. But since we are under the hypothesis that R=R−1, this tells us that (b,a)∈R, exactly as desired.
Let R be a relation that is reflexive and transitive. Prove that Rn=R for all positive integers n.
We prove this by induction on n. The case n=1 is trivial, since it is the statement R=R. Assume the inductive hypothesis that Rn=R. We must show that Rn+1=R. By definition Rn+1=Rn∘R. Thus our task is to show that Rn∘R⊆R and R⊆Rn∘R. The first uses the transitivity of R, as follows. Suppose that (a,c)∈Rn∘R. This means that there is an element b such that (a,b)∈R and (b,c)∈Rn⋅ By the inductive hypothesis, the latter statement implies that (b,c)∈R. Thus by the transitivity of R, we know that (a,c)∈R, as desired
Next assume that (a,b)∈R. We must show that (a,b)∈Rn∘R. By the inductive hypothesis, Rn=R and therefore Rn is reflexive by assumption. Thus (b,b)∈Rn. Since we have (a,b)∈R and (b,b)∈Rn, we have by definition that (a,b) is an element of Rn∘R, exactly as desired.
Let R be a reflexive relation on a set A. Show that Rn is reflexive for all positive integers n.
We use induction on n, the result being trivially true for n=1. Assume that Rn is reflexive; we must show that Rn+1 is reflexive. Let a∈A, where A is the set on which R is defined. By definition Rn+1=Rn∘R. By the inductive hypothesis, Rn is reflexive, so (a,a)∈Rn. Also, since R is reflexive by assumption, (a,a)∈R. Therefore by the definition of composition, (a,a)∈Rn∘R, as desired.
Suppose that R is a relation defined on a set A that is not reflexive. Prove or disprove that R2 is not reflexive.
We show that it is possible for R not to be reflexive but R2 to be reflexive. Let A={a,b}. Let R={(a,b),(b,a)}. Given this, R2={(a,a),(b,b)}.R is not reflexive but R2 is reflexive
Suppose R is a relation from A to B and S is a relation from B to C. Prove that S∘R=∅ iff Ran (R) and Dom(S) are disjoint.
Ran(R)={b∈B∣∃a∈A((a,b)∈R)}
Dom(S)={b∈B∣∃c∈C((b,c)∈S)}
Ran(R) and Dom(S) are disjoint. That is, the set of elements they have in common is ∅. That is, Ran(R)∩Dom(S)=∅.
S∘R={(a,c)∈A×C∣∃b∈B((a,b)∈R and (b,c)∈S)}
We must prove a biconditional here. We must prove both directions. That is, we must prove
- if S∘R=∅ then Ran(R) and Dom(S) are disjoint
- if Ran(R) and Dom(S) are disjoint then S∘R=∅.
We prove the contrapositives of both directions.
- Suppose S∘R=∅. Then we can choose some (a,c)∈S∘R. By definition of S∘R, this means that we can choose some b∈B such that (a,b)∈R and (b,c)∈S. But then b∈Ran(R) and b∈Dom(S), so Ran(R) and Dom(S) are not disjoint.
- Suppose Ran(R) and Dom(S) are not disjoint. Then we can choose some b∈Ran(R)∩Dom(S). Since b∈Ran(R), we can choose some a∈A such that (a,b)∈R. Similarly, since b∈Dom(S), we can choose some c∈C such that (b,c)∈S. But then (a,c)∈S∘R, so S∘R=∅
Suppose R is a relation on a set A. R is symmetric iff R=R−1.
Suppose R is symmetric. Let (x,y) be an arbitrary element of R. Then xRy, so since R is symmetric, yRx. Thus, (y,x)∈R, so by the definition of R−1,(x,y)∈R−1. Since (x,y) was arbitrary, it follows that R⊆R−1.
Now suppose (x,y)∈R−1. Then (y,x)∈R, so since R is symmetric, (x,y)∈R. Thus, R−1⊆R, so R=R−1.
Suppose R=R−1, and let x and y be arbitrary elements of A. Suppose xRy. Then (x,y)∈R, so since R=R−1,(x,y)∈R−1. By the definition of R−1 this means (y,x)∈R, so yRx. Thus, ∀x∈A∀y∈A(xRy→yRx), so R is symmetric. ■.
Suppose R is a relation on a set A. Prove R is reflexive iff iA⊆R, where iA is the identity relation on A.
Suppose R is reflexive. Let (x,y) be arbitrary element of iA. Then by the definition of iA,x=y∈A. Since R is reflexive, (x,y)=(x,x)∈R Since (x,y) was arbitrary, this shows that iA⊆R.
Suppose iA⊆R. Let x∈A be arbitrary. Then (x,x)∈iA, so since iA⊆R,(x,x)∈R. Since x was arbitrary, this shows that R is reflexive.
Suppose S is a relation on A. Let D=Dom(S) and R=Ran(S). Prove that iD⊆S−1∘S and iR⊆S∘S−1.
scratch:
S={(a1,a2)∈A}.
S−1={(a2,a1)∈A×A∣(a1,a2)∈S}.
D=Dom(S)={a∈A∣∃b∈B((a,b)∈S)}
iD={(x,y)∈D×D∣x=y}.
R=Ran(S)={b∈B∣∃a∈A((a,b)∈S)}
iR={(x,y)∈R×R∣x=y}.
S−1∘S={(a1,a1)∈A×A∣∃a2∈A((a1,a2)∈S and (a2,a1)∈S−1)}
1) Proving iD⊆S−1∘S :
We must prove that (x,y)∈iD→(x,y)∈S−1∘S.
Suppose (x,y)∈iD. Then x=y∈D=Dom(S), so there is some z∈A such that (x,z)∈S. Therefore (z,x)∈S−1, so (x,y)=(x,x)∈S−1∘S Thus, iD⊆S−1∘S.
2) Proving iR⊆S∘S−1:
Suppose (b,b)∈iR. Thus b∈R, or Ran(S). Since b∈Ran(S), there must exist an element a such that (a,b)∈S. It follows that (b,a)∈S−1. Since (a,b)∈S−1 and (a,b)∈S, it follows that (b,b)∈S∘S−1. Thus if (b,b)∈iD, then (b,b)∈S∘S−1. Since (b,b) is arbitrary, we can conclude that iR⊆S∘S−1.
Suppose R1 and R2 are relations on A. For each part, give either a proof or a counterexample to justify your answer.
(a) If R1 and R2 are reflexive, must R1∪R2 be reflexive?
(b) If R1 and R2 are symmetric, must R1∪R2 be symmetric?
(c) If R1 and R2 are transitive, must R1∪R2 be transitive?
(a) Suppose R1 and R2 are reflexive, and suppose a∈A. Since R1 is reflexive, (a,a)∈R1, so (a,a)∈R1∪R2.
(b) Suppose R1 and R2 are symmetric, and suppose (x,y)∈R1∪R2. Then either (x,y)∈R1 or (x,y)∈R2. If (x,y)∈
R1 then since R1 is symmetric, (y,x)∈R1, so (y,x)∈R1∪R2. Similar reasoning shows that if (x,y)∈R2 then (y,x)∈R1∪R2
(c)
Theorem: Let A, B, C, and D be sets. Suppose R is a relation from A to B, S is a relation from B to C, and T is a relation from C to D. Then
(R∘S)∘T=R∘(S∘T)
(That is, the composition of relations satisfies the associative law).
Prove this theorem.
Need to show (R∘S)∘T⊆R∘(S∘T) and R∘(S∘T)⊆(R∘S)∘T.
Suppose (a,d) belongs to (R∘S)∘T. Then there exists a c∈C such that (a,c)∈R∘S and (c,d)∈T. Since (a,c)∈R∘S, there exists a b∈B such that (a,b)∈R and (b,c)∈S. Since (b,c)∈S and (c,d)∈T, we have (b,c)∈S∘T; and since (a,b)∈R and (b,d)∈S∘T, we have (a,d)∈R∘(S∘T). Thus, (R∘S)∘T⊆R∘(S∘T). Similarly, R∘(S∘T)⊆(R∘S)∘T. Both inclusion relations prove (R∘S)∘T=R∘(S∘T).
Let R be the relation on the set of people with doctorates such that (a,b)∈R if and only if a was the thesis advisor of b. When is an ordered pair (a,b) in R2? When is an ordered pair (a,b) in Rn, when n is a positive integer? (Assume that every person with a doctorate has a thesis advisor.
For (a,b) to be in R2, we must find a c such that (a,c)∈R and (c,b)∈R. In our context, this says that b got his / her doctorate under someone who got his / her doctorate under a. Colloquially, a is the academic grandparent of b, or b is the academic grandchild of a. Generalizing, (a,b)∈Rn precisely when there is a sequence of n+1 people, starting with a and ending with b, such that each is the advisor of the next person in the sequence.
List the 16 different relations on the set {0,1}.
How many of the 16 different relations on {0,1} contain the pair (0,1)?
∅{(0,0)}{(0,1)}{(1,0)}{(1,1)}{(0,0),(0,1)}{(0,0),(1,0)}{(0,0),(1,1)}{(0,1),(1,0)}{(0,1),(1,1)}{(1,0),(1,1)}{(0,0),(0,1),(1,0)}{(0,0),(0,1),(1,1)}{(0,0),(1,0),(1,1)}{(0,1),(1,0),(1,1)}{(0,0),(0,1),(1,0),(1,1)}
A relation is just a subset. A subset can either contain a specified element or not; half of them do and half of them do not. Therefore 8 of the 16 relations on {0,1} contain the pair (0,1). Alternatively, a relation on {0,1} containing the pair (0,1) is just a set of the form {(0,1)}∪X, where X⊆{(0,0),(1,0),(1,1)}. Since this latter set has 3 elements, it has 23=8 subsets.
a) How many relations are there on the set {a,b,c,d}?
b) How many relations are there on the set {a,b,c,d} that contain the pair (a,a) ?
a) A relation on a set S with n elements is a subset of S×S. Since S×S has n2 elements, we are asking for the number of subsets of a set with n2 elements, which is 2n2. In our case n=4, so the answer is 216=65,536
b) In solving part (a), we had 16 binary choices to make-whether to include a pair (x,y) in the relation or not as x and y ranged over the set {a,b,c,d}. In this part, one of those choices has been made for us: we must include (a,a). We are free to make the other 15 choices. So the answer is 215=32,768. See Exercise 47 for more problems of this type.
¶ Prove a relation is an equivalence relation and describe its equivalence classes
Define a relation R on Z as xRy if and only if 3x−5y is even. Prove R is an equivalence relation. Describe its equivalence classes.
We must prove that R is reflexive, symmetric and transitive. The relation R is reflexive for the following reason. If x∈Z, then 3x−5x=−2x is even. But then since 3x−5x is even, we have xRx. Thus R is reflexive.
To see that R is symmetric, suppose xRy. We must show yRx. Since xRy, we know 3x−5y is even, so 3x−5y=2a for some integer a. Now reason as follows:
3x−5y3x−5y+8y−8x3y−5x=2a=2a+8y−8x=2(a+4y−4x).
From this it follows that 3y−5x is even, so yRx. We've now shown xRy implies yRx, so R is symmetric.
To prove that R is transitive, assume that xRy and yRz. (We will show that this implies xRz.) Since xRy and yRz, it follows that 3x−5y and 3y−5z are both even, so 3x−5y=2a and 3y−5z=2b for some integers a and b. Adding these equations, we get (3x−5y)+(3y−5z)=2a+2b, and this simplifies to 3x−5z=2(a+b+y). Therefore 3x−5z is even, so xRz. We've now shown that if xRy and yRz, then xRz, so R is transitive.
We've shown R is reflexive, symmetric and transitive, so it's an equivalence relation.
The completes the first part of the problem. Now we move on the second part. To find the equivalence classes, first note that [0]={x∈Z:xR0}={x∈Z:3x−5⋅0 is even }={x∈Z:3x is even }={x∈Z:x is even }.
Thus the equivalence class [0] consists of all even integers. Next, note that [1]={x∈Z:xR1}={x∈Z:3x−5⋅1 is even }={x∈Z:3x−5 is even }={x∈Z:x is odd }.
Thus the equivalence class [1] consists of all odd integers.
Consequently there are just two equivalence classes {…,−4,−2,0,2,4,…} and {…,−3,−1,1,3,5,…}.
Let E={(p,q)∈P×P∣ the person p is an enemy of the person q}, and F={(p,q)∈P×P∣ the person p is a friend of the person q}, where P is the set of all people. What does the saying "an enemy of one's enemy is one's friend" mean about the relations E and F ?
Suppose p is the enemy of q and q is the enemy of r, then it is given that p is the friend of r. Thus we have if (p,q)∈E and (q,r)∈E, then (p,r)∈F.
Now since (p,q)∈E and (q,r)∈E, it follows (p,r)∈E∘E. Thus the given statement says: if (p,r)∈E∘E, then (p,r)∈F, or Enemy of an enemy is a
friend. Since (p,r) is arbitrary, it follows that E∘E⊆F.