# Every subset has first and last element -> set is finite

Let $X$ be a partially ordered set, so that every non empty subset of $X$ has a first and a last element. Show that $X$ is a finite set.

And what if every subset only has a first element?

Well, I proved it is a linear order, but now I'm stuck.

Anyone ready to clear things up for me? Thanks a lot!

• If every subset only has a first element, the set is not necessarily finite. For example: $\mathbb N$. – ThePortakal Jun 16 '15 at 23:58
• What precisely do you mean with first and last element in the case of a poset that is not linear? If it means minimal and maximal, then this is false: Just let $\preceq$ be the poset on some infinite $X$ defined by $x \preceq y$ iff $x=y$. – Stefan Mesken Jun 17 '15 at 9:44

If it's a linear ordering with a first and last element, then it's in bijection with $\{1,...,n\}$ for some $n$. Build the bijection inductively, and you'll be done. There's a first element that should definitely map to $1$. Keep going, and eventually you'll have to stop because there's a last element. Wherever you stopped is the $n$ you want.

To answer your other question, any ordinal (with it's natural ordering) satisfies that every subset has a least element, as it's a well-ordering. In particular, the naturals numbers have this property.

• Why do I have to use induction? Can't I just say X={x1,x2,...} and set f to be f(xi) = i for every i$\in${1,...,n}? – Whyka Jun 17 '15 at 0:14
• Using $x_1, x_2,...$ implies that you have the ordering already! How do you choose what $x_i$ is? First you define $x_1$ as $min(X)$. Then define $x_2$ as $min(X\setminus\{x_1\})$ and so on. – Zach Stone Jun 17 '15 at 0:18
• But we only need a bijection, I already showed the linear ordering exists – Whyka Jun 17 '15 at 0:39
• It's not completely obvious that you ever get to the last element ... for example in $\omega+1$ you can keep taking out the first element forever, without reaching the last one. So you need to argue something like if you can keep choosing a the minimum unchosen elements $\omega$ times, then after doing so, the elements chosen so far must have a last element, which is absurd. (On the other hand, the fact that $X$ itself has a last element is of little importance). – Henning Makholm Jun 17 '15 at 0:49
• @HenningMakholm Thanks! – Whyka Jun 17 '15 at 8:30

Since $X$ is a linear order and every subset has a least element, $X$ is a well-order. It follows that it is order-isomorphic to some ordinal $\alpha$, so it is equivalent to consider the same question for $\alpha$. $\omega$ has no maximal element, hence $\omega \nsubseteq \alpha \implies \omega \notin \alpha \land \omega \neq \alpha$. It follows that $\alpha \in \omega$. Hence $|\alpha| \leq \alpha < \aleph_0$.

One may also give a more "direct" proof. Assume $X$ is infinite. We shall construct an strictly increasing/decreasing sequence which will contradict the existence of a last/first element.

Start with some element $x_1\in X$. At least one of the sets $\left\{ x>x_1 \right\}, \left\{ x<x_1 \right\}$ is infinite. Assume without loss of generality $\left\{ x>x_1 \right\}$ is infinite. By assumption, this set (as a subset of $X$), has a first element $x_2$. The set $\left\{ x>x_2 \right\}=\left\{ x>x_1 \right\}\setminus \left\{ x_2 \right\}$ is also infinite, and also contains a first element $x_3$. In this fashion we obtain a nested sequence of nonempty sets $\left\{ x>x_n \right\} \supsetneq \left\{ x>x_{n+1} \right\}$. Picking an element from each set which isn't the last one yields a strictly increasing sequence, which is a subset of $X$ without a last element. Contradiction.

(If you don't like the freedom of "picking an element", just use the sequence $\left\{ x_n \right\}$.)