# Two set theory questions

• Feb 5th 2010, 02:50 AM
KSM08
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.
• Feb 5th 2010, 06:52 AM
tonio
Quote:

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
• Feb 5th 2010, 09:26 AM
KSM08
Which part can't be understood?
• Feb 5th 2010, 10:26 AM
tonio
Quote:

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
• Feb 5th 2010, 10:38 AM
KSM08
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.
• Feb 9th 2010, 12:47 PM
MoeBlee
Do you still want help with this?

What steps have you taken toward proofs of these?