Partial Order Relation MCQs: 12 Solved Poset and Total Order Questions

Students often remember that a partial order is reflexive, antisymmetric and transitive, then lose marks by confusing antisymmetry with asymmetry, forgetting comparability in a total order, or counting linear extensions without respecting every predecessor. Reflexivity, antisymmetry and transitivity establish a partial order; comparability upgrades it to a total order, while linear-extension questions require every predecessor constraint. Place these relation tests within the wider GATE CS exam preparation syllabus, then commit to each answer before opening its explanation.

Partial order relations: the four checks to run first

Symmetry asks for a reverse pair. Antisymmetry forbids reverse pairs only for distinct elements. On A={1,2,3}, take R={(1,1),(2,2),(3,3),(1,2),(1,3),(2,3)}. Every element has its self-pair, no distinct pair appears both ways, and every required shortcut is present. Every pair is comparable, so this is the total order 1<2<3.

By contrast, subset inclusion on P({p,q}) is reflexive, antisymmetric and transitive, but {p} and {q} are incomparable. It is a partial order, not a total order. Run the first three checks for a poset, then run comparability only if the question asks for a total order.

Partial order MCQs 1 to 3: definition, antisymmetry and strict inequalities

Question 1

What is a partial order relation?

• A. A relation that is reflexive, antisymmetric, and transitive

• B. A relation that is reflexive, symmetric, and transitive

• C. A relation that is reflexive and symmetric, but not transitive

• D. A relation that is symmetric and transitive, but not reflexive

Correct answer: A. A partial order requires reflexivity, antisymmetry and transitivity. Option B instead gives the equivalence-relation pattern, replacing antisymmetry with symmetry.

Question 2

Which of these relations is anti-symmetric?

• A. R = {(1, 2), (2, 1)}

• B. R = {(1, 2), (2, 1), (1, 1)}

• C. R = {(1, 2), (2, 2), (3, 3)}

• D. R = {(1, 2), (2, 1), (3, 3)}

Correct answer: C. A, B and D contain both (1,2) and (2,1) for distinct elements, violating antisymmetry. C has no distinct reverse pair; self-pairs are allowed.

Question 3

GATE 2006

A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is:

• A. Neither a Partial Order nor an Equivalence Relation

• B. A Partial Order but not a Total Order

• C. A Total Order

• D. An Equivalence Relation

Correct answer: A. Reflexivity fails because (x,y)R(x,y) requires x<x and y>y. Transitivity holds, but reflexivity is compulsory; (0,1)R(1,0) without the reverse also disproves symmetry.

Poset MCQs 4 to 6: subset order, digitwise order and poset isomorphism

Question 4

HPSC 2015

The subset relation defined on a power set is:

• A. Reflexive and symmetric only

• B. Equivalence relation

• C. Irreflexive and transitive only

• D. Partial ordered relation

Correct answer: D. A⊆A; A⊆B and B⊆A imply A=B; and A⊆B⊆C implies A⊆C. Inclusion therefore passes reflexivity, antisymmetry and transitivity, although it is not generally symmetric.

Question 5

GATE 2007 Information Technology

A partial order P is defined on the set of natural numbers as follows. Here x/y 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)

Which of these ordered pairs of natural numbers are contained in P?

• A. (i) and (iii)

• B. (ii) and (iv)

• C. (i) and (iv)

• D. (iii) and (iv)

Correct answer: D. With leading zeroes, 101≤digit 022 fails at 1≤0, while 022≤digit 101 fails at 2≤1. The other checks are 5≤5, 4≤6, 1≤2 and 0≤3, 0≤5, 0≤1, so only (iii) and (iv) belong to P.

The same digitwise-order question appears in Set Theory and Relations MCQs: 12 Solved GATE Questions as one checkpoint among set operations, closures, equivalence relations and Hasse diagrams. Here, it trains recursive comparison before the total-order and linear-extension questions that follow.

Question 6

Consider the posets below. Which are isomorphic to (P(S), ⊆), where S={a,b,c}? I. ({1,2,3,6,14,21,42}, divides) II. ({1,2,3,6,11,22,33,66}, divides) III. ({1,2,5,7,10,14,35,70}, ≤)

• A. I and II only

• B. II only

• C. II and III only

• D. III only

Correct answer: B. P(S) has eight elements with rank sizes 1,3,3,1. Set I has only seven listed elements because divisor 7 of 42 is missing. Set II is the complete divisor set of 66=2*3*11, so mapping each divisor to its prime-factor subset preserves divisibility and inclusion. Set III has eight elements, but ordinary ≤ makes it a chain, unlike a power set where {a} and {b} are incomparable.

