What is subset partial order

Question

This is one of the example problem solved in Velleman's How to prove book:

Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x \in X$ and $x < y$ then $y \in X$.

The presented solution goes like this:

Another way to phrase the question would be to say that we are looking for the smallest element of the family of sets $F = \{X \subseteq R \mid 5 \in X \land \forall x \forall y((x \in X \land x < y) \implies y \in X)\}$, where it is understood that smallest means smallest with respect to the subset partial order. ......

Now what does "smallest with respect to the subset partial order" mean ? What is the subset partial order there ? And if there is a subset partial order there, don't we have to prove that it is a partial order before claiming it is a partial order ?

Answer 1

"$X$ is smaller than $Y$ with respect to the subset partial order" means simply that $X \subseteq Y$. However, working out from that what "smallest" means precisely is a little tricky. Here's two reasonable definitions of "smallest":

• There are no things smaller than this thing,
• Everything is larger than this thing.

In totally-ordered sets where every pair of things is comparable, these are the same, so it's not something you have to think about. But because $\subseteq$ is a partial order, and some pairs of sets are not comparable, there's actually a difference: just because nothing is smaller than you, doesn't mean you're smaller than everything. (However, being smaller than everything in a partial order DOES mean that nothing is smaller than you – perhaps this would make a good exercise if it's not already clear to you).

The terminology I'm familiar with is that the first concept – no things smaller than this thing – is a "minimal element", whereas the second – all things are larger than this thing – is a "least element". The corresponding words at the other end are "maximal" resp. "greatest" element. It's not clear which concept your question in particular is referring to, but from the fact it asks for the smallest, it's probably looking for a unique thing, and only least elements are unique. So assume it's asking for a least element.

If you haven't proven $\subseteq$ is a partial order, feel free to do so now, and then never bother to do so again.

Answer 2

A partial order is a relation that satisfies certain things. You can read more here. The subset partial order is just $A\leq B$ if and only if $A\subseteq B$.