recursive axiomatizability

101 Views Asked by At

Please feel free to correct anything if I've got it wrong.


Definitions:

Let $T$ and $T'$ be sets of formulas of languages whose syntax can be recursively arithmetized.

$T$ is 1-reducible to $T'$ ($T\leq_1 T'$) if, for some 1-1 recursive function $f,$ $x\in T$ iff $f(x)\in T'$. Note that $\leq_1$ is reflexive and transitive.

$T$ is recursively isomorphic to $T'$ if, for some 1-1 onto recursive function, $f,$ $x\in T$ iff $f(x)\in T'.$

Fact 1: $T$ is recursively isomorphic to $T'$ iff $T\leq_1 T'$ and $T'\leq_1 T.$

T is recursively axiomatizable if it has a recursive signature and a recursive set of axioms.

Let $M$ be some model theory and $L$ a language, the $L$-logic of $M$ is the set of all $L$-formulas valid on $M$ (those formulas valid on every $M$-model).

Let $L$ be a language and $M$ and $M'$ two model theories, then the interpretation of $L$ on $M$ is semantically equivalent to the interpretation of $L$ on $M'$ just in case their semantical rules are equivalent.


Questions:

(1) If you show that $A$ is recursively isomorphic to second-order logic (SOL), that's enough to show that $A$ is not recursively axiomatizable, correct?

(2) If the $L$-logic of $M$ is recursively isomorphic to SOL and the interpretation of $L$ on $M$ is semantically equivalent to the interpretation of $L$ on $M'$, is the $L$-logic of $M'$ recursively isomorphic to SOL? (Since wouldn't the set of validities be the same and so there is a recursive isomorphism from one logic to the other.)

(3) If $T$ is recursively isomorphic to SOL/not recursively axiomatizable and $T'$$\subseteq$$T$, is there a way to get a similar result for $T'$?