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)
Best Answer
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$.