Editing First-order logic (section)

===Many-sorted logic===
{{main|Many-sorted logic}}
Ordinary first-order interpretations have a single domain of discourse over which all quantifiers range. ''Many-sorted first-order logic'' allows variables to have different ''sorts'', which have different domains. This is also called ''typed first-order logic'', and the sorts called ''types'' (as in [[data type]]), but it is not the same as first-order [[type theory]]. Many-sorted first-order logic is often used in the study of [[second-order arithmetic]].<ref>{{Cite SEP|url-id=quantification|title=Quantifiers and Quantification|date=October 17, 2018|edition=Winter 2018|last=Uzquiano|first=Gabriel}} See in particular section 3.2, Many-Sorted Quantification.</ref>

When there are only finitely many sorts in a theory, many-sorted first-order logic can be reduced to single-sorted first-order logic.<ref>
[[Herbert Enderton|Enderton, H.]] ''A Mathematical Introduction to Logic'', second edition. [[Academic Press]], 2001, [https://books.google.com/books?id=dVncCl_EtUkC&pg=PT296 pp.296–299].</ref>{{rp|296–299}}
One introduces into the single-sorted theory a unary predicate symbol for each sort in the many-sorted theory and adds an axiom saying that these unary predicates partition the domain of discourse. For example, if there are two sorts, one adds predicate symbols <math>P_1(x)</math> and <math>P_2(x)</math> and the axiom:
:<math>\forall x ( P_1(x) \lor P_2(x)) \land \lnot \exists x (P_1(x) \land P_2(x))</math>.
Then the elements satisfying <math>P_1</math> are thought of as elements of the first sort, and elements satisfying <math>P_2</math> as elements of the second sort. One can quantify over each sort by using the corresponding predicate symbol to limit the range of quantification. For example, to say there is an element of the first sort satisfying formula <math>\varphi(x)</math>, one writes:
:<math>\exists x (P_1(x) \land \varphi(x))</math>.