Discreet Math - Chapter 3.1 - " Predicates and Quantified Statements I" NOTES

Predicates and Open Sentences

Foundational Quote:
- "…it was not till within the last few years that it has been realized how fundamental any and some are to the very nature of mathematics." — A. N. Whitehead (1861–1947)
Context and Logic Background:
- Sentences such as " $x^2 + 2 = 11$ " or " $x + y = 12$ " are not statements because their truth value depends entirely on the specific values assigned to the variables $x$ and $y$ .
- In grammar, a predicate is the part of a sentence that provides information about the subject. For instance, in the sentence "James is a student at Bedford College," "James" is the subject and "is a student at Bedford College" is the predicate.
- In mathematical logic, predicates are obtained by removing some or all nouns from a statement:
  - Let $P$ stand for "is a student at Bedford College".
  - Let $Q$ stand for "is a student at".
  - $P$ and $Q$ are predicate symbols.
  - The sentences " $x$ is a student at Bedford College" and " $x$ is a student at $y$ " are symbolized as $P(x)$ and $Q(x, y)$ , respectively, where $x$ and $y$ are predicate variables taking values in appropriate sets.
- When concrete values are substituted for predicate variables, a statement results.
- Predicates are also referred to as propositional functions or open sentences.
Definition of Predicate:
- A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables.
Definition of Domain:
- The domain of a predicate variable is the set of all values that may be substituted in place of the variable.
Example 3.1.1: Finding Truth Values of a Predicate:
- Let $P(x)$ be the predicate " $x^2 > x$ " with domain the set $\mathbf{R}$ of all real numbers. Write $P(2)$ , $P\left(\frac{1}{2}\right)$ , and $P\left(-\frac{1}{2}\right)$ , and indicate which of these statements are true and which are false.
- Solution:
  - $P(2)$ : $2^2 > 2$ , or $4 > 2$ . True.
  - $P\left(\frac{1}{2}\right)$ : $\left(\frac{1}{2}\right)^2 > \frac{1}{2}$ , or $\frac{1}{4} > \frac{1}{2}$ . False.
  - $P\left(-\frac{1}{2}\right)$ : $\left(-\frac{1}{2}\right)^2 > -\frac{1}{2}$ , or $\frac{1}{4} > -\frac{1}{2}$ . True.

Truth Sets of Predicates

Definition of Truth Set:
- If $P(x)$ is a predicate and $x$ has domain $D$ , the truth set of $P(x)$ is the set of all elements of $D$ that make $P(x)$ true when they are substituted for $x$ .
- The truth set of $P(x)$ is denoted as: $\{x \in D \mid P(x)\}$
- This symbolic expression is read out loud as "the set of all $x$ in $D$ such that $P(x)$ ".
Example 3.1.2: Finding the Truth Set of a Predicate:
- Let $Q(n)$ be the predicate " $n$ is a factor of $8$ ". Find the truth set of $Q(n)$ if:
  - a. The domain of $n$ is $\mathbf{Z}^+$ , the set of all positive integers.
  - b. The domain of $n$ is $\mathbf{Z}$ , the set of all integers.
- Solution:
  - a. The truth set is $\{1, 2, 4, 8\}$ because these are exactly the positive integers that divide $8$ evenly.
  - b. The truth set is $\{1, 2, 4, 8, -1, -2, -4, -8\}$ because the negative integers $-1$ , $-2$ , $-4$ , and $-8$ also divide into $8$ without leaving a remainder.

The Universal Quantifier (\\\forall\\)

