# 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.