Big Questions in First Order Logic

Question

if $\Sigma$ is a r.e set (half decidable) of sentence in first order logic,

the set of logical result of $\Sigma$ is Recursively Axiomatizable.

why this is false? or maybe it's true? pleas correct me.

Answer 1

Since $\Sigma$ is recusively enumerable, let $f : \omega \rightarrow \omega$ be a computable function that surjects onto $\Sigma$. Let $\phi_n$ be a computable listing of first order formula in your particular language.

Now define $\Gamma$ as follows:

$\phi_n \in \Gamma$ if and only if there is a $p$ and there is a $k < n$ such that $\phi_n$ takes the form $\bigwedge_{i < p} f(k)$, i.e. the conjection of $f(k)$ $p$ many times.

Clearly $\Gamma$ is recursive.

For every $n$, if you choose $m$ large enough, there is a $n' > n$ such that $\phi_{n'}$ is $\bigwedge_{i < m} f(n)$. Then by definition, $\bigwedge_{i < m} f(n)$ in $\Gamma$.

Clearly the the logical consequences of $\Gamma$ and $\Sigma$ are the same since for all $\varphi \in \Sigma$, there exists some $p$ such that $\bigwedge_{i < p} \varphi$ is in $\Gamma$; and for every element $\psi \in \Gamma$, there is a $p$ and an element $\varphi \in \Sigma$ such that $\psi = \bigwedge_{i < p} \varphi$. That is to say, $\Gamma$ consist of just multiple conjuncts of elements of $\Sigma$.