Basic Symbols

Leary's Definition 1.2.1 defines a first-order language as a collection of symbols. This is maybe a little misleading, as the later definitions of terms (Def. 1.3.1), formulas (Def. 1.3.3), and sentences (Def. 1.5.3) are also needed to fully specify a language.

First-order languages all share certain features: they share many of their basic symbols, and they share a syntax (that is, they share the definitions of terms, formulas, and sentences in terms of the basic symbols and how they are combined). However, they also differ in a few respects. The general definition of a language does not specify what particular constant symbols, relation symbols, and function symbols are to be included. Since all the other features of a language are shared among all languages, we don't need to mention them every time we specify a language; we only need to specify the features that are specific to this particular language. Therefore, we can specify a language by specifying a set of constant symbols, relation symbols, and function symbols.

(If you have studied Barwise and Etchemendy, Language, Proof, and Logic, notice that Leary's definition of a language is very similar to Barwise and Etchemendy's. They mention in Chapter 1 that it is more accurate to speak of languages (plural) of first-order logic rather than of a language (singular) of first-order logic, and they introduce several specific languages: the blocks language, with predicates like Tet(x) and Larger(x,y); a language to discuss their family members and pets, with individual constants like 'max' and 'claire', and predicates like 'Gave(x,y,z,t)'; the language of set theory, with constants for the natural numbers and a predicate for set membership; and so on. The main differences between B&E's definition and Leary's are: (1) Leary's presentation is a bit more formal; (2) Leary's first-order languages include function symbols, whereas B&E leave these out of their official language, although the mention them from time to time; (3) Leary's languages are a little more stripped-down, for example including the logical connectives $\vee$ and $\neg$, but not including $\wedge$, $\to$, or $\leftrightarrow$. This is to keep the official definition of a language as simple as possible, to make proofs easier. We can treat the things that have been left out as simply abbreviations for expressions using the symbols we do have; for example, we can treat $P \wedge Q$ as simply an abbreviation for $\neg (\neg P \vee \neg Q)$. Similarly, our official language contains only one quantifier, $\forall$, but we can regard the quantifier $\exists$ as simply an abbreviation: $(\forall x)$ abbreviates $\neg (\exists x) \neg$.)

For convenience, here is the list of basic symbols that constitute the building blocks of a first-order language (this is Leary's Definition 1.2.1).

Definition: A first-order language $\mathcal{L}$ is an infinite collection of distinct symbols, no one of which is properly contained in another, separated into the following categories:

1. Parentheses: (, ).
2. Connectives: $\vee$, $\neg$.
3. Quantifier: $\forall$.
4. Variables, one for each positive integer n: $v_1, v_2, \ldots, v_n, \ldots$. The set of variable symbols will be denoted $Vars$.
5. Equality symbol: $=$.
6. Constant symbols: Some set of zero or more symbols.
7. Function symbols: For each positive integer $n$, some set of zero or more $n$-ary function symbols.
8. Relation symbols: For each positive integer $n$, some set of zero or more $n$-ary relation symbols.

There are a couple of things to notice about this definition. A fussier version of this definition would indicate that the symbols are being mentioned rather than used by putting single quotation marks around them, e.g. Parentheses: '(', ')'. I have already mentioned that missing symbols such as '$\wedge$' can be defined in terms of the symbols provided here. Notice that all the basic symbols are specified except the constant symbols, function symbols, and relation symbols. (Actually, of course, the "equality symbol" is a relation symbol, but we list it separately because every first-order language must contain it.) "Equality symbol" may not be the best term for '=' - I would prefer "identity symbol" to emphasize that a sentence of the form '$v_1 = v_2$' is true if and only if the item denoted by the left-hand side is the very same thing as the item denoted by the right-hand side. In the last two items on the list, notice that the phrase "for each positive integer $n$" merely indicates that we will have zero or more functions and relations of each possible arity (i.e. one-place or unary functions and relations; two-place or binary functions and relations; and so on). The phrase "zero or more" of course guarantees that we don't need to provide any of these additional symbols if we don't need them!

Since everything except the constant, function, and relation symbols is prespecified, we can specify a language by merely stating which constant, function, and relation symbols we will add to the materials already provided. Note that we collect these symbols into a set in specifying a language; thus Leary notes that the language of set theory is just $\{\in\}$. (Actually, this isn't quite correct; as Barwise and Etchemendy note in chapter 15, we really need two additions to the basic materials of a first order language. It would be better to describe this language as the language $\{\in, Set()\}$. Barwise and Etchemendy's two styles of variables are a kind of abbreviation: using a variable $a, b, \ldots$ amounts to using an ordinary variable $x$ and stating that $Set(x)$.)

Leary notes that in the general case, the specification of a language will be

$$\{c_1, c_2, \ldots, f^{a(f_1)}_1, f^{a(f_2)}_2, \ldots, R^{a(R_1)}_1, R^{a(R_2)}_2, \ldots\}$$

This looks pretty weird at first, but it's really not so bad. Of course, $c_1$ is the first constant, $c_2$ is the second constant, and so on. Similarly, $f^{a(f_1)}_1$ is the first function symbol, and the superscript $a(f_1)$ is just a way of indicating the arity of the function.

We could almost save ourselves some symbols and put it this way instead: the specification of a language is

$$\{c_1, c_2, \ldots, f^1_1, f^1_2, \ldots, f^2_1, f^2_2, \ldots, \ldots, R^1_1, R^1_2, \ldots, R^2_1, R^2_2, \ldots, \ldots\}$$

where the superscript indicates the arity of the function or relation and the subscript indicates whether it is the first, second, etc. function of that arity. The problem is that perhaps this doesn't make it clear enough that we are not stopping with functions and relations of arity two. (I've tried to remedy this with double sets of ellipses, but that may be hard to interpret!)