Definition:Existential Quantifier
Contents
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.
Formally:
- $\exists ! x: \map P x \dashv \vdash \exists x: \map P x \land \forall y: \map P y \implies x = y$
In natural language, this means:
- There exists exactly one $x$ with the property $P$
- is logically equivalent to:
Also known as
Some sources refer to this 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$ | Giuseppe Peano: Formulario Mathematico (2nd ed.) (1896) |
$\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
- 1896: Giuseppe Peano: Formulario Mathematico (2nd ed.): Volume $\text{II}$, number $1$
- 1946: Alfred Tarski: Introduction to Logic and to the Methodology of Deductive Sciences (2nd ed.) ... (previous) ... (next): $\S 1.4$: Universal and Existential Quantifiers
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 2$: The Axiom of Specification
- 1964: Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning ... (previous) ... (next): $\text{III}$: 'ALL' and 'SOME': $\S 1$
- 1972: A.G. Howson: A Handbook of Terms used in Algebra and Analysis ... (previous) ... (next): $\S 1$: Some mathematical language: Variables and quantifiers
- 1972: Patrick Suppes: Axiomatic Set Theory (2nd ed.) ... (previous) ... (next): $\S 1.2$ Logic and Notation
- 1973: Irving M. Copi: Symbolic Logic (4th ed.) ... (previous) ... (next): $4.1$: Singular Propositions and General Propositions
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 4$. Relations; functional relations; mappings
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 3$: Statements and conditions; quantifiers
- 1979: G.H. Hardy and E.M. Wright: An Introduction to the Theory of Numbers (5th ed.) ... (previous) ... (next): Remarks on Notation
- 1980: D.J. O'Connor and Betty Powell: Elementary Logic ... (previous) ... (next): $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: $\text{(i)}$
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
- 1993: Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (2nd ed.) ... (previous) ... (next): $\S 1$: Naive Set Theory: $\S 1.1$: What is a Set?
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability: $\S 2.1$
- 1999: András Hajnal and Peter Hamburger: Set Theory ... (previous) ... (next): $1$. Notation, Conventions
- 2008: David Joyner: Adventures in Group Theory (2nd ed.) ... (previous) ... (next): Chapter $1$: Elementary, my dear Watson: $\S 1.1$: You have a logical mind if...: Definition $1.1.1$
- 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $1$: General Background: $\S 6$ Significance of the results