Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Prepcourse Mathematics - Basics - Propositional Logic

Quantifiers

[previous page] [next page] [table of contents][page overview]
The phrases
,,there exists ...``,    and     ,,for all ...``
are symbolically abbreviated by the existential quantifier $ \exists$ and the universal quantifier $ \forall$ respectively. These quantifiers are commonly used in the context of statements $ A(p)$ that depend on a parameter $ p$ in a set $ P$ .

Notation meaning
$ \exists\,p\in P:\ A(p)$ there is at least one $ p$ in $ P$, for which $ A(p)$ is true
$ \forall\,p \in P:\ A(p)$ $ A(p)$ is true for all $ p$ in $ P$

Negation of statements turns existential quantifiers into universial quantifiers and vice versa:

$\displaystyle \lnot\big( \exists\,p\in P:\ A(p) \big)$ $\displaystyle =$ $\displaystyle \forall\, p\in P:\ \lnot A(p)$  
$\displaystyle \lnot\big( \forall\,p\in P:\ A(p) \big)$ $\displaystyle =$ $\displaystyle \exists\, p\in P:\ \lnot A(p)$  

The symbol $ \exists!$ is also commonly used to represent the phrase ,,there exists one and only one ...``.

(Authors: Höllig/Kimmerle/Abele)
As an illustration of the quantifier calculus let's consider the statement

$\displaystyle \forall\, \varepsilon>0\ \exists\, n_\varepsilon\ \forall\, n\in\mathbb{N}:\ n>n_\varepsilon \Longrightarrow \vert a_n\vert<\varepsilon $

This means that the sequence

$\displaystyle a_1,a_2,\ldots $

converges to 0, i.e. for every sufficiently large $ n$ the absolute value of $ a_n$ is less than any given bound $ \varepsilon$.

Negation is obtained by negating the main statement and replacing the quantifiers,

$\displaystyle \exists \leftrightarrow \forall \,. $

Substituting the implication and applying de Morgan's Laws we have

$\displaystyle \lnot( n>n_\varepsilon \Longrightarrow \vert a_n\vert<\varepsilo... ...a_n\vert<\varepsilon )= n>n_\varepsilon \land \vert a_n\vert\ge\varepsilon \,. $

Finally, we obtain the negated statement

$\displaystyle \exists\,\varepsilon>0\ \forall\, n_\varepsilon\ \exists\, n\in\mathbb{N}:\ n>n_\varepsilon \land \vert a_n\vert\ge\varepsilon \,. $

This means that the sequence $ (a_n)$ does not converge to 0; that is there exists a value $ \varepsilon>0$, so that infinitely many terms of the sequence $ \vert a_n\vert$ are greater than $ \varepsilon$.
(Authors: Höllig/Abele)
[previous page] [next page] [table of contents][page overview]
  automatically generated 9/18/2007