Let Q be the partial order relation defined on P(N)×P(N) by (A, B)Q(C, D) if and only if A ⊆ C and D ⊆ B. Is Q a partial order relation? Is Q a total order relation?

Question

discrete mathematics problem

Answer 1

Let us recall what a non-strict partial order relation is. It is a relation on a set which is reflexive, anti-symmetric, and transitive.

A relation R on a set S is reflexive if for every a ∈ S, aRa.

Let A×B be an element in P(N)×P(N). Since A ⊆ A and B ⊆ B, it follows that (A,B)Q(A,B), so the relation is reflexive.

A relation R on a set S is anti-symmetric if aRb and bRa implies a = b, for a,b ∈ S.

Let A×B, C×D ∈ P(N)×P(N) that satisfy (A,B)Q(C,D) and (C,D)Q(A,B). The first implies that A ⊆ C and B ⊆ D, while the second implies that C ⊆ A and D ⊆ B. Hence, A ⊆ C and C ⊆ A gives A = C, and similarly for B and D. Thus, we conclude that (A,B) = (C,D).

A relation R on a set S is transitive if aRb and bRc imply aRc, for a,b,c ∈ S.

Let A×B, C×D, E×F ∈ P(N)×P(N) satisfying (A,B)Q(C,D) and (C,D)Q(E,F). This implies that A ⊆ C and C ⊆ E, which by the transitivity of set containment gives A ⊆ E. Similarly, B ⊆ D and D ⊆ F so B ⊆ F. Thus, (A,B)Q(E,F) and we conclude that relation is transitive.

Thus, Q is a partial order on P(N) × P(N).

A total order is a binary relation on a set which is anti-symmetric, transitive, and satisfies connexity.

Connexity is the property that for a,b ∈ S, either aRb or bRa. In words, for every pair of elements a and b of S, either aRb holds or bRa holds.

In the above example, provided the set N has cardinality at least 2, the relation is not a total order. This is because we can find singleton sets {a} and {b} for a ≠ b, a,b ∈ S. Then, ({a},{a}) and ({b}, {b}) do not satisfy ({a},{a})R({b},{b}) nor ({b},{b})R({a},{a}) since {a} ⊄ {b} and {b} ⊄ {a}.

Hence, Q is not a total order in general. In fact, if the set is N non-empty, Q is not a total order (you need to adjust the above counterexample for the case when N has cardinality 1 to show this).