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

1.1k Views Asked by At

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 ?

3

There are 3 best solutions below

4
On

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

5
On

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

3
On

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.