1

If $U$ is infinite, show that the Boolean algebra of subsets of $U$ that are finite or cofinite (i.e. their complement is finite) is not complete. A Boolean algebra $\mathcal{B}:=(B,\leq,\lor,\land,^c,0,1)$ is said to be complete if every non-empty subset of $B$ has a greatest lower bound (g.l.b).

Let $U'=\{X\subseteq U: X\text{ is finite, or}X^c=U\backslash X\text{ is finite}\}$. I think the Boolean algebra of concern here is $\mathcal{B}:= (U',\subseteq, \cup,\cap,^c,\phi, U)$, right?

From what I understand, the g.l.b operation here is just $\bigcap$, i.e. if $\phi\neq U''\subseteq U'$, then g.l.b($U''$) = $\bigcap_{z\in U''}z$, is that correct?

If that is the case, then the Boolean algebra looks complete* to me - which is contrary to what is required to be proved. Where am I going wrong?

*Looks complete because two sets will always have some intersection, empty or not!

stoic-santiago
  • 13,705

1 Answers1

2

It is closed under finite intersections, but completeness requires closure under arbitrary intersections. Let $X_i = U \setminus \{i\}$, where $i$ ranges over some infinite subset $I$ of $U$ such that $U \setminus I$ is also infinite (e.g., if $U = \Bbb{R}$, you could take $I = \Bbb{Z}$). Then $\bigcap_{i \in I} X_i = U \setminus I$ which is not in $U'$.

More formally, the family $\{X_i \mid i \in I\}$ has no g.l.b. because any finite (resp. cofinite) set $A$ such that $A \subseteq X_i$ for all $i$ must be a proper subset of $\bigcap_{i \in I} X_i = U \setminus I$ and hence can be extended to give a finite (resp. cofinite) set $B \supset A$ such that $B \subseteq X_i$ for all $i$.

Rob Arthan
  • 48,577
  • Great, this proof works! I'm wondering what motivated you to think in this direction? I did not think of working with $I$ and $U\backslash I$ where both are infinite. – stoic-santiago Nov 01 '20 at 13:34
  • 1
    I thought first about the complement: it is fairly clear the union of an infinite family of finite sets need not be finite or cofinite. – Rob Arthan Nov 01 '20 at 13:38
  • Also, one clarification - what we're really saying is that the g.l.b of $U''$ does exist, but is not contained in $U'$, of which $U''$ is a subset. Hence $U''$ does not have a greatest lower bound. Is that right? Here $U''$ contains the $X_i$'s that you have defined as $U\backslash {i}$, all of which are certainly in $U'$ since they are cofinite. – stoic-santiago Nov 01 '20 at 13:39
  • Yes. What you are calling $U''$ is $ {X_i \mid i \in I} \subseteq U'$. – Rob Arthan Nov 01 '20 at 13:50
  • Cool. What about the part where I wrote about g.l.b (in the previous comment)? It seems a little weird that we're finding a g.l.b and then saying it doesn't exist because it's not in $U'$. Is that the right (rigorous) way of doing things? – stoic-santiago Nov 01 '20 at 13:53
  • I've added a more formal description of the argument. – Rob Arthan Nov 01 '20 at 14:04
  • "Any cofinite set $A$ such that $A \subseteq X_i$ for all $i$ must be a proper subset of $\bigcap_{i \in I} X_i = U \setminus I$ and hence can be extended to give a cofinite set $B \supset A$ such that $B \subseteq X_i$ for all $i$." - I think I don't understand this well after all, could you please elaborate a little? – stoic-santiago Nov 05 '20 at 04:37
  • Adding one element to a finite set gives you a finite set and similarly for a cofinite set. – Rob Arthan Nov 05 '20 at 11:31