The Penguin's Field Guide to Sets, Functions & Proofs

{ }

Set Basics

📐 What is a Set?

An unordered collection of distinct objects. Order doesn't matter, duplicates collapse.

\(\{1, 2\} = \{2, 1\}\) · \(\{1, 1, 2\} = \{1, 2\}\)

🔢 Counting Elements — Watch the Nesting

Only count top-level elements. Nested sets are single objects.

\(\{0,\ \{1, \{2,3\}\}\}\) has 2 elements: the number \(0\) and the set \(\{1,\{2,3\}\}\)

Don't unpack nested sets. A box containing boxes still counts as one item on the shelf.

∅ vs {∅} — The #1 Trap

This distinction is everywhere on this test.

Symbol	What It Is	Elements
\(\emptyset\)	The empty set	0 elements
\(\{\emptyset\}\)	A set containing the empty set	1 element

Think of \(\emptyset\) as an empty bag. \(\{\emptyset\}\) is a bag with an empty bag inside it — it's not empty.

∈ vs ⊆ — Element vs Subset

Notation	Meaning	Example
\(a \in S\)	\(a\) is an element inside \(S\)	\(1 \in \{1,2\}\) ✓
\(A \subseteq S\)	Every element of \(A\) is in \(S\)	\(\{1\} \subseteq \{1,2\}\) ✓

Memorize \(\emptyset \subseteq S\) for every set \(S\) (vacuously true — nothing to check).

Memorize \(\emptyset \in S\) is true only if \(S\) explicitly contains \(\emptyset\) as an element.

Trap \(\emptyset \in \emptyset\) is false — the empty set has no elements at all.

Subset vs Proper Subset

\(A \subseteq B\): every element of \(A\) is in \(B\)
\(A \subset B\): \(A \subseteq B\) and \(A \neq B\)

Memorize Every set is a subset of itself: \(A \subseteq A\). No set is a proper subset of itself.

Number Sets Hierarchy

\(\mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\)

\(\mathbb{Q}\) (rationals) is a proper subset of \(\mathbb{R}\) (reals) because irrationals exist. \(\mathbb{R}\) is NOT a subset of \(\mathbb{Q}\).

Interval Notation

Notation	Meaning	Endpoints
\([a, b]\)	\(a \leq x \leq b\)	Both included
\((a, b)\)	\(a < x < b\)	Both excluded
\([a, b)\)	\(a \leq x < b\)	Left in, right out
\((a, b]\)	\(a < x \leq b\)	Left out, right in

\([1,2]\) is a set. "\(1 \leq x \leq 2\)" is a statement. They are NOT equal — different types of objects.

\(\mathbb{Z}^2\) — Integer Grid

\(\mathbb{Z}^2 = \mathbb{Z} \times \mathbb{Z}\) = all points \((x,y)\) where both coordinates are integers. Visualize it as the infinite lattice grid on the plane.

∪

Set Operations

Core Operations

Operation	Notation	Meaning
Union	\(A \cup B\)	Everything in \(A\) or \(B\) (or both)
Intersection	\(A \cap B\)	Only what's in both \(A\) and \(B\)
Difference	\(A - B\)	Elements in \(A\) but not in \(B\)
Complement	\(\overline{A}\)	Everything in \(U\) not in \(A\)

Key Identities

Formula Absorption Law: \(A \cap (A \cup B) = A\)

Formula Identity: \(A \cup \emptyset = A\) and \(A \cap \emptyset = \emptyset\)

Formula Complement of \(U\): \(\overline{U} = \emptyset\)

Formula Union with itself: \(A \cup A = A\) and \(A \cap A = A\)

Simplification Tricks

\(\{∅\} \cup \emptyset = \{∅\}\)

Union with the empty set changes nothing. The empty set adds zero elements.

\((A - B) \cup (A \cap B) \cup (B - A) = A \cup B\)

This decomposes \(A \cup B\) into three disjoint pieces: left-only, overlap, and right-only.

\(B - (A - B) = B\)

\(A - B\) contains things NOT in \(B\), so subtracting them from \(B\) removes nothing.

