forallx-cam-fol.tex

%!TEX root = forallxcam.tex
\part{First-order logic}
\label{ch.FOL}

\chapter{Building blocks of FOL}\label{s:FOLBuildingBlocks}
\section{The need to decompose sentences}
Consider the following argument, which is obviously valid in English:
\begin{earg}
\item[] Willard is a logician. 
\item[] All logicians wear funny hats. 
\item[So:] Willard wears a funny hat.
\end{earg}
To symbolise it in TFL, we might offer a symbolisation key:
\begin{ekey}
\item[L] Willard is a logician.
\item[A] All logicians wear funny hats.
\item[F] Willard wears a funny hat.
\end{ekey}
And the argument itself becomes:
$$L, A \therefore F$$
But the truth-table test will now indicate that this is \emph{invalid}. What has gone wrong?

The problem is not that we have made a mistake while symbolising the argument. This is the best symbolisation we can give \emph{in TFL}. The problem lies with TFL itself. `All logicians wear funny hats' is about both logicians and hat-wearing. By not retaining this structure in our symbolisation, we lose the connection between Willard's being a logician and Willard's wearing a hat.

The basic units of TFL are atomic sentences, and TFL cannot decompose these. To symbolise arguments like the preceding one, we will have to develop a new logical language which will allow us to \emph{split the atom}. We will call this language \emph{first-order logic}, or \emph{FOL}. 

The details of FOL will be explained throughout this chapter, but here is the basic idea for splitting the atom.

First, we have \emph{names}. In FOL, we indicate these with lowercase italic letters. For instance, we might let `$b$' stand for Bertie, or let `$i$' stand for Willard.

Second, we have predicates. English predicates are expressions like `\blank\ is a dog' or `\blank\ is a logician'. These are not complete sentences by themselves. In order to make a complete sentence, we need to fill in the gap. We need to say something like `Bertie is a dog' or `Willard is a logician'. In FOL, we indicate predicates with uppercase italic letters. For instance, we might let the FOL predicate `$D$' symbolise the English predicate `\blank\ is a dog'. Then the expression `$Db$' will be a sentence in FOL, which symbolises the English sentence `Bertie is a dog'. Equally, we might let the FOL predicate `$L$' symbolise the English predicate `\blank\ is a logician'. Then the expression `$Li$' will symbolise the English sentence `Willard is a logician'.

Third, we have quantifiers. For instance, `$\exists$' will roughly convey `There is at least one \ldots'. So we might symbolise the English sentence `there is a dog' with the FOL sentence `$\exists x Dx$', which we might read aloud as `there is at least one thing, x, such that x is a dog'.

That is the general idea. But FOL is significantly more subtle than TFL. So we will come at it slowly. 


\section{Names}
In English, a \emph{singular term} is a word or phrase that refers to a \emph{specific} person, place, or thing. The word `dog' is not a singular term, because there are a great many dogs. The phrase `Bertie' is a singular term, because it refers to a specific terrier. Likewise, the phrase `Philip's dog Bertie' is a singular term, because it refers to a specific little terrier. 

\emph{Proper names} are a particularly important kind of singular term. These are expressions that pick out individuals without describing them. The name `Emerson' is a proper name, and the name alone does not tell you anything about Emerson. Of course, some names are traditionally given to boys and other are traditionally given to girls. If `Hilary' is used as a singular term, you might guess that it refers to a woman. You might, though, be guessing wrongly. Indeed, the name does not necessarily mean that the person referred to is even a person: Hilary might be a giraffe, for all you could tell just from the name. 

In FOL, our \define{names} are lower-case letters `$a$' through to `$r$'. We can add subscripts if we want to use some letter more than once. So here are some singular terms in FOL:
	$$a,b,c,\ldots, r, a_1, f_{32}, j_{390}, m_{12}$$
These should be thought of along the lines of proper names in English. But with one difference. `Tim Button' is a proper name, but there are several people with this name. (Equally, there are  at least two people with the name `P.D.\ Magnus'.) We live with this kind of ambiguity in English, allowing context to individuate the fact that `Tim Button' refers to the lecturer of this course, and not some other guy. In FOL, we do not tolerate any such ambiguity. Each name must pick out \emph{exactly} one thing. (However, two different names may pick out the same thing.)

As with TFL, we can provide symbolisation keys. These indicate, temporarily, what a name shall pick out. So we might offer:
	\begin{ekey}
		\item[e] Elsa
		\item[g] Gregor
		\item[m] Marybeth
	\end{ekey}


\section{Predicates}
The simplest predicates are properties of individuals. They are things you can say about an object. Here are some examples of English predicates:
	\begin{quote}
		\blank\ is a dog\\
		\blank\ is a member of Monty Python\\
		A piano fell on \blank
	\end{quote}
In general, you can think about predicates as things which combine with singular terms to make sentences. Conversely, you can start with sentences and make predicates out of them by removing terms. Consider the sentence, `Vinnie borrowed the family car from Nunzio.' By removing a singular term, we can obtain any of three different predicates:
	\begin{quote}
		\blank\ borrowed the family car from Nunzio\\
		Vinnie borrowed \blank\ from Nunzio\\
		Vinnie borrowed the family car from \blank
	\end{quote}
FOL predicates are capital letters $A$ through $Z$, with or without subscripts. We might write a symbolisation key for predicates thus:
	\begin{ekey}
		\item[A] \gap{1} is angry
		\item[H] \gap{1} is happy
%		\item[T_1xy] \gap{x} is as tall or taller than \gap{y}
%		\item[T_2xy] \gap{x} is as tough or tougher than \gap{y}
%		\item[Bxyz] \gap{y} is between \gap{x} and \gap{z}
	\end{ekey}
(Why the numerical \emph{subscripts} on the gaps? I shall return to this in \S\ref{s:MultipleGenerality}.)

If we combine our two symbolisation keys, we can start to symbolise some English sentences that use these names and predicates in combination. For example, consider the English sentences:
	\begin{earg}
		\item[\ex{terms1}] Elsa is angry.
		\item[\ex{terms2a}] Gregor and Marybeth are angry.
		\item[\ex{terms2}] If Elsa is angry, then so are Gregor and Marybeth.
	\end{earg}
Sentence \ref{terms1} is straightforward: we symbolise it by `$Ae$'.

Sentence \ref{terms2a}: this is a conjunction of two simpler sentences. The simple sentences can be symbolised just by `$Ag$' and `$Am$'. Then we help ourselves to our resources from TFL, and symbolise the entire sentence by `$Ag \eand Am$'. This illustrates an important point: FOL has all of the truth-functional connectives of TFL.

Sentence \ref{terms2}: this is a conditional, whose antecedent is sentence \ref{terms1} and whose consequent is sentence \ref{terms2a}. So we can symbolise this with `$Ae \eif (Ag \eand Am)$'.

\section{Quantifiers}
We are now ready to introduce quantifiers. Consider these sentences:
	\begin{earg}
		\item[\ex{q.a}] Everyone is happy.
%		\item[\ex{q.ac}] Everyone is at least as tough as Elsa.
		\item[\ex{q.e}] Someone is angry.
	\end{earg}
It might be tempting to symbolise sentence \ref{q.a} as `$He \eand Hg \eand Hm$'. Yet this would only say that Elsa, Gregor, and Marybeth are happy. We want to say that \emph{everyone} is happy, even those with no names. In order to do this, we introduce the `$\forall$' symbol. This is called the \define{universal quantifier}.

A quantifier must always be followed by a variable. In FOL, variables are italic lowercase letters `$s$' through `$z$', with or without subscripts. So we might symbolise sentence \ref{q.a} as `$\forall x Hx$'.  The variable `$x$' is serving as a kind of placeholder. The expression `$\forall x$' intuitively means that you can pick anyone and put them in as `$x$'. The subsequent `$Hx$' indicates, of that thing you picked out, that it is happy. 

I should say that there is no special reason to use `$x$' rather than some other variable. The sentences `$\forall x Hx$', `$\forall y Hy$', `$\forall z Hz$', and `$\forall x_5 Hx_5$' use different variables, but they will all be logically equivalent.

To symbolise sentence \ref{q.e}, we introduce another new symbol: the \define{existential quantifier}, `$\exists$'. Like the universal quantifier, the existential quantifier requires a variable. Sentence \ref{q.e} can be symbolised by `$\exists x Ax$'. Whereas `$\forall x Ax$' is read naturally as `for all x, x is angry', `$\exists x Ax$' is read naturally as `there is something, x, such that x is angry'. Once again, the variable is a kind of placeholder; we could just as easily have symbolised sentence \ref{q.e} with `$\exists z Az$', `$\exists w_{256} Aw_{256}$', or whatever.

Some more examples will help. Consider these further sentences:
	\begin{earg}
		\item[\ex{q.ne}] No one is angry.
		\item[\ex{q.en}] There is someone who is not happy.
		\item[\ex{q.na}] Not everyone is happy.
	\end{earg}
Sentence \ref{q.ne} can be paraphrased as, `It is not the case that someone is angry'. We can then symbolise it using negation and an existential quantifier: `$\enot \exists x Ax$'. Yet sentence \ref{q.ne} could also be paraphrased as, `Everyone is not angry'. With this in mind, it can be symbolised using negation and a universal quantifier: `$\forall x \enot Ax$'. Both of these are acceptable symbolisations.  Indeed, it will transpire that, in general, $\forall x \enot\meta{A}$ is logically equivalent to $\enot\exists x\meta{A}$. (Notice that I have here returned to the practice of using `$\meta{A}$' as a metavariable, from \S\ref{s:UseMention}.) Symbolising a sentence one way, rather than the other, might seem more `natural' in some contexts, but it is not much more than a matter of taste.

Sentence \ref{q.en} is most naturally paraphrased as, `There is some x, such that x is not happy'. This then becomes `$\exists x \enot Hx$'. Of course, we could equally have written `$\enot\forall x Hx$', which we would naturally read as `it is not the case that everyone is happy'. And that would have been a perfectly adequate symbolisation of sentence \ref{q.na}.


\section{Domains}
Given the symbolisation key we have been using, `$\forall xHx$' symbolises `Everyone is happy'.  Who is included in this \emph{everyone}? When we use sentences like this in English, we usually do not mean everyone now alive on the Earth. We certainly do not mean everyone who was ever alive or who will ever live. We usually mean something more modest: everyone now in the building, everyone enrolled in the ballet class, or whatever.

