2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh yeah only setting $\{ x_n: n\in \mathbb{N}\}$ we obtain the desire counterexample. Thanks for your help Brian. $\endgroup$ – Jose Antonio Jan 10 '14 at 20:21

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.