Search & Filtering
Show that the relation R consisting of all pairs(x, y) such that x and y are bit
strings of length three or more that agree in their first three bits is an
equivalence relation on the set of all bit strings of length three or more.
Which of these relations on the set of all functions from Z to Z are equivalence
relations? Determine the properties of an equivalence relation that the others
lack.
a) {(f, g) | f (1) = g(1)}
b) {(f, g) | f (0) = g(0) or f (1) = g(1)}
c) {(f, g) | f (x) − g(x) = 1 for all x ∈ Z}
d) {(f, g) | for some C ∈ Z, for all x ∈ Z, f (x) − g(x) = C}
e) {(f, g) | f (0) = g(1) and f (1) = g(0)
Represent each of these relations on {1, 2, 3} with a matrix (with the elements
of this set listed in increasing order).
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 2), (2, 1), (2, 2), (3, 3)}
c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
d) {(1, 3), (3, 1)}
Let R1 and R2 be the “congruent modulo 3” and the “congruent modulo 4”
relations, respectively, on the set of integers. That is, R1 = {(a, b) | a ≡ b (mod
3)} and R2 = {(a, b) | a ≡ b (mod 4)}. Find
a) R1 ∪ R2 b) R1 ∩ R2 c) R1 − R2 d) R2 − R1 e) R1 ⊕ R2
Answer these questions for the poset ({3, 5, 9, 15, 24, 45}, |).
a) Find the maximal elements.
b) Find the minimal elements.
c) Is there a greatest element?
d) Is there a least element?
e) Find all upper bounds of {3, 5}.
f) Find the least upper bound of {3, 5}, if it exists.
g) Find all lower bounds of {15, 45}.
h) Find the greatest lower bound of {15, 45}, if it exists.
Determine whether the relation R on the set of all integers
is reflexive, symmetric, antisymmetric, and/or transitive,
where (x, y) ∈ R if and only if
a) x ≠ y. b) xy ≥ 1.
c) x = y + 1 or x = y − 1.
d) x ≡ y (mod 7). e) x is a multiple of y.
f ) x and y are both negative or both nonnegative.
g) x = y2. h) x ≥ y2
Determine whether the relation R on the set of all real
numbers is reflexive, symmetric, antisymmetric, and/or
transitive, where (x, y) ∈ R if and only if
a) x + y = 0. b) x = ±y.
c) x − y is a rational number.
d) x = 2y. e) xy ≥ 0.
f ) xy = 0. g) x = 1.
h) x = 1 or y = 1.
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 visited
Web page b.
b) there are no common links found on both Web
page a and Web page b.
c) there is at least one common link on Web page a and
Web page b.
d) there is a Web page that includes links to both Web
page a and Web page b.
Determine whether the relation R on the set of all people
is reflexive, symmetric, antisymmetric, and/or transitive,
where (a, b) ∈ R if and only if
a) a is taller than b.
b) a and b were born on the same day.
c) a has the same first name as b.
d) a and b have a common grandparent.
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)}
