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\}$.)
{"ft_lang_label":"__label__en","ft_lang_prob":0.8482312,"math_prob":0.99459827,"size":990,"snap":"2019-43-2019-47","text_gpt3_token_len":293,"char_repetition_ratio":0.1724138,"word_repetition_ratio":0.0,"special_character_ratio":0.2989899,"punctuation_ratio":0.09677419,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99963284,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-22T00:49:48Z\",\"WARC-Record-ID\":\"<urn:uuid:f344a87c-4c0e-4f49-a78d-a1dbb1c99cab>\",\"Content-Length\":\"156405\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:670e3d45-ff75-4201-9410-a9a76eefc648>\",\"WARC-Concurrent-To\":\"<urn:uuid:b241f664-04dd-4408-aeb3-3394cb33df7d>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/1328215/every-subset-has-first-and-last-element-set-is-finite/1446421\",\"WARC-Payload-Digest\":\"sha1:VKRU7HLIBFV6QG7VS4SRYI2AYVR5KAQ6\",\"WARC-Block-Digest\":\"sha1:ZT5NQMGA7T5VYQUEAAUWO5U5C6JPUN64\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987795403.76_warc_CC-MAIN-20191022004128-20191022031628-00355.warc.gz\"}"}