# Some questions about the Jech's book (Generalized De Morgan's law and distributive law )

I finished the first chapter of the book Introduction to Set Theory by Jech (I started to love). And I have questions of some exercises where I'm not totally sure if my attempt was complete or even correct. The two last are where I have more doubts.

Here we go:

(A) Generalized distributive law:

Let $S \not= \emptyset$ and $A$ be a set. Set, $\;T_{\,1}:= \left\{\,y\in \wp (A): \exists x\in S\, (\, y = A\cap x \,)\, \right\}$ and prove that: $\, A\cap \bigcup S =\bigcup T_{\,1}.$

Proof:

($\,\Rightarrow\,$) If $\,z \in A\cap \bigcup S$, $z\in A$ and $\,z\in \bigcup S$. For $\,z\in \bigcup S,\,$ that means $z \in x_{0}$ for some $\, x_{0}\in S.\,$ Then, $\,z\in A$ and $z \in x_{0}$, i.e., $\,z\in A\cap x_0\,$ (where $\,x_0 \in S\,$).

On the other hand, for $z$ be in the union of $T_{\,1}$, $\,z\in \bigcup T_{\,1}$, it is a sufficient condition that $z\in y_{0}$ for some $\,y_0 \in T_{\,1}.\,$ We define $y_{0} = A \cap x_{0}$. It follows immediately that $y_{0} \in T_{\,1}$ $($as $\,y_{0} \in \wp(A)$ and $\,x_0 \in S\,)$. So as $\,z\in A\cap x_0\,$ and we defined $\,y_{0} = A \cap x_{0}$, then $\,z\in y_{0}$ for some $\,y_0 \in T_{\,1}$, as desired. That is, $\, A\cap \bigcup S \subseteq \, \bigcup T_{\,1}$.

($\,\Leftarrow\,$) If $z\in \bigcup T_{\,1},\, z\in y_{0}$ for some $y_{0} \in T_{\,1}.\,$ Then, by the definition of $T_{\,1},\,\,y_{0} = A\cap x_{0}\,$ for some $x_{0} \in S.\;$ It follows that, if $z\in y_{0}$, then $z\in x_{0}$ ( this is because $\,y_{0} \subseteq x_{0}\,).\,$ And as there a $x_{0} \in S\,$ for which $\,z\in x_{0},$ by the union axiom we can conclude that $\,z\in \bigcup S$. Hence, $z \in A$ and $\,z\in \bigcup S$, $\,z \in A\cap \bigcup S.\,$ That is, $\bigcup T_{\,1} \subseteq\, A\cap \bigcup S.$ $\;\Box$

(B) Generalized De Morgan's laws:

Set, $\;T_{\,2}:= \left\{\,y\in \wp (A): \exists x\in S\, (\, y = A - x \,)\, \right\}\,$ and prove that: ($\,i\,$) $A - \bigcup S = \bigcap T_{2}\,$ and ($\,ii\,$) $\,A - \bigcap S = \bigcup T_{2}.$

Proof:

($\,i\,$)

($\,\Rightarrow\,$) If $z \in A - \bigcup S,\, z\in A\,$ and $z\notin \bigcup S$ ( which means that, for each $x \in S,\, z \notin x$ ). For $z$ be a member of the right-hand side, $z \in \bigcap T_{2},\,$ it is necessary that: for every $y\in T_{2}\,$ ( which assume is nonempty ) $z \in y: = A-x.\,$ Then, $z \in A$ and $z \notin x$ as in our assumption has that properties, it follows that $z \in \bigcap T_{2},\,$ i.e., $A - \bigcup S \subseteq \bigcap T_{2}.$

($\,\Leftarrow\,$) If $z \in \bigcap T_{2},\,$ where assume that $T_{2}$ is nonempty. So, for each $y\in T_{2},\,z \in y: = A-x\,$. Therefore, $z \in A$ and $z\notin x\,$ and by definition of the set $T_{2},\, x\in S$; which holds for each $y \in T_{2}.$ For all $y, \,$ we have that $x\in S\,$ and $z \notin x,\,$ $z\notin \bigcup S\,$*??* (* **

How do we know that $S$ cannot have some element out of the elements that we use by the definition of the set $T_{2}$ which could be in? I don't know maybe I misunderstood this part

*)

Hence, $z\in A$ and $z\notin \bigcup S,\,$ $z \in A - \bigcup S\,$, i.e, $\bigcap T_{2} \subseteq A- \bigcup S.$

$(\, ii \,)$

