Proof involving quantifiers

[vrble]

1. Suppose that A is a subset of the power set of A. Prove that the power set of A is a subset of the power set of the power set of A.

Note: I'm going to use P(A) to mean the power set of A and P(P(A)) to mean the power set of the power set of A.



2. None



3. Let X be an arbitrary set and y an arbitrary element of that set. Suppose that X is an element of P(A) and A is a subset of P(A). It then follows by the definition of power sets that X is a subset of A and thus y is an element of A as well as P(A). We are also able to conclude, because y is an element of X and is arbitrary, that X is a subset of P(A) as well. This result shows that X is an element of P(A) as well as the P(P(A)). Therefore, if A is a subset of P(A), then P(A) is a subset of P(P(A)).

I apologize if my wording is unclear. I'm not entirely sure of the correctness of all of the aspects of my proof, and the line "We are also able to conclude, because y is an element of X and is arbitrary, that X is a subset of P(A) as well. " bothers me in particular. Am I able to make this kind of deduction?

 

[micromass]

The proof is entirely correct!

 

[verty]

Does this work if A is the empty set? I think perhaps the wording needs to change slightly.

 

[SammyS]

Does this work if A is the empty set? I think perhaps the wording needs to change slightly.

Are you doubting whether the assertion you proved is true for A = {}, or are you questioning whether your proof covers the case of A = {} ?

 

[verty]

I (not the original poster) was doubting myself because micromass said it was entirely correct but I think he missed the corner case of A being the empty set. In that case, there is no y, so y is undefined. So the statement "y is an element of A" is meaningless and surely anything deduced from that is meaningless.

 

[vrble]

I (not the original poster) was doubting myself because micromass said it was entirely correct but I think he missed the corner case of A being the empty set. In that case, there is no y, so y is undefined. So the statement "y is an element of A" is meaningless and surely anything deduced from that is meaningless.

Would adding "Let A be a non-empty set" fix this problem?

 

[xiavatar]

It is unnecessary to indicate that A is a non-empty set. A more appropriate wording would be to relabel $P(A)=B$ and $P(P(A))=P(B)$ from which it automatically follows that B is nonempty since the power set of any set contains the null set.

 

[vrble]

It is unnecessary to indicate that A is a non-empty set. A more appropriate wording would be to relabel $P(A)=B$ and $P(P(A))=P(B)$ from which it automatically follows that B is nonempty since the power set of any set contains the null set.

I don't believe that was the issue that verty was addressing.The problem is that I assumed there was an arbitrary element y that is an element of the arbitrary set X. In the case where A = ∅, A is a subset of P(A), and X is an element of P(A), it follows that X is indeed a subset of A but this will only happen when X = ∅ as well. So there can be no "y" in that instance.

 

[micromass]

Would adding "Let A be a non-empty set" fix this problem?

No, because the theorem also holds for $A$ the empty set.

Personally, I still think your proof is correct. You took an arbitrary element of $y$. If $A$ is empty, then such $y$ does not exist, so whatever you wrote about $y$ holds vacuously.

I do see verty's point though. But I think it can be fixed with a small modification. Instead of saying "Take $y$ in $X$ arbitrary", you might say "If $y$ is an arbitrary element of $X$". That way, you make no assertion about the existence of $y$, but only about if it exists.

 

[vrble]

No, because the theorem also holds for $A$ the empty set.

Personally, I still think your proof is correct. You took an arbitrary element of $y$. If $A$ is empty, then such $y$ does not exist, so whatever you wrote about $y$ holds vacuously.

I do see verty's point though. But I think it can be fixed with a small modification. Instead of saying "Take $y$ in $X$ arbitrary", you might say "If $y$ is an arbitrary element of $X$". That way, you make no assertion about the existence of $y$, but only about if it exists.

Ah, I see. But what exactly is meant by, "whatever you wrote about $y$ holds vacuously."?

 

[micromass]

A vacuous statement is something like "All elements of the empty set are pink unicorns". This is true because there are no elements in the empty set to begin with!

 

[verty]

The change I was thinking of was to change "y is an element of A" to "any such y is an element of A". But it seems that one could always do this so it is a very formulaic change. So if we pretend those words are present (as a convention), the proof as it is is fine.

 

