Discrete Computational Structures Homework Assignment #5

CS 230 : Discrete Computational Structures

Homework Assignment #5

Suggested Reading: Rosen Sections 9.1 and 9.5; Lehman et al. Chapter 10.5, 10.6 and
10.10
For the problems below, explain your answers and show your reasoning.
1. [10 Pts] For each of these relations decide whether it is reflexive, anti-reflexive, symmetric, anti-symmetric and transitive. Justify your answers. R1 and R2 are over the
set of real numbers.
(a) (x, y) ∈ R1 if and only if xy ≥ 0
Reflexive. a ∈ R, a ∗ a ≥ 0.
Not Anti-Reflexive. it’s reflexive.
Symmetric. Communitative property of multiplication, a, b ∈ R, a ∗ b = b ∗ a, ab
is in the relation if and only if its equivalent expression ba is in the relation.
Not Anti-Symmetric. it’s Symmetric
Transitive. for xy ≥ 0, x and y must be the same sign. for z ∈ R, yz ≥ 0, y and
z must be the same sign. Therefore, x and z have the same sign, so xz ≥ 0
(b) (x, y) ∈ R2 if and only if x = 2y
Not Reflexive. x 6= 2y if x = y ∧ x, y 6= 0
Not Anti-Reflexive. Consider x = y = 0
Not Symmetric. Consider x = 6 and y = 3. (6, 3) ∈ R2, but (3, 6) ∈ R2
Anti-Symmetric. 2x = y and 2y = x cannot be both be true, that is, a non-zero
number’s half cannot be equal to it’s double
Not Transitive. Suppose a = 4, b = 2, and c = 1. (a, b) and (b, c) is in the
relation. However, (a, c) gives 4 = 2(1).
2. [8 Pts] Let R3 be the relation on Z
+ × Z+ where ((a, b),(c, d)) ∈ R3 if and only if
ad = bc.
(a) Prove that R3 is an equivalence relation.
i. Reflexive: ab = ba → (a, b)R(a, b) for all (a, b) ∈ Z × Z
ii. Symmetric: (a, b)R(c, d) → ad = bc → cb = da → (c, d)R(a, b)
iii. Transitive: Prove (a, b)R(c, d) ∧ (c, d)R(e, f) → (a, b)R(e, f)
ad = bc ∧ cf = de, c =
de
f
ad = b ∗
de
f
af = b ∗ e) → (a, b)R(e, f)
(b) Define a function f such that f(a, b) = f(c, d) if and only if ((a, b),(c, d)) ∈ R3.
f(x, y) = x
y
(c) Define the equivalence class containing (1, 1).
[(1, 1)]R = {(a, b) | a = b,(a, b) ∈ Z × Z}
(d) Describe the equivalence classes. How many classes are there and how many
elements in each class?
∀(a, b) ∈ Z × Z, [(a, b)]R = {(c, d) | ad = bc,(c, d) ∈ Z × Z}
There’s a countably infinite no. of classes, because (a, b) ∈ Z × Z is countably
infinite.
Each class has an infinitely countable no. of elements, because (c, d) ∈ Z × Z is
countably infinite.
3. [8 Pts] Are these relations on the set of 5 digit numbers equivalence relations? If
so, prove the properties satisfied, describe the equivalence classes and describe a new
equivalence relation which is a refinement of the relation given. If not, describe which
properties are violated.
(a) (a, b) ∈ R4 if and only if a and b start with the same two digits
i. Reflexive: A number’s first two digits are equal to it’s doppleganger’s two
digits.
ii. Symmetric: When the first two digits match, comparing them in reverse order
doesn’t change the match
iii. Transitive: If number A’s 2 digits match B’s, and B matches C’s, then A’s
digits = B’s digits = C’s digits.
iv. Each class contains 1000 elements, with ab000-ab999,
v. There are 100 equivalence classes, where the first two digits are 00-99
vi. A refinement would be all five digits numbers with the same 3 first digits,
with 1000 equivlance classes 000-999 and 100 elements per class
(b) (a, b) ∈ R5 if and only if a and b have the same kth digit, where k is a number
from 1 to 5
i. Reflexive: a five digit number has the same digits as it’s doppleganger. this
is true for all k locations
ii. Symmetric: Two numbers with the same kth digit compared in reversed order
will not change the matching digit at location k
iii. Transitive: If A’s kth digit matches B’s digit, and B’s matches C’s, then kth
digit of A = B = C
iv. There are five equivalance classes, for k 1-5
v. Each class has 1000*10 elements, where 10 is number of possible values for
the kth digit, and 1000 are the number of possible combinations of the four
other digits.
vi. This relation could be refined by defining the set as all five digit numbers
with the same kth and lth digits, where k and l are 1-5. This would have 5∗4
2
equivalence classes, and each class would have 100 elements.
4. [12 Pts] Prove that these relations on the set of all functions from Z to Z are equivalence relations. Describe the equivalence classes.
(a) R6 = {(f, g) | f(0) = g(0) and f(1) = g(1)}
i. Reflexive: If f, g are the same function in the relation, then f(0) = g(0), f(1)
= g(1)
ii. Symmetric: For f, g in the relation, If f(0) = g(0), f(1) = g(1), then g(0) =
f(0), g(1) = f(1)
iii. Transitive: for functions f, g, h in the relation, f(0) = g(0) = h(0), f(1) = g(1)
= h(1)
iv. There are an uncountably infinite number of piecewise functions where for
arbitrary constant C ∈ Z, set f(0) = C, g(0) = C, and D ∈ Z f(1) = D, g(1)
= D. Each function has a countably infinite number of elements because they
will only vary by some number of constants. Z × Z × Z × ... is countably
infinite.
(b) R7 = {(f, g) | ∃C ∈ Z, ∀x ∈ Z, f(x) − g(x) = C}
i. Reflexive: f(x) - f(x) = 0. 0 ∈ Z
ii. Symmetric: f(x) - g(x) = C, g(x) - f(x) = -C. C, −C ∈ Z
iii. Transitive: Because we must consider ∀x ∈ Z, the domain of f and g must
be Z. All Z have some output in Z, and any output a, b ∈ Z, a − b ∈ Z All
differences between the output of 3 functions with domain Z will exist in Z.
iv. There’s an uncountably infinite number of functions with domain in Z, so
there are an uncountably infinite number of classes. Each function has a
countably infinite number of elements because they will only vary by up to
an infinite number of constants. Z × Z × Z × ... is countably infinite.
5. [12 Pts] Consider the following relations on the set of positive real numbers. One
is an equivalence relation and the other is a partial order. Which is which? For the
equivalence relation, describe the equivalence classes. What is the equivalence class of
2? of π? Justify your answers.
(a) (x, y) ∈ R8 if and only if x/y ∈ Z. THIS IS THE PARTIAL ORDER
i. Reflexive: for any number a 6= 0, a/a = 1 ∈ Z
ii. Anti-Symmetric: y
x
is the reciprocal of x
y
. if (x, y) ∈ R8, then the quotient is
an integer. The reciprocal of an integer will never be an integer, except if x
= y.
iii. Transitive: if x
y
is an integer, then that implies y divides x. If y
z
is an integer,
then z divides y. z will then also be a factor of x, so z divides x.
(b) (x, y) ∈ R9 if and only if x − y ∈ Z. THIS IS THE EQUIVALENCE RELATION
i. Since (a) is the partial order, this must be the equivalence relation.
ii. (x, y) ∈ R ⊂ N × N Countably infinite number of classes, where each class
is determined by the value of x. Each class has a countably infinite number
of y where x - y = an integer.
iii. The class for 2 is all integers. 2 is an integer, and any integer minus an integer
will be in Z
iv. [pi]R = {π + n | n ∈ Z}