$(\, \Rightarrow \,)$ If $z\in A - \bigcap S,\, z\in A\,$ and $z \notin \bigcap S.\,$ For $z \notin \bigcap S\,$, means that there exist some $x\in S$ for which $z\notin x.$ Then, $z\in A- x_{0}\,$ for some $x_{0} \in S.\,$ We set, $\,y_{0}:= A- x_{0}.\,$ So, $\,y_{0} \in T_{2}\,$ because $\,y_{0} \in \wp(A)$ and $\, x_{0}\in S.\,$ As $\, y_{0} \in T_{2}\,$ and $\, z\in y_0,\,$ it follows that $z \in \bigcup T_{2},\,$ i.e., $A-\bigcap S \subseteq \,\bigcup T_{2}.\,$

($\,\Leftarrow\,$) if $\,z \in \bigcup T_{2}\,$, then there exist a $\,y_{0} \in T_{2}\,$ for which $\,z\in y_{0}: = A-x_{0}\,$ ( for some $\,x_{0} \in S\,).\,$ Then $z \in A\,$ and for some $\,x_{0} \in S,\, z\notin x_{0}.\,$ Therefore, $z \in A\,$ and $\,z\notin \bigcap S,\,$ $z\in A - \bigcap S,\,$ i.e., $\, \,\bigcup T_{2} \subseteq\, A-\bigcap S .\,$

Claim 1: The set $T_{2}$ is non empty

We'll show that the set $T_{2}$ is empty iff the set $S$ is empty.

Proof:

Suppose $S = \emptyset$, we need to show that $T_{2}$ is empty. Assume for the sake of the contradiction that $y$ is in $T_{2},$ $\,y\in T_{2} \leftrightarrow y = A-x$ for some $x\in S,\,$ but since $x\notin S:=\emptyset$ we have a contradiction, it follows that $y$ cannot be in $T_{2},\,$ i.e., $y \notin T_{2}.\,$ Therefore $T_{2} = \emptyset,\,$ as desired.

On the other hand, if we assume that $\,T_{2} = \emptyset,\,$ we need to seek if this assumption implies the emptiness of $S.\,$ By contradiction, suppose $S \not= \emptyset,\,$ then $x\in S,\,$ and the set $A-x \in T_{2},\,$ which is a contradiction, because is empty by hypothesis. Therefore, $S = \emptyset.\,$

Then, if we assume that $S \not= \emptyset$ it follows that $T_{2} \not= \emptyset,\,$ as desired. $\;\Box$

**

I have problems to understand what's going on in that parts where I put the question mark in boldface.... I don't know maybe I'm tired. I need a coffee.

As usual, thanks in advance :)

• Is it possible that you first write the question on your own computer, and only when you feel it's complete you would post it? – Asaf Karagila Aug 1 '13 at 16:29
• Yes, sorry. It's just that I like fix my errors when somebody give me a hint... – Jose Antonio Aug 1 '13 at 16:34

In more everyday notation, $T_2=\{A\setminus x:x\in S\}$, so $T_2=\varnothing$ iff $S=\varnothing$. If $S=\varnothing$, then $\bigcup S=\varnothing$, so $A\setminus\bigcup S=A$. Now $\bigcap T_2=\bigcap\{y\in\wp(A):\exists x\in S(y=A\setminus x)\}$; it’s an intersection of subsets of $A$, so it must be a subset of $A$. What elements of $A$ are not in it? Let $a\in A$ be arbitrary; $a\notin\bigcap T_2$ iff there is a $y\in T_2$ such that $a\notin y$. But $T_2=\varnothing$, so there is no such $y$, and therefore it’s not the case that $a\notin\bigcap T_2$, i.e., $a\in\bigcap T_2$. And $a$ was arbitrary, so $\bigcap T_2=A$ in this case, just as we wanted. (If you’re familiar with the expression vacuously true, you can say that for each $a\in A$ it’s vacuously true that $a\in\bigcap T_2$.)

Now I’ll go back to the point in the proof of $(i,\Leftarrow)$ where you had trouble. You’ve assumed that $z\in\bigcap T_2$, and you want to show that $z\in A\setminus\bigcup S$. Let $x\in S$ be arbitrary. Then $A\setminus x\in T_2$, so $z\in A\setminus x$, and in particular $z\notin x$. Thus, for each $x\in S$ we have $z\notin x$, so $z\notin\bigcup S$. And $z\in\bigcap T_2\subseteq A$, so certainly $z\in A$, and it follows that $z\in A\setminus\bigcup S$, as desired.

