A question about computability and Turing machines Part 2

Question

I asked a question a few days ago and got a response But my follow-up question was not answered (maybe my email was not sent successfully)

A question about computability and Turing machines

My quesion is:

1. If $E$ is not well-based, should the range of $F$ also exist ?
2. For every $n<w$, what is the set {$m | (w,E)$ satisfies $mEn$} ?

Answer 1

I believe you refer to "well founded" not "well based".

You are asking about a relation $E$ on $\omega$ and a function $F$ for which $$F(n)=\{F(m)\mid m\mathrel{E} n\}.$$ Such a function $F$ would have the property that $$m\mathrel{E} n\implies F(m)\in F(n)$$ And from this it follows that $E$ must be well-founded, since $\in$ is well founded. Every nonempty subset of $\omega$ would map to a set in the range of $F$, and that set would have a minimal element, whose preimage would be $E$-minimal.

If $E$ is not well-founded, therefore, there is no such function $F$ obeying the requirement.

These kinds of functions are especially useful when $E$ is an extensional well-founded relation, and the function $F$ is known as the Mostowski collapse. The basic fact is that every well-founded extensional relation $E$ on a set $X$ is isomorphic to a unique transitive set $M$. The function is simply $$F(x)=\{F(y)\mid y\mathrel{E} x\}.$$ This definition is made by transfinite recursion of $E$, which is legitimate since $E$ is well-founded. Since $E$ is extensional, one proves that $F$ is one-to-one, and since $$y\mathrel{E}x \iff F(y)\in F(x)$$ it follows that $F$ is an isomorphism between $\langle X,E\rangle$ and $\langle\text{ran}(F),\in\rangle$.

Regarding question 2, the set $$\{m\mid m\mathrel{E} n\}$$ is the set of objects in the structure $\langle\omega,E\rangle$ that this structure thinks are "elements" of the object $n$. The $E$ relation is simply a coded version of $\in$, but on the natural numbers instead of sets.

When one is working with Turing machines or infinite time Turing machines, the machines do not compute directly with sets, but the sets can be represented in terms of their codes, and that is the reason for introducing these relations $E$, which allow us to represent sets in a way that is suitable for computation.