Quantifiers Overview:
- Statements can be obtained from predicates either by substituting specific values for variables or by adding quantifiers.
- Quantifiers are words that refer to quantities such as "some" or "all" and tell for how many elements a given predicate is true.
- The formal concept of quantifier was introduced into symbolic logic in the late nineteenth century by the American philosopher, logician, and engineer Charles Sanders Peirce (1839–1914) and, independently, by the German logician Gottlob Frege (1848–1925).
Universal Quantifier Symbol and Reading:
- The symbol $\forall$ denotes the universal quantifier.
- It is read as "for every", "for each", "for any", "given any", or "for all".
- Example: "Every human being is mortal" or "All human beings are mortal" can be rewritten as: $\text{"For every human being } x\text{, } x \text{ is mortal."}$
- If $H$ is the set of all human beings, it is symbolized formally as: $\forall x \in H, x \text{ is mortal}$
- Grammar rule: Think of the symbol $x$ as an individual but generic object possessing all properties shared by every element of the domain. Use singular verbs (e.g., "For all $x$ in $H$ , $x$ is mortal", not "are mortal").
- Domain placement: Positioned either between the $\forall$ symbol and the variable name (e.g., $\forall \text{ human being } x$ ) or immediately following the variable name (e.g., $\forall x \in H$ ).
- Multiple variables: The $\forall$ symbol can refer to multiple variables simultaneously (e.g., $\forall \text{ real numbers } x \text{ and } y, x + y = y + x$ ).
Definition of Universal Statement:
- Let $Q(x)$ be a predicate and $D$ the domain of $x$ . A universal statement is a statement of the form: $\forall x \in D, Q(x)$
- It is defined to be true if, and only if, $Q(x)$ is true for each individual $x$ in $D$ .
- A value for $x$ for which $Q(x)$ is false is called a counterexample to the universal statement.
- Example 3.1.3: Truth and Falsity of Universal Statements:
  - a. Let $D = \{1, 2, 3, 4, 5\}$ , and consider the statement: $\forall x \in D, x^2 \ge x$ Write one way to read this statement out loud, and show that it is true.
  - b. Consider the statement: $\forall x \in \mathbf{R}, x^2 \ge x$ Find a counterexample to show that this statement is false.
  - Solution:
  - a. Read out loud: "For every $x$ in the set $D$ , $x^2$ is greater than or equal to $x$ ". Evaluated for each individual element:
    - $1^2 \ge 1 \implies 1 \ge 1$ (True)
    - $2^2 \ge 2 \implies 4 \ge 2$ (True)
    - $3^2 \ge 3 \implies 9 \ge 3$ (True)
    - $4^2 \ge 4 \implies 16 \ge 4$ (True)
    - $5^2 \ge 5 \implies 25 \ge 5$ (True)
    - Hence, " $\forall x \in D, x^2 \ge x$ " is true.
  - b. Counterexample: The statement claims $x^2 \ge x$ for every real number $x$ . But when $x = \frac{1}{2}$ , for example: $\left(\frac{1}{2}\right)^2 = \frac{1}{4} \ge \frac{1}{2}$ is false, since $\frac{1}{4} < \frac{1}{2}$ . Hence, " $\forall x \in \mathbf{R}, x^2 \ge x$ " is false.
- Method of Exhaustion:
  - The technique used to show the truth of a universal statement by evaluating the predicate separately for every individual element of a finite domain is called the method of exhaustion.
  - This method can be used whenever the domain of the predicate variable is finite.
  - Digital computers and computer expert systems (knowledge-based systems) make heavy use of the method of exhaustion. However, because most mathematical sets are infinite, the method of exhaustion cannot be used to derive general mathematical proofs over infinite domains.
The Existential Quantifier ( $\exists$ )
- Existential Quantifier Symbol and Reading:
  - The symbol $\exists$ denotes the existential quantifier.
  - It represents "there exists", "there is a", "we can find a", "there is at least one", "for some", or "for at least one".
  - Example: "There is a student in Math 140" can be written as: $\exists \text{ a student } x \text{ such that } x \text{ is in Math 140}$ Or more formally, letting $P$ be the set of all people: $\exists x \in P \text{ such that } x \text{ is a student in Math 140}$
  - The phrase "such that" is inserted immediately preceding the predicate.
  - In expressions like " $\exists \text{ integers } a \text{ and } b \text{ such that } a + b = 10$ ", the $\exists$ symbol refers to both variables $a$ and $b$ .
- Definition of Existential Statement:
  - Let $Q(x)$ be a predicate and $D$ the domain of $x$ . An existential statement is a statement of the form: $\exists x \in D \text{ such that } Q(x)$
  - It is defined to be true if, and only if, $Q(x)$ is true for at least one $x$ in $D$ .
- Example 3.1.4: Truth and Falsity of Existential Statements:
  - a. Consider the statement: $\exists m \in \mathbf{Z}^+ \text{ such that } m^2 = m$ Write one way to read this statement out loud, and show that it is true.
  - b. Let $E = \{5, 6, 7, 8\}$ and consider the statement: $\exists m \in E \text{ such that } m^2 = m$ Show that this statement is false.
  - Solution:
  - a. Read out loud: "There is at least one positive integer $m$ such that $m^2 = m$ ". Observe that $1^2 = 1$ . Thus " $m^2 = m$ " is true for positive integer $m = 1$ , so " $\exists m \in \mathbf{Z}^+ \text{ such that } m^2 = m$ " is true.
  - b. Note that $m^2 = m$ is not true for any integer $m$ from $5$ through $8$ :
    - $5^2 = 25 \neq 5$
    - $6^2 = 36 \neq 6$
    - $7^2 = 49 \neq 7$
    - $8^2 = 64 \neq 8$
    - Thus " $\exists m \in E \text{ such that } m^2 = m$ " is false.
