The language of zeroth-order logic

Individual constants

We now have most of what we need to specify a very important logical language we will be working with, the language of zeroth-order logic, denoted

$\mathcal{L}_0$

. The alphabet of

$\mathcal{L}_0$

consists, first, of infinitely many symbols called individual constants or names. These may be represented by indexing a single symbol with the natural numbers, as if we had a list. Like this:

$$\mathfrak{c}_1, \mathfrak{c}_2, \mathfrak{c}_3, \mathfrak{c}_4, \mathfrak{c}_5, …$$

You can read this as:

$\mathfrak{c}_1$

(‘cee one’) is the first constant,

$\mathfrak{c}_2$

(‘cee two’) is the second constant,

$\mathfrak{c}_3$

(‘cee three’) is the third constant, and so on. (The indices, in order, here would be

$1$

,

$2$

,

$3$

, and so on.) Clearly, we cannot list all of the constants (for each

$n$

), just as we cannot list all the natural numbers. That would take an infinitely long paper, and let’s not talk about the time involved! This is why we have the three dots

$…$

, implying it goes on forever. More succinctly, we may say:

$\mathfrak{c}_n$

is a constant for every natural number

$n$

.

Note also that the use of

$\mathfrak{c}$

here is completely arbitrary. I chose it because it is the first letter in the word ‘constant’, but I could have chosen

$\mathfrak{a}$

or

$\mathfrak{b}$

. On the other hand, once we specify that we use

$\mathfrak{c}$

, we have to stick with it. In other words, the choice of

$\mathfrak{c}$

is arbitrary, but using

$\mathfrak{c}$

afterwards is not arbitrary, since we explicitly chose it over other alternatives.

Predicates

Second, similar to constants, we also have infinitely many symbols called predicates in our alphabet. These will be denoted by

$\mathfrak{P}$

(like

$P$

, but in a different font). In fact, these predicates come with an additional index called their arity, denoting the number of arguments they each take (see below). So really, for each natural number

$k$

, there are infinitely many predicates for that natural number (arity)

$k$

. This might be a bit confusing at first, so let’s look at some examples.

First, the infinitely many predicates of arity

$1$

can be represented:

$$\mathfrak{P}^1_1, \mathfrak{P}^1_2, \mathfrak{P}^1_3, \mathfrak{P}^1_4, \mathfrak{P}^1_5, …$$

Then, the infinitely many predicates of arity

$2$

can be represented:

$$\mathfrak{P}^2_1, \mathfrak{P}^2_2, \mathfrak{P}^2_3, \mathfrak{P}^2_4, \mathfrak{P}^2_5, …$$

So really, the list goes on infinitely not just horizontally, but vertically too! So in full generality:

$$\begin{gathered} \mathfrak{P}^1_1, \mathfrak{P}^1_2, \mathfrak{P}^1_3, \mathfrak{P}^1_4, \mathfrak{P}^1_5, …\\ \mathfrak{P}^2_1, \mathfrak{P}^2_2, \mathfrak{P}^2_3, \mathfrak{P}^2_4, \mathfrak{P}^2_5, …\\ \mathfrak{P}^3_1, \mathfrak{P}^3_2, \mathfrak{P}^3_3, \mathfrak{P}^3_4, \mathfrak{P}^3_5, …\\ \vdots \end{gathered}$$

Just as before, this may be represented a lot more succintly by simply saying:

$\mathfrak{P}^k_n$

is a predicate for each pair of positive natural numbers

$k, n$

. In other words, no matter what positive natural number you choose for

$k$

and

$n$

, substituting it for

$k$

and

$n$

in

$\mathfrak{P}^k_n$

will get you a predicate of the language. Sometimes, we may say

$\mathfrak{P}^k_n$

is a

$k$

-place predicate.

It is important to note that in a predicate like

$\mathfrak{P}^{4}_{9}$

, the number

$4$

is called its arity, and the number

$9$

is called its index. For example, though

$4$

