Tagged Questions
5
votes
1answer
137 views
Is every φ above the second level of the arithmetical hierarchy independent of PA?
If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
6
votes
3answers
972 views
are there non-standard models of arithmetic in second order arithmetic?
non-standard models of arithmetic in second order arithmetic?
Background:
According to Godel's theorem, if we have, in a given consistent system S, a non-provable wff. A, then we can extend the ...
3
votes
1answer
72 views
Can decidability results for monadic second-order logic be extended to monadic higher-order logics?
Call a higher-order logic fully monadic if and only if all of its predicate constants (at any order) and higher-order variables (at any order) are monadic (and it has no function symbols). In Solvable ...