Translating Between Formal and Informal Language
- Example 3.1.5: Translating from Formal to Informal Language:
  - Rewrite formal statements without using symbols $\forall$ or $\exists$ :
  - a. $\forall x \in \mathbf{R}, x^2 \ge 0$
    - Translations: "Every real number has a nonnegative square." OR "All real numbers have nonnegative squares." OR "Any real number has a nonnegative square." OR "The square of each real number is nonnegative."
  - b. $\forall x \in \mathbf{R}, x^2 \neq -1$
    - Translations: "All real numbers have squares that do not equal $-1$ ". OR "No real numbers have squares equal to $-1$ ".
    - Note: The words none are or no … are are equivalent to all are not.
  - c. $\exists m \in \mathbf{Z}^+ \text{ such that } m^2 = m$
    - Translations: "There is a positive integer whose square is equal to itself." OR "We can find at least one positive integer equal to its own square." OR "Some positive integer equals its own square." OR "Some positive integers equal their own squares."
    - Note: In ordinary English, "some positive integers" might imply at least two, but in mathematics, "some positive integer" and "some positive integers" mean the exact same thing (at least one).
- Trailing Quantifiers:
  - Quantification can be placed at the end of a sentence rather than the beginning.
  - Example 3.1.6: Trailing Quantifiers:
  - a. "For any integer $n$ , $n^2$ is even." $\rightarrow$ " $n^2$ is even for any integer $n$ ".
  - b. "There exists at least one real number $x$ such that $x^2 = 0$ ". $\rightarrow$ " $x^2 = 0$ for some real number $x$ " OR " $x^2 = 0$ for at least one real number $x$ ".
- Example 3.1.7: Translating from Informal to Formal Language:
  - Rewrite formally using quantifiers and variables:
  - a. "All triangles have three sides."
    - Formal: $\forall \text{ triangle } t, t \text{ has three sides}$ OR $\forall t \in T, t \text{ has three sides}$ (where $T$ is the set of all triangles).
    - Note: "All triangles have three sides" and "Every triangle has three sides" mean the same thing.
  - b. "No dogs have wings."
    - Formal: $\forall \text{ dog } d, d \text{ does not have wings}$ OR $\forall d \in D, d \text{ does not have wings}$ (where $D$ is the set of all dogs).
  - c. "Some programs are structured."
    - Formal: $\exists \text{ a program } p \text{ such that } p \text{ is structured}$ OR $\exists p \in P \text{ such that } p \text{ is structured}$ (where $P$ is the set of all programs).
Universal Conditional Statements
- Form:
  - A universal conditional statement has the form: $\forall x, \text{if } P(x) \text{ then } Q(x)$
  - This is considered one of the most fundamental statement forms in mathematics.
- Example 3.1.8: Writing Universal Conditional Statements Informally:
  - Rewrite $\forall x \in \mathbf{R}, \text{if } x > 2 \text{ then } x^2 > 4$ informally:
  - "If a real number is greater than $2$ , then its square is greater than $4$ ".
  - "Whenever a real number is greater than $2$ , its square is greater than $4$ ".
  - "The square of any real number greater than $2$ is greater than $4$ ".
  - "The squares of all real numbers greater than $2$ are greater than $4$ ".
- Example 3.1.9: Writing Universal Conditional Statements Formally:
  - Rewrite in the form $\forall \underline{\quad}, \text{if } \underline{\quad} \text{ then } \underline{\quad}$ :
  - a. "If a real number is an integer, then it is a rational number."
    - Formal: $\forall \text{ real number } x, \text{if } x \text{ is an integer, then } x \text{ is a rational number}$ .
  - b. "All bytes have eight bits."
    - Formal: $\forall x, \text{if } x \text{ is a byte, then } x \text{ has eight bits}$ .
  - c. "No fire trucks are green."
    - Formal: $\forall x, \text{if } x \text{ is a fire truck, then } x \text{ is not green}$ .