In order to eliminate this ambiguity, we will need to specify a \define{domain}. The domain is the set of things that we are talking about. So if we want to talk about people in Chicago, we define the domain to be people in Chicago. We write this at the beginning of the symbolisation key, like this:
	\begin{ekey}
		\item[\text{domain}] people in Chicago
	\end{ekey}
The quantifiers \emph{range over} the domain. Given this domain, `$\forall x$' is to be read roughly as `Every person in Chicago is such that\ldots' and `$\exists x$' is to be read roughly as `Some person in Chicago is such that\ldots'. 

In FOL, the domain must always include at least one thing. Moreover, in English we can legitimately infer `something is angry' from `Gregor is angry'. In FOL, then, we shall want to be able to infer `$\exists x Ax$' from `$Ag$'. So we shall insist that each name must pick out exactly one thing in the domain. If we want to name people in places beside Chicago, then we need to include those people in the domain. 
	\factoidbox{
		A domain must have \emph{at least} one member. Every name must pick out \emph{exactly} one member of the domain. But a member of the domain may be picked out by one name, many names, or none at all.
	}


\chapter{Sentences with one quantifier}\label{s:MoreMonadic}
We now have all of the pieces of FOL. Symbolising more complicated sentences is just a matter of knowing how to combine predicates, names, quantifiers, and connectives. There is a knack to this, and there is no substitute for practice.

\section{Dealing with syncategorematic adjectives}
When we encounter a sentence like 
	\begin{earg}
		\item[\ex{syn1}] Herbie is a white car
	\end{earg}
We can paraphrase this as `Herbie is white and Herbie is a car'. We can then use a symbolisation key like:
	\begin{ekey}
		\item[W] \gap{1} is white
		\item[C] \gap{1} is a car
		\item[h] Herbie
	\end{ekey}
This allows us to symbolise sentence \ref{syn1} as `$Wh \eand Ch$'. But now consider:
	\begin{earg}
		\item[\ex{syn2}] Damon Stoudamire is a short basketball player. 
		\item[\ex{syn3}] Damon Stoudamire is a man.
		\item[\ex{syn4}] Damon Stoudamire is a short man.
	\end{earg}
Following the case of Herbie, we might try to use a symbolisation key like:
	\begin{ekey}
		\item[S] \gap{1} is short
		\item[B] \gap{1} is a basketball player
		\item[M] \gap{1} is a man
		\item[d] Damon Stoudamire
	\end{ekey}
Then we would symbolise sentence \ref{syn2} with `$Sd \eand Bd$', sentence \ref{syn3} with `$Md$' and sentence \ref{syn4} with `$Sd \eand Md$'. But that would be a terrible mistake! For this now suggests that sentences \ref{syn2} and \ref{syn3} together \emph{entail} sentence \ref{syn4}. But they do not. Standing at  5'10'', Damon Stoudamire is one of the shortest professional basketball players of all time, but he is nevertheless an averagely-tall man. The point is that sentence \ref{syn2} says that Damon is short \emph{qua} basketball player, even though he is of average height \emph{qua} man. So you will need to symbolise `\blank\ is a short basketball player' and `\blank\ is a short man' using completely different predicates. 

Similar examples abound. All footballers are people, but some good footballers are bad people. I might be an incompetent player of the cor anglais, but a competent individual. And so it goes. The moral is: when you see two adjectives in a row, you need to ask yourself carefully whether they can be treated as a conjunction or not.


\section{Common quantifier phrases}
Consider these sentences:
	\begin{earg}
		\item[\ex{quan1}] Every coin in my pocket is a quarter.
		\item[\ex{quan2}] Some coin on the table is a dime.
		\item[\ex{quan3}] Not all the coins on the table are dimes.
		\item[\ex{quan4}] None of the coins in my pocket are dimes.
	\end{earg}
In providing a symbolisation key, we need to specify a domain. Since we are talking about coins in my pocket and on the table, the domain must at least contain all of those coins. Since we are not talking about anything besides coins, we let the domain be all coins. Since we are not talking about any specific coins, we do not need to need to deal with any names. So here is our key:
	\begin{ekey}
		\item[\text{domain}] all coins
		\item[P] \gap{1} is in my pocket
		\item[T] \gap{1} is on the table
		\item[Q] \gap{1} is a quarter
		\item[D] \gap{1} is a dime
	\end{ekey}
Sentence \ref{quan1} is most naturally symbolised using a universal quantifier. The universal quantifier says something about everything in the domain, not just about the coins in my pocket. Sentence \ref{quan1} can be paraphrased as `for any coin, \emph{if} that coin is in my pocket \emph{then} it is a quarter'. So we can symbolise it as `$\forall x(Px \eif Qx)$'.

