Discrete Mathematics Multiple Choice Questions on “Relations – Partial Orderings”.
1. Let a set S = {2, 4, 8, 16, 32} and <= be the partial order defined by S <= R if a divides b. Number of edges in the Hasse diagram of is ______
a) 6
b) 5
c) 9
d) 4
Answer: b
Clarification: Hasse Diagram is:
32
/
16
/
8
/
2 4
So, the number of edges should be: 4.
2. The less-than relation, <, on a set of real numbers is ______
a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric
b) a partial ordering since it is asymmetric and reflexive
c) a partial ordering since it is antisymmetric and reflexive
d) not a partial ordering because it is not antisymmetric and reflexive
Answer: a
Clarification: Relation less than a set of real numbers is not antisymmetric and reflexive. Relation is not POSET because it is irreflexive. Again, aRb != bRa unless a=b and so it is antisymmetric. A relation may be ‘not asymmetric and not reflexive but still antisymmetric, as {(1,1) (1,2)}. So, the relation is not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric.
3. If the longest chain in a partial order is of length l, then the partial order can be written as _____ disjoint antichains.
a) l2
b) l+1
c) l
d) ll
Answer: c
Clarification: If the length of the longest chain in a partial order is l, then the elements in the POSET can be partitioned into l disjoint antichains.
4. Suppose X = {a, b, c, d} and π1 is the partition of X, π1 = {{a, b, c}, d}. The number of ordered pairs of the equivalence relations induced by __________
a) 15
b) 10
c) 34
d) 5
Answer: b
Clarification: The ordered pairs of the equivalence relations induced = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c), (d,d)}. Poset -> equivalence relations = each partition power set – Φ.
5. A partial order P is defined on the set of natural numbers as follows. Here a/b denotes integer division. i)(0, 0) ∊ P. ii)(a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs:
i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153)
The ordered pairs of natural numbers are contained in P are ______ and ______
a) (145, 265) and (0, 153)
b) (22, 101) and (0, 153)
c) (101, 22) and (145, 265)
d) (101, 22) and (0, 153)
Answer: d
Clarification: For ordered pair (a, b), to be in P, each digit in a starting from unit place must not be larger than the corresponding digit in b. This condition is satisfied by options (iii) (145, 265) => 5 ≤ 5, 4 < 6 and 1 < 2; (iv) (0, 153) => 0 < 3 and no need to examine further.
6. The inclusion of ______ sets into R = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make R a complete lattice under the partial order defined by set containment.
a) {1}, {2, 4}
b) {1}, {1, 2, 3}
c) {1}
d) {1}, {1, 3}, {1, 2, 3, 4}, {1, 2, 3, 5}
Answer: c
Clarification: A lattice is complete if every subset of partial order set has a supremum and infimum element. For example, here we are given a partial order set R. Now it will be a complete lattice if whatever be the subset we choose, it has a supremum and infimum element. Here relation given is set containment, so supremum element will be just union of all sets in the subset we choose. Similarly, the infimum element will be just an intersection of all the sets in the subset we choose. As R now is not complete lattice, because although it has a supremum for every subset we choose, but some subsets have no infimum. For example, if we take subset {{1, 3, 5}, {1, 2, 4}}, then intersection of sets in this is {1}, which is not present in R. So clearly, if we add set {1} in R, we will solve the problem. So adding {1} is necessary and sufficient condition for R to be a complete lattice.
7. Consider the ordering relation a | b ⊆ N x N over natural numbers N such that a | b if there exists c belong to N such that a*c=b. Then ___________
a) | is an equivalence relation
b) It is a total order
c) Every subset of N has an upper bound under |
d) (N,|) is a lattice but not a complete lattice
Answer: d
Clarification: A set is called lattice if every finite subset has a least upper bound and greatest lower bound. It is termed as a complete lattice if every subset has a least upper bound and greatest lower bound. As every subset of this will not have LUB and GLB so (N,|) is a lattice but not a complete lattice.
8. Consider the set N* of finite sequences of natural numbers with a denoting that sequence a is a prefix of sequence b. Then, which of the following is true?
a) Every non-empty subset of has a greatest lower bound
b) It is uncountable
c) Every non-empty finite subset of has a least upper bound
d) Every non-empty subset of has a least upper bound
Answer: a
Clarification: Consider any sequence like “45, 8, 7, 2” – it can have many (infinite) least upper bounds like “45, 8, 7, 2, 5”, “45, 8, 7, 2, 1” and so on but it can have only 1 greatest lower bound – “45, 8, 7” because we are using the prefix relation. So, every non-empty subset has a greatest lower bound.
9. A partial order ≤ is defined on the set S = {x, b1, b2, … bn, y} as x ≤ bi for all i and bi ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______
a) n+4
b) n2
c) n!
d) 3
Answer: c
Clarification: To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently, there is no relation between any bi and bj. So, for every bi and bj, we have to add either (bi, bj) or (bj, bi) in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways.
10. Let (A, ≤) be a partial order with two minimal elements a, b and a maximum element c. Let P:A –> {True, False} be a predicate defined on A. Suppose that P(a) = True, P(b) = False and P(a) ⇒ P(b) for all satisfying a ≤ b, where ⇒ stands for logical implication. Which of the following statements cannot be true?
a) P(x) = True for all x S such that x ≠ b
b) P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
c) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x
Answer: d
Clarification: Here, maximum element is c and so c is of a higher order than any other element in A. Minimal elements are a and b: No other element in A is of lower order than either a or b.
We are given P(a) = True. So, for all x such that a≤x, P(x) must be True. We do have at least one such x, which is c as it is the maximum element. So, P(x) = False for all x ∈ S such that a ≤ x and b ≤ x -> cannot be true. P(x) = True for all x S such that x ≠ b -> can be True as all elements mapped to TRUE doesn’t violate the given implication. P(x) = False for all x ∈ S such that x ≠ a and x ≠ c -> can be True if a is related only to c. P(x) = False for all x ∈ S such that b ≤ x and x ≠ c -> can be True as b≤x ensures x≠a and for all other elements P(x) can be False without violating the given implication.