- Logical Insight into Conditional Truth Tables:
  - Consider $\forall x \in \mathbf{R}, \text{if } x > 2 \text{ then } x^2 > 4$ . This statement is known to be true for all real numbers $x$ .
  - When $x = 1$ : Hypothesis " $1 > 2$ " is false; Conclusion " $1^2 > 4$ " ( $1 > 4$ ) is false.
  - When $x = -3$ : Hypothesis " $-3 > 2$ " is false; Conclusion " $(-3)^2 > 4$ " ( $9 > 4$ ) is true.
  - In both cases, because the universal conditional statement as a whole is true, an if-then statement with a false hypothesis must be defined as true regardless of whether its conclusion is true or false.
- Definition of Valid Argument:
  - A valid argument is itself a universal conditional statement: "For every combination of truth values for the component statements, if the premises are all true then the conclusion is also true."
Equivalent Forms of Universal and Existential Statements
- Universal Equivalences:
  - A universal conditional statement of the form: $\forall x \in U, \text{if } P(x) \text{ then } Q(x)$
  - Can be rewritten without a conditional by restricting the domain to subset $D = \{x \in U \mid P(x)\}$ : $\forall x \in D, Q(x)$
  - Example 3.1.10: Equivalent Forms for Universal Statements:
  - Statement: "All squares are rectangles."
  - Form 1 ( $\forall x, \text{if } P(x) \text{ then } Q(x)$ ).: $\forall x, \text{if } x \text{ is a square, then } x \text{ is a rectangle}$ .
  - Form 2 ( $\forall x \in D, Q(x)$ ): $\forall x \in S, x \text{ is a rectangle}$ (where $S$ is the set of all squares).
- Existential Equivalences:
  - A statement of the form: $\exists x \text{ such that } P(x) \text{ and } Q(x)$
  - Can be rewritten as: $\exists x \in D \text{ such that } Q(x)$ where $D = \{x \mid P(x)\}$ is the set of all elements for which $P(x)$ is true.
  - Example 3.1.11: Equivalent Forms for Existential Statements:
  - Definition: A prime number is an integer greater than $1$ whose only positive integer factors are itself and $1$ .
  - Statement: "There is an integer that is both prime and even."
  - Let $P(x)$ be " $x$ is prime" and $E(x)$ be " $x$ is even".
    - a. Form $\exists x \text{ such that } P(x) \text{ and } Q(x)$ : $\exists x \in \mathbf{Z} \text{ such that } P(x) \land E(x)$ .
    - b. Form $\exists x \in D \text{ such that } Q(x)$ : $\exists \text{ a prime number } x \text{ such that } x \text{ is even}$ OR $\exists \text{ an even number } x \text{ such that } x \text{ is prime}$ .
Bound Variables and Scope
- Placeholder Nature of Variables:
  - The specific letter chosen for a variable in a quantified statement does not alter the statement's logical meaning:
  - $\forall n \in \mathbf{Z}, n^2 \ge 0$
  - $\forall x \in \mathbf{Z}, x^2 \ge 0$
  - $\forall u \in \mathbf{Z}, u^2 \ge 0$
  - All three statements convey identical mathematical meaning.
- Definitions of Bound Variable and Scope:
  - A variable is bound by the quantifier that controls it.
  - The scope of a bound variable begins when the quantifier introduces it and ends at the end of the quantified statement.
  - Variable names can be reused in different statements without conflict:
  - Statement (1): $\forall x \in \mathbf{Z}, x^2 \ge 0$
  - Statement (2): $\exists x \in \mathbf{R} \text{ such that } x^2 = 0$
  - The $x$ in Statement (1) and the $x$ in Statement (2) serve completely distinct roles bounded by their respective quantifiers.
- Analogy to Computer Programming:
  - Variables in mathematics operate like local variables in computer functions.
  - Consider two Python programs:
  - Program 1: def f(): X = "Hi"; print(X) and def g(): X = "Bye"; print(X)
  - Program 2: def f(): S = "Hi"; print(S) and def g(): S = "Bye"; print(S)
  - Output for both programs: text Hi Bye       
  - In both cases, X or S is local to the function defining it, created on function call, and destroyed upon completion. Its scope is restricted to that function, allowing function definitions to reuse variable names independently.
Implicit Quantification and Logical Implication Notation
- Implicit Universal and Existential Quantification:
  - Quantifiers are frequently implied rather than explicitly stated.
  - Indefinite articles ("a", "an") often signal quantification:
  - "If a number is an integer, then it is a rational number" (Implicit Universal Quantification).
  - "The number $8$ can be written as a sum of two even integers" (Implicit Existential Quantification: $\exists \text{ even integers } a \text{ and } b \text{ such that } 8 = a + b$ ).
  - Contextual quantification: In algebra, $x^2 \ge 0$ is implicitly understood as $\forall x \in \mathbf{R}, x^2 \ge 0$ .
