Back to: Mathematics – Freshman Courses
0
Chapter 1: Propositional Logic and Set Theory
1.2 Open Propositions and Quantifiers
In the previous section, we worked with propositions—statements that are definitively True or False. However, many mathematical sentences contain variables, and their truth value depends on what values are substituted for those variables. Such sentences are called open propositions (or predicates).
1.2.1 What is an Open Proposition?
Definition 1.4: An open proposition (or predicate) is a sentence containing one or more variables such that:
- It becomes a proposition when specific values are substituted for the variables.
- Its truth value depends on those substituted values.
Examples of Open Propositions:
- \( P(x): \) “\(x\) is the day before Sunday.”
→ True if \(x = \text{Saturday}\); False otherwise. - \( Q(y): \) “\(y\) is a city in Africa.”
→ True if \(y = \text{Addis Ababa}\); False if \(y = \text{London}\). - \( R(x): x + 4 = -9 \)
→ True only when \(x = -13\).
Important Note: An open proposition is not a proposition until all its variables are replaced by specific values from a clearly defined universal set.
Universal Set (Universe of Discourse):
The universal set \( U \) is the collection of all allowable values for the variable(s) in an open proposition.
The universal set \( U \) is the collection of all allowable values for the variable(s) in an open proposition.
If \( P(x): x^2 – 1 = 0 \) and \( U = \{-1, -\frac{1}{2}, 0, 1\} \), then:
- \( P(-1) = \text{True} \)
- \( P(-\frac{1}{2}) = \text{False} \)
- \( P(0) = \text{False} \)
- \( P(1) = \text{True} \)
1.2.2 Equivalence of Open Propositions
Definition 1.5: Two open propositions \( P(x) \) and \( Q(x) \) are equivalent over a universal set \( U \) if for every \( a \in U \), the statements \( P(a) \) and \( Q(a) \) have the same truth value.
Let \( U = \{-1, -\frac{1}{2}, 0, 1\} \).
Define:
\( P(x): x^2 – 1 = 0 \)
\( Q(x): |x| \geq 1 \)
Then for every \( a \in U \), \( P(a) \) and \( Q(a) \) are both True or both False. Hence, \( P(x) \equiv Q(x) \) over \( U \).
Define:
\( P(x): x^2 – 1 = 0 \)
\( Q(x): |x| \geq 1 \)
Then for every \( a \in U \), \( P(a) \) and \( Q(a) \) are both True or both False. Hence, \( P(x) \equiv Q(x) \) over \( U \).
1.2.3 Tautologies for Open Propositions
Definition 1.6: An open proposition \( P(x) \) is a tautology over \( U \) if \( P(a) \) is True for every \( a \in U \).
\( P(x): x^2 \geq 0 \) is a tautology over \( U = \mathbb{R} \), since the square of any real number is non-negative.
1.2.4 Converting Open Propositions into Propositions: Quantifiers
Since open propositions are not yet propositions, we use quantifiers to bind their variables and produce definite truth values.
Universal Quantifier (\( \forall \)):
The phrase “for every \( x \in U \)” is symbolized by \( \forall x \).
The statement \( (\forall x)P(x) \) means:
“For all \( x \) in the universal set, \( P(x) \) is true.”
The phrase “for every \( x \in U \)” is symbolized by \( \forall x \).
The statement \( (\forall x)P(x) \) means:
“For all \( x \) in the universal set, \( P(x) \) is true.”
Existential Quantifier (\( \exists \)):
The phrase “there exists an \( x \in U \)” is symbolized by \( \exists x \).
The statement \( (\exists x)P(x) \) means:
“There is at least one \( x \) in the universal set for which \( P(x) \) is true.”
The phrase “there exists an \( x \in U \)” is symbolized by \( \exists x \).
The statement \( (\exists x)P(x) \) means:
“There is at least one \( x \) in the universal set for which \( P(x) \) is true.”
Let \( P(x): x^2 \geq 0 \), with \( U = \mathbb{R} \).
Then \( (\forall x)P(x) \) is True.
Let \( Q(x): x < x^2 \), with \( U = \mathbb{R} \).
Then \( (\forall x)Q(x) \) is False (counterexample: \( x = \frac{1}{2} \)).
But \( (\exists x)Q(x) \) is True (e.g., \( x = -1 \)). Let \( R(x): |x| = -1 \).
Then \( (\exists x)R(x) \) is False (no real number has negative absolute value).
Then \( (\forall x)P(x) \) is True.
Let \( Q(x): x < x^2 \), with \( U = \mathbb{R} \).
Then \( (\forall x)Q(x) \) is False (counterexample: \( x = \frac{1}{2} \)).
But \( (\exists x)Q(x) \) is True (e.g., \( x = -1 \)). Let \( R(x): |x| = -1 \).
Then \( (\exists x)R(x) \) is False (no real number has negative absolute value).
1.2.5 Four Fundamental Quantified Statements
Given an open proposition \( P(x) \), the following four statements are central:
| Statement | English Translation |
|---|---|
| \( (\forall x)P(x) \) | Everything has property \( P \). |
| \( (\exists x)P(x) \) | Something has property \( P \). |
| \( (\forall x)\neg P(x) \) | Nothing has property \( P \). |
| \( (\exists x)\neg P(x) \) | Something does not have property \( P \). |
Notice:
- \( (\exists x)\neg P(x) \) is the negation of \( (\forall x)P(x) \).
- \( (\forall x)\neg P(x) \) is the negation of \( (\exists x)P(x) \).
1.2.6 Negation of Quantified Statements
The rules for negating quantifiers are:
- \( \neg(\forall x)P(x) \equiv (\exists x)\neg P(x) \)
- \( \neg(\exists x)P(x) \equiv (\forall x)\neg P(x) \)
- Flip \( \forall \leftrightarrow \exists \)
- Negate the open proposition \( P(x) \)
Examples:
- \( \neg(\exists x)(x < x^2) \equiv (\forall x)\neg(x < x^2) \equiv (\forall x)(x \geq x^2) \)
- \( \neg(\forall x)(4x + 1 = 0) \equiv (\exists x)(4x + 1 \ne 0) \)
1.2.7 Translating English into Quantified Logic
Common translations (with \( U = \mathbb{R} \) or appropriate context):
| English Sentence | Logical Form |
|---|---|
| All rationals are reals. | \( (\forall x)(\mathbb{Q}(x) \Rightarrow \mathbb{R}(x)) \) |
| No rationals are reals. | \( (\forall x)(\mathbb{Q}(x) \Rightarrow \neg\mathbb{R}(x)) \) |
| Some rationals are reals. | \( (\exists x)(\mathbb{Q}(x) \land \mathbb{R}(x)) \) |
| Some rationals are not reals. | \( (\exists x)(\mathbb{Q}(x) \land \neg\mathbb{R}(x)) \) |
Caution: “All \( A \) are \( B \)” uses implication (\( \Rightarrow \)),
but “Some \( A \) are \( B \)” uses conjunction (\( \land \)).
but “Some \( A \) are \( B \)” uses conjunction (\( \land \)).
1.2.8 Multiple Quantifiers
Quantifiers can be nested. Order matters!
Common combinations:
- \( (\forall x)(\forall y)P(x,y) \): “For all \( x \) and all \( y \), \( P(x,y) \) holds.”
- \( (\exists x)(\exists y)P(x,y) \): “There exist \( x \) and \( y \) such that \( P(x,y) \) holds.”
- \( (\forall x)(\exists y)P(x,y) \): “For every \( x \), there exists a \( y \) (possibly depending on \( x \)) such that \( P(x,y) \) holds.”
- \( (\exists x)(\forall y)P(x,y) \): “There exists an \( x \) that works for all \( y \).”
Let \( U = \mathbb{Z} \), \( P(x,y): x + y = 5 \).
- \( (\exists x)(\exists y)P(x,y) \): True (e.g., \( x=4, y=1 \))
- \( (\exists x)(\forall y)P(x,y) \): False (no single \( x \) works for all \( y \))
- \( (\forall x)(\exists y)P(x,y) \): True (for any \( x \), choose \( y = 5 – x \))
- \( (\forall x)(\forall y)P(x,y) \): False (e.g., \( x=2,y=7 \Rightarrow 9 \ne 5 \))
Logical Relationship:
\( (\exists y)(\forall x)P(x,y) \Rightarrow (\forall x)(\exists y)P(x,y) \),
but the converse is not true.
\( (\exists y)(\forall x)P(x,y) \Rightarrow (\forall x)(\exists y)P(x,y) \),
but the converse is not true.
1.2.9 Summary of Key Ideas
- An open proposition contains variables and becomes a proposition only when values are assigned.
- The universal set \( U \) defines allowable values for variables.
- Quantifiers (\( \forall, \exists \)) turn open propositions into propositions.
- Negation flips the quantifier and negates the predicate.
- Order of multiple quantifiers is crucial—\( \forall\exists \ne \exists\forall \).
End of Section 1.2 – Open Propositions and Quantifiers
Section 1.2: Open Propositions and Quantifiers – Exercises with Full Solutions
Exercise 1. In each of the following, two open statements \(P(x, y)\) and \(Q(x, y)\) are given, where the domain of both \(x\) and \(y\) is \(\mathbb{R}\). Determine the truth value of \(P(x, y) \Rightarrow Q(x, y)\) for the given values of \(x\) and \(y\).
a. \(P(x, y): x^2 – y^2 = 0\), \(Q(x, y): x = y\), \((x, y) \in \{(1, -1), (3, 4), (5, 5)\}\).
b. \(P(x, y): |x| = |y|\), \(Q(x, y): x = y\), \((x, y) \in \{(1, 2), (2, -2), (6, 6)\}\).
c. \(P(x, y): x^2 + y^2 = 1\), \(Q(x, y): x + y = 1\), \((x, y) \in \{(1, -1), (-3, 4), (0, -1), (1, 0)\}\).
a. \(P(x, y): x^2 – y^2 = 0\), \(Q(x, y): x = y\), \((x, y) \in \{(1, -1), (3, 4), (5, 5)\}\).
b. \(P(x, y): |x| = |y|\), \(Q(x, y): x = y\), \((x, y) \in \{(1, 2), (2, -2), (6, 6)\}\).
c. \(P(x, y): x^2 + y^2 = 1\), \(Q(x, y): x + y = 1\), \((x, y) \in \{(1, -1), (-3, 4), (0, -1), (1, 0)\}\).
Solution:
Recall: \(P \Rightarrow Q\) is **false only when \(P\) is true and \(Q\) is false**.
a.
Recall: \(P \Rightarrow Q\) is **false only when \(P\) is true and \(Q\) is false**.
a.
- \((1, -1)\): \(P: 1 – 1 = 0\) → T; \(Q: 1 = -1\) → F ⇒ \(P \Rightarrow Q = \textbf{F}\)
- \((3, 4)\): \(P: 9 – 16 = -7 \ne 0\) → F ⇒ implication = T
- \((5, 5)\): \(P: 25 – 25 = 0\) → T; \(Q: 5 = 5\) → T ⇒ T
- \((1, 2)\): \(|1| = 1 \ne 2 = |2|\) → \(P = F\) ⇒ T
- \((2, -2)\): \(|2| = |-2| = 2\) → \(P = T\); \(Q: 2 = -2\) → F ⇒ \(P \Rightarrow Q = \textbf{F}\)
- \((6, 6)\): both T ⇒ T
- \((1, -1)\): \(1 + 1 = 2 \ne 1\) → \(P = F\) ⇒ T
- \((-3, 4)\): \(9 + 16 = 25 \ne 1\) → \(P = F\) ⇒ T
- \((0, -1)\): \(0 + 1 = 1\) → \(P = T\); \(Q: 0 + (-1) = -1 \ne 1\) → F ⇒ **F**
- \((1, 0)\): \(1 + 0 = 1\) → \(P = T\); \(Q: 1 + 0 = 1\) → T ⇒ T
Exercise 2. Let \(O\) denote the set of odd integers and let \(P(x): x^2 + 1\) is even, and \(Q(x): x^2\) is even, be open statements over the domain \(O\). State \((\forall x \in O)P(x)\) and \((\exists y \in O)Q(x)\) in words.
Solution:
– \((\forall x \in O)P(x)\): “For every odd integer \(x\), \(x^2 + 1\) is even.”
– \((\exists y \in O)Q(x)\): “There exists an odd integer \(y\) such that \(y^2\) is even.”
Note: The second statement is **false** (since square of odd is always odd), but the request was only to translate into words.
– \((\forall x \in O)P(x)\): “For every odd integer \(x\), \(x^2 + 1\) is even.”
– \((\exists y \in O)Q(x)\): “There exists an odd integer \(y\) such that \(y^2\) is even.”
Note: The second statement is **false** (since square of odd is always odd), but the request was only to translate into words.
Exercise 3. State the negation of the following quantified statements.
a. For every rational number \(r\), the number \(\frac{1}{r}\) is rational.
b. There exists a rational number \(r\) such that \(r^2 = 2\).
a. For every rational number \(r\), the number \(\frac{1}{r}\) is rational.
b. There exists a rational number \(r\) such that \(r^2 = 2\).
Solution:
Use: \(\neg(\forall x)P(x) \equiv (\exists x)\neg P(x)\), and \(\neg(\exists x)P(x) \equiv (\forall x)\neg P(x)\).
a. \(\neg\big[(\forall r \in \mathbb{Q})(\frac{1}{r} \in \mathbb{Q})\big] \equiv (\exists r \in \mathbb{Q})(\frac{1}{r} \notin \mathbb{Q})\)
→ “There exists a rational number \(r\) such that \(\frac{1}{r}\) is **not** rational.”
b. \(\neg\big[(\exists r \in \mathbb{Q})(r^2 = 2)\big] \equiv (\forall r \in \mathbb{Q})(r^2 \ne 2)\)
→ “For every rational number \(r\), \(r^2 \ne 2\).”
Use: \(\neg(\forall x)P(x) \equiv (\exists x)\neg P(x)\), and \(\neg(\exists x)P(x) \equiv (\forall x)\neg P(x)\).
a. \(\neg\big[(\forall r \in \mathbb{Q})(\frac{1}{r} \in \mathbb{Q})\big] \equiv (\exists r \in \mathbb{Q})(\frac{1}{r} \notin \mathbb{Q})\)
→ “There exists a rational number \(r\) such that \(\frac{1}{r}\) is **not** rational.”
b. \(\neg\big[(\exists r \in \mathbb{Q})(r^2 = 2)\big] \equiv (\forall r \in \mathbb{Q})(r^2 \ne 2)\)
→ “For every rational number \(r\), \(r^2 \ne 2\).”
Exercise 4. Let \(P(n): \frac{5n – 6}{3}\) is an integer, be an open sentence over the domain \(\mathbb{Z}\). Determine, with explanations, whether the following statements are true or false:
a. \((\forall n \in \mathbb{Z})P(n)\)
b. \((\exists n \in \mathbb{Z})P(n)\)
a. \((\forall n \in \mathbb{Z})P(n)\)
b. \((\exists n \in \mathbb{Z})P(n)\)
Solution:
\(P(n)\) is true ⇔ \(5n – 6\) divisible by 3 ⇔ \(5n \equiv 6 \pmod{3}\) ⇔ \(2n \equiv 0 \pmod{3}\) ⇔ \(n \equiv 0 \pmod{3}\).
a. **False.** Counterexample: \(n = 1\) → \((5 – 6)/3 = -1/3\) → not integer.
b. **True.** Example: \(n = 3\) → \((15 – 6)/3 = 9/3 = 3\) → integer.
\(P(n)\) is true ⇔ \(5n – 6\) divisible by 3 ⇔ \(5n \equiv 6 \pmod{3}\) ⇔ \(2n \equiv 0 \pmod{3}\) ⇔ \(n \equiv 0 \pmod{3}\).
a. **False.** Counterexample: \(n = 1\) → \((5 – 6)/3 = -1/3\) → not integer.
b. **True.** Example: \(n = 3\) → \((15 – 6)/3 = 9/3 = 3\) → integer.
Exercise 5. Determine the truth value of the following statements.
a. \((\exists x \in \mathbb{R})(x^2 – x = 0)\)
b. \((\forall x \in \mathbb{N})(x + 1 \geq 2)\)
c. \((\forall x \in \mathbb{R})(\sqrt{x^2} = x)\)
d. \((\exists x \in \mathbb{Q})(3x^2 – 27 = 0)\)
e. \((\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(x + y + 3 = 8)\)
f. \((\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(x^2 + y^2 = 9)\)
g. \((\forall x \in \mathbb{R})(\exists y \in \mathbb{R})(x + y = 5)\)
h. \((\exists x \in \mathbb{R})(\forall y \in \mathbb{R})(x + y = 5)\)
a. \((\exists x \in \mathbb{R})(x^2 – x = 0)\)
b. \((\forall x \in \mathbb{N})(x + 1 \geq 2)\)
c. \((\forall x \in \mathbb{R})(\sqrt{x^2} = x)\)
d. \((\exists x \in \mathbb{Q})(3x^2 – 27 = 0)\)
e. \((\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(x + y + 3 = 8)\)
f. \((\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(x^2 + y^2 = 9)\)
g. \((\forall x \in \mathbb{R})(\exists y \in \mathbb{R})(x + y = 5)\)
h. \((\exists x \in \mathbb{R})(\forall y \in \mathbb{R})(x + y = 5)\)
Solution:
a. **True** (e.g., \(x = 0\) or \(x = 1\))
b. **True** (since \(\mathbb{N} = \{1,2,3,\dots\}\), so \(x+1 \ge 2\))
c. **False** (e.g., \(x = -1\): \(\sqrt{(-1)^2} = 1 \ne -1\))
d. **True** → \(x^2 = 9\) → \(x = \pm 3 \in \mathbb{Q}\)
e. **True** (e.g., \(x = 2, y = 3\))
f. **True** (e.g., \(x = 0, y = 3\))
g. **True**: for any \(x\), choose \(y = 5 – x\)
h. **False**: no single \(x\) works for **all** \(y\)
a. **True** (e.g., \(x = 0\) or \(x = 1\))
b. **True** (since \(\mathbb{N} = \{1,2,3,\dots\}\), so \(x+1 \ge 2\))
c. **False** (e.g., \(x = -1\): \(\sqrt{(-1)^2} = 1 \ne -1\))
d. **True** → \(x^2 = 9\) → \(x = \pm 3 \in \mathbb{Q}\)
e. **True** (e.g., \(x = 2, y = 3\))
f. **True** (e.g., \(x = 0, y = 3\))
g. **True**: for any \(x\), choose \(y = 5 – x\)
h. **False**: no single \(x\) works for **all** \(y\)
Exercise 6. Consider the quantified statement: “For every \(x \in A\) and \(y \in A\), \(xy – 2\) is prime,” where \(A = \{3, 5, 11\}\).
a. Express this in symbols.
b. Is it true or false?
c. Express its negation in symbols.
d. Is the negation true?
a. Express this in symbols.
b. Is it true or false?
c. Express its negation in symbols.
d. Is the negation true?
Solution:
a. \((\forall x \in A)(\forall y \in A)(xy – 2 \text{ is prime})\)
b. Check all pairs:
c. Negation: \((\exists x \in A)(\exists y \in A)(xy – 2 \text{ is not prime})\)
d. **True** (e.g., \(x = y = 11\))
a. \((\forall x \in A)(\forall y \in A)(xy – 2 \text{ is prime})\)
b. Check all pairs:
- \(3 \cdot 3 – 2 = 7\) → prime
- \(3 \cdot 5 – 2 = 13\) → prime
- \(3 \cdot 11 – 2 = 31\) → prime
- \(5 \cdot 3 – 2 = 13\)
- \(5 \cdot 5 – 2 = 23\)
- \(5 \cdot 11 – 2 = 53\)
- \(11 \cdot 3 – 2 = 31\)
- \(11 \cdot 5 – 2 = 53\)
- \(11 \cdot 11 – 2 = 119 = 7 \cdot 17\) → **not prime**
c. Negation: \((\exists x \in A)(\exists y \in A)(xy – 2 \text{ is not prime})\)
d. **True** (e.g., \(x = y = 11\))
Exercise 7. Let \(P(x, y): \frac{x}{y} < 1\), with domain \(x \in A = \{2, 3, 5\}\), \(y \in B = \{2, 4, 6\}\).
a. State \((\forall x \in A)(\exists y \in B)P(x, y)\) in words.
b. Show it is true.
a. State \((\forall x \in A)(\exists y \in B)P(x, y)\) in words.
b. Show it is true.
Solution:
a. “For every \(x\) in \(\{2,3,5\}\), there exists a \(y\) in \(\{2,4,6\}\) such that \(\frac{x}{y} < 1\).”
b. Verify:
a. “For every \(x\) in \(\{2,3,5\}\), there exists a \(y\) in \(\{2,4,6\}\) such that \(\frac{x}{y} < 1\).”
b. Verify:
- \(x = 2\): choose \(y = 4\) → \(2/4 = 0.5 < 1\)
- \(x = 3\): choose \(y = 4\) → \(3/4 = 0.75 < 1\)
- \(x = 5\): choose \(y = 6\) → \(5/6 < 1\)
Exercise 8. Let \(P(x, y): x – y < 0\), with \(x \in A = \{3, 5, 8\}\), \(y \in B = \{3, 6, 10\}\).
a. State \((\exists y \in B)(\forall x \in A)P(x, y)\) in words.
b. Show it is true.
a. State \((\exists y \in B)(\forall x \in A)P(x, y)\) in words.
b. Show it is true.
Solution:
a. “There exists a \(y \in \{3,6,10\}\) such that for **every** \(x \in \{3,5,8\}\), \(x – y < 0\).”
b. Try \(y = 10\):
a. “There exists a \(y \in \{3,6,10\}\) such that for **every** \(x \in \{3,5,8\}\), \(x – y < 0\).”
b. Try \(y = 10\):
- \(3 – 10 = -7 < 0\)
- \(5 – 10 = -5 < 0\)
- \(8 – 10 = -2 < 0\)
All exercises from Section 1.2: Open Propositions and Quantifiers with complete solutions.