Poset and lattice MCQs 7 to 8: coordinatewise order and a relation graph

Question 7

GATE 2025 Computer Science Set 2

Let F be the set of all functions from {1, … , n} to {0,1}. Define the binary relation ≼ on F as follows:

∀f, g ∈ F, f ≼ g if and only if ∀x ∈ {1, … , n}, f(x) ≤ g(x), where 0 ≤ 1.

Which of the following statement(s) is/are TRUE?

• A. ≼ is a symmetric relation

• B. (F, ≼ ) is a partial order

• C. (F, ≼ ) is a lattice

• D. ≼ is an equivalence relation

Correct answer: B and C. Coordinatewise ≤ is reflexive and transitive; both directions force equality, giving antisymmetry. For n=2, 01 and 10 are incomparable within 00,01,10,11, but have meet 00 and join 11, proving a lattice without symmetry or equivalence.

Question 8

UGC NET 2018 Computer Science

Which of the following statements is true ?

• A. (Z,≤) is not totally ordered

• B. The set inclusion relation ⊆ is a partial ordering on the power set of a set S

• C. (Z,≠) is a poset

• D. The directed graph shown below is not a partial order

Correct answer: B. (Z,≤) is total, ≠ is not reflexive, and inclusion passes all poset tests. The loops plus a→b form the order a≤b, so D is false.

Total order and linear-extension MCQs 9 to 11

Question 9

What is a total order relation?

• A. A partial order relation that is also symmetric

• B. A partial order relation that is also antisymmetric

• C. A partial order relation that is also transitive

• D. A partial order relation that is also connex or complete

Correct answer: D. A partial order is already antisymmetric and transitive. A total order adds comparability, aRb or bRa, which is the connex or complete condition.

Question 10

GATE 1997

A partial order ≤ is defined on S = {x, a₁, a₂, ..., aₙ, y} by:

x < aᵢ for every i, and

aᵢ ≤ y for every i, where n ≥ 1.

How many total orders (linear extensions) on S extend this partial order?

• A. n!

• B. n + 2

• C. n

• D. 1

Correct answer: A. The constraints fix x first and y last, leaving the n middle elements unconstrained. They have n! permutations; for n=3, permuting a₁,a₂,a₃ gives 3!=6 extensions.

Question 11

GATE 2024 Computer Science Set 2

Let P be the partial order defined on the set {1,2,3,4} as follows

P = {(x, x) | x ∈ {1,2,3,4}} ∪ {(1,2), (3,2), (3,4)}

The number of total orders on {1,2,3,4} that contain P is __________

Correct answer: 5. The active constraints are 1<2, 3<2 and 3<4. Choosing 1 first gives (1,3,2,4) and (1,3,4,2); choosing 3 first gives (3,1,2,4), (3,1,4,2) and (3,4,1,2), so 2+3=5.

Partial order assertion-reason MCQ 12: disprove with one counterexample

Question 12

UGC NET 2026 Computer Science January

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.

Assertion A: Let R ⊆ A × A be a binary relation as defined below:

A = N × N; ((a, b), (c, d)) ∈ R if and only if a ≤ c or b ≤ d. This binary relation R is a partial order.

Reason R: A binary relation will be a partial order if this satisfy reflexive, anti-symmetric and transitive property.

In the light of the above statements, choose the most appropriate answer from the options given below:

1. Both A and R are correct and R is the correct explanation of A

2. Both A and R are correct but R is NOT the correct explanation of A

3. A is correct but R is not correct

4. A is not correct but R is correct

• A. 1

• B. 2

• C. 3

• D. 4

Correct answer: D. Reason R gives the correct test. With x=(2,3), y=(3,1), z=(1,2), xRy holds by 2≤3 and yRz by 1≤2, but xRz fails because 2≤1 and 3≤2 are false. Thus A is false and R is true, mapping to statement 4 and option D.

Partial order MCQ traps and the next practice step

In 60 seconds, test a=a, hunt a distinct reverse pair, chain two true pairs, then check comparability. For extensions, branch only on current minima.

If Questions 1, 3, 4 or 8 went wrong, rebuild with Set Theory and Relations Explained for GATE. Retest 5, 6, 7, 11 and 12 unaided.

Follow GATE Guidance by Sanchit Sir for sequenced Discrete Mathematics. The short version: posets need reflexivity, antisymmetry and transitivity; total orders add comparability; one counterexample defeats a universal claim.