Set theory question

[Steven G]

Hi,
I must be tired because I just can't see how to do this proof.

Let 0 be the empty set.

Let A /= 0 and f:A --> P(A) [powerset of A] be any function

Let B ={a in A | a is not in f(a)}

Show there is no b in A s/t f(b) = B



Here is what I do understand. You have a set A/=0 and P(A) is the set of all subsets of A. These two pieces I understand perfectly.

Now for B ={a in A | a is not in f(a)}. How do you get into B? You look at the function f and compute f(z) for every z in A. Now every time z is not an element in f(z) you put z in B. So I understand B.

I admit, I am at a loss seeing what to do next. I guess that I really am not getting what there is no b in A s/t f(b) = B means wrt the rest of the theorem.

Some friendly guidance will be most appreciated.

 

[pka]

Let 0 be the empty set.
Let A /= 0 and f:A --> P(A) [powerset of A] be any function
Let B ={a in A | a is not in f(a)}
Show there is no b in A s/t f(b) = B

\(\displaystyle A\ne\emptyset\text{ and }f:A\to\mathcal{P}(A)\)+++++++[ tex]A\ne\emptyset\text{ and }f:A\to\mathcal{P}(A)[/tex] without the space in [ t
As I understand the definition of \(\displaystyle B\) it is:
\(\displaystyle B=\{a\in A: a\notin f(a)\}\)+++++++[ tex][B=\{a\in A: a\notin f(a)\}[/tex]

You need to show that \(\displaystyle x\in A \Rightarrow f(x)\ne B\).

What happens if \(\displaystyle (\exists b\in A)[f(b)=B]~?\)

P.S.
Now either \(\displaystyle b\in B\) or \(\displaystyle b\notin B\) must be true. Take them one at a time.

1) If \(\displaystyle b \in B \), Because \(\displaystyle B\subset A\) that means \(\displaystyle b \in A \wedge \left( {b \notin f(b) = B} \right)\) that is a contradiction because it cannot be that \(\displaystyle b\in B~\&~b\notin B \)

2) Let's try \(\displaystyle b\notin B\). That means \(\displaystyle \left[ {b \notin A} \right] \vee \left[ {b \in f(b) = B} \right]\).
Again, that is a contradiction because it cannot be that \(\displaystyle b\in B~\&~b\notin B \)

Thus the proof by contradiction is complete.

 

[Steven G]

\(\displaystyle A\ne\emptyset\text{ and }f:A\to\mathcal{P}(A)\)+++++++[ tex]A\ne\emptyset\text{ and }f:A\to\mathcal{P}(A)[/tex] without the space in [ t
As I understand the definition of \(\displaystyle B\) it is:
\(\displaystyle B=\{a\in A: a\notin f(a)\}\)+++++++[ tex][B=\{a\in A: a\notin f(a)\}[/tex]

You need to show that \(\displaystyle x\in A \Rightarrow f(x)\ne B\).

What happens if \(\displaystyle (\exists b\in A)[f(b)=B]~?\)

P.S.
Now either \(\displaystyle b\in B\) or \(\displaystyle b\notin B\) must be true. Take them one at a time.

1) If \(\displaystyle b \in B \), Because \(\displaystyle B\subset A\) that means \(\displaystyle b \in A \wedge \left( {b \notin f(b) = B} \right)\) that is a contradiction because it cannot be that \(\displaystyle b\in B~\&~b\notin B \)

2) Let's try \(\displaystyle b\notin B\). That means \(\displaystyle \left[ {b \notin A} \right] \vee \left[ {b \in f(b) = B} \right]\).
Again, that is a contradiction because it cannot be that \(\displaystyle b\in B~\&~b\notin B \)

Thus the proof by contradiction is complete.

Thanks for your initial reply. I finally figured it out and was about to reply when I saw that you finished the proof. My proof is very similar to yours. Thanks for your help.

I do have a question regarding your proof. In 2 you state \(\displaystyle b\notin B\subset A\). Then \(\displaystyle b\notin A\). Is that enough for a contradiction?

My proof went as follows.

if \(\displaystyle a\in B\), then \(\displaystyle a\notin f(a)\). So \(\displaystyle f(a)\ne\ B\)

