Axiom of Schema Foundation

[rebeka]

$$\exists x \phi(x) \implies \exists x ( \phi(x) \land (\forall y \in x) \lnot \phi(y)), where \; y \; is \; not \; free \; in \; \phi(x)$$

I understand what Russels Paradox is saying and what the difference is between a subset and a member but I'm having trouble with this definition of Foundation. I guess what is causing me troubles is how it holds that if $$\phi(y)$$ is false then a set is not a member of itself? I would assume that if $$\phi$$ holds then it holds also for all members of the set that it holds true for? I'm a little confused and it may be in how I am observing formulas of the basic language but I am not sure.

 

[AKG]

I can't make much sense of your post, but perhaps you want to see how this axiom can be used to prove that there's no set which is a member of itself. Suppose otherwise, i.e. suppose $\exists x (x \in x)$. Here our formula $\phi (x)$ will obviously $x \in x$. By the axiom above, we'd have that:

$$\exists x (x \in x \wedge \forall y \in x (y \notin y))$$

For any $x$ witnessing this statement, we'd have:

$$x \in x \wedge \forall y \in x (y \notin y)$$

which gives the contradiction:

$$x \in x \wedge x \notin x$$

 

[rebeka]

Yeah, no I get that, it's this definition that is giving me trouble. I think where I went wrong was I forgot to assume that x is a member of y and as a result of Russells Paradox and the negation of the Axiom of Comprehension well, the rest follows. I'm taking this from Basic Set Theory by Azriel Levy as laid out in the first twenty-five pages that I've now read four dozen times. It's just a little difficult to follow sometimes but the author was a student under Fraenkel so I continue reading.

 

[rebeka]

Suppose otherwise, i.e. suppose $\exists x (x \in x)$. Here our formula $\phi (x)$ will obviously $x \in x$. By the axiom above, we'd have that:

I am still having a hard time with this and it is a problem I am having in general. I don't understand how to take the first steps. The ones that follow are very obvious to me but when I have to ask myself well what makes this work I get stuck!

And I am still a little unsure of my decision to regard this as an abbreviation where x is assumed to be a member of y. If I do accept it as such than I see a logical path but I feel as though I may have missed something that held more meaning.

 

[rebeka]

I guess I am expecting that what it should be saying is if $$x \in y \implies y \not\in x$$ but I don't get this from your answer. Your answer is suggesting that if $$x \in x \implies Russels \; Paradox$$[edit]

sorry I guess that holds too if I do it as you seem to have ..

take $$x \in y$$ then:

$$\exists x \left ( x \in y \right ) \implies \exists x \left ( \left ( x \in y \right ) \land \left ( \forall y \in x \right ) \left ( y \not\in y \right ) \right ), where \; y \; is \; not \; free \; in \; \phi(x)$$

I think this makes more sense to me now, I just have to go over the part $$where \; y \; is \; not \; free \; in \; \phi(x)$$.

Sorry for bringing the thread up again!

 

[AKG]

I guess I am expecting that what it should be saying is if $$x \in y \implies y \not\in x$$ but I don't get this from your answer. Your answer is suggesting that if $$x \in x \implies Russels \; Paradox$$


[edit]

sorry I guess that holds too if I do it as you seem to have ..

take $$x \in y$$ then:

$$\exists x \left ( x \in y \right ) \implies \exists x \left ( \left ( x \in y \right ) \land \left ( \forall y \in x \right ) \left ( y \not\in y \right ) \right ), where \; y \; is \; not \; free \; in \; \phi(x)$$

I think this makes more sense to me now, I just have to go over the part $$where \; y \; is \; not \; free \; in \; \phi(x)$$.

Sorry for bringing the thread up again!

Again, sorry if English is not your native language, but I can't exactly understand what you're saying. As I showed in my first post, you can prove $\neg \exists x (x \in x)$ by contradiction, using the Axiom of Foundation. You can also prove $\neg \exists x \exists y (x \in y \wedge y \in x)$ by contradiction using Foundation. What you did doesn't work. First of all, it doesn't prove what you want it to prove. Second, if you take $\phi$ to be $x \in y$, then clearly $y$ is free in $\phi$ and so you obviously can't apply Foundation.

First, let me state more accurately the Axiom Scheme of Foundations:

For every formula $\phi (x, v_1, \dots , v_n)$ with $n+1$ free variables, the following is an axiom:

$$\forall v_1 \dots \forall v_n \left [ \exists x \phi (x, v_1, \dots , v_n) \Rightarrow \exists x \left ( \phi (x, v_1, \dots , v_n) \wedge \forall y \in x [\neg \phi (y, v_1, \dots , v_n)]\right ) \right ]$$

So now suppose there are two sets which are members of each other. Let's express this as $\exists v \exists x (x \in v \wedge v \in x)$. Apply Foundation to the formula $\phi (x, v) \equiv (x \in v \wedge v \in x)$.

 

[rebeka]

OK thank you! I think $\neg \exists x \exists y (x \in y \wedge y \in x)$ puts the whole of the picture into perspective for me. I still don't understand your first reply because if $$\phi(x) = x \in x$$ is the chosen equation where is the y in the equation that cannot be free? I had been thinking that membership was right bound in that y was restricted by x but I see where this is not logical as y isn't necessarily restricted to being those members which are x.

I really hope my English isn't that bad, although French was the language I was educated in until high school, I had still spoken English in the home. You are the first to ever say anything and I have tried very hard to improve my grammar and spelling over the years.

 

[AKG]

OK thank you! I think $\neg \exists x \exists y (x \in y \wedge y \in x)$ puts the whole of the picture into perspective for me. I still don't understand your first reply because if $$\phi(x) = x \in x$$ is the chosen equation where is the y in the equation that cannot be free? I had been thinking that membership was right bound in that y was restricted by x but I see where this is not logical as y isn't necessarily restricted to being those members which are x.

I really hope my English isn't that bad, although French was the language I was educated in until high school, I had still spoken English in the home. You are the first to ever say anything and I have tried very hard to improve my grammar and spelling over the years.

Since $y$ doesn't even appear in $x \in x$, it's certainly not free in that formula, hence we're safe to use that formula.