﻿ 3.2 Variables and quantifiers

### 3.2 Variables and quantifiers

#### Variables, open sentences, existential quantifier

Besides the predicate letters (“F”, “G”...) and the constants (“a”, “b”…), there is another type of symbols that play an important role in the symbolism of predicate logic. These are the so-called variables. The variables are a lot like constants, because they denote (refer to) things, but unlike them, they do it indefinitely. Most people have a contact with variables in school because the letters “x”, “y”... in mathematical equations are precisely variables that indefinitely denote any number. However, in logic variables are not limited to numbers – they can denote, in the same indefinite way, all sorts of things, whether abstract (such as numbers, properties, sets… etc.), or things existing in the space-time (such as Socrates, this chair… etc.). As variables are singular terms (their purpose is to denote, not to be true or false of things), we can place them where we place names or other singular terms to form atomic sentences.1 Therefore, starting from an atomic sentence, we could replace some of the singular terms in it with variables. Because of the indefinite way variables refer to things, the obtained sentence will cease to be true or false. Here is an example:

 (1) Vienna is east of Paris.

This is an atomic sentence consisting of two singular terms (“Vienna” and “Paris”) and one two-place predicate (“...is to the east of...”). If we represent “Vienna” and “Paris” with the constants “a” and “b” and the predicate with the predicate letter “F”, then its symbolic representation will be:

 (2) Fab

Now in the place of the singular term “Vienna” in (1), respectively in place of “a” in (2), we will place the variable “x”. We get the sentence

 (3) x is east of Paris

which is symbolized by

 (4) Fxb

Unlike the name “Vienna” (respectively, the constant “a”), the variable “x” in (3) and (4) does not denote the capital of Austria, but indefinitely denotes anything. We can imagine that it runs through each existing thing and never stops at a certain thing. The things a variable runs through are the values it can take. Since “x” does not refer to something definite, (3) (respectively (4)) is neither true nor false. It is true for some values of x, such as Vienna, Black Sea, or the Himalayas, and false for others, such as London, or the Atlantic Ocean (since the former are east of Paris and the latter are not), but it is not simply true or false. Such sentences, which are neither true nor false because there is a variable in them, are called open sentences. So (3) is an open sentence and (4) represents symbolically such a sentence.

Now we will put the following phrase before the open sentence (3):

 (5) for some x,

The result is:

 (6) For some x, x is east of Paris.

As x has all existing things as values, the meaning of (6) is not different from the meaning of “Something is east of Paris”, or “There is something that is east of Paris”, or “There exists something to the east of Paris”. In the last three sentences, unlike the open sentence (3), “x” is not mentioned at all. Since (6) has the same meaning, it is not an open sentence. It is a real sentence, a statement, or a proposition, which has a truth value – obviously a trivial truth. We will call (5) and similar phrases like “there is something x such that” existential quantifier and will represent it symbolically with “∃x”. Accordingly, the symbolic representation of (6) is

 (7) ∃xFxb

The statement (6) ((7) in symbols) was obtained as the existential quantifier “for some x” (“∃x”) was referred to the variable “x” in the open sentence (3) ((4) in symbols). Therefore, the second occurrence of “x” in (6) and (7) is said to be bound (by the quantifier), while the variable “x” in (3) and (4), which is not bound by a quantifier, is said to be free. When we bind by quantifiers all variables in a sentence as in (6), the sentence ceases to be an open sentence. It becomes a proposition (statement), which has a truth value – it is either true or false. In natural languages, bound variables are not uttered at all. No one in the everyday language would say something like (6) referring to x, y… etc. Instead, he or she would say, for example, “There is something to the east of Paris”. The two statements have the same meaning though.

