2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ If every subset only has a first element, the set is not necessarily finite. For example: $\mathbb N$. $\endgroup$ – ThePortakal Jun 16 '15 at 23:58
  • $\begingroup$ 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$. $\endgroup$ – Stefan Mesken Jun 17 '15 at 9:44
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}? $\endgroup$ – Whyka Jun 17 '15 at 0:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Zach Stone Jun 17 '15 at 0:18
  • $\begingroup$ But we only need a bijection, I already showed the linear ordering exists $\endgroup$ – Whyka Jun 17 '15 at 0:39
  • 5
    $\begingroup$ 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). $\endgroup$ – Henning Makholm Jun 17 '15 at 0:49
  • $\begingroup$ @HenningMakholm Thanks! $\endgroup$ – Whyka Jun 17 '15 at 8:30
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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\}$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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