We often consider very similar propositions over and over: \(3 \lt 5\text{,}\)\(2 \lt 5\text{,}\)\(7 \lt 5\text{,}\) etc... In this section, we take what is in common with these statements and build a generic function whose input is from some domain (in this example, numbers), and whose output is either true or false.
For example, if my predicate function is “\(x\) is sharp”, the function has a different meaning if my universe of discourse is “all college students” versus “all tools.”
The domain of discourse is the domain of the propositional function. Like all functions, it depends on the particular function we’re considering. The codomain of a propositional function will always be the set \(\{\text{true, false}\}\text{.}\)
With the idea of generic propositional functions taken care of, we now want to make sweeping claims about the truth of a propositional function over some domain. Is the statement true for every value in the domain? Is the statement true for some specific value? These questions come up so frequently in mathematics that we give them each their own symbol.
The universal quantification of \(P(x)\) is the statement that \(P(x)\) is true for all values of \(x\) in the domain of discourse. We write \(\forall x P(x)\)
The existential quantification of \(P(x)\) is the statement that there is some value \(x\) in the universe of discourse for which \(P(x)\) is true. We write \(\exists x P(x)\)
Counterexamples to universal statements work because if \(\exists x \neg P(x)\) is true, then \(\neg \forall x P(x)\) is also true, that is, \(\forall x P(x)\) is false!
If the universe of discourse is all people at the university, and \(P(x)\) is the statement “\(x\) loves to drink coffee,” express each statement in plain English:
Let \(C(x)\) denote the predicate “\(x\) is in the correct place”, let \(E(x)\) denote “\(x\) is in excellent condition”, and let \(T(x)\) denote “\(x\) is a tool” where the domain of each predicate is the set of objects in a garage. Translate each into plain English:
Applying DeMorgan’s laws many, many times and noting that the opposite of \(x\lt a\) is \(x \ge a\text{:}\)
\begin{align*}
\amp\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\
\amp\equiv \neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\
\amp \equiv \exists x \neg \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\
\amp \equiv \exists x \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\
\amp \equiv \exists x \forall y \neg(x \lt y ) \lor \neg ( \exists z (x \lt z \vee y \lt z)) ) \\
\amp \equiv \exists x \forall y \neg(x \lt y ) \lor \forall z \neg (x \lt z \vee y \lt z)) ) \\
\amp \equiv \exists x \forall y \neg(x \lt y ) \lor \forall z \neg (x \lt z) \land \neg (y \lt z))) \\
\amp \equiv \exists x \forall y (x \ge y ) \lor \forall z (x \ge z) \land (y \ge z)))
\end{align*}
This statement can be written \(\exists n \neg \exists x (x \le n)\text{.}\) It can be simplified as \(\exists n \forall x \neg (x \le n)\text{,}\) and even further as \(\exists n \forall x (x \gt n)\)
This statement can be written \(\neg \forall n \exists x \exists y (x \lt n \lt y)\)
\begin{align*}
\neg \forall n \exists x \exists y (x \lt n \lt y) \amp \equiv \exists n \neg \exists x \exists y (x \lt n \lt y) \\
\amp \equiv \exists n \forall x \neg \exists y (x \lt n \lt y) \\
\amp \equiv \exists n \forall x \forall y \neg (x \lt n \lt y)
\end{align*}
Let \(c\) come from the universe of colleges in the US, \(b\) be from the universe of buildings on a chosen campus and \(r\) be the rooms in a chosen building.
Start with the negation on the left and apply DeMorgan’s laws
\begin{align*}
\amp \neg \exists c \exists b \forall r (b \text{ on the campus of } c \text{ in
which } r \text{ is painted white})\\
\amp \equiv \forall c \forall b \exists r \neg(b \text{ on the campus of } c
\text{ in which } r \text{ is painted white})
\end{align*}
