2
$\begingroup$

The question I have concerns a part in the proof of this lemma:

Prove: Let $X$ be a set and $F$ be a family of subsets of $X$ with the finite intersection property. Then there is a maximal family of subsets of $X$ that contain $F$ and has the finite intersection property.

Let $Z$ be the collection of all families of subsets of $X$ which contiain $F$ and have the finite intersection property, and define the $\le$ in the normal way for subsets, and let $Y$ be any linearly ordered subset of $Z$. We claim that $\bigcup_{y \in Y} y$ is an upper bound for $Y$. Clearly this contains $F$, so we have to show only that it has the finite intersection property. So let $S_1,S_2, ..., S_n \in \bigcup_{y \in Y} y$. Then each $S_i \in y_i$, for some $y_i \in Y$. As $Y$ is linearly ordered, one of the $y_i$ contains all the others. Thus $S_1, s_2, ..., S_n$ all belong to that $y_i$. As $y_i$ has the finite intersection property, $S_1 \cap S_2 \cap ... \cap S_n \neq \emptyset.$ Hence $\bigcup_{y \in Y} y$ has the finite intersection property and is, therefore, an upper bound in $X$ of $Y$. Thus by Zorn's Lemma, $Z$ has a maximal element.

My question is: How does proving that $\bigcup_{y \in Y} y$ has the finite intersection property prove that it is an upper bound?

$\endgroup$
2
$\begingroup$

The structure of the proof is as follows: we define a poset as follows:

The elements of the poset $Z$ are families $G$ of subsets of $X$, that contain $F$ (the fixed $F$ we start out with, and which has the FIP), so we have $F \subseteq G$ for all $G \in Z$, and such that $G$ has the FIP. Also, $Z$ is ordered by inclusion, i.e. $G_1 \le G_2$ iff $G_1 \subseteq G_2$. By the usual properties of inclusion this obeys the poset axioms, and $Z$ is non-empty because $F$ is in it.

The claim is: $Z$ has a maximal element, so a $G \in Z$ such that there does not exist a $G' \neq G, G' \in Z$ such that $G \le G'$. To do this we use Zorn's lemma: if a poset $Z$ obeys the condition that for every linearly ordered subset $Y$ of $Z$, there exists some $G \in Z$ such that, for all $H \in Y$ we have $H \le G$, then $Z$ has a maximal element.

So we need to check that if we take some linearly ordered subset $Y$ of $Z$, then it has an upper bound in $Z$. The claim in the proof is that for such $Y$ we can always take $G = \cup_{y \in Y} y$. This would be an upper bound for $Y$, because $Y \subseteq G$: every $y \in Y$ is a subset of the union $G$, which is the union of all $y \in Y$. Note the level of abstraction: $y$ is a family of subsets of $X$ (as all members of $Z$ are) and $Y$ is thus a collection/set of those. But we need to see $G$ is in $Z$ itself.

For that we check two conditions: $F \subseteq G$ (the same fixed $F$), but this is clear, as any $y$ in $Y$ (being a member of $G$) contains $F$ and so the union does too.

Next we have to show that $G$ has the FIP as well, knowing again that all member families of $Y$ do. So pick $S_1,\ldots,S_n$ all in $G = \cup_{y \in Y} y$. This means that there are $y_1,\ldots,y_n \in Y$ such that $S_i \in y_i$ for all $i=1,\ldots,n$. But for any two $y_i,y_j$ from $Y$ we know that either $y_i \le y_j$ or $y_j \le y_i$, by being linearly ordered, and in fact we know that a finite subset of a linearly ordered set has a maximum. So assume that $y_{i_0}$ is that maximum, so $y_1,\ldots,y_n \le y_{i_0}$, which just means that $y_1,\ldots,y_n \subseteq y_{i_0}$ (these are all families of sets, keep that in mind). This means that in fact the all $S_i$ all lie in $y_{i_0}$, and as the latter set, being a member of $Z$!, has the FIP, we know that $\cap_{i=1}^n S_i \neq \emptyset$, as required. So $G$ has the FIP.

Now we know that by definition, $G \in Z$ and we already saw that if it is, it is an upper bound. So Zorn's lemma can be applied, as $Y$ was arbitrary.

So the FIP is needed to show $G$ is even a contender for being an upper bound: it has to lie in $Z$ first (and $Z$ is not closed under unions in general, but it happens to be for linearly ordered subsets).

$\endgroup$
  • $\begingroup$ On the third paragraph from the bottom, do you mean "Next we have to show that $G$ has the FIP as well"? Because $F$ has the finite intersection property by definition. $\endgroup$ – Oliver G Jul 2 '16 at 17:09
  • $\begingroup$ @OliverG yes, that's what I mean, I'll edit. $\endgroup$ – Henno Brandsma Jul 2 '16 at 17:46
1
$\begingroup$

It isn't very well expressed: the sentence beginning "We claim" should say "... upper bound for $Y$ in $Z$". In more detail, the idea is that you want to use Zorn's lemma to prove the existence of a maximal member of $Z$ (with respect to the inclusion ordering). To do this you have to show that every linearly ordered subset $Y$ of $Z$ has an upper bound in $Z$. $\bigcup_{y\in Y}Y$ is clearly an upper bound for $Y$ with respect to our ordering. So to apply Zorn's lemma, you need to show that $\bigcup_{y\in Y}Y$ belongs to $Z$: i.e., that it has the finite intersection property.

Now you have given the full text of the proof, we can see how to correct it. The apparent implication that proving the finite interception property proves that $Y$ is an upper bound is not intended. Here are the relevant sentences corrected with explanations in square brackets:

We claim that $\bigcup_{y \in Y} y$ is an upper bound for $Y$ in $Z$. Clearly this union contains $Y$ [so it is an upper bound for $Y$] and it contains $F$ [so it satisfies one of the conditions for membership of $Z$, so [to prove the claim] we have to show only that the union has the finite intersection property [so that it satisfies both conditions for membership of $Z$ and hence is in $Z$].

...

Hence $\bigcup_{y \in Y} y$ has the finite intersection property and is, therefore, an upper bound $Y$ [we noted that immediately after stating the claim] in $Z$ [we've just proved it has the F.I.P and $Z$ comprises all sets with that property].

$\endgroup$
  • $\begingroup$ So "we claim ..." is just the fact that it is the upper bound and "we have only to show..." is the start of the proof for the maximal family with the intersection property? $\endgroup$ – Oliver G Jul 2 '16 at 14:28
  • $\begingroup$ I can't really comment without knowing the context of your quotation. The context should obviously say something about Zorn's lemma and given Zorn;s lemma the problem reduces to showing that unions of linearly ordered subsets of $Z$ have the finite intersection property. $\endgroup$ – Rob Arthan Jul 2 '16 at 14:46
  • $\begingroup$ Edited the question to include the entire proof. What's confusing me is more accurately the third and second to last line. I don't see how proving that it satisfies the F.I.P proves that it's an upper bound. $\endgroup$ – Oliver G Jul 2 '16 at 14:51
  • $\begingroup$ That interpretation of the statements is understandable but is not intended. See my revised answer. $\endgroup$ – Rob Arthan Jul 2 '16 at 15:00
  • $\begingroup$ $F$ is not a typo. We need all elements to contain $F$ by definition. $\endgroup$ – Henno Brandsma Jul 2 '16 at 15:34

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.