Thread: Two set theory questions

1) Prove that there is no function f with domain ω such that f (n+) ∈ f (n) for all n ∈ ω. [Hint: apply the Axiom of Foundation to ran f .] Deduce that, for any set x, it is false that x ∈ x.

2) Prove, using the Principle of Induction and the fact that each n ∈ ω is a transitive set, that n ∈ n is false for every natural number n.

Presumably, the idea in the first question is to show that if it were the case that there were such a function, then the range of f would contradict the axiom of Foundation, but I'm not entirely sure how to do the details.

Any help would be greatly appreciated. Many thanks.

Originally Posted by KSM08

1) Prove that there is no function f with domain ω such that f (n+) ∈ f (n) for all n ∈ ω. [Hint: apply the Axiom of Foundation to ran f .] Deduce that, for any set x, it is false that x ∈ x.

2) Prove, using the Principle of Induction and the fact that each n ∈ ω is a transitive set, that n ∈ n is false for every natural number n.

Presumably, the idea in the first question is to show that if it were the case that there were such a function, then the range of f would contradict the axiom of Foundation, but I'm not entirely sure how to do the details.

Any help would be greatly appreciated. Many thanks.

Rewrite the question and PREVIEW it to check it comes right. The way you wrote it can't be understood properly.

Tonio

Which part can't be understood?

Originally Posted by KSM08

Which part can't be understood?

For example this: f (n+) ∈ f (n) what is that little square between f(n+) and f(n)?

Tonio

I see what's happened- the symbols are displayed on my screen, but clearly not on everyone's... I thought I couldn't see what the problem was...

In normal language, the questions are:

1) Prove that there is no function f with domain ω (omega) such that f (n+) is a member of f (n) for all n in ω (omega). Deduce that, for any set x, it is false that x is a member of itself. (where n+ is the sucessor of n)

2) Prove, using the Principle of Induction and the fact that each n in ω (omega) is a transitive set, that the statement "n is a member of itself" is false for every natural number n. (i.e. prove without using the Axiom of Foundation)

Sorry for the confusion.

Do you still want help with this?

What steps have you taken toward proofs of these?