Disjoint Sets & Complement Pairs

Def Disjoint: \(A \cap B = \emptyset\) (no shared elements)

Def Complement pair: \(A \cap B = \emptyset\) AND \(A \cup B = U\)

Pair	Universal Set	Complement?
Positive reals & Negative reals	\(\mathbb{R}\)	✗ (miss 0)
Even integers & Odd integers	\(\mathbb{Z}\)	✓
Rationals & Irrationals	\(\mathbb{R}\)	✓

Union of Intervals

When merging intervals, draw them on a number line and find the combined coverage.

\([-1,3] \cup (-2,0) \cup [1,4) = (-2, 4)\)

Sketch it out. The leftmost starting point and rightmost ending point give you the answer, adjusting for open/closed.

Intersection of Intervals

\((2,4) \cap (3,5) = (3,4)\) — infinitely many elements

Overlapping real-number intervals always have infinitely many points in common.

Complement of an Interval

Example: Universal set \(= [0,2]\), find \(\overline{(0,1)}\).

\(\overline{(0,1)} = \{0\} \cup [1,2]\)

\(0\) is in \([0,2]\) but not in \((0,1)\) — it's an isolated point. Everything from \(1\) to \(2\) is also excluded from \((0,1)\).

Cardinality of Union

\(|A \cup B| = |A| + |B| - |A \cap B|\)

If \(|A|=5\) and \(|B|=7\), the union does NOT necessarily have 12 elements. Overlap gets subtracted.

𝒫

Power Sets

Definition

\(\mathcal{P}(S)\) = the set of ALL subsets of \(S\).

\(|\mathcal{P}(S)| = 2^{|S|}\)

Every element is either in or out of a subset → 2 choices per element → \(2^n\) subsets total.

Critical Examples

Set	Power Set	Size
\(\emptyset\)	\(\{\emptyset\}\)	\(2^0 = 1\)
\(\{1\}\)	\(\{\emptyset,\ \{1\}\}\)	\(2^1 = 2\)
\(\{1,2\}\)	\(\{\emptyset,\ \{1\},\ \{2\},\ \{1,2\}\}\)	\(2^2 = 4\)

\(\mathcal{P}(\emptyset) = \{\emptyset\} \neq \emptyset\). The power set of the empty set is NOT empty!

Power Set of a Power Set

Example: \(\mathcal{P}(\mathcal{P}(\{1\}))\)

Step 1: \(\mathcal{P}(\{1\}) = \{\emptyset,\ \{1\}\}\) — a 2-element set.

Step 2: Take all subsets of \(\{\emptyset,\ \{1\}\}\):

\(\mathcal{P}(\mathcal{P}(\{1\})) = \{\emptyset,\ \{\emptyset\},\ \{\{1\}\},\ \{\emptyset, \{1\}\}\}\)

4 elements, as expected from \(2^2 = 4\).

\(\emptyset\) and \(\mathcal{P}(\emptyset)\)

Memorize \(\emptyset \in \mathcal{P}(\emptyset)\) — TRUE. \(\mathcal{P}(\emptyset) = \{\emptyset\}\), and \(\emptyset\) is the element inside.

Memorize \(\emptyset \subseteq \mathcal{P}(\emptyset)\) — TRUE. \(\emptyset\) is a subset of every set.

Cartesian Products

Definition

\(A \times B = \{(a, b) \mid a \in A,\ b \in B\}\)

All ordered pairs with first element from \(A\), second from \(B\). Uses parentheses \((a,b)\), NOT curly braces.

Key Properties

Formula \(|A \times B| = |A| \cdot |B|\)

Trap \(A \times B \neq B \times A\) in general. Order matters in ordered pairs: \((1,2) \neq (2,1)\).

Memorize \(A \times \emptyset = \emptyset\). Can't form pairs if one set is empty.

Example

\(\{1,2\} \times \{1,3\} = \{(1,1),\ (1,3),\ (2,1),\ (2,3)\}\)

4 pairs because \(2 \times 2 = 4\). Think of it as a grid: rows are \(A\), columns are \(B\).

Functions

Injective (One-to-One)

\(f(a) = f(b) \implies a = b\)

Different inputs → different outputs. No two inputs land on the same output.

To PROVE injectivity: start with "Suppose \(f(a) = f(b)\)" and derive \(a = b\). Do NOT prove the converse (\(a=b \implies f(a)=f(b)\)) — that's always true and proves nothing.

Surjective (Onto)

\(\forall y \in B,\ \exists x \in A : f(x) = y\)

Every element of the codomain is hit. Range = Codomain.

To make any function surjective, redefine its codomain to equal its range.

Bijective = Injective + Surjective

Perfect one-to-one correspondence. Every input maps to a unique output, and every output is covered.

\(f(x) = x^2\) — The Most Tested Function

Domain → Codomain	Injective?	Surjective?
\(\mathbb{R} \to \mathbb{R}\)	✗ f(-1)=f(1)	✗ negatives missed
\([0,\infty) \to \mathbb{R}\); \(x^2+1\)	✓ strictly increasing	✗ range=[1,∞)
\([-2,2] \to [0,4]\)	✗ f(-2)=f(2)	✓ range=[0,4]
\([-2,0) \to [0,4]\)	✓ strictly decreasing	✗ 0 not in range
\([0,1] \to \mathbb{R}\)	✓ (Sun's proof)	✗ negatives missed
\([-1,0] \to [0,1]\)	✓	✓ bijective!

Always check injectivity and surjectivity relative to the GIVEN domain and codomain, not the formula in general.

Image and Preimage

\(f(S) = \{f(x) : x \in S\}\) — "where does \(f\) send the set \(S\)?"

\(f^{-1}(T) = \{x : f(x) \in T\}\) — "what inputs land in \(T\)?"

Example with \(f(x) = x^2\), \(f: \mathbb{R} \to \mathbb{R}\):

Set	Result	Why
\(f((-1,1))\)	\([0,1)\)	0 achieved at \(x=0\), approaching 1 but never hitting it
\(f^{-1}((0,1])\)	\([-1,0) \cup (0,1]\)	Need \(0 < x^2 \leq 1\), exclude \(x=0\), include \(x=\pm1\)
\(\|x\|^{-1}([-2,1))\)	\((-1,1)\)	\(\|x\| \geq 0\) always, so effective constraint is \(\|x\| < 1\)

Monotonicity

Property	Definition
Increasing	\(a \leq b \implies f(a) \leq f(b)\)
Strictly increasing	\(a < b \implies f(a) < f(b)\)
Decreasing	\(a \leq b \implies f(a) \geq f(b)\)
Strictly decreasing	\(a < b \implies f(a) > f(b)\)

Memorize Strictly increasing/decreasing → always injective (no two inputs can share an output).

Memorize A constant function is increasing AND decreasing (non-strict), but NOT strictly either.

Single-Element Domain: \(f: \{0\} \to \{0\}\)

This function is: increasing ✓, strictly increasing ✓, decreasing ✓, strictly decreasing ✓, constant ✓, injective ✓, surjective ✓.

Vacuous truth: "for all \(a < b\) in the domain..." — with one element, there are NO such pairs, so EVERY condition is vacuously satisfied.

Fixing Injectivity / Surjectivity

Memorize To fix non-injective: restrict the domain (remove colliding inputs).

Memorize To fix non-surjective: redefine codomain = range.

Changing the codomain does NOT affect injectivity. Changing the domain does NOT automatically give surjectivity.

⌊⌉

Floor & Ceiling Functions

Definitions

\(\lfloor x \rfloor\) = greatest integer \(\leq x\) (round down)
\(\lceil x \rceil\) = smallest integer \(\geq x\) (round up)

⭐ Inequality Rules — Memorize These

Floor	Equivalent
\(\lfloor t \rfloor \geq n\)	\(t \geq n\)
\(\lfloor t \rfloor \leq n\)	\(t < n + 1\)
\(\lfloor t \rfloor > n\)	\(t \geq n + 1\)
\(\lfloor t \rfloor < n\)	\(t < n\)

Ceiling	Equivalent
\(\lceil t \rceil \geq n\)	\(t > n - 1\)
\(\lceil t \rceil \leq n\)	\(t \leq n\)
\(\lceil t \rceil > n\)	\(t > n\)
\(\lceil t \rceil < n\)	\(t \leq n - 1\)

Worked Example: \(1 \leq \lfloor 2x+1 \rfloor \leq 6\)

Left: \(\lfloor 2x+1 \rfloor \geq 1 \implies 2x+1 \geq 1 \implies x \geq 0\)

Right: \(\lfloor 2x+1 \rfloor \leq 6 \implies 2x+1 < 7 \implies x < 3\)

Answer: \([0, 3)\)

Worked Example: \(1 < \lceil 2x+1 \rceil < 6\)

Left: \(\lceil 2x+1 \rceil > 1 \implies 2x+1 > 1 \implies x > 0\)

Right: \(\lceil 2x+1 \rceil < 6 \implies 2x+1 \leq 5 \implies x \leq 2\)

Answer: \((0, 2]\) or \((0, 5/2]\) depending on exact problem form

Image of Ceiling Function

Ceiling maps intervals to discrete integer sets:

\(\lceil (1/2,\ 3/2) \rceil = \{1, 2\}\)

Values in \((1/2, 1]\) map to 1, values in \((1, 3/2)\) map to 2.

Common Trap

\(\lfloor ab \rfloor \neq \lfloor a \rfloor \lfloor b \rfloor\). Counterexample: \(a = b = 1.5\). \(\lfloor 2.25 \rfloor = 2\) but \(\lfloor 1.5 \rfloor \cdot \lfloor 1.5 \rfloor = 1\).

Sequences & Summations

Arithmetic vs Geometric

Type	Pattern	Test
Arithmetic	Constant difference	\(a_{n+1} - a_n = d\)
Geometric	Constant ratio	\(a_{n+1} / a_n = r\)

\(a_n = 2 + 5n\) → arithmetic, \(d = 5\)
\(a_n = 3 \cdot 11^n\) → geometric, \(r = 11\)

In \(a_n = 2 + 5n\), the "2" is the starting offset, not the common difference. The coefficient of \(n\) is \(d\). In \(3 \cdot 11^n\), the "3" is a scaling factor, not the ratio.

Summation Formulas

Formula Sum of first \(n\) integers: \(\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\)

Formula Sum of first \(n\) squares: \(\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\)

Formula Geometric sum: \(\displaystyle\sum_{k=0}^{n} r^k = \frac{r^{n+1} - 1}{r - 1}\) for \(r \neq 1\)

Partial Sums via Subtraction

Sum from \(a\) to \(b\) = (sum from 1 to \(b\)) − (sum from 1 to \(a-1\)).

\(\displaystyle\sum_{k=1000}^{5000} k = \frac{5000 \cdot 5001}{2} - \frac{999 \cdot 1000}{2}\)

Subtract up to \(a-1 = 999\), NOT \(a = 1000\). You want 1000 included.

Evaluating Geometric Sums (example: \(3^4 + \cdots + 3^9\))

Valid methods:

Subtract two full geometric sums: \((3^0 + \cdots + 3^9) - (3^0 + \cdots + 3^3)\)
Factor out: \(3^4(3^0 + 3^1 + \cdots + 3^5)\) then use geometric formula
Brute force: \(81 + 243 + 729 + 2187 + 6561 + 19683 = 29484\)

INVALID: Adding exponents. \(3^4 + 3^5 \neq 3^9\). Exponent rules apply to multiplication, NOT addition.

Index Shifting

To shift \(\sum_{k=a}^{b}\) so it starts at \(k=0\): substitute \(k \to k + a\) everywhere, new bounds go from 0 to \(b-a\).

∎

Proof Techniques

Universal Statements: \(\forall x,\ P(x)\)

Start with: "Let \(x\) be an arbitrary [element of domain]."

Then prove \(P(x)\) holds for this arbitrary \(x\).

NEVER prove by example. Showing \(P(1)\) does NOT prove \(\forall x, P(x)\). One example only works for existential statements.

Existential Statements: \(\exists x,\ P(x)\)

Strategy: exhibit a specific witness and verify it works.

Example: Prove \(\exists x \forall y (x + y = y)\).

"Let \(x = 0\). Then for any \(y\), \(x + y = 0 + y = y\). ∎"

Do NOT start with "Suppose \(P(x)\) for some \(x\)" — that assumes what you're proving!

Mixed Quantifiers: \(\forall x \exists y,\ P(x,y)\)

Structure:

"Let \(x\) be an arbitrary [element]." (handle the ∀)
"Let \(y = \text{[expression depending on } x\text{]}.\)" (provide the ∃ witness)
Verify that \(P(x, y)\) holds.

Example: Prove \(\forall x \exists y\ (y < 2x+1 \text{ and } y \text{ is odd})\).

1. "Let \(x\) be an arbitrary integer."

2. "Let \(y = 2x - 1\)."

3. "Then \(y = 2x - 1 < 2x + 1\), and \(y = 2(x-1)+1\) is odd since it's one more than an even number. ∎"

Common Proof Mistakes

Trap "Therefore" before defining a variable. You CHOOSE \(k\), it doesn't follow logically. Say "Let" or "Choose" instead.

Trap Re-quantifying a fixed variable. Once you say "let \(n\) be an integer," \(n\) is fixed. Don't write "for all integers \(n\)" again.

Trap Proving the converse of injectivity. "\(a = b \implies f(a) = f(b)\)" is trivially true. You need \(f(a) = f(b) \implies a = b\).

Trap Assuming what you're proving. "Suppose \(3n+5=8\) for some \(n\)" assumes a solution exists. Instead, exhibit \(n=1\) and verify.

Trap Weak conclusion. "This proves an integer \(k\) exists" is incomplete. State the full theorem in the conclusion.

The "Even Integer in an Interval" Proof

Statement: For all positive integers \(n\), there exists an even integer \(k\) such that \(n - 1/n < k < n + 2 + 1/n\).

Key insight: The interval has length \(2 + 2/n > 2\). Any interval of length greater than 2 must contain an even integer. Choose \(k = n+1\) if \(n\) is odd (making \(k\) even), or \(k = n\) or \(k = n+2\) if \(n\) is even.

⚡

Quick-Fire Cheat Sheet

True / False Speed Round

Statement	Answer
\(\emptyset \in \emptyset\)	False
\(\emptyset \subseteq \emptyset\)	True
\(\emptyset \in \mathcal{P}(\emptyset)\)	True
\(\emptyset \subseteq \mathcal{P}(\emptyset)\)	True
\(\{\emptyset\} = \emptyset\)	False
\(\{1,2\} = \{2,1\}\)	True
\(A \times B = B \times A\)	False (in general)
\(A \subseteq A\)	True (always)
\(A \subset A\)	False (always)
\(\overline{U} = \emptyset\)	True
\(\lfloor ab \rfloor = \lfloor a \rfloor \lfloor b \rfloor\)	False
\(\sum k^2 = n(n+1)(2n+1)/6\)	True

Formulas at a Glance

\(|\mathcal{P}(A)| = 2^{|A|}\) · \(|A \times B| = |A| \cdot |B|\) · \(|A \cup B| = |A| + |B| - |A \cap B|\)

\(\displaystyle\sum_{k=1}^n k = \frac{n(n+1)}{2}\) · \(\displaystyle\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}\) · \(\displaystyle\sum_{k=0}^n r^k = \frac{r^{n+1}-1}{r-1}\)

Proof Starters

Quantifier	Start With
\(\forall x\)	"Let \(x\) be an arbitrary..."
\(\exists x\)	"Let \(x = \text{[specific value]}\)."
\(\forall x \exists y\)	"Let \(x\) be arbitrary. Let \(y = \text{[expr with } x\text{]}.\)"
\(\exists x \forall y\)	"Let \(x = \text{[value]}\). Then for any \(y\)..."