may look like the power or exponent, this is just because of the similar notation. In reality, these two ideas are not related in any way, and should not be confused.

The connectives and the rest

Just like with the language

$\mathcal{L}_{AE}$

, simpler expressions will be combined together to form more complex expressions using special symbols (similar to the

$+$

,

$–$

, and

$\times$

signs). We call these symbols connectives, for obvious reasons. Table 2.1 lists the four connectives we will be using. Note that each symbol comes with a fixed arity, like our predicates. The table also includes, in scare quotes, the closest natural language approximation for the meaning of these symbols. For now (and perhaps altogether), this is irrelevant.

You may already know some or all of these connectives by their name, but perhaps not by their specific symbol (e.g.,

$\sim$

instead of

$\neg$

, & instead of

$\wedge$

). As noted when talking about alphabetic variants previously (see p. ), what the exact symbols of the alphabet are do not really matter, only the role they play. On the other hand, most contemporary writings on logic use these symbols for the connectives, as opposed to some of the older variants, so our choice is not entirely arbitrary.

Finally, we will keep using the left and right parentheses ‘

$($

’ and ‘

$)$

’, along with the comma symbol ‘

$,$

’. Thus:

The formulas of $\mathcal{L}_0$

Now that we have our alphabet, we can look at how our formulas are built up. Just as with some of the other languages we considered, not any sequence of symbols will qualify as a formula. Our base rule looks like this:

$\mathcal{L}_0$

: if

$\mathfrak{c}_{n_1}, …, \mathfrak{c}_{n_k}$

are

$k$

-many (not necessarily distinct) individual constants and

$\mathfrak{P}^k_i$

is a predicate of arity

$k$

, then

$\mathfrak{P}^k_i(\mathfrak{c}_{n_1}, …, \mathfrak{c}_{n_k})$

is a formula. We shall also call any such formula an atomic formula.

This is an extremely precise formulation of our base rule, and thus can be rather confusing at first. However, it really isn’t very complicated, for all it says is that if you take any predicate with arity

$k$

, then you need to have

$k$

individual constants following it in order for it to be a formula. In other words, any predicate

$\mathfrak{P}^k_n$

wears on its sleeves the number of individual constants it demands – namely,

$k$

many! Note however that these individual constants need not be distinct. For example, for

$\mathfrak{P}^2_5$

, we may write

$\mathfrak{P}^2_5(\mathfrak{c}_5, \mathfrak{c}_5)$

just as well as

$\mathfrak{P}^2_5(\mathfrak{c}_5, \mathfrak{c}_3)$

.

After our atomic formulas are defined, we can give our usual productive rule, which enables us to form more complex, i.e., ‘non-atomic’ formulas iteratively.

Of course,

$X$

and

$Y$

are variables, which can denote (as noted) any formula of

$\mathcal{L}_0$

, both atomic and non-atomic (complex).

Analyzing formulas; again

As before, we can now start analyzing the possible formulas of the language

$\mathcal{L}_0$

, checking whether they are in fact well-formed formulas of the language, and how they can be constructed. We previously saw two ways of doing this, one linear, the other making use of trees. These two ways are both applicable to formulas of

$\mathcal{L}_0$

. In general,

$X$

is a formula of the language

$\mathcal{L}_0$

if, and only if, it has a linear derivation and a tree derivation. Thus, if an expression cannot be derived, it is not a formula of

$\mathcal{L}_0$

, but if it is a formula of

$\mathcal{L}_0$

, you must be able to derive it somewhow.

As an example, let’s analyze the formula:

$$((\neg \mathfrak{P}^3_4(\mathfrak{c}_1, \mathfrak{c_2}, \mathfrak{c_1}) \wedge \neg \mathfrak{P}^1_4(\mathfrak{c}_3)) \rightarrow \mathfrak{P}^2_5(\mathfrak{c}_4, \mathfrak{c}_4))$$

From bottom to top, linearly, we can show that this is indeed a formula of the language as follows:

