quantifier

from Wikipedia, the free encyclopedia

A quantifier or quantifier , the re-Latinization of the expression “quantifier” introduced by CS Peirce , is an operator of the predicate logic . In addition to the joiners , the quantifiers are basic signs of predicate logic. What all quantifiers have in common is that they bind variables .

The two most common quantifiers are the existential quantifier (expressed in natural language, for example, as “at least one”) and the universal quantifier (expressed in natural language, for example, as “all” or “everyone”). Other types of quantifiers are number quantifiers such as “one” or “two”, which can be traced back to existential or universal quantifiers, and quantifiers such as “some”, “some” or “many”, which are not in classical logic due to their indeterminacy be used.

Existential and universal quantifier

Spelling and speaking

The existential quantifier is represented by the character ∃ (a horizontally mirrored “E”) or by the character , sometimes (especially in typewritten texts) as an ordinary “E” in brackets . The universal quantifier is represented by the character ∀ (an "A" turned upside down) or the character or simply by a variable in brackets.

Notation version 1 Variant 2 Way of speaking Common names
For (at least) one / some / some x applies;

There exists / is an x ​​for which applies

Existential quantifier, existential quantifier, particularizer, one quantifier, man quantifier
For all / every x applies Universal quantifier, universal quantifier, universal quantifier, generalizer

The spelling (not the existential quantifier itself) was introduced by Giuseppe Peano in 1897 in the first volume of his Formulaire de mathématiques ; It was spread through its use in the Principia Mathematica , the basic work of Russell and Whitehead published from 1910 . Gerhard Gentzen introduced the notation (not the universal quantifier itself) in 1934.

The spelling of the universal quantifier in variant 1 is based on the logical and (if one statement applies to all x, then it applies to ), just as the spelling of the existential quantifier in variant 1 is based on the logical or (there is an x ​​for the the statement holds, then the statement holds for ). From this analogy one can get the rules for the negation of a proposition containing an universal quantifier or an existential quantifier using De Morgan's laws .

Some authors see a subtle difference between the spelling , and Version 1, which, however, only in currying consists, not in the result but in the order in which the quantifiers act on their arguments. In order to ensure clarity, the two spellings may have to be bracketed differently.

The set of elements x considered is called the “ individual area ”.

Truth conditions

The statement is true if there is at least one x that has the property F. The statement is therefore also true if all x are F and the basic set that is used for quantification is not empty. The statement is true if all x are F, otherwise false.

It seems obvious to understand the existential quantifier as a chain of disjunctions (“or”) and the universal quantifier as a chain of conjunctions (“and”). If we assume that x can take on a natural number as a value, one is tempted to write:

The decisive difference, however, is that the variable of the quantifier can potentially take on an infinite number of values ​​with an infinitely large range of individuals, while a conjunction or disjunction can never be infinitely long. Therefore, in the above example, you have to make do with dots (for "etc.") at the end of the conjunction or disjunction.

Examples of formalizations

Examples of single-digit predicates

If the space of a single-digit predicate is bound by a quantifier, a finished statement is created. There are therefore only two ways of converting a one-digit predicate into a statement using a quantifier: universal quantification and existential quantification .

Using the example of the single-digit predicate "_ is pink", which should be formalized here as "F (_)":

Universal quantification
"Everything is pink" - "For every 'thing' it is pink" - "For every x: x is pink".
Existential quantification
"Something (at least one 'thing') is pink" - "There is at least one 'thing' that is pink" - "There is at least one x for which the following applies: x is pink".

Examples of complex sentences

When formalizing linguistic utterances, the existential quantifier is naturally combined with the "and" ( conjunction ) and the universal quantifier with the "if - then" (material implication )

Existential quantifier
Let us formalize the sentence:
A man smokes.
this is initially to be understood as:
There is someone who is a man and smokes.
or - if, as in the formalization, the co-reference of the relative connection "someone ... who" is expressed by using a variable -:
There is at least one x for which the following applies: x is a man and x smokes.
(note the "and") and then formalize it as follows:
,
where M (x) stands for "x is a man" and R (x) for "x smokes".
Universal quantifier
Let us formalize on the other hand:
All men smoke.
so we first transform this into:
For every “thing” applies: If it's a man, then it smokes.
respectively:
For every x: if x is a man, then x smokes.
(where we use the "if - then") and then formalize:
Nonexistence
The natural-language quantifier "none" can be formalized in different ways:
No man smokes.
can be rewritten as:
It is not true that there is at least one "thing" that is a man that smokes.
respectively:
It is not true that there is at least one x for which x is a man and x smokes.
whereupon it can be formalized as follows:
Another formalization is achieved if the statement “No man smokes” is understood as “For all x: if x is a man, x does not smoke”.

Examples of quantor logical sentence formulas

Simply quantified sentence formulas

The following applies to all things x: if the predicate S applies to x, then the predicate R also applies to x. Or: All S are R.
The following applies to all things x: if the predicate S applies to x, then the predicate R does not apply to x. Or: All S are not R. Or: No S is an R.
There is (at least) one thing x for which the following applies: the predicate S applies to x and the predicate R applies to x. Or: some S are R.
There is (at least) one thing x for which the following applies: the predicate S applies to x and the predicate R does not apply to x. Or: some S are not R.
For all things x the following applies: the predicate S applies to x and the predicate R applies to x. Or: Everything is S and R.
There is (at least) one thing x for which the following applies: if the predicate S applies to x, then the predicate R applies to x. Or: not all x are S and not R.
All pigs are pink (literally: for every thing: If it's a pig, then it's pink too.)
No pig is pink (literally: The following applies to every thing: If it's a pig, then it's not pink.)
There is at least one pink pig (literally: there is at least one thing that is both pig and pink.)
There is at least one non-pink pig (literally: there is at least one thing that is both pig and non-pink.)
Everything is a pink pig (literally: Any thing is considered to be both a pig and pink).
This seldom used statement, the literal translation of which is “There is at least one thing that is pink, provided that it is a pig”, makes the statement that not all things are non-pink pigs.

