Alternative argument - set theory problem

220 Views Asked by At

I tried to solve the following problem:

Let $ \mathcal{F}$ be a nonempty family of sets with the following properties:

(a) If $ X \in \mathcal{F}$, then there are some $ Y \in \mathcal{F}$ and $ Z \in \mathcal{F}$ such that $ Y \cap Z =\emptyset$ and $ Y \cup Z=X$.

(b) If $ X \in \mathcal{F}$, and $ Y \cup Z =X , Y \cap Z=\emptyset$, then either $ Y \in \mathcal{F}$ or $ Z \in \mathcal{F}$.

Show that there is a decreasing sequence $ X_0 \supseteq X_1 \supseteq X_2 \supseteq ...$ of sets $ X_n \in \mathcal{F}$ such that $$\bigcap_{n=0}^{\infty} X_n= \emptyset.$$

(some old Miklos Schweitzer problem)

And I came up with the following proof

Proof: Suppose that for every decreasing sequence $(X_n)$ we have $\cap X_n \neq \emptyset$. Pick now an arbitrary decreasing sequence $(Y_n)$ and denote $Y= \cap Y_n$. We would like to prove that $Y \in \mathcal{F}$. Suppose that $Y \notin \mathcal{F}$. Then we construct the sequence $ A_n = Y_n\setminus Y $ and note that since $Y_n=A_n \cup Y$, by rule (b) either $Y$ or $A_n$ is in $\mathcal{F}$. Suppose that $A_n \in \mathcal{F}$ for infinitely many $n$. Then we reach a contradiction with the assumption made, since $\cap A_n=\cap (Y_n\setminus Y)=(\cap Y_n) \setminus Y=\emptyset$. Since this is false, we have $Y \in \mathcal{F}$.

Now we are done, because we have just proven that every chain in $\mathcal{F}$ ordered by $X \leq Y \Leftrightarrow X \supseteq Y$ has an upper bound, so by Zorn's lemma, $\mathcal{F}$ has maximal elements.

Pick now a maximal element $M$. If it is not the empty set, then by rule (a) it can be decomposed into two parts which are both in $\mathcal{F}$ and one is strictly greater than it (in the proposed ordering). Therefore $\emptyset$ is the maximal element of $\mathcal{F}$ and we are done since we can choose the sequence $X_n=\emptyset$.

Is it possible to come up with an ending argument which does not use the constant sequence $X_n=\emptyset$?


It looks like the argument is not valid at all, since I'm not allowed to use Zorn's lemma if I only have information on countable chains.

1

There are 1 best solutions below

2
On

Towards a contradiction assume for every descending sequence $\{X_n : n \in \omega \}$ in $\mathcal{F}$, $\bigcap_n X_n$ is non empty.

Claim: For every $X \in \mathcal{F}$, there are disjoint sets $Y, Z \in \mathcal{F}$ contained in $X$ such that $(\forall W)(Y \subseteq W \subseteq Y \bigcup Z \implies W \in \mathcal{F})$.

Proof of claim: Fix $X \in \mathcal{F}$. First obtain a disjoint collection $\{X_n : n \in \omega\}$ with $X_n \in \mathcal{F}$, $\displaystyle X' = \bigcup_{n \in \omega} X_n \in \mathcal{F}$ and $X' \subseteq X$. Next inductively try to construct a sequence $\{A_n : n \in \omega\} \subseteq \mathcal{F}$ such that

(1) $A_0 = X'$

(2) $A_{n+1} \subseteq A_n$

(3) $A_{n+1} \bigcap (\bigcup_{i < n+1} X_i) = \phi$

(4) $A_{n+1} \bigcap X_{i} \in \mathcal{F}$ for infinitely many $i$'s

Notice that the construction must stop at some finite stage otherwise $\{A_n : n \in \omega\}$ is a descending sequence in $\mathcal{F}$ with empty intersection. Suppose $A_{n+1}$ doesn't exist (and $A_n$ does). Let $m$ be larger than $n$ such that $A_n \bigcap X_m \in \mathcal{F}$. Put $Y = A_n \bigcap X_n$ and $Z = A_n \bigcap X_m$. Then $Z \in \mathcal{F}$. If possible, suppose $Y \subseteq W \subseteq Y \bigcup Z$ and $W \notin \mathcal{F}$. Then $A_{n+1} = A_n \backslash W \in \mathcal{F}$ satisfies clauses (2), (3) and (4) which is impossible. This finishes the proof of claim.

Now fix $X \in \mathcal{F}$. Let $Y_0, Z_0$ be like the $Y, Z$ of claim. Let $Y_1, Z_1$ be similar sets for $Z_0$ and so on. Then $X_n = \bigcup_{i \geq n} Y_i$ is a descending sequence in $\mathcal{F}$ with empty intersection - Contradiction.