Proof involving quantifiers

1. May 2, 2014

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?

2. May 2, 2014

micromass

The proof is entirely correct!

3. May 4, 2014

verty

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

4. May 4, 2014

SammyS

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

5. May 5, 2014

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.

6. May 5, 2014

vrble

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

7. May 5, 2014

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.

8. May 5, 2014

vrble

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.

9. May 5, 2014

micromass

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.

Last edited: May 5, 2014
10. May 5, 2014

vrble

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

11. May 5, 2014

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!

12. May 5, 2014

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.

Last edited: May 5, 2014
13. May 5, 2014

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.

14. May 5, 2014

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

15. May 5, 2014

verty

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.

16. May 5, 2014

vrble

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.

17. May 5, 2014

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.

18. May 5, 2014

vrble

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.

19. May 5, 2014

xiavatar

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

20. May 5, 2014

vrble

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