[HallsofIvy]

Rather than saying "let y be an element of A", say "if y is an element of A". The point is that a proof starting "let y be an element of A" fails if A is empty but "If y is an element of A" leads immediately to the "vacuously true" situation micromass refer to: the statement "if X then Y" is true whenever X is false, whether Y is true or false.

 

[xiavatar]

@vrble That was the issue verty was addressing. The problem with your original expression was that you were using an argument about $A$ and its power set $P(A)$ to deduce that $P(A)\in$ $P(P(A))$. But to do that you needed to assume that A was non empty. If you use my relabeling you don't have to make this unnecessary detour. You can directly conclude that $P(A)\in$ $P(P(A))$

 

[verty]

@vrble That was the issue verty was addressing. The problem with your original expression was that you were using an argument about $A$ and its power set $P(A)$ to deduce that $P(A)\in$ $P(P(A))$. But to do that you needed to assume that A was non empty. If you use my relabeling you don't have to make this unnecessary detour. You can directly conclude that $P(A)\in$ $P(P(A))$

I think xiavatar is saying that there is a shorter proof, but I think we should leave this because if vrble wants to find another proof, that is another matter.

 

[vrble]

@vrble That was the issue verty was addressing. The problem with your original expression was that you were using an argument about $A$ and its power set $P(A)$ to deduce that $P(A)\in$ $P(P(A))$. But to do that you needed to assume that A was non empty. If you use my relabeling you don't have to make this unnecessary detour. You can directly conclude that $P(A)\in$ $P(P(A))$

Why would I need to assume A was non-empty? If A is empty then it immediately follows that it is a subset of P(A) and that P(A) is a subset of P(P(A)). I thought that it was implicit that P(A) will never be empty despite the contents of A.

 

[xiavatar]

@vrble Yes, that fact about power sets is true, but your earlier statement "Let X be an arbitrary set and y an arbitrary element of that set" is fallacious for empty sets since you clearly can't choose an element from an empty set.

 

[vrble]

@vrble Yes, that fact about power sets is true, but your earlier statement "Let X be an arbitrary set and y an arbitrary element of that set" is fallacious for empty sets since you clearly can't choose an element from an empty set.

I'm aware to that now thanks to the wonderful members of this board, but I'm still not sure how your notation would allow me to avoid assuming that A is non-empty. Micromass's suggested rewording ""If y is an arbitrary element of X" seems to fix the problem.

 

[xiavatar]

Think about the definition of the power set of a set, and you will see that $P(A)$ is always nonempty.

 

[vrble]

Think about the definition of the power set of a set, and you will see that $P(A)$ is always nonempty.

I know that. How is that relevant to the issue at hand? Sorry if I sound stupid.

 

[xiavatar]

Well you know that if $A$ is a set then $A\in P(A)$. What I am saying is that you can avoid the convoluted argument you gave, so that if you let $B=P(A)$, then $B\in P(B)$ from which it follows that $P(A)\in P(P(A))$.

 

[vrble]

Well you know that if $A$ is a set then $A\in P(A)$. What I am saying is that you can avoid the convoluted argument you gave, so that if you let $B=P(A)$, then $B\in P(B)$ from which it follows that $P(A)\in P(P(A))$.

Ahh, I see now. Thank you.

 

[SammyS]

Well you know that if $A$ is a set then $A\in P(A)$. What I am saying is that you can avoid the convoluted argument you gave, so that if you let $B=P(A)$, then $B\in P(B)$ from which it follows that $P(A)\in P(P(A))$.

Yes, $A\in P(A) \ .\$ But, what does it mean for $A\subseteq P(A) \ ?\$

That's the premise here and that's a whole different can of worms.

 

[xiavatar]

Sorry I didn't notice that was the premise in the question.

 

[xiavatar]

In that case we could do the following. Note that this is a proof that avoids some of the ambiguity in the wording of the OP's post. Suppose $X\in P(A)$. It follows then that $X\subseteq A$. But since $A\subseteq P(A)$ it follows that $X\subseteq P(A)$. Thus $X\in P(P(A))$. It therefore follows that $P(A)\subseteq P(P(A))$.

OP's proof is basically the same thing, except it has the unnecessary intermediary step of choosing an element y from the element X from the power set.