The next step after zeroeth order logic is first order logic. In fact it’s also normally the last step. Higher order logic exists as well, but the standard formulation of mathematics makes no use of it, using only first or logic and set theory as its foundations. We’ll talk about set theory later and first order logic now.
The most important thing which first order logic introduces is quantifiers, specifically the universal quantifier “for all” and the existential quantifier “for some”.
There are some other new elements as well. One is “predicates”. The term is unfortunate. It’s borrowed from linguistics, but in a way which is incompatible with the way it’s used there. A word which better reflects the role they play might have been “property”, but “predicate” is standard.
First order logic can be difficult to follow though if you have no examples in mind. We’ll use first order logic soon in discussing the integers and sets, so it may be helpful to give some examples chosen from those.
For integer arithmetic “… is prime” is an example of a unary predicate, i.e. one which takes a single variable. The variable in this case is an integer and the value of the predicate is true or false depending on whether that integer is or is not prime. One the other hand “… is less than …” is a binary predicate, one which takes two values and is either true or false depending on whether the first is less than the second or not. There are also ternary predicates, with three variable, like “… is the sum of … and …”, which is true if first variable is the sum of the second and third. For set theory an important unary predicate is “… is finite”. A binary predicate is “… is a member of …”. A ternary predicate is “… is the union of … and …”.
Although the examples above may be helpful in understanding what role predicates play first order logic doesn’t concern itself with the meaning of predicates and indeed has no way to represent any such meaning. Predicates appear as letters, just as variables do. This letter is just as unspecified in its meaning as a variable is. First order logic doesn’t care whether a ternary predicate represents “… is the sum of … and …” or “… is the union of … and …” or something else entirely.
In addition to quantifiers, variables and predicates we also have “parameters”. It’s somewhat harder to describe what a parameter is. When we discussed the rule of substitution in zeroeth order logic we saw that not all variables are equally variable. Some are allowed to vary more than others. Parameters represent instantiated variables. Suppose, for example, we’re operating in a context where we have available the statement that for every integer \({ n }\) there is a prime number greater than \({ n }\). This statement, which has a universal quantifier in the “for every” and an existential quantifier in the “there is”, might be available because it’s already been proved or it might be available because we’ve introduced it as a hypothesis, as we discussed when we talked about natural deduction. In this case the statement happens to be true but it could conceivably have appeared in a proof by contradiction. In any case we have the statement available. Now 2024 is an integer, so we are assured by this statement that there is a prime number greater than 2024. We could then say “let \({ p }\) be such a prime”. In that case a logician would describe \({ p }\) as a parameter. Like variables, parameters are allowed to appear as arguments of predicates. Mathematicians tend not to bother with such distinctions and would refer to both \({ n }\) and \({ p }\) as variables but logicians are more careful and distinguish between variables and parameters because the rules of inference treat them somewhat differently, as we’ll see.
The distinction between variables and parameters may become clearer when we apply first order logic in other theories, like elementary arithmetic or set theory. In arithmetic, for example, the variables will be numerical. We will also have numerical expressions, like \({ n + 3 }\). When applying first order logic we will be able to substitute numerical expressions for parameters, but not for variables.
We’ll also retain the logical operators of zeroeth order logic along with the parentheses but we’ll leave behind the Boolean variables. The things connected by the operators will be expressions built from predicates. We still have variables but they are not, or at least are not necessarily, Boolean variables and it will not make sense to talk about variables being true or false. In integer arithmetic the variables will represent numbers and in set theory they will represent sets. In neither case does it make sense to ask whether they are true or false.
The version of first order logic we’ll consider is “untyped”. In other words there is only one set of variables. This isn’t the way mathematicians or computer scientists are used to working. If we’re discussing linear algebra we might, for example, want to have three types of variables, for scalars, vectors and matrices. Traditional linear algebra textbooks use lower case Greek letters for scalars, bold lower case Latin letters for vectors, and upper case Latin letters for matrices, for example. While that’s often convenient it’s not strictly necessary. We could accomplish the same thing by having a single set of variables and introducing the unary predicates “… is a scalar”, “… is a vector” and “… is a matrix”. In fact we’d be better off not introducing the last of these and simply thinking of vectors as matrices with only one column and of scalars as vectors with only one row. First order logic makes no assumptions about what this one type of variable might represent.