# 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.

The set of valid first-order sentences over the signature $$S_{\infty}$$ is recursively enumerable.
The set of satisfiable first-order sentences over the signature $$S_{\infty}$$ is recursively enumerable.
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.
The set of first-order sentences over the signature $$S_{\infty}$$ that are satisfied in some finite model is recursively enumerable.