show the set of valid second-order $\emptyset$-sentences is not R-enumerable

Question

show the set of valid second-order $\emptyset$-sentences is not R-enumerable

this would have the empty symbol set i.e. $S = \emptyset$

so it would be sentences that are universally or existentially quantified but would have no relations, functions or constants.

this just seems like a consequence of the Incompleteness of Second Order Logic. would it be proven similarly as $S_{\infty}-$sentences is proven to be not R-enumerable?

Answer 1

If you already know that the valid second-order sentences over the signature $S_\infty$ are not enumerable, you only have to construct from a $S_\infty$-sentence $\varphi$ a $\emptyset$-sentence $\varphi'$ such that $\varphi$ is valid if and only if $\varphi'$ is valid.

You can do this by replacing all distinct function symbols in $\varphi$ by distinct function variables of the same arity and all distinct relation symbols by distinct relation variables of the same arity and universally quantifying them.

Now assume you could enumerate all valid $\emptyset$-sentences. Whenerver you list a formula of the form $\forall R_1\dots R_n\forall f_1\dots f_m\psi'$ write down $\psi$, this would enumerate all valid $S_\infty$-sentences. Contradiction.

The result for $S_\infty$ follows from Trakhtenbrot's theorem and the fact that finiteness is definable by a second-order sentence.

Answer 2

There is a single sentence in the second-order language of equality whose contents is something like "There are relations and function symbols and a fixed element which satisfy the second-order axioms of Peano arithmetic with the elements of the universe".

Since second-order Peano has a unique model, $\Bbb N$, saying that a set satisfies this axiom means that it is countable, really.

But we can, given a code of a sentence $\varphi$ in the first-order language of arithmetic, recursively translate it to a second-order sentence whose content is essentially, "For every relations and functions which turn the universe into a model of second-order Peano, $\varphi$ as interpreted with those functions and relations holds".

It is not hard to see that this sort of statement is a logical truth if and only if $\varphi$ is true in $\Bbb N$ as a model of first-order $\sf PA$.

So if the logically valid sets were recursively enumerable -- or even arithmetic, we could have given a truth definition in first-order $\sf PA$. Which is a contradiction to Tarski's theorem.