Each quantifier has a scope. This is the expression (usually an open sentence) that states the condition after the “there is something x such that” of the quantifier “∃x”. For example, in (6) the scope of the quantifier is the open sentence “x is east of Paris”. Accordingly, in its symbolic representation “∃xFxb” the scope of the existential quantifier “∃x” is “Fxb”. When a free variable enters the scope of a quantifier (with the same variable), the quantifier binds the variable and from free, it becomes bound.

In everyday language, the existential quantifier is expressed in various ways – “exists”, “there is”, “something”, “someone,” “some”, with negation – “nothing”, “no one” … etc.

Let us continue with our example. In (6) we came to a statement that in everyday language we would paraphrase as “Something is east of Paris” and that is symbolized by “∃xFxb”. Now, if we replace the singular term “Paris” in it with the variable “y”, we will get the sentence

 (8) Something is east of y.

whose symbolic representation is

 (9) ∃xFxy.

This sentence is not a statement but an open sentence because of the free variable “y” in it. Depending on the values this variable takes, (8) and (9) will become sometimes true and sometimes false2; in themselves, they are neither true nor false. Although it is in the scope of the quantifier “∃x”, the variable “y” is free in (9) because the quantifier’s variable (“x”) is not the same. The situation would be different if in (9) we had “∃xFxx”. The last formula tells us “There is something x such that it is east of x”, i.e. of itself. So, it is the symbolic representation of the statement “Something is east of itself”. Since the quantifier binds both occurrences of “x”, “∃xFxx” symbolizes a statement (albeit false), not an open sentence.

Another existential quantifier whose variable is “y” (i.e. the expression “there is something y such that”) can be put in front of (8), which will bind the free variable “y”. Then we will get the trivially true statement

 Something is east of something.

(literally “For some y and some x holds that x is east of y”) whose symbolization is

 ∃y∃xFxy

From a syntactic (grammatical) point of view, quantifiers behave like negation. The convention for negation was that if there is no opening parenthesis after it, it refers to the closest sentence on its right side and if there is – to the expression enclosed in the parentheses. Similarly, if there is no opening parenthesis after a quantifier, its scope is the closest sentence to the right and if there is, it is the expression in the parentheses. In this connection, let us consider the following three formulas:

 (10) ∃xFx ∧ ∃xGx

 (11) ∃xFx ∧ Gx

 (12) ∃x(Fx ∧ Gx)

In the first, we have two existential quantifiers “∃x”, after which there are no parenthesis, so their scope is the closest sentence on the right. For the first, it is the open sentence “Fx” and for the second it is the open sentence “Gx”. The quantifiers bind the occurrences of “x” in “Fx” and “Gx”, so there are no free variables in the formula and it symbolizes a statement of the form of conjunction, which tells us that there is something that is F and something that is G. For example, if “F” symbolizes the predicate “…is round” and “G” the predicate “… is square”, (10) will correspond to the true statement “Something is round and something is square”. Unlike (10), in (11) there is only one quantifier. Its scope is again Fx, so the first occurrence of “x” is bound by it. However, the second occurrence of “x” remains free, because the scope of the quantifier does not reach it and does not bind it. As a consequence, (11) symbolizes an open sentence, not a statement, namely (for the same interpretation of “F” and “G”) the open sentence “Something is round and x square”. The latter is neither true nor false, because it remains undetermined what x is. As in (11), in (12) there is only one quantifier but there are also parentheses after it, which show that its scope is the whole conjunction “FxGx”. Therefore, the quantifier binds both occurrences of “x”. The result is that the meaning of (12) is that there is something x such that x is F and x (the same) is G”, in other words – that there is something which is both F and G. In the above interpretation, (12) corresponds to the false statement “Something is (both) round and square”.