if \(\displaystyle a\notin B\), then \(\displaystyle a\in f(a)\). So \(\displaystyle f(a)\ne\ B\)

 

[pka]

I do have a question regarding your proof. In 2 you state \(\displaystyle \color{red}{b\notin B\subset A}\). Then \(\displaystyle b\notin A\). Is that enough for a contradiction?

My proof went as follows.
if \(\displaystyle a\in B\), then \(\displaystyle a\notin P(a)\). So \(\displaystyle P(a)\ne\ B\)
if \(\displaystyle a\notin B\), then \(\displaystyle a\in P(a)\). So \(\displaystyle P(a)\ne\ B\)

First of all I never wrote that. I did say that \(\displaystyle b\notin B\) means that \(\displaystyle \left[ {b \notin A} \right] \vee \left[ {b \in f(b) = B} \right]\) which follows from the negation of \(\displaystyle \{ b \in A:b \notin f(b)\} \) which is \(\displaystyle \left[ {b \notin A} \right] \vee \left[ {b \in f(b) = B} \right]\). But we began with \(\displaystyle \left[ {b \in A} \right]\) so it follows that \(\displaystyle \left[ {b \in f(b) = B} \right]\)

In yours I do not know what \(\displaystyle P(a)\) is? Did you mean \(\displaystyle a \notin f(a) \in P(A)~?\)

 

[Steven G]

First of all I never wrote that. I did say that \(\displaystyle b\notin B\) means that \(\displaystyle \left[ {b \notin A} \right] \vee \left[ {b \in f(b) = B} \right]\) which follows from the negation of \(\displaystyle \{ b \in A:b \notin f(b)\} \) which is \(\displaystyle \left[ {b \notin A} \right] \vee \left[ {b \in f(b) = B} \right]\). But we began with \(\displaystyle \left[ {b \in A} \right]\) so it follows that \(\displaystyle \left[ {b \in f(b) = B} \right]\)

In yours I do not know what \(\displaystyle P(a)\) is? Did you mean \(\displaystyle a \notin f(a) \in P(A)~?\)

Fair enough you said \(\displaystyle b\notin B\). But clearly \(\displaystyle B\subset A\). Combining these two statements we get \(\displaystyle b\notin A\).

I edited my post removing the two typos. Thanks for your professional help.

 

[pka]

\(\displaystyle b\notin B\). But clearly \(\displaystyle B\subset A\). Combining these two statements we get \(\displaystyle b\notin A\).

You have real problems understanding set theory. That is FALSE!
\(\displaystyle B\subset A\) means \(\displaystyle x \in B \Rightarrow \;x \in A\) or \(\displaystyle x \notin B \vee x \in A\).
The negation of that is \(\displaystyle x \in B \wedge x \notin A\).

Therefore, to say that \(\displaystyle B \subset A\;\& \;x \notin B\) simply means \(\displaystyle x \notin A \vee x \in \left( {A\backslash B} \right)\).
In this case we began by saying \(\displaystyle b\in A\) thus it must be \(\displaystyle b\in A\setminus B\) which means \(\displaystyle b\in f(b)=B\)

 

[HallsofIvy]

For example, A= {a, b, c, d, e, f}, B= {a, b, c}. Each of d, e, and f is not in B but is in A.

 

[Steven G]

You have real problems understanding set theory. That is FALSE!
\(\displaystyle B\subset A\) means \(\displaystyle x \in B \Rightarrow \;x \in A\) or \(\displaystyle x \notin B \vee x \in A\).
The negation of that is \(\displaystyle x \in B \wedge x \notin A\).

Therefore, to say that \(\displaystyle B \subset A\;\& \;x \notin B\) simply means \(\displaystyle x \notin A \vee x \in \left( {A\backslash B} \right)\).
In this case we began by saying \(\displaystyle b\in A\) thus it must be \(\displaystyle b\in A\setminus B\) which means \(\displaystyle b\in f(b)=B\)

OK, I'm an idiot. Of course what I wrote is not true. I knew that quite well but for some reason I wrote what I did. I apologize for bothering you with this nonsense.