OSA: Mathematical Logic

Question 1

Which of the following claims are correct? Here, \(S_{\infty}\) denotes a signature with countably many constant symbols and for each arity countable many function and relation symbols.

question	answer	explanation
The set of valid first-order sentences over the signature \(S_{\infty}\) is recursively enumerable.	yesno	This set can be enumerated using a proof calculus such as sequent calculus, which is correct and complete by Gödel's Completeness Theorem.
The set of satisfiable first-order sentences over the signature \(S_{\infty}\) is recursively enumerable.	yesno	If this set was recursively enumerable then it would also be decidable, since \(\varphi\) is satisfiable if, and only if, \(\neg \varphi\) is not valid. But this is not the case since the halting problem can be reduced to satisfiability of FO sentences.
The set of first-order sentences over the signature \(S_{\infty}\) that are satisfied in /all/ finite structures (over a suitable signature \(S \subseteq S_{\infty}\)) is recursively enumerable.	yesno	This follows from Trakhtenbrot's Theorem.
The set of first-order sentences over the signature \(S_{\infty}\) that are satisfied in some finite model is recursively enumerable.	yesno	Since each such sentence can use only finitely many of the symbols in \(S_{\infty}\) one can recursively enumerate all finite structures over this signature until a model is found.