GATE Overflow Test Series | Discrete Mathematics | Test 3 | Question: 9

Question

Which of the following is/are correct?

1. A relation that is reflexive, anti-symmetric, and transitive is called a partial order.
2. When every two elements in a set are comparable, the relation is called a total ordering (linear ordering).
3. The poset $(\mathbb{Z},\leq)$ is not totally ordered, where $\mathbb{Z}$ is the set of integers.
4. The inclusion relation $\subseteq$ is a partial ordering on the power set of a set.

 

• A. I and II only
• B. I and III only
• C. I, II and III only
• D. I, II and IV only

Comments

@gatecse SIr, the definition in option II is incomplete, even an equivalence relation on a set of size $>=2$ will satisfy the condition of every two elements being comparable but that equivalence relation is not anti-symmetric, and hence not even a partial order relation (total order relation).

Answer 1

The poset $(\mathbb{Z}, \leq)$ is totally ordered, because for any integers $a,b, a\leq b$ or $b\leq a.$ Other three statements are true.

So, the correct answer is $(D)$.

Comments

Can someone please clarify the D part

@Deepak Poonia sir 

---

@Harshit Dubey

For any set $S,$ $(P(S), \subseteq )$ is a POSET as well as Distributive Complemented Lattice.

For any set $S,$ $(P(S), \subseteq )$ is a boolean algebra(boolean lattice).