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 ...
Some authors call this the particular quantifier.
There are variants of this symbol:
- $\exists !$ means there exists uniquely, or, there is one and only one.
- $\exists_n$ means there exist exactly $n$.
Thus $\exists_1$ means the same thing as $\exists !$.
Propositional Expansion
The existential quantifier can be considered as a repeated disjunction:
Let $\exists$ be the existential quantifier.
What $\exists x: P \left({x}\right)$ 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:
- $P \left({\mathbf X_1}\right) \lor P \left({\mathbf X_2}\right) \lor P \left({\mathbf X_3}\right) \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.
Variants
Some authors use $\bigvee x$ to mean $\exists x$, which is appropriate when considering the propositional expansion.
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: P \left({x}\right)$.
Note, however, that it is also used to symbolize the concept most.
Beware
Now, you have to be careful with most. It has to be interpreted in the same way as some.
Compare these sequents:
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle a\) | \(\text {are}\) | \(\displaystyle b.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle b\) | \(\text {are}\) | \(\displaystyle c.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle c\) | \(\text {are}\) | \(\displaystyle d.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {Therefore, all}\) | \(\displaystyle \) | \(\displaystyle a\) | \(\text {are}\) | \(\displaystyle d.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
... which can be epitomised by:
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle \text {cats}\) | \(\text {are}\) | \(\displaystyle \text {mammals.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle \text {mammals}\) | \(\text {are}\) | \(\displaystyle \text {animals.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle \text {animals}\) | \(\text {are}\) | \(\displaystyle \text {organisms.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {Therefore, all}\) | \(\displaystyle \) | \(\displaystyle \text {cats}\) | \(\text {are}\) | \(\displaystyle \text {organisms.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
... which one has to admit seems plausible.
On the other hand, check this out:
| \(\displaystyle \) | \(\displaystyle \text {Most}\) | \(\displaystyle \) | \(\displaystyle a\) | \(\text {are}\) | \(\displaystyle b.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle b\) | \(\text {are}\) | \(\displaystyle c.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {Most}\) | \(\displaystyle \) | \(\displaystyle c\) | \(\text {are}\) | \(\displaystyle d.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {Therefore, most}\) | \(\displaystyle \) | \(\displaystyle a\) | \(\text {are}\) | \(\displaystyle d.\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
... an example of which reasoning may be:
| \(\displaystyle \) | \(\displaystyle \text {Most}\) | \(\displaystyle \) | \(\displaystyle \text {champion chess players}\) | \(\text {are}\) | \(\displaystyle \text {human.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | (There are some which are computers, of course.) | ||
| \(\displaystyle \) | \(\displaystyle \text {All}\) | \(\displaystyle \) | \(\displaystyle \text {humans}\) | \(\text {are}\) | \(\displaystyle \text {organisms.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {Most}\) | \(\displaystyle \) | \(\displaystyle \text {organisms}\) | \(\text {are}\) | \(\displaystyle \text {monocellular.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \text {Therefore, most}\) | \(\displaystyle \) | \(\displaystyle \text {champion chess players}\) | \(\text {are}\) | \(\displaystyle \text {monocellular.}\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
Well I don't know about you, but I've never been beaten at chess by an amoeba.
Historical Note
The symbol $\exists$ was first used by Giuseppe Peano in volume II, number 1, of Formulario Mathematico (2nd edition) 1896.
However, Bertrand Russell was the first to use $\exists$ as a variable binding operator.
Also see
References
- ↑ See Earliest Uses of Symbols of Set Theory and Logic in Jeff Miller's website Earliest Uses of Various Mathematical Symbols.
Sources
- Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 2$: The Axiom of Specification
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{III}: \S 1$
- T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 4$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 3$
- Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.1$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 2.1$
