$\alpha$-computable set is $\alpha$-finite if $\alpha^*<\alpha$

63 Views Asked by At

My question is concerned with $\alpha$-computability theory, a definability theory over Goedel's $L_\alpha$ where $\alpha$ is an admissible ordinal.

Let the $\Sigma_1$ projectum of $\alpha$ be $\alpha^*$ and let $\alpha^* < \alpha$. Let $\phi$ be the following statement:
$\forall A \subseteq \alpha$ [if $A$ is $\alpha$-computable, then $A \in L_\alpha$]

My confusion is that I can prove both $\phi$ and its negation $\neg \phi$.

Proof of $\neg \phi$:
Assume that $\phi$ holds. Then let $A := \alpha^*$. Clearly $A$ is $\alpha$-computable. Hence also $\alpha - A$ is $\alpha$-computable. By $\phi$, both $A$ and $\alpha - A$ are in $L_\alpha$. So their union $\alpha$ is in $L_\alpha$. But $\alpha$ is not bounded in $\alpha$ trivially, so $\alpha \not\in L_\alpha$. That is the contradiction. So $\neg \phi$ must be true.

Proof of $\phi$:
Fact1: $\forall B \subseteq \alpha$ [$B \in L_\alpha$ iff $B$ is $\alpha$-computable and bounded in $\alpha$]
As $\alpha^*$ is a $\Sigma_1$ projectum of $\alpha$, let $i : \alpha \to \alpha^*$ be an $\alpha$-computable injection and $p_1 : \alpha^* \to \alpha$ an $\alpha$-computable projection, i.e. $p_1=i^{-1}$. Let $K:=i[A]$ (the image of $i$ on the subdomain $A$). As $i$ and $A$ are $\alpha$-computable, so $K$ must be $\alpha$-computable. But $K$ is also bounded by $\alpha^* < \alpha$. Thus $K \in L_\alpha$ by Fact1.
Note that $p_1[K]=A$. Hence $A \in L_\alpha$ by the $\alpha$-computability of $p_1$, $\alpha$-finiteness of $K$ and by the admissibility of $\alpha$.

What is wrong in the proofs above?

1

There are 1 best solutions below

0
On BEST ANSWER

I think I found the fallacy in the proof of $\phi$, namely in the following claim:
If $A \subseteq \alpha$ and $f:\alpha \to \alpha$ are $\alpha$-computable, then $f[A]$ is $\alpha$-computable.

That claim is wrong by the following.
Fact2: Every $\alpha$-computably enumerable set is a range of some $\alpha$-computable function.
Now take some $\alpha$-computably enumerable set $B$ which is not $\alpha$-computable. Then let $f:\alpha \to \alpha$ be some $\alpha$-computable function such that its range is $B$. Note that $\alpha$ is an $\alpha$-computable set and $f[\alpha]=B$. So by the claim $B$ has to be $\alpha$-computable, but it is not. Hence the claim must be false in general.