When there is no quantifier in the scope of another quantifier, it does not matter which are the variables in the quantifiers – whether we are using “∃x”, “∃y”… etc. “∃xFx”, “∃yFy”, “∃zFz” have exactly the same meaning. The three formulas tell us that something is F. Using bound variables, we talk in general – by each of the three we are saying that there is something (call it “x”, “y”, “z” – it does not matter) that is F. Each variable refers (in the same indefinite way) to each of the existing things, so it does not matter which we are using. The only thing that is important in such cases is the variable of the quantifier and the variables in its scope to be the same. In this regard, the formula “∃xFx ∧ ∃xGx”, which we interpreted as the statement “Something is round and something is square”, could be equivalently replaced with “∃xFx ∧ ∃yGy”, “∃yFy ∧ ∃xGx”, or “∃zFz ∧ ∃zGz“… – they all symbolize the same statement.

Why do we use different variables at all, and not just “x”? The answer is that (usually) the variables of the quantifiers need to be different when there is a quantifier in the scope of a quantifier, although again it does not matter which exactly variables we are using. This was the case above, where we interpreted “∃yxFxy” as “Something is east of something”. If we try to use only “x” and substitute it for “y”, we will get “∃xxFxx”. This formula no longer tells us the trivial truth that something is east of something. It tells us the trivial falsehood that something is east of itself (with the first quantifier superfluous). This is so since the scope of the second quantifier is “Fxx”, which is why it binds both occurrences of “x” (before, the same quantifier did not bind the free occurrence of “y” in “Fxy” as its variable is different). As a result, “∃xFxx” is not an open sentence but a statement, which tells us that there is some x that is east of x, i.e. of itself. Thus, for the first quantifier there is no free variable to bind and it becomes redundant – “∃xxFxx” tells us literally that there is something such that something is eats of itself. On the other hand, as long as the two variables are different and related in the same way in the formula, it does not matter which they are – except with “∃yxFxy”, the fact that something is east of something may be equally well expressed with “∃xyFyx”, or with “∃yzFzy”, or with “∃zxFxz”, etc.

By the definite article “the” we form singular terms. “The ring” is a singular term, which we should represent by a constant (for example “r”); it refers to a particular ring in any given context. As for the indefinite article (“a”), sometimes is a part of a predicate (as in the predicate“…is a ring”), and sometimes it indicates existential quantifier. Compare the following sentences:

 Bob gave Alice the ring.
 Bob gave Alice a ring.

Notice that they are not equivalent, as the first can be false while the second is true. It is possible that Bob has not given Alice the ring the speaker is referring to by “the ring” in the first sentence but has given her another ring, which will make the first sentence false and the second true. In the first sentence, we have one three-place predicate (…gave… …) and three singular terms (“Bob”, “Alice” and “the ring”), while in the second we have the same predicate, two singular terms (“Bob” and “Alice”) and another predicate – the one place predicate “…is a ring”. The symbolic representation of the first sentence is straightforward. If we symbolize the predicate “…gave… …” with “F” and the singular terms “Bob”, “Alice” and “the ring” with “b”, “a”, and “r” respectively, the sentence is symbolized with

 Fbar

As for the second sentence, notice that it can be paraphrased as “There is something that is a ring and that Bob gave to Alice”. In other words, “There is something x such that x is a ring and Bob gave Alice x”. If “G” represents the predicate “ring”, the latter sentence is directly symbolized with

 ∃x(Gx ∧ Fbax)

So, the indefinite article in the second sentence indicates an existential quantifier.

The difference between the above two sentences may seem exaggerated or artificial, but it is not. To convince ourselves, notice that if a is a singular term, the sentence “a is F and a is not F” is always a contradiction. “Bob gave Alice the ring and Bob did not give Alice the ring” is a contradiction. On the contrary, “Something is F and something is not F” is not a contradiction usually – “Something is round and something is not round” is a trivial truth. “Something” expresses existential quantifier, it is not a singular term. “A ring” in “Bob gave Alice a ring” has the same behavior. “Bob gave Alice a ring and Bob did not give Alice a ring” is not a contradiction (interpreted appropriately); it can be true – imagine that he bought two rings but gave her only one of them. Then there is a ring he did not give her.

