Existential quantification

Existential quantification

In predicate logic, an existential quantification is the predication [The term "predication" in grammar means the predicate of a sentence which refers to subject and is an adverb or adjective, or equivalent, that describes an attribute of the subject. In logic, "predication" is a declaration (or assertion) that is claimed to be self-evident and can be assumed as the basis for argument.] of a property or relation to at least one member of the domain. [http://dictionary.reference.com/browse/predication] In laymen's terms, it simply refers to something. It is denoted by the logical operator symbol ∃ (pronounced "there exists" or "for some"), which is called the existential quantifier. Existential quantification is distinct from "universal" quantification (pronounced "for all"), which asserts that the property or relation holds for "any" members of the domain.

Basics

Suppose you wish to write a formula which is true if and only if some natural number multiplied by itself is 25. A slow, brute-force approach you might try is the following:: 0·0 = 25, or 1·1 = 25, or 2·2 = 25, or 3·3 = 25, and so on.This would seem to be a logical disjunction because of the repeated use of "or".However, the "and so on" makes this impossible to integrate and to interpret as a disjunction in formal logic.Instead, we rephrase the statement as: For some natural number "n", "n"·"n" = 25.This is a single statement using existential quantification.

Notice that this statement is really more precise than the original one.It may seem obvious that the phrase "and so on" is meant to include all natural numbers, and nothing more, but this wasn't explicitly stated, which is essentially the reason that the phrase couldn't be interpreted formally. In the quantified statement, on the other hand, the natural numbers are mentioned explicitly.

This particular example is true, because 5 is a natural number, and when we substitute 5 for "n", we produce "5·5 = 25", which is true.It does not matter that "n"·"n" = 25" is false for "most" natural numbers "n", in fact false for all of them "except" 5; even the existence of a single solution is enough to prove the existential quantification true.In contrast, "For some even number "n", "n"·"n" = 25" is false, because there are no even solutions.

On the other hand, "For some odd number "n", "n"·"n" = 25" is true, because the solution 5 is odd.This demonstrates the importance of the "domain of discourse", which specifies which values the variable "n" is allowed to take.Further information on using domains of discourse with quantified statements can be found in the Quantification article.But in particular, note that if you wish to restrict the domain of discourse to consist only of those objects that satisfy a certain predicate, then for existential quantification, you do this with a logical conjunction.For example, "For some odd number "n", "n"·"n" = 25" is logically equivalent to "For some natural number "n", "n" is odd and "n"·"n" = 25".Here the "and" construction indicates the logical conjunction.

In symbolic logic, we use the existential quantifier "∃" (a backwards letter "E" in a sans-serif font) to indicate existential quantification.Thus if "P"("a", "b", "c") is the predicate "a"·"b" = c" and mathbb{N} is the set of natural numbers, then: exists{n}{in}mathbb{N}, P(n,n,25) is the (true) statement: For some natural number "n", "n"·"n" = 25.Similarly, if "Q"("n") is the predicate "n" is even", then: exists{n}{in}mathbb{N}, ig(Q(n);!;! {wedge};!;! P(n,n,25)ig) is the (false) statement: For some even number "n", "n"·"n" = 25.Several variations in the notation for quantification (which apply to all forms) can be found in the quantification article.

Properties

Negation

Note that a quantified propositional function is a statement; thus, like statements, quantified functions can be negated. The notation mathematicians and logicians utilize to denote negation is: lnot .

For example, let P("x") be the propositional function "x is between 0 and 1"; then, for a Universe of Discourse X of all natural numbers, consider the existential quantification "There exists a natural number "x" which is between 0 and 1"::exists{x}{in}mathbf{X}, P(x)

A few seconds' thought demonstrates this as irrevocably false; then, truthfully, we may say, "It is not the case that there is a natural number "x", that is between 0 and 1", or, symbolically::lnot exists{x}{in}mathbf{X}, P(x).

Take a moment and consider what, exactly, negating the existential quantifier means: if the there is no element of the Universe of Discourse for which the statement is true, then it must be false for all of those elements. That is, the negation of exists{x}{in}mathbf{X}, P(x) is logically equivalent to "For any natural number "x", x is not between 0 and 1", or::forall{x}{in}mathbf{X}, lnot P(x)

Generally, then, the negation of a propositional function's existential quantification is an universal quantification of that propositional function's negation; symbolically,:lnot exists{x}{in}mathbf{X}, P(x) equiv forall{x}{in}mathbf{X}, lnot P(x)

A common error is writing "all persons are not married" (i.e. "there exists no person who is married") when one means "not all persons are married" (i.e. "there exists a person who is not married")::lnot exists{x}{in}mathbf{X}, P(x) equiv forall{x}{in}mathbf{X}, lnot P(x) otequiv lnot forall{x}{in}mathbf{X}, P(x) equiv exists{x}{in}mathbf{X}, lnot P(x)

Rules of Inference

A rule of inference is a rule justifying a logical step from hypothesis to conclusion. There are several rules of inference which utilize the existential

"Existential introduction" concludes that, if the propositional function is known to be true for a particular element of the universe of discourse, then it must be true that there exists an element for which the proposition function is true. Symbolically, this is represented as

: P(a) o exists{x}{in}mathbf{X}, P(x)

"Existential elimination" is a fairly complicated rule. The reasoning behind it is as follows: If we know that there exists an element for which the proposition function is true, then if we can reach a conclusion by giving that object an arbitrary name, we know that conclusion to be true, as long as it does not contain the name. Symbolically, for an arbitrary "c" and for a proposition Q in which "c" does not appear:

: exists{x}{in}mathbf{X}, P(x) o ((P(c) o Q) o Q)

It is especially important to note "c" must be completely arbitrary; else, the logic does not follow: if "c" is not arbitrary, and is instead a specific element of the Universe of Discourse, then stating P("c") might unjustifiably give us more information about that object.

Finally, unlike the universal quantifier, the existential quantifier distributes over logical disjunctions:

exists{x}{in}mathbf{X}, P(x) or Q(x) o (exists{x}{in}mathbf{X}, P(x) or exists{x}{in}mathbf{X}, Q(x))

The Empty set

By convention, the formula exists {x}{in}emptyset , P(x) is always false, regardless of the formula "P"("x"); see vacuous truth.

Notes

See also

* Quantifiers
* First-order logic

References

*cite book | author = Hinman, P. | title = Fundamentals of Mathematical Logic | publisher = A K Peters | year = 2005 | id = ISBN 1-568-81262-0


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Quantification — has two distinct meanings.In mathematics and empirical science, it refers to human acts, known as counting and measuring that map human sense observations and experiences into members of some set of numbers. Quantification in this sense is… …   Wikipedia

  • Existential — may refer to:*Existential clause *Existential crisis *Existential fallacy *Existential humanism *Existential forgery *Existential risk *Existential therapy *Existential graph *Existential phenomenology *Existential quantification *Existentialism… …   Wikipedia

  • Existential graph — An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote his first paper on graphical logic in 1882 and continued to develop the method until his death in 1914.The… …   Wikipedia

  • existential import — The implications of a proposition as to what exists. If a proposition entails the existence of something, then it has existential import. It should be noticed that in the predicate calculus the universal quantification (∀x )(F x → G x ) has no… …   Philosophy dictionary

  • quantification — See quantifiable. * * * ▪ logic       in logic, the attachment of signs of quantity to the predicate or subject of a proposition. The universal quantifier, symbolized by (∀ ) or ( ), where the blank is filled by a variable, is used to express… …   Universalium

  • Universal quantification — In predicate logic, universal quantification is an attempt to formalize the notion that something (a logical predicate) is true for everything , or every relevant thing.The resulting statement is a universally quantified statement, and we have… …   Wikipedia

  • Plural quantification — In mathematics and logic, plural quantification is the theory that an individual variable x may take on plural , as well as singular values. As well as substituting individual objects such as Alice, the number 1, the tallest building in London… …   Wikipedia

  • Uniqueness quantification — This article is about mathematics. For the electronic group, see Unique (band). In mathematics and logic, the phrase there is one and only one is used to indicate that exactly one object with a certain property exists. In mathematical logic, this …   Wikipedia

  • Dependence logic — is a logical formalism, created by Jouko Väänänen[1], which adds dependence atoms to the language of first order logic. A dependence atom is an expression of the form , where are terms, and corresponds to the statement that the value of is… …   Wikipedia

  • Czesław Lejewski — ( 1913–2001 ) was a Polish philosopher and logician, and a member of the Lwow Warsaw School of Logic. He studied under Jan Łukasiewicz and Karl Popper in the London School of Economics, and W.V.O. Quine.[1][2][3] Logic and Existence (1954–5) In… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”