Statements vs Open Statements

• Statement: A sentence with a definite truth value (True/False)
• Open Statement: Contains a free variable; truth value depends on variable

Examples:

1. (2 + 2 = 4) → Statement
2. (x + 2 = 5) → Open statement (depends on (x))
3. “Close the door” → Not a statement

---

Variables in Logic

• Bound Variable: Variable whose scope is restricted by quantifiers

  • Example: (\forall x \in \mathbb{Z}, x^2 \ge 0) → (x) is bound

• Free Variable: Variable not restricted by quantifiers; truth depends on value

  • Example: (P(x) = x^2 = 4) → Truth depends on (x)

---

Sets and Membership

• Definition: A collection of objects/elements
• Set notation with conditions:

$$A = {x \mid x \text{ is prime}}$$

• Membership: (x \in A) → x belongs to set A
• Subset: (B \subseteq A) → all elements of B are in A

Example:

$${x \in \mathbb{Z} \mid x^2 = 1} = {-1, 1}$$

---

Quantifiers

1. Universal Quantifier: (\forall x \in D, P(x)) → “For all x in domain D, P(x) is true”
2. Existential Quantifier: (\exists x \in D, P(x)) → “There exists at least one x in D such that P(x) is true”

Negation Rules:

$$\neg (\forall x, P(x)) \equiv \exists x, \neg P(x)$$ $$\neg (\exists x, P(x)) \equiv \forall x, \neg P(x)$$

---

Implications in Logic

• Implication: (p \to q) → False only if (p) is True and (q) is False
• Negation:

$$\neg(p \to q) \equiv p \land \neg q$$

Example:

$$\forall x \in \mathbb{Z},; (x > 0 \to x^2 > 0)$$

Negation:

$$\exists x \in \mathbb{Z},; (x > 0 \land x^2 \le 0)$$

---

Nested Quantifiers

• Example:

$$\forall x \in \mathbb{Z},; \exists y \in \mathbb{Z},; x < y$$

• English: “Every integer has a larger integer” ✅

• Negation:

$$\exists x \in \mathbb{Z},; \forall y \in \mathbb{Z},; x \ge y$$

• Truth: Original True, Negation False

• Tip: Order of quantifiers matters drastically.

  • (\forall x \exists y) ≠ (\exists y \forall x)

---

Drills & Examples

Single Quantifier + Implication

$$\forall x \in \mathbb{Z}^+, \exists y \in \mathbb{Z}^+, (y > x \to y^2 > x)$$

• Negation:

$$\exists x \in \mathbb{Z}^+, \forall y \in \mathbb{Z}^+, (y > x \land y^2 \le x)$$

Truth Evaluation

$$\exists x \in \mathbb{Z},; \forall y \in \mathbb{Z},; (x + y > 0) ;;\text{False}$$

Reason: No integer (x) works for all (y)

---

Key Lessons Learned

1. Always translate English → symbols → evaluate

2. Check bound vs free variables

3. Negate quantifiers carefully:

   • Flip quantifiers
   • Apply (\neg(p \to q) = p \land \neg q)

4. Multi-quantifier statements are tricky → check order and counterexamples

5. Implications often produce vacuous truths when hypothesis is false

Variables and Sets - Study Notes

Velleman: How to Prove It | Session Summary

---

1. Variables in Sentential Logic

Definition

A propositional variable represents a statement that has a truth value:

$$\text{True} \quad \text{or} \quad \text{False}$$

Key Idea

• Does not represent a number or object
• Represents an entire proposition

Example

$$p = \text{“It is raining”}, \quad q = \text{“I am studying”}$$

---

2. Sets and Set-Builder Notation

Definition

A set is a collection of objects defined either:

• Explicitly:

$$\{1,2,3\}$$

• By a property:

$$A = \{x \mid P(x)\}$$

---

Set-Builder Form

$$A = \{x \mid P(x)\}$$

• $x$: placeholder (variable)
• $P(x)$: condition for membership

---

Example

$$A = \{x \mid x \in \mathbb{Z},\ x^2 = 1\}$$

This gives:

$$A = \{-1, 1\}$$

---

3. Membership vs Subset

Membership

$$x \in A$$

Means:

$x$ is an element of $A$

---

Subset

$$A \subseteq B$$

Means:

Every element of $A$ is in $B$

---

Important Distinction

$$\{-1,1\} \in \mathbb{Z} \quad \text{False}$$ $$\{-1,1\} \subseteq \mathbb{Z} \quad \text{True}$$

---

4. Bound vs Free Variables

Bound Variable

A variable is bound if it appears inside a defining structure:

$$\{x \mid x \in \mathbb{Z},\ x^2 = 1\}$$

Properties:

• Exists only inside the expression
• Can be renamed without changing meaning

Example:

$$\{x \mid x^2 = 1\} = \{y \mid y^2 = 1\}$$

---

Free Variable

A variable is free if it is not bound.

Example:

$$x \in \{-1,1\}$$

• Not defined inside the expression
• Truth depends on value of $x$

---

5. Open Statements vs Propositions

Proposition

A statement with a definite truth value.

Example:

$$2 \in \{1,2,3\} \quad \text{True}$$

---

Open Statement (Predicate)

A statement with a free variable.

Example:

$$x \in \{-1,1\}$$

• True if $x = -1$ or $x = 1$
• False otherwise

---

6. Renaming Bound Variables (α-equivalence)

$$\{x \mid x \in \mathbb{Z}, x^2 = 1\} = \{y \mid y \in \mathbb{Z}, y^2 = 1\}$$

Key Idea:

• Variable names do not matter
• Only the structure and condition matter

---

7. Interpreting Expressions Correctly

Example

$$x \in \{x \mid x \in \mathbb{Z}, x^2 = 1\}$$

Step 1: Rename inner variable

$$x \in \{y \mid y \in \mathbb{Z}, y^2 = 1\}$$

Step 2: Evaluate set

$$x \in \{-1,1\}$$

Step 3: Classify

• This is an open statement
• Truth depends on $x$

---

8. Common Mistakes

• Confusing $\in$ with $\subseteq$
• Treating all variables like numbers
• Not distinguishing free vs bound variables
• Thinking bound variables persist after definition
• Using vague language like “cannot conclude” instead of identifying open statements

---

9. Mental Model Summary

• Variable (logic) → represents a statement
• Set-builder variable → placeholder (bound)
• Free variable → unresolved → creates open statement
• Membership → element relation
• Subset → inclusion relation

---

10. Final Insight

The key difficulty is not sets or variables alone,
but understanding how variables behave inside structures.

Mastering:

• variable binding
• scope
• statement classification

is foundational for all advanced mathematics.