Since sentence \ref{quan1} is about coins that are both in my pocket \emph{and} that are quarters, it might be tempting to translate it using a conjunction. However, the sentence `$\forall x(Px \eand Qx)$' would symbolise the sentence `every coin is both a quarter and in my pocket'. This obviously means something very different than sentence \ref{quan1}. And so we see:
	\factoidbox{
		A sentence can be symbolised as $\forall x (\script{F}x \eif \script{G}x)$ if it can be paraphrased in English as `every F is G'.
	}
Sentence \ref{quan2} is most naturally symbolised using an existential quantifier. It can be paraphrased as `there is some coin which is both on the table and which is a dime'. So we can symbolise it as `$\exists x(Tx \eand Dx)$'.

Notice that we needed to use a conditional with the universal quantifier, but we used a conjunction with the existential quantifier. Suppose we had instead written `$\exists x(Tx \eif Dx)$'. That would mean that there is some object in the domain of which `$(Tx \eif Dx)$' is true. Recall that, in TFL, $\meta{A} \eif \meta{B}$ is tautologically equivalent to $\enot\meta{A} \eor \meta{B}$. This equivalence will also hold in FOL. So `$\exists x(Tx \eif Dx)$' is true if there is some object in the domain, such that `$(\enot Tx \eor Dx)$' is true of that object. That is, `$\exists x (Tx \eif Dx)$' is true if some coin is \emph{either} not on the table \emph{or} is a dime. Of course there is a coin that is not on the table: there are coins lots of other places. So it is \emph{very easy} for `$\exists x(Tx \eif Dx)$' to be true. A conditional will usually be the natural connective to use with a universal quantifier, but a conditional within the scope of an existential quantifier tends to say something very weak indeed. As a general rule of thumb, do not put conditionals in the scope of existential quantifiers unless you are sure that you need one.
	\factoidbox{
		A sentence can be symbolised as $\exists x (\script{F}x \eand \script{G}x)$ if it can be paraphrased in English as `some F is G'.
	}		
Sentence \ref{quan3} can be paraphrased as, `It is not the case that every coin on the table is a dime'. So we can symbolise it by `$\enot \forall x(Tx \eif Dx)$'. You might look at sentence \ref{quan3} and paraphrase it instead as, `Some coin on the table is not a dime'. You would then symbolise it by `$\exists x(Tx \eand \enot Dx)$'. Although it is probably not immediately obvious yet, these two sentences are logically equivalent. (This is due to the logical equivalence between $\enot\forall x\meta{A}$ and $\exists x\enot\meta{A}$, mentioned in \S\ref{s:FOLBuildingBlocks}, along with the equivalence between $\enot(\meta{A}\eif\meta{B})$ and $\meta{A}\eand\enot\meta{B}$.)

Sentence \ref{quan4} can be paraphrased as, `It is not the case that there is some dime in my pocket'. This can be symbolised by `$\enot\exists x(Px \eand Dx)$'. It might also be paraphrased as, `Everything in my pocket is a non-dime', and then could be symbolised by `$\forall x(Px \eif \enot Dx)$'. Again the two symbolisations are logically equivalent. Both are correct symbolisations of sentence \ref{quan4}.


\section{Empty predicates}
In \S\ref{s:FOLBuildingBlocks}, I emphasised that a name must pick out exactly one object in the domain. However, a predicate need not apply to anything in the domain. A predicate that applies to nothing in the domain is called an \define{empty} predicate. This is worth exploring.

Suppose we want to symbolise these two sentences:
	\begin{earg}
		\item[\ex{monkey1}] Every monkey knows sign language
		\item[\ex{monkey2}] Some monkey knows sign language
	\end{earg}
It is possible to write the symbolisation key for these sentences in this way:
	\begin{ekey}
		\item[\text{domain}] animals
		\item[M] \gap{1} is a monkey.
		\item[S] \gap{1} knows sign language.
	\end{ekey}
Sentence \ref{monkey1} can now be symbolised by `$\forall x(Mx \eif Sx)$'. Sentence \ref{monkey2} can be symbolised as `$\exists x(Mx \eand Sx)$'.

It is tempting to say that sentence \ref{monkey1} \emph{entails} sentence \ref{monkey2}. That is, we might think that it is impossible that every monkey knows sign language unless some monkey knows sign language.  But this would be a mistake. It is possible for the sentence `$\forall x(Mx \eif Sx)$' to be true even though the sentence `$\exists x(Mx \eand Sx)$' is false.

How can this be? The answer comes from considering whether these sentences would be true or false \emph{if there were no monkeys}. If there were no monkeys at all (in the domain), then `$\forall x(Mx \eif Sx)$' would be \emph{vacuously} true: take any monkey you like---it knows sign language! But if there were no monkeys at all (in the domain), then `$\exists x(Mx \eand Sx)$' would be false: the truth of that sentence requires a (signing) monkey.

Another example will help to bring this home. Suppose we extend the above symbolisation key, by adding:
	\begin{ekey}
		\item[R] \gap{1} is a refrigerator
	\end{ekey}
Now consider the sentence `$\forall x(Rx \eif Mx)$'. This symbolises `every refrigerator is a monkey'. And this sentence is true, given our symbolisation key. This is counterintuitive, since we do not want to say that there are a whole bunch of refrigerator monkeys. It is important to remember, though, that `$\forall x(Rx \eif Mx)$' is true iff every refrigerator \emph{in the domain} is also a monkey. Since the domain comprises only \emph{animals}, there are no refrigerators in the domain. Again, then, the sentence is \emph{vacuously} true. (Of course, if you were actually dealing with the sentence `All refrigerators are monkeys', then you would most likely want to include kitchen appliances in the domain. Then the predicate `$R$' would not be empty and the sentence `$\forall x(Rx \eif Mx)$' would be false.)
	\factoidbox{
		When $\meta{F}$ is an empty predicate, any sentence $\forall x (\meta{F}x \eif \ldots)$ is vacuously true.
	}


\section{Picking a domain}
The appropriate symbolisation of an English language sentence in FOL will depend on the symbolisation key. Choosing a key can be difficult. Suppose we want to symbolise the English sentence:
	\begin{earg}
		\item[\ex{pickdomainrose}] Every rose has a thorn.
	\end{earg}
We might offer this symbolisation key:
	\begin{ekey}
		\item[R] \gap{1} is a rose
		\item[T] \gap{1} has a thorn
	\end{ekey}
It is tempting to say that sentence \ref{pickdomainrose} should be symbolised as `$\forall x(Rx \eif Tx)$'. But we have not yet chosen a domain. If the domain contains all roses, this would be a good symbolisation. Yet if the domain is merely \emph{things on my kitchen table}, then `$\forall x(Rx \eif Tx)$' would only come close to covering the fact that every rose \emph{on my kitchen table} has a thorn. If there are no roses on my kitchen table, the sentence would be trivially true. This is not what we want. To symbolise sentence \ref{pickdomainrose} adequately, we need to include all the roses in the domain. But now we have two options. 

First, we can restrict the domain to include all roses but \emph{only} roses. Then sentence \ref{pickdomainrose} can, if we like, be symbolised with `$\forall x Tx$'. This is true iff everything in the domain has a thorn; since the domain is just the roses, this is true iff every rose has a thorn. By restricting the domain, we have been able to symbolise our English sentence with a very short sentence of FOL. So this approach can save us trouble, if every sentence that we want to deal with is about roses.

Second, we can let the domain contain things besides roses: rhododendrons; rats; rifles; whatevers.  And we will certainly need to include a more expansive domain if we simultaneously want to symbolise sentences like:
	\begin{earg}
		\item[\ex{pickdomaincowboy}] Every cowboy sings a sad, sad song.
	\end{earg}
Our domain must now include both all the roses (so that we can symbolise sentence \ref{pickdomainrose}) and all the cowboys (so that we can symbolise sentence \ref{pickdomaincowboy}). So we might offer the following symbolisation key:
	\begin{ekey}
		\item[\text{domain}] people and plants
		\item[C] \gap{1} is a cowboy
		\item[S] \gap{1} sings a sad, sad song
		\item[R] \gap{1} is a rose
		\item[T] \gap{1} has a thorn
	\end{ekey}
Now we will have to symbolise sentence \ref{pickdomainrose} with `$\forall x (Rx \eif Tx)$', since `$\forall x Tx$' would symbolise the sentence `every person or plant has a thorn'. Similarly, we will have to symbolise sentence \ref{pickdomaincowboy} with `$\forall x (Cx \eif Sx)$'. 

In general, the universal quantifier can be used to symbolise the English expression `everyone' if the domain only contains people. If there are people and other things in the domain, then `everyone' must be treated as `every person'.


\section{The utility of paraphrase}
When symbolising English sentences in FOL, it is important to understand the structure of the sentences you want to symbolise. What matters is the final symbolisation in FOL, and sometimes you will be able to move from an English language sentence directly to a sentence of FOL. Other times, it helps to paraphrase the sentence one or more times. Each successive paraphrase should move from the original sentence closer to something that you can finally symbolise directly in FOL.

For the next several examples, we will use this symbolisation key:
	\begin{ekey}
		\item[\text{domain}] people
		\item[B] \gap{1} is a bassist
		\item[R] \gap{1} is a rock star
		\item[k] Kim Deal
	\end{ekey}
Now consider these sentences:
	\begin{earg}
		\item[\ex{pronoun1}] If Kim Deal is a bassist, then she is a rock star.
		\item[\ex{pronoun2}] If a person is a bassist, then she is a rock star.
	\end{earg}
The same words appear as the consequent in sentences \ref{pronoun1} and \ref{pronoun2} (`$\ldots$ she is a rock star'), but they mean very different things. To make this clear, it often helps to paraphrase the original sentences, removing pronouns.

Sentence \ref{pronoun1} can be paraphrased as, `If Kim Deal is a bassist, then \emph{Kim Deal} is a rockstar'. This can obviously be symbolised as `$Bk \eif Rk$'.

Sentence \ref{pronoun2} must be paraphrased differently: `If a person is a bassist, then \emph{that person} is a rock star'. This sentence is not about any particular person, so we need a variable. As a halfway house, we can paraphrase this as, `For any person x, if x is a bassist, then x is a rockstar'. Now this can be symbolised as `$\forall x (Bx \eif Rx)$'. This is the same sentence we would have used to symbolise `Everyone who is a bassist is a rock star'. And on reflection, that is surely true iff sentence \ref{pronoun2} is true, as we would hope.

Consider these further sentences:
	\begin{earg}
		\item[\ex{anyone1}] If anyone is a bassist, then Kim Deal is a rock star.
		\item[\ex{anyone2}] If anyone is a bassist, then she is a rock star.
	\end{earg}
The same words appear as the antecedent in sentences \ref{anyone1} and \ref{anyone2}  (`If anyone is a bassist$\ldots$'). But it can be tricky to work out how to symbolise these two uses. Again, paraphrase will come to our aid. 

Sentence \ref{anyone1} can be paraphrased, `If there is at least one bassist, then Kim Deal is a rock star'. It is now clear that this is a conditional whose antecedent is a quantified expression; so we can symbolise the entire sentence with a conditional as the main logical operator: `$\exists x Bx \eif Rk$'.

Sentence \ref{anyone2} can be paraphrased, `For all people x, if x is a bassist, then x is a rock star'. Or, in more natural English, it can be paraphrased by `All bassists are rock stars'. It is best symbolised as `$\forall x(Bx \eif Rx)$', just like sentence \ref{pronoun2}.

The moral is that the English words `any' and `anyone' should typically be symbolised using quantifiers. And if you are having a hard time determining whether to use an existential or a universal quantifier, try paraphrasing the sentence with an English sentence that uses words \emph{besides} `any' or `anyone'.



\section{Quantifiers and scope}
Continuing the example, suppose I want to symbolise these sentences:
	\begin{earg}
		\item[\ex{qscope1}] If everyone is a bassist, then Tim is a bassist
		\item[\ex{qscope2}] Everyone is such that, if they are a bassist, then Tim is a bassist.
	\end{earg}
To symbolise these sentences, I need to add a new name to the symbolisation key, namely:
	\begin{ekey}
		\item[b] Tim
	\end{ekey}
Sentence \ref{qscope1} is a conditional, whose antecedent is `everyone is a bassist'. So we will symbolise it with `$\forall x Bx \eif Bb$'. This sentence is \emph{necessarily} true: if \emph{everyone} is indeed a bassist, then take any one you like---for example Tim---and he will be a bassist. 

Sentence \ref{qscope2}, by contrast, might best be paraphrased by `every person x is such that, if x is a bassist, then Tim is a bassist'. This is symbolised by `$\forall x (Bx \eif Bb)$'. And this sentence is false. Kim Deal is a bassist. So `$Bk$' is true. But Tim is not a bassist, so `$Bb$' is false. Accordingly, `$Bk \eif Bb$' will be false. So `$\forall x (Bx \eif Bb)$' will be false as well. 

In short, `$\forall x Bx \eif Bb$' and `$\forall x (Bx \eif Bb)$' are very different sentences. We can explain the difference in terms of the \emph{scope} of the quantifier. The scope of quantification is very much like the scope of negation, which we considered when discussing TFL, and it will help to explain it in this way.

In the sentence `$\enot Bk \eif Bb$', the scope of `$\enot$' is just the antecedent of the conditional. We are saying something like: if `$Bk$' is false, then `$Bb$' is true. Similarly, in the sentence `$\forall x Bx \eif Bb$', the scope of `$\forall x$' is just the antecedent of the conditional. We are saying something like: if `$Bx$' is true of \emph{everything}, then `$Bb$' is also true. 

In the sentence `$\enot(Bk \eif Bb)$', the scope of `$\enot$' is the entire sentence. We are saying something like: `$(Bk \eif Bb)$' is false. Similarly, in the sentence `$\forall x (Bx \eif Bb)$', the scope of `$\forall x$' is the entire sentence. We are saying something like: `$(Bx \eif Bb)$' is true of \emph{everything}.

The moral of the story is simple. When you are using conditionals, be very careful to make sure that you have sorted out the scope correctly. 

\practiceproblems
\problempart
\label{pr.BarbaraEtc}
Here are the syllogistic figures identified by Aristotle and his successors, along with their medieval names:
\begin{ebullet}
	\item \textbf{Barbara.} All G are F. All H are G. So:  All H are F
	\item \textbf{Celarent.} No G are F. All H are G. So: No H are F
	\item \textbf{Ferio.} No G are F. Some H is G. So: Some H is not F
	\item \textbf{Darii.} All G are F. Some H is G. So: Some H is F.
	\item \textbf{Camestres.} All F are G. No H are G. So: No H are F.
	\item \textbf{Cesare.} No F are G. All H are G. So: No H are F.
	\item \textbf{Baroko.} All F are G. Some H is not G. So: Some H is not F.
	\item \textbf{Festino.} No F are G. Some H are G. So: Some H is not F.
	\item \textbf{Datisi.} All G are F. Some G is H. So: Some H is F.
	\item \textbf{Disamis.} Some G is F. All G are H. So: Some H is F.
	\item \textbf{Ferison.} No G are F. Some G is H. So: Some H is not F.
	\item \textbf{Bokardo.} Some G is not F. All G are H. So:  Some H is not F.
	\item \textbf{Camenes.} All F are G. No G are H So: No H is F.
	\item \textbf{Dimaris.} Some F is G. All G are H. So: Some H is F.
	\item \textbf{Fresison.} No F are G. Some G is H. So: Some H is not F.
\end{ebullet}
Symbolise each argument in FOL.

\

\problempart
\label{pr.FOLvegetarians}
Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] people
\item[K] \gap{1} knows the combination to the safe
\item[S] \gap{1} is a spy
\item[V] \gap{1} is a vegetarian
%\item[Txy] \gap{x} trusts \gap{y}.
\item[h] Hofthor
\item[i] Ingmar
\end{ekey}
symbolise the following sentences in FOL:
\begin{earg}
\item Neither Hofthor nor Ingmar is a vegetarian.
\item No spy knows the combination to the safe.
\item No one knows the combination to the safe unless Ingmar does.
\item Hofthor is a spy, but no vegetarian is a spy.
\end{earg}
\problempart\label{pr.FOLalligators}
Using this symbolisation key:
\begin{ekey}
\item[\text{domain}] all animals
\item[A] \gap{1} is an alligator.
\item[M] \gap{1} is a monkey.
\item[R] \gap{1} is a reptile.
\item[Z] \gap{1} lives at the zoo.
\item[a] Amos
\item[b] Bouncer
\item[c] Cleo
\end{ekey}
symbolise each of the following sentences in FOL:
\begin{earg}
\item Amos, Bouncer, and Cleo all live at the zoo. 
\item Bouncer is a reptile, but not an alligator. 
%\item If Cleo loves Bouncer, then Bouncer is a monkey. 
%\item If both Bouncer and Cleo are alligators, then Amos loves them both.
\item Some reptile lives at the zoo. 
\item Every alligator is a reptile. 
\item Any animal that lives at the zoo is either a monkey or an alligator. 
\item There are reptiles which are not alligators.
%\item Cleo loves a reptile.
%\item Bouncer loves all the monkeys that live at the zoo.
%\item All the monkeys that Amos loves love him back.
\item If any animal is an reptile, then Amos is.
\item If any animal is an alligator, then it is a reptile.
%\item Every monkey that Cleo loves is also loved by Amos.
%\item There is a monkey that loves Bouncer, but sadly Bouncer does not reciprocate this love.
\end{earg}


\problempart
\label{pr.FOLarguments}
For each argument, write a symbolisation key and symbolise the argument in FOL.
\begin{earg}
\item Willard is a logician. All logicians wear funny hats. So Willard wears a funny hat
\item Nothing on my desk escapes my attention. There is a computer on my desk. As such, there is a computer that does not escape my attention.
\item All my dreams are black and white. Old TV shows are in black and white. Therefore, some of my dreams are old TV shows.
\item Neither Holmes nor Watson has been to Australia. A person could see a kangaroo only if they had been to Australia or to a zoo. Although Watson has not seen a kangaroo, Holmes has. Therefore, Holmes has been to a zoo.
\item No one expects the Spanish Inquisition. No one knows the troubles I've seen. Therefore, anyone who expects the Spanish Inquisition knows the troubles I've seen.
\item All babies are illogical. Nobody who is illogical can manage a crocodile. Berthold is a baby. Therefore, Berthold is unable to manage a crocodile.
\end{earg}



\chapter{Multiple generality}\label{s:MultipleGenerality}
So far, we have only considered sentences that require one-place predicates and one quantifier. The full power of FOL really comes out when we start to use many-place predicates and multiple quantifiers. For this insight, we largely have Gottlob Frege (1879) to thank, but also Peirce.


\section{Many-placed predicates}
All of the predicates that we have considered so far concern properties that objects might have. The predicates have one gap in them, and to make a sentence, we simply need to slot in one name. They are \define{one-place} predicates.

But other predicates concern the \emph{relation} between two things. Here are some examples of relational predicates in English:
	\begin{quote}
		\blank\ loves \blank\\
		\blank\ is to the left of \blank\\
		\blank\ is in debt to \blank
	\end{quote}
These are \define{two-place} predicates. They need to be filled in with two terms in order to make a sentence. Conversely, if we start with an English sentence containing many singular terms, we can remove two singular terms, to obtain different two-place predicates. Consider the sentence `Vinnie borrowed the family car from Nunzio'. By deleting two singular terms, we can obtain any of three different two-place predicates
	\begin{quote}
		Vinnie borrowed \blank\ from \blank\\
		\blank\ borrowed the family car from \blank\\
		\blank\ borrowed \blank\ from Nunzio
	\end{quote}
And by removing all three singular terms, we  obtain a \define{three-place} predicate:
	\begin{quote}
		\blank\ borrowed \blank\ from \blank
	\end{quote}
Indeed, there is no in principle upper limit on the number of places that our predicates may contain.

\section{Mind the gap(s)!}
There is a little foible with the above. I have used the same symbol, `\blank', to indicate a gap formed by deleting a term from a sentence. However, as Frege emphasised, these are \emph{different} gaps. To obtain a sentence, we can fill them in with the same term, but we can equally fill them in with different terms, and in various different orders. These are three perfectly perfectly good sentences, obtained by filling in the gaps in `\blank\ loves \blank{}' in different ways; but they all have distinctively different meanings:
	\begin{earg}
	\item[\ex{terms3}] Karl loves Imre.
	\item[\ex{terms3b}] Imre loves Karl.
	\item[\ex{terms3a}] Karl loves Karl.
\end{earg}
The point is that we need to keep track of the gaps in predicates, so that we can keep track of how we are filling them in. To keep track of the gaps, I assign them numbers. And my method is explained by example. Suppose I want to symbolise the preceding sentences. Then I might start with the following representation key:
	\begin{ekey}
		\item[\text{domain}] people
		\item[i] Imre
		\item[k] Karl
		\item[L] \gap{1} loves \gap{2}
	\end{ekey}
Sentence \ref{terms3} will be symbolised by `$Lki$', sentence \ref{terms3b} will be symbolised by `$Lik$', and sentence \ref{terms3a} will be symbolised by `$Lkk$'. Here are a few more sentences that I can symbolise with the same key:
\begin{earg}
	\item[\ex{terms4}] Imre loves himself.
	\item[\ex{terms5}] Karl loves Imre, but not vice versa.
	\item[\ex{terms6}] Karl is loved by Imre.
\end{earg}
Sentence \ref{terms4} can be paraphrased as `Imre loves Imre', and so symbolised by `$Lii$'. Sentence \ref{terms5} is a conjunction. We can paraphrase it as `Karl loves Imre, and Imre does not love Karl', and so symbolise it as `$Lki \eand \enot Lik$'. Sentence \ref{terms6} can be paraphrased by `Imre loves Karl', and so symbolised as `$Lik$'. In this last case, of course, we have lots the difference in \emph{tone} between the active and passive voice; but we have at least preserved the truth conditions.

But the relationship between `Imre loves Karl' and `Karl is loved by Imre' highlights something important. To see what, suppose we add another entry to our symbolisation key:
	\begin{ekey}
		\item[M] \gap{2} loves \gap{1}
	\end{ekey}
The entry for `$M$' uses exactly the same English word---`loves'---as the entry for `$L$'. \emph{But the gaps have been swapped around!} (Just look closely at the subscripts.) And this \emph{matters}.

To explain: when we see a sentence like `$Lki$', we are being told to take the \emph{first} name (i.e.\ `$k$') and associate its value (i.e.\ Karl) with the gap labelled `$1$', then take the \emph{second} name (i.e.\ `$i$') and associate its value (i.e.\ Imre) with the gap labelled `$2$', and so come up with: \emph{Karl loves Imre}. The sentence `$Mik$' also tells us to take the \emph{first} name (i.e.\ `$i$') and plug its value into the gap labelled `$1$', and take the \emph{second} name (i.e.\ `$k$) and plug its value into the gap labelled `$2$', and so come up with: \emph{Imre loves Karl}. 

So, `$Lik$' and `$Mki$' {both} symbolise `Imre loves Karl', whereas `$Lki$' and `$Mik$'  {both} symbolise `Karl loves Imre'. Since love can be unrequited, these are different claims. 

One last example might be helpful. Suppose we add this to our symbolisation key: 
\begin{ekey}
	\item[P] \gap{1} prefers \gap{1} to \gap{2}
\end{ekey}
Now the sentence `$Pik$' symbolises `Imre prefers Imre to Karl', and `$Pki$' symbolises `Karl prefers Karl to Imre'.  And note that we could have achieved the same effect, if we had instead specified:
\begin{ekey}
	\item[P] \gap{1} prefers themselves to \gap{2}
\end{ekey}
In any case, the overall moral of this is simple. \emph{When dealing with predicates with more than one place, pay careful attention to the order of the gaps!}

\section{The order of quantifiers}
Consider the sentence `everyone loves someone'. This is potentially ambiguous. It might mean either of the following:
	\begin{earg}
		\item[\ex{lovecycle}] For every person, there is some person whom the former loves
		\item[\ex{loveconverge}] There is some particular person whom every person loves
	\end{earg}
Sentence \ref{lovecycle} can be symbolised by `$\forall x \exists y Lxy$', and would be true of a love-triangle. For example, suppose that our domain of discourse is restricted to Imre, Juan and Karl. Suppose also that Karl loves Imre but not Juan, that Imre loves Juan but not Karl, and that Juan loves Karl but not Imre. Then sentence \ref{lovecycle} will be true. 

Sentence \ref{loveconverge} can be symbolised by `$\exists y \forall x Lxy$'. Sentence \ref{loveconverge} is \emph{not} true in the situation just described. Again, suppose that our domain of discourse is restricted to Imre, Juan and Karl. Then all of Juan, Imre and Karl must converge on (at least) one object of love. 

The point of the example is to illustrate that the order of the quantifiers matters a great deal. Indeed, to switch them around is called a \emph{quantifier shift fallacy}. Here is an example, which comes up in various forms throughout the philosophical literature:
	\begin{earg}
		\item[] For every person, there is some truth they cannot know. \hfill ($\forall \exists$)
		\item[So:] There is some particular truth that no person can know. \hfill ($\exists \forall$)
	\end{earg}
This argument form is obviously invalid. It's just as bad as:\footnote{Thanks to Rob Trueman for the example.}
	\begin{earg}
		\item[] Every dog has its day. \hfill ($\forall \exists$)
		\item[So:] There is a day for all the dogs. \hfill ($\exists \forall$)
	\end{earg}
The moral is simple. \emph{Take care with the order of your quantifiers!}

%The fallacies, though, arise only when we swap around universal with existential quantifiers.  does not much matter within a single block of quantifiers. Using the same scheme, compare `$\exists x \exists y Lxy$' and `$\exists y \exists x Lxy$'. These would naturally symbolise the English sentences `there is someone who loves someone' and `there is someone whom is loved by someone', respectively. But, though these differ in nuance, they are true in exactly the same situations. (Similar comments apply to the universal quantifier.)


\section{Stepping-stones to symbolisation}
As we are starting to see, symbolisation in FOL can become a bit tricky. So, when symbolising a complex sentence, I recommend laying down several stepping-stones. As usual, the idea is best illustrated by example. Consider this symbolisation key:
\begin{ekey}
\item[\text{domain}] people and dogs
\item[D] \gap{1} is a dog
\item[F] \gap{1} is a friend of \gap{2}
\item[O] \gap{1} owns \gap{2}
\item[g] Geraldo
\end{ekey}
And now let's try to symbolise these sentences:
\begin{earg}
\item[\ex{dog2}] Geraldo is a dog owner.
\item[\ex{dog3}] Someone is a dog owner.
\item[\ex{dog4}] All of Geraldo's friends are dog owners.
\item[\ex{dog5}] Every dog owner is the friend of a dog owner.
\item[\ex{dog6}] Every dog owner's friend owns a dog of a friend.
\end{earg}
Sentence \ref{dog2} can be paraphrased as, `There is a dog that Geraldo owns'. This can be symbolised by `$\exists x(Dx \eand Ogx)$'.

Sentence \ref{dog3} can be paraphrased as, `There is some y such that y is a dog owner'. Dealing with part of this, we might write `$\exists y(y\text{ is a dog owner})$'. Now the fragment we have left as `$y$ is a dog owner' is much like sentence \ref{dog2}, except that it is not specifically about Geraldo. So we can symbolise sentence \ref{dog3} by:
$$\exists y \exists x(Dx \eand Oyx)$$
I need to pause to clarify something here. In working out how to symbolise the last sentence, we wrote down `$\exists y(y\text{ is a dog owner})$'. To be very clear: this is \emph{neither} an FOL sentence \emph{nor} an English sentence: it uses bits of FOL (`$\exists$', `$y$') and bits of English (`dog owner'). It is really is \emph{just a stepping-stone} on the way to symbolising the entire English sentence with a FOL sentence. You should regard it as a bit of rough-working-out, on a par with the doodles that you might absent-mindedly draw in the margin of this book, whilst you are concentrating fiercely on some problem.  

Sentence \ref{dog4} can be paraphrased as, `Everyone who is a friend of Geraldo is a dog owner'. Using our stepping-stone tactic, we might write 
$$\forall x \bigl[Fxg \eif x \text{ is a dog owner}\bigr]$$
Now the fragment that we have left to deal with, `$x$ is a dog owner', is structurally just like sentence \ref{dog2}. But it would be a mistake for us simply to write 
$$\forall x \bigl[Fxg \eif \exists x(Dx \eand Oxx)\bigr]$$
for we would here have a \emph{clash of variables}. The scope of the universal quantifier, `$\forall x$', is the entire conditional, so the `$x$' in `$Dx$' should be governed by that. But `$Dx$' also falls under the scope of the existential quantifier `$\exists x$', so the `$x$' in `$Dx$' should be governed by that. And now confusion reigns: which `$x$' are we talking about? Suddenly the sentence would be ambiguous (if it is even meaningful at all), and logicians hate ambiguity. The broad moral is that a single variable cannot serve two masters simultaneously. 

To continue our symbolisation, then, we must choose some different variable for our existential quantifier. What we want is something like:
$$\forall x\bigl[Fxg \eif\exists z(Dz \eand Oxz)\bigr]$$
and this adequately symbolises sentence \ref{dog4}.

Sentence \ref{dog5} can be paraphrased as `For any x that is a dog owner, there is a dog owner who is a friend of x'. Using our stepping-stone tactic, this becomes 
$$\forall x\bigl[\mbox{$x$ is a dog owner}\eif\exists y(\mbox{$y$ is a dog owner}\eand Fyx)\bigr]$$
Completing the symbolisation, we end up with
$$\forall x\bigl[\exists z(Dz \eand Oxz)\eif\exists y\bigl(\exists z(Dz \eand Oyz)\eand Fyx\bigr)\bigr]$$
Note that we have used the same letter, `$z$', in both the antecedent and the consequent of the conditional, but that these are governed by two different quantifiers. This is ok: there is no clash here, because is clear which quantifier the letter falls under. We might graphically represent the scope of the quantifiers thus:
$$\overbrace{\forall x\bigl[\overbrace{\exists z(Dz \eand Oxz)}^{\text{scope of 1st `}\exists z\text{'}}\eif \overbrace{\exists y(\overbrace{\exists z(Dz \eand Oyz)}^{\text{scope of 2nd `}\exists z\text{'}}\eand Fyx)\bigr]}^{\text{scope of `}\exists y\text{'}}}^{\text{scope of `}\forall x\text{'}}$$
This shows that no variable is being forced to serve two masters simultaneously.

Sentence \ref{dog6} is the trickiest yet. First we paraphrase it as `For any x that is a friend of a dog owner, x owns a dog which is also owned by a friend of x'. Using our stepping-stone tactic, this becomes:
$$\forall x\bigl[x\text{ is a friend of a dog owner}\eif x\text{ owns a dog which is owned by a friend of }x\bigr]$$
Breaking this down a bit more:
$$\forall x\bigl[\exists y(Fxy \eand y\text{ is a dog owner})\eif \exists y(Dy \eand Oxy \eand y\text{ is owned by a friend of }x)\bigr]$$
And a bit more: 
$$\forall x\bigl[\exists y(Fxy \eand \exists z(Dz \eand Oyz)) \eif \exists y(Dy \eand Oxy \eand \exists z(Fzx \eand Ozy))\bigr]$$
And we are done!

\practiceproblems
\problempart
Using this symbolisation key:
\begin{ekey}
\item[\text{domain}] all animals
\item[A] \gap{1} is an alligator
\item[M] \gap{1} is a monkey
\item[R] \gap{1} is a reptile
\item[Z] \gap{1} lives at the zoo
\item[L] \gap{1} loves \gap{2}
\item[a] Amos
\item[b] Bouncer
\item[c] Cleo
\end{ekey}
symbolise each of the following sentences in FOL:
\begin{earg}
%\item Amos, Bouncer, and Cleo all live at the zoo. 
%\item Bouncer is a reptile, but not an alligator. 
\item If Cleo loves Bouncer, then Bouncer is a monkey. 
\item If both Bouncer and Cleo are alligators, then Amos loves them both.
%\item Some reptile lives at the zoo. 
%\item Every alligator is a reptile. 
%\item Any animal that lives at the zoo is either a monkey or an alligator. 
%\item There are reptiles which are not alligators.
\item Cleo loves a reptile.
\item Bouncer loves all the monkeys that live at the zoo.
\item All the monkeys that Amos loves love him back.
%\item If any animal is an reptile, then Amos is.
%\item If any animal is an alligator, then it is a reptile.
\item Every monkey that Cleo loves is also loved by Amos.
\item There is a monkey that loves Bouncer, but sadly Bouncer does not reciprocate this love.
\end{earg}

\problempart 
Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] all animals
\item[D] \gap{1} is a dog
\item[S] \gap{1} likes samurai movies
\item[L] \gap{1} is larger than \gap{2}
\item[b] Bertie
\item[e] Emerson
\item[f] Fergis
\end{ekey}
symbolise the following sentences in FOL:
\begin{earg}
\item Bertie is a dog who likes samurai movies.
\item Bertie, Emerson, and Fergis are all dogs.
\item Emerson is larger than Bertie, and Fergis is larger than Emerson.
\item All dogs like samurai movies.
\item Only dogs like samurai movies.
\item There is a dog that is larger than Emerson.
\item If there is a dog larger than Fergis, then there is a dog larger than Emerson.
\item No animal that likes samurai movies is larger than Emerson.
\item No dog is larger than Fergis.
\item Any animal that dislikes samurai movies is larger than Bertie.
\item There is an animal that is between Bertie and Emerson in size.
\item There is no dog that is between Bertie and Emerson in size.
\item No dog is larger than itself.
\item Every dog is larger than some dog.
\item There is an animal that is smaller than every dog.
\item If there is an animal that is larger than any dog, then that animal does not like samurai movies.
\end{earg}

\problempart
Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] people and dishes at a potluck
\item[R] \gap{1} has run out.
\item[T] \gap{1} is on the table.
\item[F] \gap{1} is food.
\item[P] \gap{1} is a person.
\item[L] \gap{1} likes \gap{2}.
\item[e] Eli
\item[f] Francesca
\item[g] the guacamole
\end{ekey}
symbolise the following English sentences in FOL:
\begin{earg}
\item All the food is on the table.
\item If the guacamole has not run out, then it is on the table.
\item Everyone likes the guacamole.
\item If anyone likes the guacamole, then Eli does.
\item Francesca only likes the dishes that have run out.
\item Francesca likes no one, and no one likes Francesca.
\item Eli likes anyone who likes the guacamole.
\item Eli likes anyone who likes the people that he likes.
\item If there is a person on the table already, then all of the food must have run out.
\end{earg}

\problempart
\label{pr.FOLballet}
Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] people
\item[D] \gap{1} dances ballet.
\item[F] \gap{1} is female.
\item[M] \gap{1} is male.
\item[C] \gap{1} is a child of \gap{2}.
\item[S] \gap{1} is a sibling of \gap{2}.
\item[e] Elmer
\item[j] Jane
\item[p] Patrick
\end{ekey}
symbolise the following arguments in FOL:
\begin{earg}
\item All of Patrick's children are ballet dancers.
\item Jane is Patrick's daughter.
\item Patrick has a daughter.
\item Jane is an only child.
\item All of Patrick's sons dance ballet.
\item Patrick has no sons.
\item Jane is Elmer's niece.
\item Patrick is Elmer's brother.
\item Patrick's brothers have no children.
\item Jane is an aunt.
\item Everyone who dances ballet has a brother who also dances ballet.
\item Every woman who dances ballet is the child of someone who dances ballet.
\end{earg}


\chapter{Identity}
\label{sec.identity}

Consider this sentence:
\begin{earg}
\item[\ex{else1}] Pavel owes money to everyone
\end{earg}
Let the domain be people; this will allow us to symbolise `everyone' with a universal quantifier. Offering the symbolisation key:
	\begin{ekey}
		\item[O] \gap{1} owes money to \gap{2}
		\item[p] Pavel
	\end{ekey}
we can symbolise sentence \ref{else1} by `$\forall x Opx$'. But this has a (perhaps) odd consequence. It requires that Pavel owes money to every member of the domain (whatever the domain may be). The domain certainly includes Pavel. So this entails that Pavel owes money to himself. And maybe we did not want to say that. Maybe we meant to say:
	\begin{earg}
		\item[\ex{else1b}] Pavel owes money to everyone \emph{else}
		\item[\ex{else1c}] Pavel owes money to everyone \emph{other than} Pavel
		\item[\ex{else1d}] Pavel owes money to everyone \emph{except} Pavel himself
	\end{earg}
But we do not have any way for dealing with the italicised words yet. The solution is to add another symbol to FOL. 

\section{Adding identity}

The symbol `$=$' will be a two-place predicate. Since it will have a special meaning, we shall write it a bit differently: we put it \emph{between} two terms, rather than out front. (This should also be familiar; consider a mathematical equation like $\frac{1}{2} = 0.5$.) And the special meaning for `$=$' is given by the fact that we \emph{always} adopt the following symbolisation key:
	\begin{ekey}
		\item[=] \gap{1} is identical to \gap{2}
	\end{ekey}
This does not mean \emph{merely} that the objects in question are indistinguishable, or that all of the same things are true of them. Rather, it means that the objects in question are \emph{the very same} object.

To put this to use, suppose we want to symbolise this sentence:
\begin{earg}
\item[\ex{else2}] Pavel is Mister Checkov.
\end{earg}
Let us add to our symbolisation key:
	\begin{ekey}
		\item[c] Mister Checkov
	\end{ekey}
Now sentence \ref{else2} can be symbolised as `$p=c$'. This tells us that the names `$p$' and `$c$' both name the very same thing.

We can also now deal with sentences \ref{else1b}--\ref{else1d}. All of these sentences can be  paraphrased as `Everyone who is not Pavel is owed money by Pavel'. Paraphrasing some more, we get: `For all x, if x is not Pavel, then x is owed money by Pavel'. Now that we are armed with our new identity symbol, we can symbolise this as `$\forall x (\enot x = p \eif Opx)$'.

This last sentence contains the formula `$\enot x = p$'. And that might look a bit strange, because the symbol that comes immediately after the `$\enot$' is a variable, rather than a predicate. But this is no problem. We are simply negating the entire formula, `$x = p$'. 

In addition to sentences that use the word `else', `other than' and `except', identity will be helpful when symbolising some sentences that contain the words `besides' and `only.' Consider these examples:

\begin{earg}
\item[\ex{else3}] No one besides Pavel owes money to Hikaru.
\item[\ex{else4}] Only Pavel owes Hikaru money.
\end{earg}
Letting `$h$' name Hikaru, sentence \ref{else3} can be paraphrased as, `No one who is not Pavel owes money to Hikaru'. This can be symbolised by `$\enot\exists x(\enot x = p \eand Oxh)$'. Equally, sentence \ref{else3} can be paraphrased as `for all x, if x owes money to Hikaru, then x is Pavel'. Then it can be symbolised as `$\forall x (Oxh \eif x = p)$'.

Sentence \ref{else4} can be treated similarly. But there is one subtlety here. Do either sentence \ref{else3} or \ref{else4} entail that Pavel himself owes money to Hikaru? 

\section{There are at least\ldots}
We can also use identity to say how many things there are of a particular kind. For example, consider these sentences:
\begin{earg}
\item[\ex{atleast1}] There is at least one apple
\item[\ex{atleast2}] There are at least two apples
\item[\ex{atleast3}] There are at least three apples
\end{earg}
We shall use the symbolisation key:
	\begin{ekey}
		\item[A] \gap{1} is an apple
	\end{ekey}
Sentence \ref{atleast1} does not require identity. It can be adequately symbolised by `$\exists x Ax$': There is some apple; perhaps many, but at least one.

It might be tempting to also translate sentence \ref{atleast2} without identity. But consider the sentence `$\exists x \exists y(Ax \eand Ay)$'. Roughly, this says that there is some apple x in the domain and some apple y in the domain. Since nothing precludes these from being one and the same apple, this would be true even if there were only one apple. To make sure that we are dealing with \emph{different} apples, we need to use identity. Sentence \ref{atleast2} needs to say that the apples are distinct, so it can be symbolised by `$\exists x \exists y(Ax \eand Ay \eand \enot x = y)$'.

Sentence \ref{atleast3} requires talking about three different apples. Now we need three existential quantifiers, and we need to make sure that each will pick out something different: `$\exists x \exists y\exists z(Ax \eand Ay \eand Az \eand \enot x = y \eand \enot y = z \eand \enot x = z)$'.

\section{There are at most\ldots}
Now consider these sentences:
\begin{earg}
	\item[\ex{atmost1}] There is at most one apple
	\item[\ex{atmost2}] There are at most two apples
\end{earg}
Sentence \ref{atmost1} can be paraphrased as, `It is not the case that there are at least \emph{two} apples'. This is just the negation of sentence \ref{atleast2}: 
$$\enot \exists x \exists y(Ax \eand Ay \eand \enot x = y)$$
But sentence \ref{atmost1} can also be approached in another way. It means that if you pick out an object and it's an apple, and then you pick out an object and it's also an apple, you must have picked out the same object both times. With this in mind, it can be symbolised by
$$\forall x\forall y\bigl[(Ax \eand Ay) \eif x=y\bigr]$$
The two sentences will turn out to be logically equivalent.

Similarly, sentence \ref{atmost2} can be approached in two equivalent ways. It can be paraphrased as `It is not the case that there are \emph{three} or more distinct apples', so we can offer:
$$\enot \exists x \exists y\exists z(Ax \eand Ay \eand Az \eand \enot x = y \eand \enot y = z \eand \enot x = z)$$
Or, we can read it as saying that if you pick out an apple, and an apple, and an apple, then you will have picked out (at least) one of these objects more than once. Thus:
$$\forall x\forall y\forall z\bigl[(Ax \eand Ay \eand Az) \eif (x=y \eor x=z \eor y=z)\bigr]$$


\section{There are exactly\ldots}
We can now consider precise statements of numerical quantity, like:
\begin{earg}
\item[\ex{exactly1}] There is exactly one apple.
\item[\ex{exactly2}] There are exactly two apples.
\item[\ex{exactly3}] There are exactly three apples.
\end{earg}
Sentence \ref{exactly1} can be paraphrased as, `There is \emph{at least} one apple and there is \emph{at most} one apple'. This is just the conjunction of sentence \ref{atleast1} and sentence \ref{atmost1}. So we can offer:
$$\exists x Ax \eand \forall x\forall y\bigl[(Ax \eand Ay) \eif x=y\bigr]$$
But it is perhaps more straightforward to paraphrase sentence \ref{exactly1} as, `There is a thing x which is an apple, and everything which is an apple is just x itself'. Thought of in this way, we offer: 
$$\exists x\bigl[Ax \eand \forall y(Ay \eif x= y)\bigr]$$
Similarly, sentence \ref{exactly2} may be paraphrased as, `There are \emph{at least} two apples, and there are \emph{at most} two apples'. Thus we could offer 
$$\exists x \exists y(Ax \eand Ay \eand \enot x = y) \eand \forall x\forall y\forall z\bigl[(Ax \eand Ay \eand Az) \eif (x=y \eor x=z \eor y=z)\bigr]$$
More efficiently, though, we can paraphrase it as `There are at least two different apples, and every apple is one of those two apples'. Then we offer:
$$\exists x\exists y\bigl[Ax \eand Ay \eand \enot x = y \eand \forall z(Az \eif ( x= z \eor y = z)\bigr]$$
Finally, consider these sentence:
\begin{earg}
\item[\ex{exactly2things}] There are exactly two things
\item[\ex{exactly2objects}] There are exactly two objects
\end{earg}
It might be tempting to add a predicate to our symbolisation key, to symbolise the English predicate `\blank\ is a thing' or `\blank\ is an object'. But this is unnecessary. Words like `thing' and `object' do not sort wheat from chaff: they apply trivially to everything, which is to say, they apply trivially to every thing. So we can symbolise either sentence with either of the following:
	\begin{center}
		$\exists x \exists y \enot x = y \eand \enot \exists x \exists y \exists z (\enot x = y \eand \enot y = z \eand \enot x = z)$\\
		$\exists x \exists y \bigl[\enot x = y \eand \forall z(x=z \eor y = z)\bigr]$
	\end{center}

\practiceproblems

\problempart Explain why:
	\begin{ebullet}
		\item   `$\exists x \forall y(Ay \eiff x= y)$' is a good symbolisation of `there is exactly one apple'.
		\item `$\exists x \exists y \bigl[\enot x = y \eand \forall z(Az \eiff (x= z \eor y = z)\bigr]$' is a good symbolisation of `there are exactly two apples'.
	\end{ebullet}		


\chapter{Definite descriptions}\label{subsec.defdesc}
Consider sentences like:
	\begin{earg}
		\item[\ex{traitor1}] Nick is the traitor.
		\item[\ex{traitor2}] The traitor went to Cambridge.
		\item[\ex{traitor3}] The traitor is the deputy 
	\end{earg}
These are definite descriptions: they are meant to pick out a \emph{unique} object. They should be contrasted with \emph{indefinite} descriptions, such as `Nick  is \emph{a} traitor'. They should equally be contrasted with \emph{generics}, such as `\emph{The} whale is a mammal' (when it's inappropriate to ask \emph{which} whale). The question we face is: how should we deal with definite descriptions in FOL?


\section{Treating definite descriptions as terms}
One option would be to introduce new names whenever we come across a definite description. This is probably not a great idea. We know that \emph{the} traitor---whoever it is---is indeed \emph{a} traitor. We want to preserve that information in our symbolisation.

A second option would be to use a \emph{new} definite description operator, such as `$\maththe$'. The idea would be to symbolise `the F' as `$\maththe xFx$' (think `the $x$ such that $Fx$'); or to symbolise `the G' as `$\maththe xGx$', etc. Expressions of the form $\maththe \meta{x} \meta{A}\meta{x}$ would then behave like names. If we were to follow this path, then we could use the following symbolisation key:
	\begin{ekey}
		\item[\text{domain}] people
		\item[T] \gap{1} is a traitor
		\item[D] \gap{1} is a deputy
		\item[C] \gap{1} went to Cambridge
		\item[n] Nick
	\end{ekey}
Then, we could symbolise sentence \ref{traitor1} with `$\maththe x Tx = n$', sentence \ref{traitor2} with `$C\maththe xTx$', and sentence \ref{traitor3} with `$\maththe x Tx = \maththe x Dx$'. 

However, it would be nice if we didn't have to add a new symbol to FOL. And we might be able to make do without one.

\section{Russell's analysis}
Bertrand Russell offered an \emph{analysis} of definite descriptions. Very briefly put, he observed that, when we say `the F' in the context of a definite description, our aim is to pick out the \emph{one and only} thing that is F (in the appropriate context). Thus Russell analysed the notion of a definite description as follows:\footnote{Bertrand Russell, `On Denoting', 1905, \emph{Mind 14}, pp.\ 479--93; also Russell, \emph{Introduction to Mathematical Philosophy}, 1919, London: Allen and Unwin, ch.\ 16.}
	\begin{align*}
		\text{the F is G \textbf{iff} }&\text{there is at least one F, \emph{and}}\\
	&\text{there is at most one F, \emph{and}}\\	
	&\text{every F is G}
\end{align*}
Note a very important feature of this analysis: \emph{`the' does not appear on the right-side of the equivalence.} Russell is aiming to provide an understanding of definite descriptions, in terms that do not presuppose them. 

Now, one might worry that I can say `the table is brown' without implying that there is one and only one table in the universe. But this is not (yet) a fantastic counterexample to Russell's analysis. The domain of discourse is likely to be restricted by context (e.g.\ to salient objects in my vicinity).

If we accept Russell's analysis of definite descriptions, then we can symbolise sentences of the form `the F is G' using our strategy for numerical quantification in FOL. After all, we can deal with the three conjuncts on the right-hand side of Russell's analysis as follows:
	$$\exists x Fx \eand \forall x \forall y ((Fx \eand Fy) \eif x = y) \eand \forall x (Fx \eif Gx)$$
In fact, we could express the same point rather more crisply, by recognising that the first two conjuncts just amount to the claim that there is \emph{exactly} one F, and that the last conjunct tells us that that object is G. So, equivalently, we could offer:
	$$\exists x \bigl[Fx \eand \forall y (Fy \eif x = y) \eand Gx\bigr]$$
Using these sorts of techniques, we can now symbolise sentences \ref{traitor1}--\ref{traitor3} without using any new-fangled fancy operator, such as `$\maththe$'. 

Sentence \ref{traitor1} is exactly like the examples we have just considered. So we would symbolise it by `$\exists x (Tx \eand \forall y(Ty \eif x = y) \eand x = n)$'. 

Sentence \ref{traitor2} poses no problems either: `$\exists x (Tx \eand \forall y(Ty \eif x = y) \eand Cx)$'.

Sentence \ref{traitor3} is a little trickier, because it links two definite descriptions. But, deploying  Russell's analysis, it can be paraphrased by `there is exactly one traitor, x, and there is exactly one deputy, y, and x = y'. So we can symbolise it by: 
$$\exists x \exists y \bigl(\bigl[Tx \eand \forall z(Tz \eif x = z)\bigr] \eand \bigl[Dy \eand \forall z(Dz \eif y = z)\bigr] \eand x = y\bigr)$$
Note that the formula `$x = y$' must fall within the scope of both quantifiers!

\section{Empty definite descriptions}
One of the nice features of Russell's analysis is that it allows us to handle \emph{empty} definite descriptions neatly. 

France has no king at present. Now, if we were to introduce a name, `$k$', to name the present King of France, then everything would go wrong: remember from \S\ref{s:FOLBuildingBlocks} that a name must always pick out  some object in the domain, and whatever we choose as our domain, it will contain no present kings of France. 

Russell's analysis neatly avoids this problem. Russell tells us to treat definite descriptions using predicates and quantifiers, instead of names. Since predicates can be empty (see \S\ref{s:MoreMonadic}), this means that no difficulty now arises when the definite description is empty. 

Indeed, Russell's analysis helpfully highlights two ways to go wrong in a claim involving a definite description. To adapt an example from Stephen Neale (1990),\footnote{Neale, \emph{Descriptions}, 1990, Cambridge: MIT Press.}  suppose I, Tim Button, claim:
	\begin{earg}
		\item[\ex{kingdate}] The present king of France is my spouse
	\end{earg}
Using the following symbolisation key:
	\begin{ekey}
		\item[b] Tim
		\item[K] \gap{1} is a present king of France
		\item[M] \gap{1} is married to \gap{2}
	\end{ekey}
(NB: the symbolisation key speaks of \emph{a} present King of France, not \emph{the} present King of France; i.e.\ it employs indefinite, rather than definite, description.) Sentence \ref{kingdate} would be symbolised by `$\exists x (\forall y(Ky \eiff  x = y) \eand Bxb)$'. Now, this can be false in (at least) two ways, corresponding to these two different sentences:
	\begin{earg}
		\item[\ex{outernegation}] There is no one who is both the present King of France and Tim's spouse.
		\item[\ex{innernegation}] There is a unique present King of France, but he is not Tim's spouse.
	\end{earg}
Sentence \ref{outernegation} can be symbolised by `$\enot \exists x\bigl[Kx \eand \forall y(Ky \eif  x = y) \eand Mbx \bigr]$'. We might call this \emph{outer} negation, since the negation governs the entire sentence. Note that the sentence is true if there is no present King of France.

Sentence \ref{innernegation} can be symbolised by `$\exists x (Kx \eand \forall y(Ky \eif x = y) \eand \enot Mbx)$. We might call this \emph{inner} negation, since the negation occurs within the scope of the definite description. Note that its truth requires that there is a present King of France, albeit one who is not Tim's spouse.


\section{The adequacy of Russell's analysis}
How good is Russell's analysis of definite descriptions? This question has generated a substantial philosophical literature, but I shall content myself with two observations.

One worry focusses on Russell's treatment of \emph{empty} definite descriptions. If there are no Fs, then on Russell's analysis, both `the F is G' is and  `the F is non-G' are false. P.F.\ Strawson suggested that such sentences should not be regarded as false, exactly, but involve \emph{presupposition failure}, and so need to be treated as \emph{neither} true \emph{nor} false.\footnote{P.F.\ Strawson, `On Referring', 1950, \emph{Mind 59}, pp.\ 320--34.} 

If we agree with Strawson here, we shall need to revise our logic. For, in our logic, there are only two truth values (True and False), and every sentence is assigned exactly one of these truth values. 

But there is room to disagree with Strawson. Strawson is appealing to some linguistic intuitions, but it is not clear that they are very robust. For example: isn't it just \emph{false}, not `gappy', that the present King of France is my spouse?\footnote{This is Neale's (1990) line.}

Keith Donnellan raised a second sort of worry, which (very roughly) can be brought out by thinking about a case of mistaken identity.\footnote{Keith Donnellan, `Reference and Definite Descriptions', 1966, \emph{Philosophical Review 77}, pp.\ 281--304.} Two men stand in the corner: a very tall man drinking what looks like a gin martini; and a very short man drinking what looks like a pint of water. Seeing them, Malika says:
	\begin{earg}
		\item[\ex{gindrinker}] The gin-drinker is very tall!
	\end{earg}
Russell's analysis will have us render Malika's sentence as:
	\begin{earg}
		\item[\ref{gindrinker}$'$.] There is exactly one gin-drinker [in the corner], and whomever is a gin-drinker [in the corner] is very tall.
	\end{earg}
But now suppose that the very tall man is actually drinking \emph{water} from a martini glass; whereas the very short man is drinking a pint of (neat) gin. By Russell's analysis, Malika has said something false. But don't we want to say that Malika has said something \emph{true}? 

Again, one might wonder how clear our intuitions are on this case. We can all agree that Malika intended to pick out a particular man, and say something true of him (that he was tall). On Russell's analysis, she actually picked out a different man (the short one), and consequently said something false of him. But  maybe advocates of Russell's analysis only need to explain \emph{why} Malika's intentions were frustrated, and so why she said something false. This is easy enough to do:  Malika said something false because she had false beliefs about the men's drinks; if Malika's beliefs about the drinks had been true,  then she would have said something true.\footnote{For more, see Saul Kripke, `Speaker Reference and Semantic Reference', 1977.} 
%, in French et al (eds.), \emph{Contemporary Perspectives in the Philosophy of Language}, Minneapolis: University of Minnesota Press, pp.\ 6-27.}

To say much more here would lead us into deep philosophical waters. That would be no bad thing, but for now it would distract us from the immediate purpose of learning formal logic. So, for now, we shall stick with Russell's analysis of definite descriptions, when it comes to putting things into FOL. It is certainly the best that we can offer, without significantly revising our logic. And it is quite defensible as an analysis. 

\practiceproblems

\problempart
Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] people
\item[K] \gap{1} knows the combination to the safe.
\item[S] \gap{1} is a spy.
\item[V] \gap{1} is a vegetarian.
\item[T] \gap{1} trusts \gap{2}.
\item[h] Hofthor
\item[i] Ingmar
\end{ekey}
symbolise the following sentences in FOL:
\begin{earg}
\item Hofthor trusts a vegetarian.
\item Everyone who trusts Ingmar trusts a vegetarian.
\item Everyone who trusts Ingmar trusts someone who trusts a vegetarian.
\item Only Ingmar knows the combination to the safe.
\item Ingmar trusts Hofthor, but no one else.
\item The person who knows the combination to the safe is a vegetarian.
\item The person who knows the combination to the safe is not a spy.
\end{earg}

\problempart
\label{pr.FOLcards}
Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] cards in a standard deck
\item[B] \gap{1} is black.
\item[C] \gap{1} is a club.
\item[D] \gap{1} is a deuce.
\item[J] \gap{1} is a jack.
\item[M] \gap{1} is a man with an axe.
\item[O] \gap{1} is one-eyed.
\item[W] \gap{1} is wild.
\end{ekey}
symbolise each sentence in FOL:
\begin{earg}
\item All clubs are black cards.
\item There are no wild cards.
\item There are at least two clubs.
\item There is more than one one-eyed jack.
\item There are at most two one-eyed jacks.
\item There are two black jacks.
\item There are four deuces.
\item The deuce of clubs is a black card.
\item One-eyed jacks and the man with the axe are wild.
\item If the deuce of clubs is wild, then there is exactly one wild card.
\item The man with the axe is not a jack.
\item The deuce of clubs is not the man with the axe.
\end{earg}

\

\problempart Using the following symbolisation key:
\begin{ekey}
\item[\text{domain}] animals in the world
\item[B] \gap{1} is in Farmer Brown's field.
\item[H] \gap{1} is a horse.
\item[P] \gap{1} is a Pegasus.
\item[W] \gap{1} has wings.
\end{ekey}
symbolise the following sentences in FOL:
\begin{earg}
\item There are at least three horses in the world.
\item There are at least three animals in the world.
\item There is more than one horse in Farmer Brown's field.
\item There are three horses in Farmer Brown's field.
\item There is a single winged creature in Farmer Brown's field; any other creatures in the field must be wingless.
\item The Pegasus is a winged horse.
\item The animal in Farmer Brown's field is not a horse.
\item The horse in Farmer Brown's field does not have wings.
\end{earg}

\problempart
In this section, I symbolised `Nick is the traitor' by `$\exists x (Tx \eand \forall y(Ty \eif x = y) \eand x = n)$'. Explain why these would be equally good symbolisations:
	\begin{ebullet}
		\item $Tn \eand \forall y(Ty \eif n = y)$
		\item $\forall y(Ty \eiff y = n)$
	\end{ebullet}


\chapter{Sentences of FOL}\label{s:FOLSentences}
We know how to represent English sentences in FOL. The time has finally come to define the notion of a \emph{sentence} of FOL.

\section{Expressions}
There are six kinds of symbols in FOL:

\begin{center}
\begin{tabular}{l l}
Predicates & $A,B,C,\ldots,Z$\\
with subscripts, as needed & $A_1, B_1,Z_1,A_2,A_{25},J_{375},\ldots$\\
\\
Constants & $a,b,c,\ldots, r$\\
with subscripts, as needed & $a_1, b_{224}, h_7, m_{32},\ldots$\\
\\
Variables & $s, t, u, v, w, x,y,z$\\
with subscripts, as needed & $x_1, y_1, z_1, x_2,\ldots$\\
\\
Connectives & $\enot,\eand,\eor,\eif,\eiff$\\
\\
Brackets &( , )\\
\\
Quantifiers & $\forall, \exists$\\
\end{tabular}
\end{center}
We define an \define{expression of FOL} as any string of symbols of FOL. Take any of the symbols of FOL and write them down, in any order, and you have an expression.

\section{Terms and formulas}
In \S\ref{s:TFLSentences}, we went straight from the statement of the vocabulary of TFL to the definition of a sentence of TFL. In FOL, we shall have to go via an intermediary stage: via the notion of a  \emph{formula}. The intuitive idea is that a formula is any sentence, or anything which can be turned into a sentence by adding quantifiers out front. But this intuitive idea will take some time to unpack.

We start by defining the notion of a term.
	\factoidbox{A \define{term} is any name or any variable. }
So, here are some terms:
	$$a, b, x, x_1 x_2, y, y_{254}, z$$
We next need to define atomic formulas.
	\factoidbox{
		\begin{enumerate}
		\item If $\meta{R}$ is an $n$-place predicate and $\meta{t}_1, \meta{t}_2, \ldots, \meta{t}_n$ are terms, then $\meta{Rt}_1 \meta{t}_2 \ldots \meta{t}_n$ is an atomic formula.
		\item If $\meta{t}_1$ and $\meta{t}_2$ are terms, then $\meta{t}_1 = \meta{t}_2$ is an atomic formula.
		\item Nothing else is an atomic formula.
		\end{enumerate}}
This use of bold-italic-fonts follows the conventions laid down in \S\ref{s:UseMention}. So, `$\meta{R}$' is not itself a predicate of FOL. Rather, it is a symbol of our metalanguage (augmented English) which I am using here to talk about any predicate of FOL. Similarly, `$\meta{t}_1$' is not a term of FOL, but a symbol of the metalanguage that I am using to talk about any term of FOL. 

Now, let `$F$' be a one-place predicate, let `$G$' is a three-place predicate, and let `$S$' is a six-place predicate. Here are some atomic formulas:
	\begin{center}
		$x = a$\\
		$a = b$\\
		$Fx$\\
		$Fa$\\
		$Gxay$\\
		$Gaaa$\\
		$Sx_1 x_2 a b y x_1$\\
		$Sby_{254} z a a z$
	\end{center}
Once we know what atomic formulas are, we can offer recursion clauses to define arbitrary formulas. The first few clauses are exactly the same as for TFL.
	\factoidbox{
	\begin{enumerate}
		\item Every atomic formula is a formula. 
		\item If \meta{A} is a formula, then $\enot\meta{A}$ is a formula.
		\item If \meta{A} and \meta{B} are formulas, then $(\meta{A}\eand\meta{B})$ is a formula.
		\item If \meta{A} and \meta{B} are formulas, then $(\meta{A}\eor\meta{B})$ is a formula.
		\item If \meta{A} and \meta{B} are formulas, then $(\meta{A}\eif\meta{B})$ is a formula.
		\item If \meta{A} and \meta{B} are formulas, then $(\meta{A}\eiff\meta{B})$ is a formula.
		\item If \meta{A} is a formula, \meta{x} is a variable, \meta{A} contains at least one occurrence of \meta{x}, and \meta{A} contains neither $\forall \meta{x}$ nor $\exists \meta{x}$, then $\forall\meta{x}\meta{A}$ is a formula.
		\item If \meta{A} is a formula, \meta{x} is a variable, \meta{A} contains at least one occurrence of \meta{x}, and \meta{A} contains neither $\forall \meta{x}$ nor $\exists \meta{x}$, then $\exists\meta{x}\meta{A}$ is a formula.
		\item Nothing else is a formula.
	\end {enumerate}
	}
So, assuming again that `$F$' is a one-place predicate, `$G$' is a three-place predicate and `$H$' is a six place-predicate, here are some formulas:
	\begin{center}
		$Fx$\\
		$Gayz$\\
		$Syzyayx$\\
		$(Gayz \eif Syzyayx)$\\
		$\forall z (Gayz \eif Syzyayx)$\\
		$Fx \eiff \forall z (Gayz \eif Syzyayx)$\\
		$\exists y (Fx \eiff \forall z (Gayz \eif Syzyayx))$\\
		$\forall x \exists y (Fx \eiff \forall z (Gayz \eif Syzyayx))$		\end{center}
But this is \emph{not} a formula:
	\begin{center}
		$\forall x \exists x Gxxx$
	\end{center}
Certainly `$Gxxx$' is a formula. And `$\exists x Gxxx$' is therefore also a formula. But we cannot form a new formula by putting `$\forall x$' at the front. This violates the constraints on clause 7 of our recursive definition: `$\exists x Gxxx$' contains at least one occurrence of `$x$', but it already contains `$\exists x$'.

These constraints have the effect of ensuring that variables only serve one master at any one time (see \S\ref{s:MultipleGenerality}). And in fact, we can now give a formal definition of scope, which incorporates the definition of the scope of a quantifier. Here we follow the case of TFL, though we note that a logical operator can be either a connective or a quantifier:
	\factoidbox{
		The \define{main logical operator} in a formula is the operator that was introduced most recently, when that formula was constructed using the recursion rules.
		
		\

		The \define{scope} of a logical operator in a formula is the subformula for which that operator is the main logical operator.
	}
So we can graphically illustrate the scope of the quantifiers in the preceding example thus:
	$$\overbrace{\forall x \overbrace{\exists y (Fx \eiff \overbrace{\forall z (Gayz \eif Syzyayx)}^{\text{scope of `}\forall z\text{'}}}^{\text{scope of `}\exists y\text{'}})}^{\text{scope of `}\forall x\text{'}}$$

\section{Sentences}
Recall that we are largely concerned in logic with assertoric sentences: sentences that can be either true or false. Many formulas are not sentences. Consider the following symbolisation key:
	\begin{ekey}
		\item[\text{domain}] people
		\item[L] \gap{1} loves \gap{2}
		\item[b] Boris
	\end{ekey}
Consider the atomic formula `$Lzz$'. All atomic formula are formulas, so `$Lzz$' is a formula. But can it be true or false? You might think that it will be true just in case the person named by `$z$' loves herself, in the same way that `$Lbb$' is true just in case Boris (the person named by `$b$') loves himself. \emph{But `$z$' is a variable, and does not name anyone or any thing.}

Of course, if we put an existential quantifier out front, obtaining `$\exists zLzz$', then this would be true iff someone loves themselves. Equally, if we wrote `$\forall z Lzz$', this would be true iff everyone loves themselves. The point is that we need a quantifier to tell us how to deal with a variable. 

Let's make this idea precise.
	\factoidbox{
		An occurrence of a variable \meta{x} is \define{bound} iff it falls within the scope of either $\forall\meta{x}$ or $\exists\meta{x}$. A variable which is not bound is \define{free}.}
For example, consider the formula
	$$(\forall x(Ex \eor Dy) \eif \exists z(Ex \eif Lzx))$$
The scope of the universal quantifier `$\forall x$' is `$\forall x (Ex \eor Dy)$', so the first `$x$' is bound by the universal quantifier. However, the second and third occurrence of `$x$' are free. Equally, the `$y$' is free. The scope of the existential quantifier `$\exists z$' is `$(Ex \eif Lzx)$', so `$z$' is bound. 

Finally we can say the following.	
	\factoidbox{	
		A \define{sentence} of FOL is any formula of FOL that contains no free variables.
	}

\section{Bracketing conventions}

We will adopt the same notational conventions governing brackets that we did for TFL (see \S\ref{s:TFLSentences} and \S\ref{s:MoreBracketingConventions}.) 

First, we may omit the outermost brackets of a formula. 

Second, we may use square brackets, `[' and `]', in place of brackets to increase the readability of formulas. 

Third, we may omit brackets between each pair of conjuncts when writing long series of conjunctions. 

Fourth, we may omit brackets between each pair of disjuncts when writing long series of disjunctions.


\section{Superscripts on predicates}
Above, I said that an $n$-place predicate followed by $n$ terms is an atomic formula. But there is a small issue with this definition: the symbols we use for predicates do not, themselves, indicate how many places the predicate has. Indeed, in some places in this book, I have used the letter `$G$' as a one-place predicate; in other places I have used it as a three-place predicate. So, unless I state explicitly whether I want to use `$G$' as a one-place predicate or as a three place predicate, it is \emph{indeterminate} whether `$Ga$' is an atomic formula or not.

There is an easy way to avoid this, which many books adopt. Instead of saying that our predicates are just capital letters (with numerical subscripts as necessary), we could say that they are capital letters \emph{with numerical superscripts} (and with numerical subscripts as necessary). The purpose of the superscript would be to say explicitly how many places the predicate has. On this approach, `$G^1$' would be a one-place predicate, and `$G^3$' would be an (entirely different) three places predicate. They would need to have different entries in any symbolisation key. And `$G^1a$' would be an atomic formula, whereas `$G^3a$' would not; likewise `$G^3abc$' would be an atomic formula, and `$G^1abc$' would not. 

So, as I say, we \emph{could} add superscripts to all our predicates. This would have the advantage of making certain things completely explicit. However, it would have the disadvantage of making our formulas much harder to read; the superscripts would distract the eye. So, we will not bother to make this change. Our predicates will remain \emph{without} superscripts.  (And, in practice, any book which includes superscripts almost immediately stops including them!)

However, this leaves open a possibility of ambiguity. So, when any ambiguity could arise---in practice, very rarely---you should say, explicitly, how many places your predicate(s) have. 



\practiceproblems
\problempart
\label{pr.freeFOL}
Identify which variables are bound and which are free.
\begin{earg}
\item $\exists x Lxy \eand \forall y Lyx$
\item $\forall x Ax \eand Bx$
\item $\forall x (Ax \eand Bx) \eand \forall y(Cx \eand Dy)$
\item $\forall x\exists y[Rxy \eif (Jz \eand Kx)] \eor Ryx$
\item $\forall x_1(Mx_2 \eiff Lx_2x_1) \eand \exists x_2 Lx_3x_2$
\end{earg}