Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
up vote 1 down vote accepted

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$.

share|cite|improve this answer
Ah, great, thankyou! That makes a lot more sense than the relation I came up with. – Callum M Apr 8 '13 at 20:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.