Multiple quantified sentence formulas

The two statements “At least one loves at least one” and “At least one is loved by at least one” are synonymous.
The two statements "everyone loves everyone" and "everyone is loved by everyone" are synonymous.
There is someone who loves everyone (literally: there is one thing, so that for all things, the former loves the latter); shorter: someone loves everyone.
There is someone who is loved by everyone (literally: there is one thing, so that for all things, the latter loves the former); shorter: someone is loved by everyone (i.e., everyone loves the same).
For everyone there is someone, so that the former loves the latter (literally: for every thing there is a thing, so that the former loves the latter), in short: everyone loves someone (i.e., everyone loves, but not everyone has to be the same / love the same).
For everyone there is someone who loves him or her (literally: for every thing there is a thing, so that the latter loves the former); shorter: Nobody is unloved.

Complex examples

"There is exactly one F," more literally: "There is at least one 'thing' that is on the one hand F and for which applies that all 'other' Fs are identical to it."
A synonym for the above sentence, literally: "There is at least one F, and for all 'things' x and all 'things' y: If both x and y are F, then x and y are identical."

Mutual definability of the quantifiers

In classical logic , each of the two quantifiers can be expressed by the other:

  1. The universal statement ( "all x ") is equivalent to a negated existential statement , ( "no x there that does not is"); here is a statement form in which the variable x can appear freely, but does not have to.
  2. The existence statement (“at least one x is ”) is equivalent to a negative universal statement (“It is not the case that all x are not ”).

Due to the above equivalences, one can be content with using only one of the two quantifiers as a basic sign in a formal language for the classical predicate logic and, if necessary, defining the other quantifier by this .

Example for (1)
If everything is imperishable, nothing is imperishable. Conversely: if nothing is imperishable, then all things are imperishable.
Example for (2)
If there is something green, not all things are not green. Conversely, if not all things are not green, there must be something green.

Modern quantifiers and Aristotelian syllogistics

When formalizing an universal statement, it should be noted that according to the definitions of the universal quantifier and implication, a statement “For all x: If A (x), then B (x)” is already true if there is no A. Thus, for example, the statement is:

All square circles are gold.

true because there are no square circles.

This leads to the fact that some conclusions of the Aristotelian syllogistics are not valid if one identifies their universal statements with the modern quantifiers.

The so-called Modus Barbari is an example :

All Munich are Bavaria, (formal notation quantifiers: )
all Schwabing are from Munich, (formally:) it follows:
some of them are from Bavaria. (formal: )

According to the modern view, the premises would both be true if there were no Schwabinger and Münchner at all. But then the conclusion would be wrong: Since there are no Schwabingers, there could not be some Schwabing Bavarians. So the premises could be true and the conclusion still false, i.e. that is, it was not a valid conclusion. Aristotle probably always assumed the existence of As when making a statement “All A are B” , so that the simple translation does not do justice to his intentions. What is the adequate interpretation and translation of the syllogistic universal statements is still the subject of research today; The article Syllogism provides information and references .

Even with the simple translation as an all-quantified implication, for example, the so-called mode barbarian a is valid , according to which it follows from the above premises:

All Schwabing are Bavarians (formally:) .

This statement follows because, according to modern opinion, it would also be true if there were no Schwabingers.

Number quantifiers

In addition to universal and existential quantifiers, number quantifiers are occasionally used in logic . In this way it can be expressed that there are “ exactly one”, “ exactly two”, ... things for which something applies.

In contrast to the existential quantifier , which says that there is at least one for which something applies, the uniqueness quantifier or uniqueness quantifier means that there is exactly one such (no more and no less). You write for him or you write . One can define this quantifier by means of the universal and existential quantifier as well as the identity sign "=" as follows:

,

in words:

"There is exactly one for which applies is synonymous with the fact that one exists for which applies and for all : if applies, then is identical with ."

In general, analogous to the uniqueness quantifier for quantifiers (or ) can also be defined, which say that there are exactly different ones. In particular, is equivalent to .

is defined accordingly as what the quantifier is sometimes used for: "There is no with ..."

Other quantifiers, such as “most ”, are rarely dealt with in logic. One area of ​​application for such quantifiers is the semantics of natural languages .

See also

Individual evidence

  1. ^ "Quantor", in: Historical Dictionary of Philosophy , Volume 7, page 1830
  2. Florian Cajori : A History of Mathematical Notations. Volume II: Notations Mainly in Higher Mathematics . Open Court, Chicago 1929, reprinted as a volume from Dover, ISBN 0-486-67766-4
  3. ^ Gentzen: Inquiry into logical reasoning . In: Mathematische Zeitschrift 39, 1934, 176–210

Web links

Wiktionary: Quantor  - explanations of meanings, word origins, synonyms, translations
Wikibooks: Math for non-freaks: Quantor  - learning and teaching materials