Quantifiers/Applied sciences/Introduction/Section

We consider again the propositions

Martians are green

and

I eat a hat,

and have a closer look at its structure (we replace my hat by a hat). In the first statement, a certain property is assigned to a certain kind of creatures, like we say that cheetahs are fast and sloths are slow. By the statement, one can mean that Martians are "usually“ or "almost always“ green, or, strictly speaking, that really all Martians are green. In mathematics, one is interested in statements which are true without exceptions (or that one can list the exceptions explicitly), so that we want to understand the statement in the strict sense. It is a universal statement. We have two predicates (representing a property, an attribute), to be a Martian and to be green. A predicate ${}P$ is something what can be assigned to an object, an item, an element or not. A predicate alone is not a proposition; with the help of a predicate, there are two different ways to build a proposition, the first is by applying (inserting) it to a concrete object ${}a$ to get the statement

$P(a),$

which means that the object ${}a$ has the property ${}P$, what might be true or not. The second way is by using a quantifier. In this way one can construct the statement that all objects (typically from a given basic set) have the property ${}P$, what again might be true or false. This is expressed formally as

$\forall xP(x).$

The symbol

$\forall$

is an abbreviation for for all, or for every and does not have any deeper meaning. It is called universal quantifier. The proposition about the Martians may be expressed by

$\forall x(M(x)\rightarrow G(x)).$

This means that for all objects without any restriction, the following holds: if it is a Martian, then it is green. For every ${}x$ we have an implication inside the wide bracket.

The second statement can mean that I eat exactly one hat or at least one hat. The meaning of the indefinite article is not unique. In mathematics, it usually means at least one. Hence, we can paraphrase by saying

There exists a hat which I eat.

This is an existential proposition. A formal representation is

$\exists x(H(x)\wedge E(x)),$

where ${}H(x)$ means that the object ${}x$ is a hat and where ${}E(x)$ means that ${}x$ is eaten by me. One could also write

$\exists x(E(x)\wedge H(x)).$

The symbol

$\exists$

is called existence quantifier.

A universal proposition claims that a certain predicate holds for all objects (from a given set). Like all propositions, this might be true or false. A universal proposition is false if and only if there exists at least one object for which the predicate does not hold. Therefore the two quantifiers, the universal quantifier and the existence quantifier, can be expressed by one another with the help of the negation. We have the rules

$\neg (\forall xP(x)){\text{ is equivalent with }}\exists x(\neg P(x)),$

$\neg (\exists xP(x)){\text{ is equivalent with }}\forall x(\neg P(x)),$

$\forall xP(x){\text{ is equivalent with }}\neg (\exists x(\neg P(x)))$

and

$\exists xP(x){\text{ is equivalent with }}\neg (\forall x(\neg P(x))).$

Apart from monadic predicates like ${}P(x)$ there are also binary and multinary predicates of the form

$P(x,y){\text{ or }}Q(x,y,z){\text{ etc. }}$

which express a relation between several objects like "is related with“, "is larger than“, "are parents of“ etc. Here one can quantify with respect to several variables, one has expressions like

$\forall x(\exists yP(x,y)),\,\exists x(\forall yP(x,y)),\,\forall x(\exists y(\forall zQ(x,y,z))){\text{ etc. }}$

The name of the variable in a quantified statement is not important, it does not make a difference whether we write ${}\forall aP(a)$ or ${}\forall tP(t)$. The only thing one has to take into account is that only names (letters) for variables are used which are not already used in the given context.

The logic which deals with quantified statements is called predicate logic or quantificational logic. We will not deal with it systematically, as it occurs in mathematics as set theory. Instead of ${}P(x)$, that a predicate is assigned to an object, we usually write ${}x\in P$ where ${}P$ is the set of all object which fulfil the property. Multinary predicates occur in mathematics as relations.