In addition to the existential quantifier, there is also a universal quantifier. While the existential quantifier states that there is at least one thing that satisfies a certain condition, the universal quantifier states that the condition is satisfied by everything. The notation for the universal quantifier is “∀x” (respectively “∀y”, “∀z”…). For example, if “F” symbolizes the predicate “…is equal to…”, “∀xFxx” will be the symbolic representation of the sentence “Everything is equal to itself” (literally “For each thing x, x is equal to x”).

Sentences beginning with a universal quantifier (the rest of the sentence being within its scope) are called universal, and sentences beginning with an existential quantifier are called existential.

As we know, traditional logic considers only sentences with a subject-predicate form, which are called categorical and which are divided into four types – universal affirmative (A), universal negative (E), particular affirmative (I) and particular negative (O). Let us see how these sentences are expressed in the symbolic language of predicate logic.

The standard form of a universal affirmative sentence is “All F are G” (e.g. “All cats are intelligent”). Such sentence can be paraphrased with the sentence “If something is F, it is G” (“If something is a cat, it is intelligent”). By paraphrasing the last sentence again, so that the universal quantifier contained in it becomes obvious, we get the sentence “For each thing x, if x is F, then x is G”, i.e.:

 ∀x(Fx → Gx)

This is the standard way to symbolize a general affirmative sentence in the symbolism of predicate logic.

What about universal negative sentences? Every sentence of the form “No F are G” (e.g. “No cats are intelligent”) can be paraphrased with the sentence “If something is F, it is not G” (“If something is a cat, it is not intelligent”), which, after making the quantifier explicit, becomes “For each thing x, if x is F, x is not G”, i.e.:

 ∀x(Fx → ¬Gx)

The meaning of a sentence of the form “Some F is G” (a particular affirmative sentence) is that there is at least one F that is G. But if that is true, there will be at least one G that is F, too (for example, if there is at least one cat that is intelligent, there will be at least one intelligent being that is a cat – the same cat)3. Therefore, instead of saying that there is at least one F that is G, or that there is at least one G that is F, we can say that there is at least one thing that is both F and G (for example, that there is at least one thing which is both a cat and intelligent). By making explicit the quantifier, we obtain the statement “There is something x such that x is F and x is G”. Therefore, every sentence of the form “Some F are G” can be symbolized by

 ∃x(Fx ∧ Gx)

Similarly, a particular negative sentence, whose standard form is “Some F are not G”, can be paraphrased as “There is at least one thing that is F and not G”, i.e. “There is at least one thing x such that x is F and x is not G”. Thus, we get that an I-sentence may be symbolized with

 ∃x(Fx ∧ ¬Gx)

The following table summarizes the standard way of representing categorical sentences in predicate logic:

 Universal affirmative (“All F are G”) ∀x(Fx → Gx) Universal negative (“No F are G”) ∀x(Fx → ¬Gx) Particular affirmative (“Some F are G”) ∃x(Fx ∧ Gx) Particular negative (“Some F are not G”) ∃x(Fx ∧ ¬Gx)

This is not the only way to symbolize categorical sentences in predicate logic. An alternative way is due to the fact that universal affirmative (A) sentences are exact negations of particular negative (O) sentences and universal negative (E) sentence are exact negations of the particular affirmative (I) sentences (see 2.2 Square of opposition). If we put a negation before the standard symbolic representation of a particular negative sentence (the last row of the table), we will get a way to symbolize universal affirmative sentences by means of an existential rather than a universal quantifier:

 ¬∃x(Fx ∧ ¬Gx)

Intuitively, the last expression corresponds just as well to the meaning of a universal affirmative sentence as the standard symbolic representation. What it tells us is that there is no F that is not G – to say that there is no cat that is not intelligent is to say that all cats are intelligent. Similarly, the negation of the standard symbolic representation of a particular affirmative sentence “¬∃x(FxGx)” tells us that there is no F that is G. To say that there is no intelligent cat is to say that no cats are intelligent. The situation is similar with the negations of the standard symbolizations of the universal sentences. “¬∀x(FxGx)” and “¬∀x(Fx→¬Gx)” are alternative ways to symbolize particular negative and particular affirmative sentences respectively.

