Takako Nemoto (Tohoku University)

Priority method over intuitionistic logic

In this talk, we consider how much non-constructive principles are sufficient for Friedberg-Muchinik construction of degree $d$ such that $0<d<0'$. We will see that the only point we need a non-constructive principle is to show "if a recursive set $S$ of natural number has finite cardinality, then $S$ has an upper bound", which requires $\Sigma^0_1$ law of excluded middle.