- Double Arrow Symbols ( $\Rightarrow$ and $\Leftrightarrow$ ):
  - Let $P(x)$ and $Q(x)$ be predicates with common domain $D$ .
- $P(x) \Rightarrow Q(x)$ means that every element in the truth set of $P(x)$ is in the truth set of $Q(x)$ , which is logically equivalent to $\forall x \in D, P(x) \rightarrow Q(x)$ .
- $P(x) \Leftrightarrow Q(x)$ means that $P(x)$ and $Q(x)$ have identical truth sets, which is logically equivalent to $\forall x \in D, P(x) \leftrightarrow Q(x)$ .
Example 3.1.12: Using $\Rightarrow$ and $\Leftrightarrow$ :
- Let $P(x)$ be " $x$ is a factor of $4$ ", $Q(x)$ be " $x$ is a factor of $8$ ", $R(x)$ be " $x < 5$ and $x \neq 3$ ", with domain $D = \mathbf{Z}^+$ (positive integers).
- Truth sets:
  - Truth set of $P(x)$ is $\{1, 2, 4\}$ .
  - Truth set of $Q(x)$ is $\{1, 2, 4, 8\}$ .
  - Truth set of $R(x)$ is $\{1, 2, 4\}$ .
- Relationships:
  1. Every element in the truth set of $P(x)$ is in the truth set of $Q(x)$ . Thus, $P(x) \Rightarrow Q(x)$ (" $x$ is a factor of $4 \Rightarrow x$ is a factor of $8$ ").
  2. Truth set of $P(x)$ is identical to truth set of $R(x)$ . Thus, $P(x) \Leftrightarrow R(x)$ (" $x$ is a factor of $4 \Leftrightarrow x < 5$ and $x \neq 3$ "). Also, $R(x) \Rightarrow Q(x)$ .
Explicit Interpretation of Text Material:
- a. Statement " $x^2 \ge 0$ " $\rightarrow$ Explicit: \forall \text{ real number } x, x^2 \ge 0$.\n * b. Command "Solve x^2 = 4 $"$ \rightarrow $Explicit: Find if$ \exists \text{ a real number } x \text{ such that } x^2 = 4$.

Application in Tarski's World

Overview:
- Tarski's World is a computer software program created by information scientists Jon Barwise and John Etchemendy (The Language of First-Order Logic) to teach logic, named in honor of logician Alfred Tarski (1902–1983).

Grid System and Predicates:
- Objects of various shapes (triangles, squares, circles), sizes, and colors (blue, black, gray) are arranged on a grid.

*   Notation examples:
    *    $\text{Triangle}(x)$ : " $x$  is a triangle"
    *    $\text{Blue}(x)$ : " $x$  is blue"
    *    $\text{RightOf}(x, y)$ : " $x$  is to the right of  $y$ "

Example 3.1.13: Investigating Tarski's World:
- Determine the truth or falsity of each statement for the domain of all objects $\mathbf{D} = \{a, b, c, d, e, f, g, h, i, j, k\}$ in Figure 3.1.1:
  - a. $\forall x, \text{Triangle}(x) \rightarrow \text{Blue}(x)$
    - Truth Value: True. Every triangle ( $a, c, g$ ) in the grid is blue.
  - b. $\forall x, \text{Blue}(x) \rightarrow \text{Triangle}(x)$
    - Truth Value: False
    - Counterexample: Object $e$ is blue, but it is a square, not a triangle.
  - c. $\exists x \text{ such that } \text{Square}(x) \land \text{RightOf}(x, d)$
    - Truth Value: True
    - Explanation: Objects $h$ and $j$ are both squares and object $d$ is to their left (making $h$ and $j$ to the right of $d$ ).
  - d. $\exists x \text{ such that } \text{Square}(x) \land \text{Gray}(x)$
    - Truth Value: False
    - Explanation: All squares in the grid ( $e$ , $h$ , $j$ ) are either blue

Discreet Math - Chapter 3.1 - " Predicates and Quantified Statements I" NOTES

Predicates and Open Sentences

Truth Sets of Predicates

The Universal Quantifier (\\\forall\\)

The Existential Quantifier (∃\exists∃)

Translating Between Formal and Informal Language

Universal Conditional Statements

Equivalent Forms of Universal and Existential Statements

Bound Variables and Scope

Implicit Quantification and Logical Implication Notation

Application in Tarski's World

The Existential Quantifier ( $\exists$ )