# A basic doubt on axiom of foundation of Zermelo-Fraenkel set theory

I have read in a book that the "axiom of foundation prevents anomalies such as a set being an element of itself".

Now, axiom of foundation says that there exist an element in every set which is disjoint with the set.

Now if $S$ be a set then according to the above axiom $S=\{S\}$ can't be a set. But, $S=\{\{1\},S\}$ satisfies axiom of foundation and contains $S$.

So, is the statement mentioned in the book correct ?

-

Consider $A=S\setminus\{1\}=\{S\}$, which exists by the various comprehension schemata. Then $S\cap A=\{S\}$.

Therefore $A$ is a counterexample to the axiom of foundations.

Understanding the axiom of foundation as stating "there are no anomalies such as ..." is a very informal. It is as informal as saying that the axiom of infinity states "there exists an infinite set". This is an informal notion which captures the intuition behinds the axiom, but it doesn't really tells us what is the content of the axiom.

The axiom of foundation states that $\in$ is a well-founded relation. From this assertion it follows that anomalies like $x\in y\in z\in w\in u\in x$ cannot occur. But in fact it tells us more. It tells us that we can use $\in$ for recursive definitions, what is commonly known as Epsilon induction/recursion.

So while saying that the axiom of foundation prevents anomalies such as X is not incorrect, it is not well-defined either. What is an anomaly? Why is X is an anomaly? These notions are informal, and so is the term "such as". It is better to state the axiom in its correct form "$\in$ is a well-founded relation".

-
My question was whether the statement "axiom of foundation prevents anomalies such as a set being an element of itself" is correct ? I think it is not. I have shown such an example whether both axiom of foundation is true and S contains itself. Am I correct ? –  RIchard Williams May 10 '13 at 11:19
If both answers are different than you expect, perhaps it is best to edit your question rather than comment. In any case, I'll edit my answer now to address this comment. –  Asaf Karagila May 10 '13 at 11:21
@prasenjit For me, the most intuitive definition of well-founded is that there's no countable descending chain. Thus, the axiom of foundation guarantees that if you start with a set, proceed to an element of that set, then to an element of that element, and so on, you will reach the empty set (and thus stop!) in finitely many steps. I always viewed this as a very weak form of the axium of constructability. The latter tells you how do construct sets, while the axiom of foundation tells you how to deconstruct them, in a way. –  fgp May 10 '13 at 11:36
@fgp: While true, it is important to point out that the principle of dependent choice is required for this sort of characterization to hold in full. –  Asaf Karagila May 11 '13 at 2:48

If $S\in S$ then $\{S\}$ will violate the axiom of foundation.

-
My question was whether the statement "axiom of foundation prevents anomalies such as a set being an element of itself" is correct ? I think it is not. I have shown such an example whether both axiom of foundation is true and S contains itself. Am I correct ? –  RIchard Williams May 10 '13 at 11:20
@prasenjit No, you're wrong. True, your $S$ doesn't directly violate the axiom of foundation, but it allows other sets to be constructed (both answers contain an example) which do. In other words, your example violates e.g. the combination of the axiom of foundation and the axiom about singleton sets (i.e., for all $x$ there's a set $\{x\}$). Given that you need the latter to even define your $A$ (you're using $\{1\}$), it makes little sense to ask whether $A$ can exist in a theory containing only the axiom of foundation. –  fgp May 10 '13 at 11:43
The axiom of foundation prevents certain things in conjunction with the other axioms. There is little interest in systems that satisfy the axiom of foundation but not the other axioms of ZF. Similarly, air bags are intended prevent certain injuries in car crashes, but only when the car also has seat belts (and seats...). –  Carl Mummert May 10 '13 at 11:49
@CarlMummert Not to mention the need for a car … –  Harald Hanche-Olsen May 10 '13 at 12:24
To amplify Carl Mummert's comment: The axiom of foundation, together with the fact (usually proved as a consequence of the axiom of pairing) that the singletons $\{x\}$ exist for all sets $x$, suffices to prove that no set is a member f itself (as in Harald's answer). So, although one usually assumes the other axioms of ZF in this connection, one actually needs far less, just a consequence of pairing. –  Andreas Blass May 11 '13 at 20:04

You seem to think that you can find a set $S$ such that $S=\{\{1\},S\}$.

But can you really? Go on, write down this set explicitly. Truth is...you won't be able to.

Put it in another way: assume ab absurdo, that you can find such a set $S$. So $S \in S$. Then the set $\{S\}$ violates the axiom of regularity since both $\{S\}$ and $S$ contain $S$, so $\{S\} \cap S = \{S\}$ and thus non empty.

-
Lots of sets in ZF can't be written down "explicitly", no matter how you interpret that word. Your comment about $\{S\}$ is good, if similar to other answers. –  Mark S. May 21 '13 at 1:38
Try and writing $\omega$ explicitly. Try writing a well-ordering of $2^\omega$ explicitly. Try writing a non-principal ultrafilter on $\omega$ explicitly. Try writing $\omega_1$ explicitly... –  Asaf Karagila May 21 '13 at 1:58
MarkS. and @AsafKaragila I know, I know, but I was under the impression that the OP thought it was relatively easy to come up with such a set S, so I encouraged him to actually do it. –  magma May 21 '13 at 23:01