Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $(A,\le)$ be a poset. Suppose that for any $a < b \in A$ and for any chain $Q$ of $A$ whose maximum and minimum are $a$ and $b$ respectively, $Q$ is finite. Let $C$ be the set of all chains of $A$, ordered under inclusion. I'd like to show that the poset $(C,\subset)$ satisfies the ascending chain condition (ACC).

I tried to show it by contradiction. Negating the ACC, we can say the existence of an infinite sequence $(Q_i)_{i\in\mathbb{N}}$ of elements of $C$ such that $Q_0 \subsetneq Q_1 \subsetneq Q_2 \subsetneq \cdots$. I think this contradicts the fact that all elements of $C$ are finite, but I cannot show it vigorously.

EDIT: What I really wanted to prove was that $(C, \subset)$ satisfies the ACC, where C is the set of chains whose whose maximum and minimum are $a$ and $b$ respectively. I'm sorry, but the answers seem to still hold.

share|improve this question
    
If $A=\mathbb N$ under the usual order, then it satisfies your condition, but there is an infinite sequence of chains $Q_i=\{1,...,i\}$ –  Thomas Andrews Dec 15 '11 at 14:48
    
Oh, and note that your condition is not that all chains are finite, it says that all chains with a maximum and minimum are finite. Obviously, my example doesn't work if you read your condition as saying all chains are finite. –  Thomas Andrews Dec 15 '11 at 14:50
    
Finally, if you rephrase your condition that all chains are finite, then you can just take $\Cup Q_i$ for any ascending sequence of chains $Q_i$. This is necessarily a chain, so must be finite, so must be some $Q_k$. –  Thomas Andrews Dec 15 '11 at 14:54
add comment

1 Answer

up vote 2 down vote accepted

Note that the increasing union of chains is a chain. Formally:

Suppose for $i\in\mathbb N$, $Q_i$ is a chain in $(A,\le)$ and for $i < j$ we have $Q_i\subseteq Q_j$, then $\bigcup Q_i=Q$ is a chain.

Proof: Given $a,b\in Q$ then for some $i,j$ we have $a\in Q_i$ and $b\in Q_j$. Since either $Q_i\subseteq Q_j$ or $Q_j\subseteq Q_i$ we have that $a,b\in Q_{\max\{i,j\}}$ and therefore $a\le b$ or $b\le a$. Thus, $Q$ is a chain.

By the same argument you can also show that if $a$ is the minimum of $Q_i$ and $b$ is the maximum of $Q_i$, for all $i\in\mathbb N$ then $a,b$ are also the minimum/maximum of $Q$.


Now if you have an infinite chain of strict inclusions then there is some $a_i\in Q_i\setminus\bigcup_{j<i}Q_j$ such that $a<a_i<b$ (simply because there is a strict inclusion between the $Q_i$'s).

The collection $\{a_i\mid i\in\mathbb N\}\subseteq Q=\bigcup Q_i$, and $a_i\neq a_j$ since if $j<i$ then $a_i\notin Q_j$, but $a_j\in Q_i$. This means that the chain $Q$ is infinite, and its minimum is $a$ and its maximum is $b$ - which contradicts the property of every chain strictly between $a$ and $b$ is finite.

share|improve this answer
    
Could you elaborate on the latter half? I don't understand that there exists an element of $Q_i$ strictly between $a$ and $b$, and that $a_i$ constitute a chain. –  Pteromys Dec 15 '11 at 15:01
    
@Pteromys: I hope it's clearer now. –  Asaf Karagila Dec 15 '11 at 15:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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