Union of a chain of consistent subsets is consistent.

932 Views Asked by At

In a proof of Gödel's completeness theorem via Lindenbaum's Lemma I have seen it is necesssary to prove that if we have a chain of consistent sets, ordered by the $\subseteq$ relation, the union over those sets is also consistent.

However I can't seem to find a proof of this anywhere, although the result seems quite obvious.

Any ideas?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $\Delta_i (i \in \omega)$ be each set and let $\Delta$ stand for their union (I'm assuming here, for simplicity, that the chain is enumerable). First, you'll need a lemma saying that, if $\Gamma$ is a finite subset of $\Delta$, then there's an $i$ such that $\Gamma \subseteq \Delta_i$. Using this lemma, you can prove the result by contradiction: suppose $\Delta$ is not consistent. Then there's a proof of a contradiction from $\Delta$. Since proofs are finitary objects, only finitely many formulas are needed in this proof. Thus, there's a finite $\Gamma \subseteq \Delta$ such that $\Gamma$ is inconsistent. But, by the lemma, $\Gamma \subseteq \Delta_i$ for some $i$, contradicting the hypothesis that each $\Delta_i$ was consistent.

You can also prove this directly using Zorn's Lemma.