This is a past exam question.

Let S = {a,b,c}

Define $\mathcal{P}(S)$ as the power set of S.

Consider $\mathcal{P}(S)\setminus S$

Explain how this structure illustrates the concepts of partial order and maximal element.


Generalising, let the relation $R_p$ be defined such that apb $\Longleftrightarrow b = \mathcal{P}(A)\setminus A$

Of course, a partial order is a relation on a set (in this case, I think it'd be the theoretical universal set U s.t. all sets $A \in U$), which is reflexive, antisymmetric and transitive.

However, I don't understand how this relation is reflexive. Taking the example of S={a,b,c}, $\mathcal{P}(S)\setminus S = \{\emptyset, \{a\},\{b\},\{c\},\{a,b\},\{a,c\}, \{b,c\}\}$ Clearly, by definition, $S \notin \mathcal{P}(S)\setminus S$. Defining the relation to be subset inclusion also does not make it reflexive. I can't think of any appropriate relationship that would be reflexive.

I can see that the question wants me to show that it is a partial order, and then discuss how there is no unique maximal element - since {a,b}, {a,c} and {b,c} are all maximal. However, I feel like I must be missing something here - how can it be that a partial order exists between S and $\mathcal{P}(S)\setminus S$, when $\mathcal{P}(S)\setminus S$ seems to contradict the definition of reflexivity?

(partial-order may be an appropriate tag, but I can't add it myself)


1 Answer 1


The partial order is set inclusion. It is reflexive as (for example) $\{a\} \subseteq \{a\}$. It is not a partial order batween $S$ and $\mathcal{P}(S)\setminus S$, it a partial order within $\mathcal{P}(S)\setminus S$.

  • $\begingroup$ Ah, great, thankyou! That makes a lot more sense than the relation I came up with. $\endgroup$
    – Callum M
    Apr 8, 2013 at 20:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .