Book of Proof - Chapter 1: Set

Cheatsheet Content

### Introduction to Sets A **set** is a collection of distinct objects, called **elements**. - Sets are denoted by listing elements in braces: $\{2, 4, 6, 8\}$. - An **infinite set** has infinitely many elements, e.g., integers: $\{\dots, -2, -1, 0, 1, 2, \dots\}$. - A **finite set** has a finite number of elements. - Two sets are **equal** if they contain exactly the same elements, e.g., $\{2, 4, 6, 8\} = \{4, 2, 8, 6\}$. - $x \in A$ means "$x$ is an element of $A$." - $x \notin A$ means "$x$ is not an element of $A$." #### Special Sets - **Natural Numbers (N):** $\{1, 2, 3, \dots\}$ (positive whole numbers) - **Integers (Z):** $\{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$ - **Real Numbers (R):** All numbers on the number line (e.g., from calculus). - **Empty Set (Ø or {}):** A set with no elements. $|\emptyset| = 0$. - Note: $\emptyset \neq \{\emptyset\}$ because $\{\emptyset\}$ contains one element (the empty set itself). #### Cardinality The **cardinality** or **size** of a finite set $X$ is the number of elements it has, denoted $|X|$. - Example: $|A| = 4$ for $A = \{2, 4, 6, 8\}$. #### Set-Builder Notation Used for large or complex sets: $X = \{\text{expression} : \text{rule}\}$. - Reads: "X equals the set of all things of form 'expression', such that 'rule' is true." - Example: $E = \{2n : n \in \mathbb{Z}\}$ (the set of even integers). - Example: $\{n : n \text{ is a prime number}\} = \{2, 3, 5, 7, \dots\}$. - Example: $\{x \in \mathbb{R} : x^2 - 2 = 0\} = \{\sqrt{2}, -\sqrt{2}\}$. - Example: $\{x \in \mathbb{Z} : x^2 - 2 = 0\} = \emptyset$. - Example: $\{x \in \mathbb{Z} : |x| ### The Cartesian Product The **Cartesian product** of sets $A$ and $B$, denoted $A \times B$, is the set of all **ordered pairs** $(a, b)$ where $a \in A$ and $b \in B$. - **Ordered pair:** A list $(x, y)$ where order matters, i.e., $(x, y) \neq (y, x)$ unless $x=y$. - Definition: $A \times B = \{(a, b) : a \in A, b \in B\}$. - Example: If $A = \{k, l, m\}$ and $B = \{q, r\}$, then $A \times B = \{(k, q), (k, r), (l, q), (l, r), (m, q), (m, r)\}$. - **Cardinality:** If $A$ and $B$ are finite sets, then $|A \times B| = |A| \cdot |B|$. - **Cartesian Power:** For a set $A$ and positive integer $n$, $A^n = A \times A \times \dots \times A = \{(x_1, x_2, \dots, x_n) : x_1, x_2, \dots, x_n \in A\}$. - $\mathbb{R}^2$ is the Cartesian plane, $\mathbb{R}^3$ is 3D space. ### Subsets - **Definition:** $A$ is a **subset** of $B$, denoted $A \subseteq B$, if every element of $A$ is also an element of $B$. - $A \not\subseteq B$ means there is at least one element in $A$ that is not in $B$. - **Empty Set Property:** The empty set is a subset of every set: $\emptyset \subseteq B$ for any set $B$. - **Self-Subset:** Every set is a subset of itself: $A \subseteq A$. #### Number of Subsets - If a finite set has $n$ elements, then it has $2^n$ subsets. ### Power Sets - **Definition:** The **power set** of $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$. - $\mathcal{P}(A) = \{X : X \subseteq A\}$. - Example: If $A = \{1, 2, 3\}$, then $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$. - **Cardinality:** If $A$ is a finite set, then $|\mathcal{P}(A)| = 2^{|A|}$. ### Union, Intersection, Difference Operations to combine sets: - **Union ($\cup$):** $A \cup B = \{x : x \in A \text{ or } x \in B\}$. (Elements in A, or B, or both). - **Intersection ($\cap$):** $A \cap B = \{x : x \in A \text{ and } x \in B\}$. (Elements in both A and B). - **Difference ($- $):** $A - B = \{x : x \in A \text{ and } x \notin B\}$. (Elements in A but not in B). #### Properties - **Commutative:** $X \cup Y = Y \cup X$, $X \cap Y = Y \cap X$. - **Non-Commutative:** $X - Y \neq Y - X$ in general. ### Complement - **Universal Set ($U$):** A larger set that contains all sets under consideration. - **Definition:** The **complement** of $A$, denoted $\bar{A}$, is the set of all elements in the universal set $U$ that are not in $A$. - $\bar{A} = U - A$. - Example: If $U = \mathbb{N}$ and $P$ is the set of prime numbers, then $\bar{P} = \mathbb{N} - P = \{1, 4, 6, 8, 9, 10, 12, \dots\}$ (composite numbers and 1). ### Venn Diagrams - Informal schematic diagrams representing sets as circles (or ovals) within a rectangle (the universal set). - Used to visualize set operations: - $A \cup B$: Shaded area covering both circles. - $A \cap B$: Shaded area where circles overlap. - $A - B$: Shaded area in A that does not overlap with B. #### Important Points for Expressions with $\cup$, $\cap$ - If an expression uses only $\cup$, parentheses are optional (e.g., $A \cup B \cup C$). - If an expression uses only $\cap$, parentheses are optional (e.g., $A \cap B \cap C$). - If an expression uses both $\cup$ and $\cap$, parentheses are essential to define the order of operations (e.g., $(A \cup B) \cap C \neq A \cup (B \cap C)$). ### Indexed Sets - Using subscripts (indices) to keep track of many sets, e.g., $A_1, A_2, A_3$. - **Index Set ($I$):** The set from which the indices are drawn (e.g., $\{1, 2, 3\}$ or $\mathbb{N}$). - **Union of Indexed Sets:** $\bigcup_{i \in I} A_i = \{x : x \in A_i \text{ for at least one } A_i \text{ with } i \in I\}$. - **Intersection of Indexed Sets:** $\bigcap_{i \in I} A_i = \{x : x \in A_i \text{ for every } A_i \text{ with } i \in I\}$. - Example: If $A_1 = \{0, 2, 5\}$, $A_2 = \{1, 2, 5\}$, $A_3 = \{2, 5, 7\}$, then $\bigcup_{i=1}^3 A_i = \{0, 1, 2, 5, 7\}$ and $\bigcap_{i=1}^3 A_i = \{2, 5\}$. ### Sets That Are Number Systems - Number systems like $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$ have operations (addition, multiplication) that obey familiar commutative, associative, and distributive properties. - **Well-Ordering Principle:** Any non-empty subset of natural numbers ($\mathbb{N}$) has a smallest element. - **Division Algorithm:** Given integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = qb + r$ and $0 \le r ### Russell's Paradox - A paradox in set theory that arises from considering the set of all sets that do not contain themselves as elements: $A = \{X : X \text{ is a set and } X \notin X\}$. - The paradox: If $A \in A$, then by definition $A \notin A$. If $A \notin A$, then $A$ should be an element of itself, $A \in A$. This creates a contradiction. - Highlights the importance of precision in set theory and led to the development of axiomatic set theory (e.g., Zermelo-Fraenkel axioms) to prevent such contradictions. ### Logic - Statements - A **statement** is a sentence or mathematical expression that is either definitely true or definitely false. - **Open Sentence:** A sentence whose truth value depends on the value of one or more variables (e.g., "The integer $x$ is even"). Not a statement until variables are assigned values or quantified. ### Logic - And, Or, Not - **And ($\land$):** $P \land Q$ is true if both $P$ and $Q$ are true; otherwise it is false. - **Truth Table for $\land$:** | P | Q | P $\land$ Q | |---|---|-----------| | T | T | T | | T | F | F | | F | T | F | | F | F | F | - **Or ($\lor$):** $P \lor Q$ is true if $P$ is true, or $Q$ is true, or both are true. (Inclusive or). - **Truth Table for $\lor$:** | P | Q | P $\lor$ Q | |---|---|-----------| | T | T | T | | T | F | T | | F | T | T | | F | F | F | - **Not ($\neg$):** $\neg P$ (negation of $P$) is true if $P$ is false, and false if $P$ is true. - **Truth Table for $\neg$:** | P | $\neg$ P | |---|-------| | T | F | | F | T | ### Logic - Conditional Statements - **If P, then Q ($P \Rightarrow Q$):** A conditional statement is true unless $P$ is true and $Q$ is false. - **Truth Table for $\Rightarrow$:** | P | Q | P $\Rightarrow$ Q | |---|---|---------------| | T | T | T | | T | F | F | | F | T | T | | F | F | T | - Various ways to express $P \Rightarrow Q$: "P implies Q", "If P, then Q", "Q if P", "Q whenever P", "Q, provided that P", "P is a sufficient condition for Q", "Q is a necessary condition for P", "P only if Q". - **Implied Universal Quantifier:** In mathematics, an unquantified conditional statement involving variables (e.g., $P(x) \Rightarrow Q(x)$) is understood to mean $\forall x, P(x) \Rightarrow Q(x)$. ### Logic - Biconditional Statements - **P if and only if Q ($P \Leftrightarrow Q$):** This statement is true if $P$ and $Q$ are both true or both false. It means $(P \Rightarrow Q) \land (Q \Rightarrow P)$. - **Truth Table for $\Leftrightarrow$:** | P | Q | P $\Leftrightarrow$ Q | |---|---|---------------| | T | T | T | | T | F | F | | F | T | F | | F | F | T | - Various ways to express $P \Leftrightarrow Q$: "P if and only if Q", "P is a necessary and sufficient condition for Q", "P is equivalent to Q", "If P, then Q, and conversely". - **Converse:** The converse of $P \Rightarrow Q$ is $Q \Rightarrow P$. It is not logically equivalent to $P \Rightarrow Q$. ### Logic - Truth Tables for Statements - Truth tables are used to determine the truth value of complex logical statements based on the truth values of their components. - Helper columns can be used for intermediate expressions. ### Logic - Logical Equivalence - Two statements are **logically equivalent** if their truth values match line-for-line in a truth table. - **DeMorgan's Laws:** - $\neg (P \land Q) \Leftrightarrow (\neg P \lor \neg Q)$ - $\neg (P \lor Q) \Leftrightarrow (\neg P \land \neg Q)$ - Other Equivalences: - **Contrapositive Law:** $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$ - **Commutative Laws:** $(P \land Q) \Leftrightarrow (Q \land P)$, $(P \lor Q) \Leftrightarrow (Q \lor P)$ - **Distributive Laws:** $P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$, $P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R)$ - **Associative Laws:** $P \land (Q \land R) \Leftrightarrow (P \land Q) \land R$, $P \lor (Q \lor R) \Leftrightarrow (P \lor Q) \lor R$ ### Logic - Quantifiers - **Universal Quantifier ($\forall$):** "For all", "For every", "For each". - Example: $\forall n \in \mathbb{Z}, 2n \text{ is even}$. - **Existential Quantifier ($\exists$):** "There exists a", "There is a". - Example: $\exists n \in \mathbb{Z}, n \text{ is not even}$. - **Quantified Statements:** Statements containing quantifiers. - **Order of Quantifiers:** Reversing the order of different quantifiers can change the meaning of a statement. - Example: $(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y^3 = x)$ (True) vs. $(\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, y^3 = x)$ (False). ### Logic - Negating Statements - The **negation** of a statement $R$ is $\neg R$. - Negating quantified statements: - $\neg (\forall x \in X, P(x)) \Leftrightarrow \exists x \in X, \neg P(x)$ - $\neg (\exists x \in X, P(x)) \Leftrightarrow \forall x \in X, \neg P(x)$ - Negating conditional statements: - $\neg (P \Rightarrow Q) \Leftrightarrow (P \land \neg Q)$ ### Logic - Logical Inference - Deducing new true statements from existing true statements. - **Modus Ponens:** From $P \Rightarrow Q$ and $P$, infer $Q$. - **Modus Tollens:** From $P \Rightarrow Q$ and $\neg Q$, infer $\neg P$. - **Elimination:** From $P \lor Q$ and $\neg P$, infer $Q$. ### Counting - Lists - A **list** is an ordered sequence of objects, denoted by parentheses: $(a, b, c)$. - **Entries:** The objects in a list. - Order matters: $(a, b, c) \neq (b, a, c)$. - Repetition is allowed in lists. - **Length:** The number of entries in a list. - **Empty List:** $()$, has length 0. - **String:** A list of symbols written without parentheses and commas (e.g., SOS). ### Counting - The Multiplication Principle - If a list of length $n$ is formed by making $a_1$ choices for the first entry, $a_2$ for the second, ..., $a_n$ for the $n$-th, then the total number of such lists is $a_1 \cdot a_2 \cdot \dots \cdot a_n$. - Useful for counting lists with or without repetition. - Example: License plates with 3 letters and 4 digits (repetition allowed) = $26^3 \cdot 10^4$. - Example: Non-repetitive lists of length 4 from 7 symbols = $7 \cdot 6 \cdot 5 \cdot 4$. ### Counting - The Addition and Subtraction Principles - **Addition Principle:** If a finite set $X$ can be decomposed into disjoint parts $X_1, X_2, \dots, X_n$ (i.e., $X = X_1 \cup X_2 \cup \dots \cup X_n$ and $X_i \cap X_j = \emptyset$ for $i \neq j$), then $|X| = |X_1| + |X_2| + \dots + |X_n|$. - **Subtraction Principle:** If $X$ is a subset of a finite universal set $U$, then $|U - X| = |U| - |X|$. - Useful when it's easier to count what you want to exclude. ### Counting - Factorials and Permutations - **Factorial ($n!$):** The number of non-repetitive lists of length $n$ made from $n$ symbols. - $0! = 1$, $1! = 1$. For $n > 1$, $n! = n \cdot (n-1) \cdot \dots \cdot 3 \cdot 2 \cdot 1$. - Recursive definition: $n! = n \cdot (n-1)!$. - **Permutation:** An arrangement of all elements of a set in a row (a non-repetitive list using every element). - **$k$-permutation ($P(n, k)$):** A non-repetitive list of length $k$ made from elements of an $n$-element set. - $P(n, k) = n(n-1)\dots(n-k+1)$. - Formula: $P(n, k) = \frac{n!}{(n-k)!}$ for $0 \le k \le n$. - $P(n, k) = 0$ if $k > n$. ### Counting - Subsets ($\binom{n}{k}$) - **$\binom{n}{k}$ ("n choose k"):** Denotes the number of subsets of size $k$ that can be made from an $n$-element set. - Formula: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for $0 \le k \le n$. - $\binom{n}{k} = 0$ if $k n$. - **Symmetry Property:** $\binom{n}{k} = \binom{n}{n-k}$. ### Counting - Pascal's Triangle and the Binomial Theorem - **Pascal's Triangle:** A triangular arrangement of binomial coefficients $\binom{n}{k}$. - Each number (except for the 1s at the ends) is the sum of the two numbers directly above it. - **Pascal's Formula:** $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$. - Row $n$ lists the coefficients $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. - **Binomial Theorem:** For a non-negative integer $n$: - $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$. ### Counting - The Inclusion-Exclusion Principle - For two finite sets $A$ and $B$: $|A \cup B| = |A| + |B| - |A \cap B|$. - For three finite sets $A, B, C$: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$. ### Counting - Multisets - A **multiset** is like a set but allows repeated elements, denoted by square brackets: $[1, 1, 1, 5, 5]$. - **Cardinality:** The total number of elements, including repetitions. - **Multiplicity:** The number of times an element appears. - **Stars and Bars Method:** Used to count $k$-element multisets from an $n$-element set (or non-negative integer solutions to $x_1 + \dots + x_n = k$). - The number of $k$-element multisets from an $n$-element set is $\binom{k+n-1}{k}$ or $\binom{k+n-1}{n-1}$. - This is equivalent to arranging $k$ "stars" (elements) and $n-1$ "bars" (separators). ### Counting - The Division and Pigeonhole Principles - **Floor ($\lfloor x \rfloor$):** $x$ rounded down to the nearest integer. - **Ceiling ($\lceil x \rceil$):** $x$ rounded up to the nearest integer. - **Division Principle:** If $n$ objects are placed into $k$ boxes: - At least one box contains $\lceil n/k \rceil$ or more objects. - At least one box contains $\lfloor n/k \rfloor$ or fewer objects. - **Pigeonhole Principle:** (A useful variant of the Division Principle) - If $n$ objects are placed into $k$ boxes and $n > k$, then at least one box contains more than one object. - If $n ### Counting - Combinatorial Proof - A method of proving two expressions are equal by showing they both count the same thing. - Example: $\binom{n}{k} = \binom{n}{n-k}$ can be proved by showing both count subsets of size $k$ (or $n-k$) from an $n$-element set. ### Proof - Direct Proof - For a proposition "If P, then Q": 1. Assume P is true. 2. Use logic, definitions, and known mathematical facts to show that Q must be true. - A **theorem** is a true mathematical statement that has been verified. - A **proof** is a written verification showing a theorem is true. - A **definition** is an exact, unambiguous explanation of a mathematical term. - **Proposition:** A true statement, less significant than a theorem. - **Lemma:** A theorem whose main purpose is to help prove another theorem. - **Corollary:** A result that is an immediate consequence of a theorem or proposition. - **Definitions as Conditional Statements:** Definitions are often phrased as conditionals (e.g., "An integer $n$ is even if $n = 2a$ for some integer $a$"), but are interpreted as biconditionals ("if and only if"). ### Proof - Contrapositive Proof - For a proposition "If P, then Q": 1. Assume $\neg Q$ (Q is not true). 2. Use logic, definitions, and known mathematical facts to show that $\neg P$ (P is not true) must follow. - This works because $P \Rightarrow Q$ is logically equivalent to its contrapositive $\neg Q \Rightarrow \neg P$. - **Congruence Modulo n:** $a \equiv b \pmod{n}$ means $n | (a-b)$. In practical terms, $a$ and $b$ have the same remainder when divided by $n$. ### Proof - Proof by Contradiction - For a proposition P: 1. Assume $\neg P$ (P is false). 2. Deduce a contradiction (a statement that is always false, e.g., $C \land \neg C$). 3. Conclude that the initial assumption $\neg P$ must be false, so P is true. - For a conditional statement "If P, then Q": 1. Assume $P \land \neg Q$ (P is true and Q is false). 2. Deduce a contradiction. 3. Conclude that $P \Rightarrow Q$ is true. - **Irrational Numbers:** A number $x$ is irrational if it cannot be expressed as a fraction $a/b$ where $a, b \in \mathbb{Z}$ and $b \neq 0$. ### Proof - Proving Non-Conditional Statements - **If-and-Only-If Proof ($P \Leftrightarrow Q$):** 1. Prove $P \Rightarrow Q$ (using direct, contrapositive, or contradiction). 2. Prove $Q \Rightarrow P$ (using direct, contrapositive, or contradiction). - **Equivalent Statements:** If a list of statements $S_1, S_2, \dots, S_n$ are asserted to be equivalent, it means they are either all true or all false. To prove this, show a circular chain of implications: $S_1 \Rightarrow S_2 \Rightarrow \dots \Rightarrow S_n \Rightarrow S_1$. - **Existence Proofs ($\exists x, R(x)$):** - **Constructive Proof:** Provide a specific example of $x$ that makes $R(x)$ true. - **Existence and Uniqueness Proofs ($\exists! x, R(x)$):** 1. Prove existence (constructively). 2. Prove uniqueness by assuming two such elements $x_1, x_2$ exist and showing $x_1 = x_2$. - **Non-Constructive Proof:** Proves an example exists without explicitly giving it. ### Proof - Disproof - To **disprove** a statement P, prove its negation $\neg P$. - **Disproving Universal Statements ($\forall x \in S, P(x)$):** - Produce a **counterexample**: an $x \in S$ that makes $P(x)$ false. This is equivalent to proving $\exists x \in S, \neg P(x)$. - **Disproving Conditional Statements ($P(x) \Rightarrow Q(x)$):** - Produce a **counterexample**: an $x$ that makes $P(x)$ true and $Q(x)$ false. This is equivalent to proving $\exists x, P(x) \land \neg Q(x)$. - **Disproof by Contradiction:** To disprove P, assume P is true and deduce a contradiction. ### Proof - Mathematical Induction - Used to prove statements $S_n$ for all natural numbers $n$. - **Outline for Proof by Induction (Weak Induction):** 1. **Basis Step:** Prove $S_1$ is true (or $S_0$, or relevant starting point). 2. **Inductive Step:** Assume $S_k$ is true for an arbitrary integer $k \ge 1$ (the **inductive hypothesis**), and then prove $S_{k+1}$ is true. - **Outline for Proof by Strong Induction:** 1. **Basis Step:** Prove $S_1$ is true (or multiple initial statements if needed, e.g., $S_1, S_2, S_3$). 2. **Inductive Step:** Assume $S_m$ is true for all integers $m$ such that $1 \le m \le k$, (the **inductive hypothesis**), and then prove $S_{k+1}$ is true. - **Proof by Smallest Counterexample:** (Hybrid of induction and contradiction) 1. Check that the first statement $S_1$ is true. 2. Assume, for contradiction, that not every $S_n$ is true. 3. Let $k$ be the smallest integer for which $S_k$ is false. ($k > 1$ because $S_1$ is true). 4. This implies $S_{k-1}$ is true and $S_k$ is false. Use this to derive a contradiction. - **Fibonacci Numbers ($F_n$):** A sequence where $F_1=1, F_2=1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \ge 3$. - **Fundamental Theorem of Arithmetic:** Every integer greater than 1 has a unique prime factorization. ### Relations, Functions and Cardinality ### Relations - Introduction - A **relation** expresses a mathematical relationship between entities (e.g., $ ### Relations - Properties - Let $R$ be a relation on a set $A$: - **Reflexive:** $xRx$ for every $x \in A$. (Every element relates to itself). - **Symmetric:** If $xRy$, then $yRx$ for all $x, y \in A$. (If $x$ relates to $y$, $y$ relates to $x$). - **Transitive:** If $xRy$ and $yRz$, then $xRz$ for all $x, y, z \in A$. (If $x$ relates to $y$ and $y$ relates to $z$, then $x$ relates to $z$). - Example: The relation $\le$ on $\mathbb{Z}$ is reflexive and transitive, but not symmetric. The relation $=$ on $\mathbb{Z}$ is reflexive, symmetric, and transitive. ### Relations - Equivalence Relations - An **equivalence relation** $R$ on a set $A$ is a relation that is reflexive, symmetric, and transitive. - **Equivalence Class ($[a]$):** For an equivalence relation $R$ on $A$ and element $a \in A$, the equivalence class containing $a$ is $[a] = \{x \in A : xRa\}$. - **Theorem:** $[a] = [b]$ if and only if $aRb$. - **Integers Modulo n ($\mathbb{Z}_n$):** The relation $a \equiv b \pmod{n}$ is an equivalence relation on $\mathbb{Z}$. - Its equivalence classes are $[0], [1], \dots, [n-1]$. - These classes can be added and multiplied: $[a] + [b] = [a+b]$, $[a] \cdot [b] = [ab]$. ### Relations - Partitions - A **partition** of a set $A$ is a set of non-empty subsets of $A$ such that: 1. The union of all subsets equals $A$. 2. The intersection of any two different subsets is $\emptyset$. - **Theorem:** The set of equivalence classes of an equivalence relation on a set $A$ forms a partition of $A$. - Conversely, any partition of $A$ describes an equivalence relation. ### Relations - Between Sets - A **relation from a set A to a set B** is a subset $R \subseteq A \times B$. - We still write $xRy$ for $(x,y) \in R$. - This generalizes the idea of a relation on a single set. ### Functions - Definitions - A **function** $f$ from set $A$ to set $B$ (denoted $f: A \to B$) is a relation $f \subseteq A \times B$ such that for each $a \in A$, $f$ contains exactly one ordered pair of the form $(a, b)$. - $f(a) = b$ means $(a, b) \in f$. - **Domain:** The set $A$ (all possible input values). - **Codomain:** The set $B$ (the target set for output values). - **Range:** The set $\{f(a) : a \in A\} = \{b : (a,b) \in f\}$. The range is a subset of the codomain. - **Equal Functions:** $f = g$ if and only if $f(x) = g(x)$ for every $x$ in the domain. Functions can have different codomains and still be equal if their outputs match for all domain elements. ### Functions - Injective and Surjective Functions - **Injective (one-to-one):** For all $a, a' \in A$, $a \neq a'$ implies $f(a) \neq f(a')$. (Distinct inputs map to distinct outputs). - **Surjective (onto B):** For every $b \in B$, there is an $a \in A$ with $f(a) = b$. (Every element in the codomain is an output). - **Bijective:** A function that is both injective and surjective. ### Functions - Composition - For functions $f: A \to B$ and $g: B \to C$ (where codomain of $f$ equals domain of $g$), their **composition** is $g \circ f: A \to C$. - $(g \circ f)(x) = g(f(x))$. - **Associative:** $(h \circ g) \circ f = h \circ (g \circ f)$. - **Not Commutative:** $g \circ f \neq f \circ g$ in general. - **Injective/Surjective Properties:** - If $f$ and $g$ are injective, then $g \circ f$ is injective. - If $f$ and $g$ are surjective, then $g \circ f$ is surjective. ### Functions - Inverse Functions - **Identity Function ($i_A$):** For a set $A$, $i_A: A \to A$ defined by $i_A(x) = x$. It is always bijective. - **Inverse Relation ($R^{-1}$):** For a relation $R$ from $A$ to $B$, $R^{-1} = \{(y, x) : (x, y) \in R\}$. - **Inverse Function ($f^{-1}$):** If $f: A \to B$ is bijective, its inverse $f^{-1}: B \to A$ is also a function. - $f^{-1} \circ f = i_A$ and $f \circ f^{-1} = i_B$. - **Condition for inverse function:** An inverse relation $R^{-1}$ is a function if and only if $R$ is bijective. ### Functions - Image and Preimage - For a function $f: A \to B$: - **Image ($f(X)$):** For $X \subseteq A$, $f(X) = \{f(x) : x \in X\} \subseteq B$. - **Preimage ($f^{-1}(Y)$):** For $Y \subseteq B$, $f^{-1}(Y) = \{x \in A : f(x) \in Y\} \subseteq A$. - Note: $f^{-1}(Y)$ is defined even if $f$ is not invertible. ### Proofs in Calculus ### Calculus - The Triangle Inequality - **Absolute Value ($|x|$):** $x$ if $x \ge 0$, $-x$ if $x ### Calculus - Definition of a Limit - **Informal Definition:** $\lim_{x \to c} f(x) = L$ means $f(x)$ is arbitrarily close to $L$ when $x$ is sufficiently close to $c$. - **Precise Definition ($\epsilon-\delta$ definition):** $\lim_{x \to c} f(x) = L$ means that for any $\epsilon > 0$, there exists a $\delta > 0$ such that if $0 ### Calculus - Limits That Do Not Exist - A limit $\lim_{x \to c} f(x)$ does not exist if: 1. $f(x)$ approaches different values from the left and right of $c$. 2. $f(x)$ oscillates without approaching a single value (e.g., $\sin(1/x)$ as $x \to 0$). 3. $f(x)$ approaches $\pm \infty$. ### Calculus - Limit Laws - If $\lim_{x \to c} f(x) = L$ and $\lim_{x \to c} g(x) = M$: - **Sum Rule:** $\lim_{x \to c} (f(x) + g(x)) = L + M$. - **Difference Rule:** $\lim_{x \to c} (f(x) - g(x)) = L - M$. - **Constant Multiple Rule:** $\lim_{x \to c} (a \cdot f(x)) = a \cdot L$. - **Multiplication Rule:** $\lim_{x \to c} (f(x) \cdot g(x)) = L \cdot M$. - **Division Rule:** $\lim_{x \to c} \left(\frac{f(x)}{g(x)}\right) = \frac{L}{M}$, provided $M \neq 0$. - **Squeeze Theorem:** If $g(x) \le f(x) \le h(x)$ for $x$ near $c$, and $\lim_{x \to c} g(x) = \lim_{x \to c} h(x) = L$, then $\lim_{x \to c} f(x) = L$. ### Calculus - Continuity and Derivatives - **Continuous at $x=c$:** A function $f(x)$ is continuous at $x=c$ if $\lim_{x \to c} f(x) = f(c)$. This requires: 1. $f(c)$ is defined. 2. $\lim_{x \to c} f(x)$ exists. 3. $\lim_{x \to c} f(x) = f(c)$. - **Discontinuous:** If one or more of these conditions fail. - **Differentiable at $c$:** A function $f$ is differentiable at $c$ if $f'(c) = \lim_{x \to c} \frac{f(x) - f(c)}{x-c}$ exists. - **Theorem:** If $f$ is differentiable at $c$, then $f$ is continuous at $c$. - **Composition Rule for Continuity:** If $\lim_{x \to c} g(x) = L$ and $f$ is continuous at $L$, then $\lim_{x \to c} f(g(x)) = f(\lim_{x \to c} g(x))$. ### Calculus - Limits at Infinity - $\lim_{x \to \infty} f(x) = L$: For any $\epsilon > 0$, there exists an $N > 0$ such that if $x > N$, then $|f(x) - L| 0$, there exists an $N 0$, there exists an $N > 0$ such that if $x > N$, then $f(x) > L$. - $\lim_{x \to \infty} f(x) = -\infty$: For any $L 0$ such that if $x > N$, then $f(x) ### Calculus - Sequences - A **sequence** is an infinitely long list of real numbers: $a_1, a_2, a_3, \dots$. - **General Term ($a_n$):** The rule for the $n$-th term. A sequence is often denoted $\{a_n\}$. - **Convergence of a Sequence:** A sequence $\{a_n\}$ **converges to $L$** ($\lim_{n \to \infty} a_n = L$) if for any $\epsilon > 0$, there exists an $N \in \mathbb{N}$ such that if $n > N$, then $|a_n - L| 0$, there exists an $N > 0$ such that if $n > N$, then $a_n > L$. - **Divergence to $-\infty$:** $\lim_{n \to \infty} a_n = -\infty$ if for any $L 0$ such that if $n > N$, then $a_n ### Calculus - Series - A **series** is an infinite sum: $\sum_{k=1}^\infty a_k = a_1 + a_2 + a_3 + \dots$. - **Partial Sum ($s_n$):** The sum of the first $n$ terms: $s_n = \sum_{k=1}^n a_k$. - **Convergence of a Series:** A series $\sum_{k=1}^\infty a_k$ **converges to $S$** if its sequence of partial sums $\{s_n\}$ converges to $S$. - **Divergence of a Series:** A series that does not converge. - **Divergence Test:** If $\sum_{k=1}^\infty a_k$ converges, then $\lim_{n \to \infty} a_n = 0$. (Contrapositive: If $\lim_{n \to \infty} a_n \neq 0$ or $\lim_{n \to \infty} a_n$ does not exist, then $\sum_{k=1}^\infty a_k$ diverges). - **Harmonic Series:** $\sum_{k=1}^\infty \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \dots$ diverges. - **Geometric Series:** $\sum_{k=0}^\infty ar^k = a + ar + ar^2 + \dots$ converges to $\frac{a}{1-r}$ if $|r| ### Cardinality - Sets with Equal Cardinalities - **Definition:** Two sets $A$ and $B$ have the **same cardinality** ($|A| = |B|$) if there exists a **bijective function** $f: A \to B$. - **Unequal Cardinalities:** $|A| \neq |B|$ if no such bijection exists. - Example: $|\mathbb{N}| = |\mathbb{Z}|$ because there is a bijection $f: \mathbb{N} \to \mathbb{Z}$ (e.g., $f(n) = n/2$ if $n$ is even, $f(n) = -(n-1)/2$ if $n$ is odd). - Example: $|\mathbb{R}| = |(0,1)|$. ### Cardinality - Countable and Uncountable Sets - **Countably Infinite:** A set $A$ is countably infinite if $|A| = |\mathbb{N}|$. - **Countable:** A set is countable if it is finite or countably infinite. - **Uncountable:** A set is uncountable if it is infinite and $|A| \neq |\mathbb{N}|$. - **Cardinality of Natural Numbers ($\aleph_0$):** The special symbol $\aleph_0$ (aleph naught) denotes the cardinality of $\mathbb{N}$. So, $|\mathbb{N}| = \aleph_0$. - **Theorem:** $|\mathbb{N}| \neq |\mathbb{R}|$, so $\mathbb{R}$ is uncountable. (Proved by Cantor's diagonalization argument). - **Theorem:** A set $A$ is countably infinite if and only if its elements can be arranged in an infinite list $a_1, a_2, a_3, \dots$. - **Theorem:** The set $\mathbb{Q}$ of rational numbers is countably infinite. - **Theorem:** If $A$ and $B$ are both countably infinite, then $A \times B$ is countably infinite. - **Corollary:** Given $n$ countably infinite sets $A_1, \dots, A_n$, their Cartesian product $A_1 \times \dots \times A_n$ is countably infinite. - **Theorem:** If $A$ and $B$ are both countably infinite, then $A \cup B$ is countably infinite. - **Theorem:** An infinite subset of a countably infinite set is countably infinite. - **Theorem:** If $U \subseteq A$ and $U$ is uncountable, then $A$ is uncountable. ### Cardinality - Comparing Cardinalities - **Definition:** - $|A| = |B|$ if there is a bijection $A \to B$. - $|A| \le |B|$ if there is an injection $A \to B$. - $|A| ### Cardinality - The Cantor-Bernstein-Schröder Theorem - **Theorem:** If $|A| \le |B|$ and $|B| \le |A|$, then $|A| = |B|$. - In other words, if there are injections $f: A \to B$ and $g: B \to A$, then there is a bijection $h: A \to B$. - This theorem is very useful for proving sets have the same cardinality, as finding two injections can be easier than finding one bijection directly.