# 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 | result | explanation |
---|---|---|---|

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