I am working through Hrbacek and Jech's Introduction to Set Theory and am not yet feeling totally confident in my proof writing, so I figured I would post solutions on here to get feedback. Is this a valid proof in ZF?
Claim
For any set $A$ there is some $x \notin A$.
Proof
Suppose (toward contradiction) there is a set $A$ such that for all sets $x, x \in A$. Consider the property $P(x):x\notin x$. By the axiom of separation, there exists a set $B$ such that $x\in B$ iff $x \in A$ and $x \notin x$.
Now, either $B \in B$ or $B \notin B$.
Suppose $B \in B.$ Then $B\notin B.$
On the other hand, suppose $B \notin B$. But $B \in A$ also (since for all sets $x, x\in A$). It follows that $B \in B$.
What did we show? We showed that $B \in B$ iff $B \notin B$, a contradiction. So our hypothesis was false, and for all sets $A$ there exists a set $x:x\notin A$.
Questions
Is there a direct proof of this statement? Here are the axioms the book has introduced so far:
- Existence
- Extension
- Separation
- Pairing
- Union
- Powerset
Doing a bit of research, I noticed that there are arguments that use other theorems. For example, we know that for all sets $A,|P(A)|$ is strictly larger than $|A|$. So there must be some $x\in P(A): x \notin A$. But I have not proved this theorem so did not want to use it. I also noticed there are some who claim one can invoke the foundation axiom and make an argument using that. That path seems less clear then me - in any case; I am interested in other proofs of the statement.
Plus, the argument is essentially the same as the argument I made to prove the claim that the set of all sets does not exist; the original statement is just worded slightly differently. So I'm thinking I might be on the right track and am noticing what the authors intended for me to notice ¯_(ツ)_/¯