• Only a question, if $T_{2} = \emptyset\,$ happens, the intersection $\bigcap T_{2}$ is not "ill-defined" because would have to be the universal set (the set of all the sets), doesn't it? Thanks, I need to read carefully the second part. – Jose Antonio Aug 1 '13 at 15:33
• @Jose: You can get around that by noting that since you’re intersecting subsets of $A$, the intersection should itself be a subset of $A$: $\bigcap T_2=\{a\in A:\forall y\in T_2(a\in y)\}$. – Brian M. Scott Aug 1 '13 at 20:08
• I really sorry if I'm abuse of your gentleness, but could you explain that a little bit more, please? Let me explain, I can see that the intersection is indeed a subset of $A\,$ but I have troubles to see where there are problems with the intersection of a empty set; when is vacuously true for each set and give us the universe set. I think the problem is only when we cannot fixed a set where applies replacement schema. – Jose Antonio Aug 1 '13 at 20:40
• @Jose: It’s true that if we have no context, $\bigcap\varnothing$ causes the problem that you mention. I’m saying that here we have a context: we know that we should consider $\bigcap T_2$ to be a subset of $A$, so in this particular setting we can define it as I did in my previous comment, making it equal to $A$. On re-reading the problem, however, I suspect that you are intended to assume that $S\ne\varnothing$ in (B) as well as in (A), so that the issue does not arise. – Brian M. Scott Aug 1 '13 at 21:20
• @Jose: You’re welcome. – Brian M. Scott Aug 1 '13 at 21:34

(A)
Proof. ($\rightarrow$) Suppose $x \in A \cap \bigcup S$. Then $x \in A$ and $x \in \bigcup S$. Since $x \in \bigcup S$, we can choose some $B \in S$ such that $x \in B$. Since $x \in A$ and $x \in B$, $x \in A \cap B$. We have shown that $B \in S$ and $x \in A \cap B$, so since $A \cap B \in \mathcal P \left({A}\right)$, we can conclude that $x \in \bigcup T_1$.
($\leftarrow$) Suppose $x \in \bigcup T_1$. Then we can choose some $B \in T_1$ such that $x \in B$. Since $B \in T_1$, $B \in \mathcal P \left({A}\right)$ and $B = A \cap X$ for some $X \in S$. But then since $x \in B$ and $B = A \cap X$, $x \in A \cap X$, so $x \in A$ and $x \in X$. Since $X \in S$ and $x \in X$, it follows that $x \in \bigcup S$. We have shown that $x \in A$ and $x \in \bigcup S$, so $x \in A \cap \bigcup S$.

(B)
i) Proof. ($\rightarrow$) Suppose $x \in A \setminus \bigcup S$. Then $x \in A$ and $x \notin \bigcup S$. Let $B \in T_2$ be arbitrary. Then $B \in \mathcal P \left({A}\right)$ and $B = A \setminus X$ for some $X \in S$. Since $x \notin \bigcup S$ and $X \in S$, $x \notin X$. Since $x \in A$ and $x \notin X$, $x \in A\setminus X$, so $x \in B$. But then since $B \in T_2$ was arbitrary, $x \in \bigcap T_2$.
($\leftarrow$) Suppose $x \in \bigcap T_2$. Let $B \in S$ be arbitrary. Clearly $A \setminus B \in \mathcal P \left({A}\right)$, so since $x \in \bigcap T_2$ and $B \in S$, it follows that $x \in A \setminus B$. This means that $x \in A$ and $x \notin B$. Since $B \in S$ was arbitrary, $x \notin \bigcup S$. Since $x \in A$ and $x \notin \bigcup S$, we can conclude that $x \in A \setminus \bigcup S$.

ii) Proof. ($\rightarrow$) Suppose $x \in A \setminus \bigcap S$. Then $x \in A$ and $x \notin \bigcap S$. Since $x \notin \bigcap S$, we can choose some set $B \in S$ such that $x \notin B$. Since $x \in A$ and $x \notin B$, $x \in A \setminus B$. Clearly $A \setminus B \in \mathcal P \left({A}\right)$, so since $B \in S$ and $x \in A \setminus B$, it follows that $x \in \bigcup T_2$.
($\leftarrow$) Suppose $x \in \bigcup T_2$. Then we can choose some set $B \in T_2$ such that $x \in B$. Since $B \in T_2$, it follows that $B \in \mathcal P \left({A}\right)$ and $B = A \setminus X$ for some $X \in S$. But then since $x \in B$ and $B = A \setminus X$, $x \in A \setminus X$, so $x \in A$ and $x \notin X$. Since $X \in S$ and $x \notin X$, $x \notin \bigcap S$. We have shown that $x \in A$ and $x \notin \bigcap S$, so $x \in A \setminus \bigcap S$.

• Thanks, it is very helpful. :) – Jose Antonio Aug 1 '13 at 20:40
• You are welcome. Bear in mind that you might also use a different set notation: $A \cap (\bigcup S) = \bigcup_{X \in S}(A \cap X)$, $A \setminus \bigcup S = \bigcap_{X \in S}(A \setminus X)$, and $A \setminus \bigcap S = \bigcup_{X \in S}(A \setminus X)$. – user21530 Aug 2 '13 at 19:28
• Indeed is more common the notation that you typed. But, to be honest I prefer to use the sets $T_{i},\, i \in \left\{\,1,2\, \right\}$. It is clearer at least for me. Thanks again :) – Jose Antonio Aug 2 '13 at 20:14