[SOLVED] Cs215: discrete math (h) written assignment # 5

Q.1 Show that a subset of an antisymmetric relation is also antisymmetric.
Q.2 Define a relation R on R, the set of real numbers, as follows: For all x
and y in R, (x, y) ∈ R if and only if x − y is rational. Answer the followings,
and explain your answers.
(1) Is R reflexive?
(2) Is R symmetric?
(3) Is R antisymmetric?
(4) Is R transitive?
Q.3 How many relations are there on a set with n elements that are
(a) symmetric?
(b) antisymmetric?
(c) irreflexive?
(d) both reflexive and symmetric?
(e) neither reflexive nor irreflexive?
(f) both reflexive and antisymmetric?
(g) symmetric, antisymmetric and transitive?
Q.4 Suppose that the relation R is symmetric. Show that R∗
is symmetric.
Q.5 Prove or give a counterexample to the following: For a set A and a binary
relation R on A, if R is reflexive and symmetric, then R must be transitive
as well.
Q.6 Let R be a reflexive relation on a set A. Show that R ⊆ R2
.
1
Q.7 Let R and S both be transitive relations on a set A. For each of the
relations below, either prove that it is transitive, or give a counterexample,
showing that it may not be transitive.
(1) R ∩ S
(2) R ∪ S
(3) R ◦ S
Q.8
(1) Give an example to show that the transitive closure of the symmetric
closure of a relation is not necessarily the same as the symmetric closure
of the transitive closure of this relation.
(2) Show that the transitive closure of the symmetric closure of a relation
must contain the symmetric closure of the transitive closure of this
relation.
Q.9 Let R be the relation on Z, the set of integers, as follows: For all m and
n in Z, (m, n) ∈ R if and only if 3 divides (m2 − n
2
).
(1) Prove that R is an equivalence relation.
(2) Describe the equivalence classes of R.
Q.10 Let S be a finite set and T be a subset of S. We define a binary relation
R on the power set P(S) of set S: for subsets A and B of S, (A, B) ∈ R if
and only if (A∪B)(A∩B) ⊆ T. Prove that the relation R is an equivalence
relation.
Q.11 Show that the relation R on Z × Z defined on (a, b)R(c, d) if and only
if a + d = b + c is an equivalence relation.
Q.12 Let ∼ be a relation defined on N by the rule that x ∼ y if x = 2k
y or
y = 2kx for some k ∈ N. Show that ∼ is an equivalence relation.
2
Q.13 Which of these are posets?
(a) (Z, =)
(b) (Z, ̸=)
(c) (Z, ≥)
(d) (Z, ̸ |)
Q.14 Consider a relation ∝ on the set of functions from N
+ to R, such that
f ∝ g if and only if f = O(g).
(a) Is ∝ an equivalence relation?
(b) Is ∝ a partial ordering?
(c) Is ∝ a total ordering?
Q.15 The relation R on the set X = {(a, b, c) : a, b, c ∈ N} with (a1, b1, c1)R(a2, b2, c2)
if and only if 2a1 3
b1 5
c1 ≤ 2
a2 3
b2 5
c2
.
(1) Prove that R is a partial ordering.
(2) Write two comparable and two incomparable elements if they exist.
(3) Find the least upper bound and the greatest lower bound of the two
elements (5, 0, 1) and (1, 1, 2).
(4) List a minimal and a maximal element if they exist.
Q.16 Define the relation ≼ on Z × Z according to
(a, b) ≼ (c, d) ⇔ (a, b) = (c, d) or a
2 + b
2 < c2 + d
2
.
Show that (Z×Z, ≼) is a poset; Construct the Hasse diagram for the subposet
(B, ≼), where B = {0, 1, 2} × {0, 1, 2}.
3
Q.17 We consider partially ordered sets whose elements are sets of natural
numbers, and for which the ordering is given by ⊆. For each such partially
ordered set, we can ask if it has a minimal or maximal element. For example, the set {{0}, {0, 1}, {2}}, has minimal elements {0}, {2}, and maximal
elements {0, 1}, {2}.
(a) Prove or disprove: there exists a nonempty R ⊆ P(N) with no maximal
element.
(b) Prove or disprove: there exists a nonempty R ⊆ P(N) with no minimal
element.
(c) Prove or disprove: there exists a nonempty T ⊆ P(N) that has neither
minimal nor maximal elements.
Q.18 Answer these questions for the poset ({3, 5, 9, 15, 24, 45}, |).
(1) Find the maximal elements.
(2) Find the minimal elements.
(3) Is there a greatest element?
(4) Is there a least element?
(5) Find all upper bounds of {3, 5}.
(6) Find the least upper bound of {3, 5}, if it exists.
(7) Find all lower bounds of {15, 45}.
(8) Find the greatest lower bound of {15, 45}, if it exists.