Definition:Existential Quantifier

From ProofWiki
Jump to navigation Jump to search

Definition

The symbol $\exists$ is called the existential quantifier.

It expresses the fact that, in a particular universe of discourse, there exists (at least one) object having a particular property.


That is:

$\exists x:$

means:

There exists at least one object $x$ such that ...


In the language of set theory, this can be formally defined:

$\exists x \in S: \map P x := \set {x \in S: \map P x} \ne \O$

where $S$ is some set and $\map P x$ is a propositional function on $S$.


Propositional Expansion

The existential quantifier can be considered as a repeated disjunction:

Suppose our universe of discourse consists of the objects $\mathbf X_1, \mathbf X_2, \mathbf X_3, \ldots$ and so on.

Let $\exists$ be the existential quantifier.

What $\exists x: \map P x$ means is:

At least one of $\mathbf X_1, \mathbf X_2, \mathbf X_3, \ldots$ has property $P$.

This means:

Either $\mathbf X_1$ has property $P$, or $\mathbf X_2$ has property $P$, or $\mathbf X_3$ has property $P$, or ...

This translates into propositional logic as:

$\map P {\mathbf X_1} \lor \map P {\mathbf X_2} \lor \map P {\mathbf X_3} \lor \ldots$


This expression of $\exists x$ as a disjunction is known as the propositional expansion of $\exists x$.


The propositional expansion for the existential quantifier can exist in actuality only when the number of objects in the universe is finite.

If the universe is infinite, then the propositional expansion can exist only conceptually, and the existential quantifier cannot be eliminated.


Exact Quantifier

The symbol $\exists_n$ denotes the existence of an exact number of objects fulfilling a particular condition.

$\exists_n x: \map P x$

means:

There exist exactly $n$ objects $x$ such that $\map P x$ holds.


Unique Quantifier

The symbol $\exists !$ denotes the existence of a unique object fulfilling a particular condition.

$\exists ! x: \map P x$

means:

There exists exactly one object $x$ such that $\map P x$ holds

or:

There exists one and only one $x$ such that $\map P x$ holds.


This quantifier is called the unique existential quantifier.


Also known as

Some sources refer to the existential quantifier as the particular quantifier.


Semantics

The existential quantifier can, and often is, used to symbolize the concept some.

That is:

Some $x$ have $P$

is also symbolized as:

$\exists x: \map P x$


It is also used to symbolize the concept most.


Also see

  • Results about the existential quantifier can be found here.


Notational Variants

Various symbols are encountered that denote the concept of existential quantifier:

Symbol Origin
$\exists x$ 1896: Giuseppe Peano: Formulario Mathematico (2nd ed.)
$\Sigma x$ Łukasiewicz's Polish notation
$\lor x$ or $\bigvee x$
$\ds \operatorname {\Large {\textsf E} } \limits_{x, y \dotsc}$ 1946: Alfred Tarski: Introduction to Logic and to the Methodology of Deductive Sciences


Historical Note

The symbol $\exists$ was first used for the existential quantifier by Giuseppe Peano in volume $\text{II}$, number $1$, of Formulario Mathematico, 2nd ed. of $1896$.

However, Bertrand Russell was the first to use $\exists$ as a variable binding operator.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Existential_Quantifier&oldid=714206"