The four categorical sentences (A, E, I and O) are very often found in non-standard form (the standard form being “All F are G” for A-sentences, “No F are G” for E-sentences, “Some F are G” for I-sentences and “Some F are not G” for O-sentences). This is especially true for universal affirmative sentences. Here are some non-standard but common ways of making A-statements.

“The dolphin is a mammal” is not an atomic sentence as “The president is a woman” although outwardly they have exactly the same form. The first sentence is equivalent to “All dolphins are mammals” and have to be symbolized with, say, “∀FxGx” while the second is symbolized with, say, “Fa”.

As with the conditional in propositional logic, where adding the word “only” swaps the places of the antecedent and the consequent (see), adding “only” before a universal affirmative sentence swaps the places of the subject and the predicate. In standard form, “Cats are intelligent” is “All cats are intelligent”, but “Only cats are intelligent” has the meaning of “All intelligent beings are cats” – the addition of “only” has the effect of “cats” and “intelligent” exchanging their roles. In general, sentences with the form “F are G” (“Cats are intelligent”) are paraphrased in standard form with “All F are G” (“All cats are intelligent”), while sentences with the form “Only F are G” (“Only cats are intelligent”) are paraphrased in standard form with “All G are F” (“All intelligent beings are cats”). Similarly, to say “If something is F, it is G” is the same as to say “All F are G”, but “Only if something is F it is G” is equivalent to “All G are F”. The resemblance to the conditional in propositional logic is not accidental. As we have seen, we symbolize A-sentences through a conditional – “∀x(FxGx)”. Such sentences and formulas (a universal sentence in which the scope of the quantifier is a conditional) are sometimes called formal implications.

The notions of a necessary and sufficient condition are closely related to universal affirmative sentences. “All F are G” can be paraphrased as “Being F is a sufficient condition for being G”. For example, if it is true that all cats are intelligent, then being a cat will be a sufficient condition for being intelligent; conversely, if being a cat is a sufficient condition for being intelligent, then surely all cats will be intelligent. On the other hand, “All F are G” can also be paraphrased as “Being G is a necessary condition for being F”. If it is true that all cats are intelligent, then being intelligent is a necessary condition for being a cat (if something is not intelligent, it cannot be a cat); conversely, if being intelligent is a necessary condition for being a cat, then if something is a cat, it will be intelligent. It turns out that what falls under the subject of a true universal affirmative sentence is a sufficient condition for what falls under its predicate and what falls under its predicate is a necessary condition for what falls under its subject.

Sentences such as “Nothing is F unless it is G” also have the meaning of “All F are G”. “Nothing is a cat unless it is intelligent” has the meaning of “All cats are intelligent” because in effect it tells us that to be intelligent is a necessary condition for to be а cat, and, as we saw in the previous paragraph, “G is а necessary condition for F” has the meaning of “All F are G”.

The sentence “There is no F that is not G” also has the meaning of “All F are G”. Instead of “All cats are intelligent”, we may equivalently say “There is no cat that is not intelligent”. The second sentence corresponds to the alternative way of symbolizing universal affirmative sentences mentioned above. Since A-sentences are exact negations of the corresponding O-sentences, in addition to the standard “∀x(FxGx)”, A-sentences may also be symbolized with “¬∃x(Fx∧¬Gx)”, i.e. “There is no F that is not G”.

