Hi everyone is my second exercise of posets. And find the following, the first part I think is not difficult at all. But for the converse I have some serious troubles to prove it. I have two questions: Is the following correct? and second, there is some constructive proof for the second statement assuming that this is correct? Any advice, suggestion would be great. Thanks in advance
Lemma: Suppose $Y$ is a poset and let $X \subset Y$ be a finite totally ordered set. Then every non-empty subset of $X$ contains a minimum and maximum element. Conversely, if $X$ is a totally ordered set and every non-empty subset of $X$ has both minimum and maximum element. Then the set is finite.
Proof: Suppose $X$ is a finite totally ordered set and let $P(n)$ be the statement: "If $X$ is a finite totally ordered set with $n$ elements then every non-empty subset of $X$ contains a maximum and minimum element". The assertion is vacuously true when $n=0$, since $X$ is empty and it does not contain a non-empty subset. Now suppose we have already proven the assertion for $n\ge 0$; we'd like to show that also is true when $\,\#X=n+1$. Clearly $X$ is a non-empty set, then it contain an element $x_0\in X$.
Let define $X'= X \backslash \{x_0\}$. Then $X'$ contain $n$ elements and every non-empty subset of $X'$ contain a minimum and maximum element by the inductive hypothesis. Suppose $F$ is a given non-empty subset of $X$. Then either $x_0\in F$ or $x_0 \notin F$. For the former, let $F'= F\backslash \{x_0\}$, so $F'\subset X'$ and contain a maximum and minimum element. Let $a$ and $b$ be the maximum and minimum element respectively. So, we need to compare $x_0$ with $a,b$ (this is always possible because $X$ is totally ordered) in the case that $a < x_0 $ or $x_0<b$ but not both at the same time (if were $a<x_0<b$, i.e., $a<b$ which is not possible ), we set this as the maximum or minimum element of the set. The case when $x_0\notin F$ is trivial because $F\subset X'$. Thus the claim hold in any case as desired.
Conversely, suppose for the sake of contradiction that $X$ is an infinite totally ordered set and each non-empty set of $X$ contain a maximum and minimum element. We define the elements $x_n$ recursively by setting $x_0 = \text{min} (X)$ and $x_{n+1}= \text{min}(\{ x\in X: \forall i \le n\, (x\not=x_i) \})$. This definition is well-define since $X$ is assume to be an infinite set and each subset contain a minimum element by hypothesis.
We claim that for all $n,m\in \mathbb{N}$ if $n<m$ then $x_n<x_m$. Let us fix $n$ an suppose by contradiction that exist an element for which the claim is false. Let $m_0$ be the least element. So, $x_n\ge x_{m_0}$ and $n< m_0$. Since $x_{n}<x_{n+1}$, then $m_0\not= n+1$. It follows that $m_0=k+1$ and thus $x_k<x_{m_0}$. By transitivity $x_k < x_n$ which contradicts the minimality of $m_0$. Then the result follows by reductio ad absurdum.
Then we have and increasing sequence $x_0 < x_1 <…<x_n…$ of elements of $X$. Let define $(x_n):=\{x\in X: x\le x_n \}$ (notice that this sets are non-empty for all $n$) and $X':= \bigcup_{n=0}^\infty (x_n)$. Clearly $X'\subset X$, then it has a maximum element by hypothesis, let call it $x_{max}$. Then $x_{max} \in X'$, i.e., $x_{max} \in (x_n)$ for some $n\in \mathbb {N}$. But $x\le x_n$ and if we set some $m>n$ we therefore have $x_{max}< x_m$ which is a contradiction.
Best Answer
The whole proof works great, although you could just use the sequence $x_n$ instead of the sets $(x_n)$. The sequence can't have a maximum because you constructed a successor for each element.
A constructive proof is not likely because your hypothesis (that there exists a max and min) is not itself constructive.