Predicates and Quantifiers
Formal mathematical statements are often built by predicates.
Discover Bridges
Study Predicates and Quantifiers
Definition 1 (Predicate). If \(X\) is any set and \(A(x)\) is a logical statement depending on \(x \in X\) (and true or false for every \(x\in X\)), we call \(A(x)\) a predicate with variable \(x\). Usually, one writes simply \(A(x)\) instead of \(A(x)=\) true.
Example 2. \[X=\mathbb{R}\qquad A(x) \;=\; x < 0\] Then we can define the set \[\{ x \in X : A(x) \} = \{ x \in \mathbb{R} : x < 0 \}\]
Definition 3 (Quantifiers \(\forall\) and \(\exists\)). We use \(\forall\) (“for all”) and \(\exists\) (“it exists”) and call them quantifiers. Moreover, we use the double point “ \(:\) ” inside the set brackets, which means “that fulfil”.
The quantifiers and predicates are very useful for a compact notation:
\(\forall x \in X : A(x)~~\) for all \(x\in X\) \(A(x)\) is true
\(\exists x \in X : A(x)~~\) there exists at least one \(x\in X\) for which \(A(x)\) is true
\(\exists! x \in X : A(x)~~\) there exists exactly one \(x\in X\) for which \(A(x)\) is true
Negation of statements with quantifiers:
\(\neg (\forall x \in X : A(x)) ~\Leftrightarrow~ \exists x \in X : \neg A(x)\)
\(\neg (\exists x \in X : A(x)) ~\Leftrightarrow~ \forall x \in X : \neg A(x)\)
Example 4. There is no greatest natural number:
\(A(n) \;=\; n\) is the greatest natural number
In our notation: \(\neg (\exists n \in \mathbb{N} : A(n))\) this is the same as \(\forall n \in \mathbb{N} : \neg A(n)\), i.e. Each \(n \in \mathbb{N}\) is not the greatest natural number . But this is clear, because \(n+1 > n\).
Rule of Thumb 5 (Negation of the quantifier (\(\forall\) and \(\exists\))).
\(\neg\forall = \exists \neg\) and \(\neg\exists = \forall \neg\)
Example 6. The set \(M:=\{x\in\mathbb{Z} \colon x^2=25\}\) is defined by the set of each integer \(x\) that squares to 25. We immediately see that this is just \(-5\) and \(5\).
Discuss your questions by typing below.
Solve the WeBWorK Exercise
The data for the interactive network on this webpage was generated with pntfx Copyright Fabian Gabel and Julian Großmann. pntfx is licensed under the MIT license. Visualization of the network uses the open-source graph theory library Cytoscape.js licensed under the MIT license.