The sentence “All humans are mortal” contains the predicate “…is human”, which is symbolized by “F” in “∀x(FxGx)”. However, sometimes “human” is only implicitly present through the usage of “everyone” (“everybody”), “someone” (“somebody”), “no one” (“nobody”), etc. For example, the sentence “Someone likes Socrates” obviously refers to one or more persons (humans), not to one or more things (humans or not). Therefore, if we represent it symbolically with “∃xFxa” (where “F” represents “…likes…”), the formula will rather symbolize the sentence “Something likes Socrates” (“x” takes as values all things, not just people). Therefore, we may add additional predicate letter (say “H”) for “…is human” as follows: “∃x(HxFxa)”. The last formula corresponds exactly to the meaning of the sentence because it tells us that there is something that is human and that likes Socrates. Similarly, it seems incorrect to symbolize “Everyone likes Socrates” with “∀xFxa”, as the formula states that everything (inanimate things included) likes Socrates. Again, we may use additional predicate letter for “human”, or “person”, or (depending on the context) “citizen of Athens”, etc. This time, however, since the quantifier is universal, we should add it not with a conjunction, but with a conditional: “∀x(HxFxa)”. The last expression tells us that for each thing x, if x is human, x likes Socrates; in other words, every human likes Socrates.

Alternatively, instead of adding the implicit predicate, we can restrict the range of things our variables run through. Such a restriction is in harmony with the fact that discussion is often limited to a certain set of things. For example, the subject of a conversation between mathematicians could be limited to numbers, to geometric figures, and so on. Similarly, a conversation between biologists could be limited to plants, certain types of plants, and so on. The set of all things referred to is further narrowed in the different contexts of everyday language. When we utter sentences like “Everyone agrees”, “everyone” is almost always limited not just to the people, but to a certain group of people – for example, to the people present or to those who are familiar with the topic under discussion, etc. In accordance with this frequent limitation of the things referred to, we will introduce the concept of universe of discourse. This is the set of things that are values of our variables in the context. We will denote it by “D” (from “domain”). When we symbolize natural language sentences, we will be allowed to limit or not the universe of discourse D so that all or only part of the existing things are included in it. When we limit it, we will have to state explicitly what the set is. If we do not specify it, we will imply that the universe of discourse includes all things.

By limiting the universe of discourse to the set of humans, the above two sentences – “Someone likes Socrates” and “Everyone likes Socrates” – will be symbolized by “∃xFxa” and “∀xFxa” respectively (“F” corresponds to “…likes…” and “a” to “Socrates”). Because the variable “x” takes as values all things from the universe of discourse, and in this case they are limited to humans, the meaning of “∃x” is no longer “there is something such that”, but “there is some person such that”. Accordingly, the meaning of “∀x” is not “for all things”, but “for all humans”.

Limiting universe of discourse simplifies symbolic representation by reducing the number of predicate letters by one – the letter that would otherwise symbolize the predicate corresponding to the universe of discourse (for example, “human” if the universe of discourse is the set of all humans). Any sentence symbolized by imitating the universe of discourse can be symbolized without it by paraphrasing the sentence so that it itself limits the range of its denotation. We saw how this is done in the case of “Someone respects Socrates” and “Everyone respects Socrates”. In general, any existential sentence that is symbolized with “∃x(…x…)” by limiting D to a given set corresponding to a given predicate can be symbolized without the limitation with “∃x(Hx ∧ …x…)”, where “H” (or another letter) symbolizes the predicate. Accordingly, any universal sentence that is symbolized with “∀x(…x…)” by limiting the universe of discourse can be symbolized without the limitation with “∀x(Hx →…x…)”. We see that limiting D simplifies symbolic representation by reducing “H”.

However, limiting the universe of discourse is not always possible. To be possible, all things referred to in the context must be elements of a set corresponding to some predicate. For example, unlike “Someone likes Socrates”, the sentence “Someone likes Crime and Punishment” cannot be symbolized with “∃xFxa” by restricting D to humans because, in addition to humans, it speaks of a novel. That novel is also part of the universe of discourse (the totality of things in the context) and the variables will have it as a value as well, which prevents them from being restricted to humans.