Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question
1  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
    
Thanks, It is already clear :). –  Jose Antonio Aug 1 '13 at 21:32

(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$.

share|improve this answer
    
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)$. –  Stavros 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.