From top to bottom, using a tree and visualizing its structure, we can do it as follows:

As before, we can also ask about the main operator for each formula. The main operator is always the one introduced from the previous level or levels. Here:

1. The formulas

   $\mathfrak{P}^3_4(\mathfrak{c}_1, \mathfrak{c_2}, \mathfrak{c_1})$,

   $\mathfrak{P}^1_4(\mathfrak{c}_3)$, and

   $\mathfrak{P}^2_5(\mathfrak{c}_4, \mathfrak{c}_4)$are atomic, and have no operator;

2. The main operator of

   $\neg\mathfrak{P}^3_4(\mathfrak{c}_1, \mathfrak{c_2}, \mathfrak{c_1})$and

   $\neg\mathfrak{P}^1_4(\mathfrak{c}_3)$is

   $\neg$;

3. The main operator of

   $(\neg \mathfrak{P}^3_4(\mathfrak{c}_1, \mathfrak{c_2}, \mathfrak{c_1}) \wedge \neg \mathfrak{P}^1_4(\mathfrak{c}_3))$is

   $\wedge$;

4. The main operator of

   $((\neg \mathfrak{P}^3_4(\mathfrak{c}_1, \mathfrak{c_2}, \mathfrak{c_1}) \wedge \neg \mathfrak{P}^1_4(\mathfrak{c}_3)) \rightarrow \mathfrak{P}^2_5(\mathfrak{c}_4, \mathfrak{c}_4))$is

   $\rightarrow$.

Why the weird typeface?

You may be wondering why we are using this weird typeface where a simple

$P$

looks like this:

$\mathfrak{P}$

; and a simple

$c$

looks like this:

$\mathfrak{c}$

. This is because as we move forward, we will start using

$P$

,

$c$

, and some other letters to simplify our formulas if it does not matter at that moment which exact formula of the language we are talking about. This often happens when we want to talk about a class of formulas sharing the same structure. Thus, they will serve a separate, but very important, purpose.

It is important that you do not mix the notation freely! In logic, different ways of writing the same thing may have a different meaning. For example,

$p$

,

$P$

,

$\mathbf{P}$

and

$\mathfrak{P}$

will all mean different things. You should be careful which is used at any one point (see immediately below for a distinction!).

Variables like

$P$

and

$c$

are usually called metavariables, emphasizing that they are not part of the language, but outside of it. You may think of

$n$

here and the natural numbers. When we want to talk about some natural number or other, we use

$n$

, even though

$n$

is not a (representation of a) natural number itself (it is not a formula of

$\mathcal{L}_\mathbb{N}$

). Similarly, when we want to talk about some predicate or other, we may use the uppercase

$P, Q, R, …$

, and when we want to talk about some constant or another, we may use the lowercase

$a, b, c, …$

.

For example, we may represent a set of atomic formulas

$P(c_1, c_2, c_3)$

, meaning all formulas such that they start with

$\mathfrak{P}^3_n$

for some

$n$

, and continue with the required three (not necessarily distinct) constants

$\mathfrak{c}_k$

,

$\mathfrak{c}_j$

,

$\mathfrak{c}_l$

. That is, any formula of form:

$\mathfrak{P}^3_n(\mathfrak{c}_k, \mathfrak{c}_j, \mathfrak{c}_l)$

for some

$n$

,

$k$

,

$j$

,

$l$

. We may also write something like

$Q(c_1, c_1)$

, which would correspond to the class of all formulas

$\mathfrak{P}^2_n(\mathfrak{c}_k, \mathfrak{c}_k)$

for some

$n$

,

$k$

. Clearly, these specifications are painful, hence the simplification.

Though these variables are arbitrary, just like

$n$

,

$k$

,

$j$

, etc., you should make sure they don’t clash in a given context. Thus, using something like

$P(c_1, c_2) \wedge P(c_1, c_2, c_3)$

is bad, because the two

$P$

clearly denote two distinct classes of predicates, one

$2$

-place, one

$3$

-place.