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.