Logic, Sets & Relations¶
This is the vocabulary the rest of the course speaks. None of it is hard on its own, but it is the language every later proof is written in — so time spent here is repaid everywhere. The material splits three ways: sets and cardinality (how to count and compare collections, even infinite ones), relations and functions (how elements of sets are paired up), and propositional logic (how statements combine).
Sets and cardinality¶
A set is just a collection of distinct things, its elements. Everything in this section is about two questions: how do we combine sets, and how do we compare their sizes?
Operations¶
Three ways to build a new set from old ones:
- Union \(A \cup B\) — everything in \(A\) or \(B\) (or both). Think "throw both bags together."
- Intersection \(A \cap B\) — everything in \(A\) and \(B\). The overlap.
- Complement \(A^c\) — everything not in \(A\) (within some agreed universe). The leftovers.
The one identity worth committing to memory is De Morgan's laws, which say how complement interacts with the other two:
Why they hold. Read the left one in words: "not in (\(A\) or \(B\))" means you dodged both \(A\) and \(B\) — you're outside \(A\) and outside \(B\). That's exactly \(A^c \cap B^c\). Taking a complement flips "or" into "and". The second law is the same sentence with the roles of union and intersection swapped.
Power set¶
The power set \(\mathcal{P}(A)\) is every possible subset of \(A\), collected into one bag — including the empty set \(\emptyset\) and all of \(A\) itself.
Size of the power set
If \(\lvert A \rvert = n\), then
Why \(2^n\)? Building a subset means walking down the \(n\) elements one at a time and, for each, deciding in or out. That's \(n\) independent yes/no choices, and independent choices multiply: \(2 \cdot 2 \cdots 2 = 2^n\).
Concrete. Take \(A = \{a, b\}\), so \(n = 2\). The subsets are \(\emptyset,\ \{a\},\ \{b\},\ \{a, b\}\) — four of them, and \(2^2 = 4\). ✓
\(\in\) versus \(\subseteq\) — a favourite seminar trap
These two symbols are not interchangeable, and mixing them up is the single most common set-theory error. \(\in\) means "is an element of"; \(\subseteq\) means "is a subset of". An element is a single thing in the bag; a subset is a smaller bag.
For \(A = \{a, b, c\}\):
- \(\emptyset \subseteq A\) is true — the empty set is a subset of everything (it asks nothing of \(A\)).
- \(\emptyset \subseteq \mathcal{P}(A)\) is true, for the same reason.
- \(\{a\} \in \mathcal{P}(A)\) is true — the elements of \(\mathcal{P}(A)\) are the subsets of \(A\), and \(\{a\}\) is one of them.
- \((a, 1) \in A \times B\) is true (a pair is an element of the product), but \((a, 1) \subseteq A \times B\) is false (a single pair is not a sub-collection).
The pattern to hold onto: \(\mathcal{P}(A)\) shifts everything up one level. Subsets of \(A\) (a "level 1" idea) become elements of \(\mathcal{P}(A)\) (a "level 2" object).
Comparing sizes: cardinality¶
For finite sets, "same size" just means "same number of elements". The clever move in this course is that we make that idea work for infinite sets too, using a definition that never counts anything:
Definition of same cardinality
Two sets have the same cardinality if there is a bijection between them — a pairing that matches every element of one to exactly one element of the other, with nothing left over on either side.
Read this carefully, because it is the only tool you have for infinite sets. You cannot argue by "size", and you cannot argue that one set is bigger because it seems to contain more. The only legitimate move is to build a bijection (to prove equal) or to prove no bijection can exist (to prove unequal).
The two facts to know:
- \(\mathbb{Z}\) (integers) and \(\mathbb{Q}\) (rationals) are countable: each can be bijected with \(\mathbb{N} = \{0, 1, 2, \dots\}\). "Countable" literally means "can be listed in an order that eventually reaches every element."
- \(\mathbb{R}\) (reals) is uncountable: no such list exists. This is Cantor's diagonal argument — assume you had a complete list of reals, then build a new real that differs from the \(n\)-th listed real in its \(n\)-th digit, so it can't be on the list. Contradiction.
Infinite sets break your intuition — expect it
Here is a statement that sounds obviously true and is in fact false:
If \(A\) and \(B\) are infinite and \(B \subsetneq A\) (strictly smaller), then \(\lvert B \rvert < \lvert A \rvert\).
Counterexample. Let \(B = 2\mathbb{Z}\) (the even integers) sitting inside \(A = \mathbb{Z}\). Clearly \(B\) is missing all the odd numbers, so surely it's smaller? No: the map \(n \mapsto 2n\) pairs every integer with an even integer, perfectly, with nothing left over. That's a bijection, so \(\lvert B \rvert = \lvert A \rvert\).
The lesson: a proper subset of an infinite set can be exactly the same size. "Being a subset" and "being smaller" come apart once sets are infinite. Trust the bijection, not the picture.
Proving a set is uncountable¶
This is a recurring Part C problem, so it's worth a reliable method. There are two routes:
- Inject \(\mathbb{R}\) into it. If you can build an injective (one-to-one) map \(\varphi: \mathbb{R} \to S\), then \(S\) has at least as many elements as \(\mathbb{R}\), so \(\lvert S \rvert \geq \lvert \mathbb{R} \rvert\) and \(S\) is uncountable.
- Run the diagonal argument directly on \(S\), exactly as Cantor did for \(\mathbb{R}\).
Route 1 is usually cleaner when \(S\) visibly "contains a copy of the reals".
Exam (May 2024, Problem 8): decimals of 1's and 5's
Problem. Let \(S\) be the set of real numbers whose decimal expansion uses only the digits \(1\) and \(5\) (so \(1.51151111\ldots \in S\) but \(1.34 \notin S\)). Is \(S\) countable?
Answer: uncountable. We'll use route 1 and inject \(\mathbb{R}\) into \(S\).
The idea. A real number has a binary expansion — a string of two symbols, \(0\) and \(1\). An element of \(S\) is a string of two symbols too, \(1\) and \(5\). Two symbols is two symbols. So we can just relabel: turn each binary digit into a "\(1\)-or-\(5\)" digit and land inside \(S\).
The construction. Let \(\psi: \{0,1\} \to \{1,5\}\) be \(\psi(1) = 1\), \(\psi(0) = 5\). Given a real number with binary expansion \(a_1 a_2 \ldots a_n . b_1 b_2 b_3 \ldots\), define \(\varphi\) to send it to
Why it's injective. Binary expansions are unique once you forbid the ones ending in all-1's (the same fix that stops \(0.0111\ldots = 0.1000\ldots\) in base 10), so different reals give different strings, hence different elements of \(S\).
Conclusion. \(\varphi\) injects \(\mathbb{R}\) into \(S\), so \(\lvert S \rvert \geq \lvert \mathbb{R} \rvert\) and \(S\) is not countable. \(\square\)
The one insight to take away: the digits \(1\) and \(5\) carry no arithmetic meaning in this problem — they're just two symbols, and two symbols is precisely what a binary expansion needs. Spotting "this is really just binary in disguise" is the whole problem.
Proving a set is countable¶
The other half of the exam skill: showing a set is small. "Countable" means "listable" — you must exhibit (or convincingly describe) an ordering that eventually reaches every element. Three building blocks cover almost every case, and they combine freely:
The three countability facts to quote
- A subset of a countable set is countable. (Listing the big set and skipping the elements you don't want still reaches everything you do.)
- \(\mathbb{N} \times \mathbb{N}\) is countable. Walk the grid along its anti-diagonals: \((0,0),\ (0,1),(1,0),\ (0,2),(1,1),(2,0),\dots\) — each diagonal is finite, so the walk reaches every pair in finite time.
- A countable union of countable sets is countable. Same diagonal walk: put set \(A_i\) in row \(i\), list each row, and sweep the anti-diagonals.
From these, the standard results assemble themselves. \(\mathbb{Z}\) is countable (list \(0,1,-1,2,-2,\dots\)). \(\mathbb{Q}\) is countable because each rational is a pair (numerator, denominator), so \(\mathbb{Q}\) injects into \(\mathbb{Z}\times\mathbb{Z}\) — fact 2 plus fact 1. The set of finite strings over a finite alphabet is countable — group them by length (finitely many of each) and use fact 3.
The pattern that decides which way to argue
A set built by finite recipes — finite tuples, finite strings, "a numerator and a denominator", polynomials with integer coefficients — is almost always countable (inject it into some \(\mathbb{Z}^k\)). A set encoding an infinite amount of independent choice — all subsets of \(\mathbb{N}\), all infinite \(0/1\) sequences, all reals — is almost always uncountable (run the diagonal argument). Ask "how much information does one element carry?" before picking a method.
Worked: the set of finite subsets of \(\mathbb{N}\) is countable
Let \(F\) be all finite subsets of \(\mathbb{N}\) (so \(\{2,5,9\}\in F\) but the evens are not).
Split \(F\) by size: let \(F_k\) be the subsets with exactly \(k\) elements. A \(k\)-element subset is determined by its list of members in increasing order, i.e. a point of \(\mathbb{N}^k\), so \(F_k\) injects into \(\mathbb{N}^k\) — countable (fact 2, applied \(k-1\) times). Then
is a countable union of countable sets, hence countable by fact 3. \(\square\)
Contrast this sharply with the set of all subsets of \(\mathbb{N}\) (the power set), which is uncountable — dropping the word "finite" changes the answer completely, because an arbitrary subset encodes infinitely many independent in/out choices.
Relations¶
A relation is a way of saying which elements are linked to which. Formally, a binary relation \(R\) on a set \(A\) is just a set of ordered pairs — a subset of \(A \times A\) — and we write \(x \mathbin{R} y\) as shorthand for "\((x, y)\) is in that set", i.e. "\(x\) is related to \(y\)". "Is less than", "divides", "is congruent to mod \(n\)" are all relations.
We classify relations by which of these five properties they have:
| Property | Definition | In words |
|---|---|---|
| Reflexive | \(x \mathbin{R} x\) for all \(x\) | everything relates to itself |
| Symmetric | \(x \mathbin{R} y \implies y \mathbin{R} x\) | the relation doesn't care about direction |
| Anti-symmetric | \(x \mathbin{R} y\) and \(y \mathbin{R} x \implies x = y\) | the only way it goes both ways is \(x = y\) |
| Transitive | \(x \mathbin{R} y\) and \(y \mathbin{R} z \implies x \mathbin{R} z\) | links chain together |
Two particular combinations get their own names, because they show up constantly:
- Equivalence relation = reflexive + symmetric + transitive. Captures "these things are the same for our purposes."
- Partial order = reflexive + anti-symmetric + transitive. Captures "this comes before that", allowing some pairs to be incomparable.
Equivalence classes¶
Equivalence relations matter because of one clean consequence: they carve a set into disjoint groups. Each group, called an equivalence class, gathers everything mutually related:
The key fact: every element lands in exactly one class — the classes don't overlap and together they cover all of \(A\). Splitting a set into non-overlapping, exhaustive pieces is called a partition, and that's precisely what an equivalence relation produces.
Why you should care. This one idea reappears in disguise throughout the course:
- Congruence mod \(n\) (\(a \sim b\) when \(n \mid a - b\)) is an equivalence relation. Its classes are the \(n\) "remainder buckets" \(\{0, n, 2n, \dots\}\), \(\{1, n+1, \dots\}\), and so on — and those buckets are the elements of \(\mathbb{Z}_n\). See number theory.
- In group theory, cosets partition a group the same way, and that partition is the entire mechanism behind Lagrange's theorem.
So if you understand "equivalence relation → partition" here, you've already understood the skeleton of two later topics.
Anti-symmetric is not 'not symmetric'
A common misread. Anti-symmetry doesn't forbid \(x \mathbin{R} y\) and \(y \mathbin{R} x\) from both holding — it just says that when they do, \(x\) and \(y\) must be equal.
Example. Take divisibility on the positive divisors of \(100\). If \(a \mid b\) and \(b \mid a\), then indeed \(a = b\) — so it's anti-symmetric, and it's a partial order. It's only partial because some pairs are incomparable: neither \(4 \mid 5\) nor \(5 \mid 4\), so \(4\) and \(5\) simply aren't ordered relative to each other.
Functions¶
A function \(f: A \to B\) assigns to each element of the domain \(A\) exactly one element of the codomain \(B\). The three adjectives you need describe how the arrows land in \(B\):
- Injective (one-to-one): no two inputs share an output — every element of \(B\) is hit at most once. Equivalently, \(f(x) = f(y)\) forces \(x = y\). ("No collisions.")
- Surjective (onto): every element of \(B\) is hit at least once — nothing in the codomain is missed. ("Full coverage.")
- Bijective: both at once — every element of \(B\) is hit exactly once. ("A perfect pairing.")
A handy picture: injective = no two arrows point at the same target; surjective = no target is left un-pointed-at; bijective = arrows and targets match up perfectly.
Bijections are exactly the "perfect pairings" that cardinality is defined through, which is why nearly every countability problem boils down to building one function and checking it's injective (or bijective).
Propositional logic¶
Propositional logic is the algebra of statements that are each simply true or false. We build compound statements with connectives and ask when they come out true.
Truth tables¶
A truth table lists every possible combination of truth values for the variables and works out the result. If a compound statement is true in every row it's a tautology; if false in every row it's a contradiction.
Here are the connectives. The only one that regularly surprises people is implication, so watch its column:
| \(p\) | \(q\) | \(p \land q\) (and) | \(p \lor q\) (or) | \(p \implies q\) (if–then) | \(p \iff q\) (iff) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | F | T | T | F |
| F | F | F | F | T | T |
Why implication looks like that. Read \(p \implies q\) as a promise: "if \(p\), then \(q\)". The promise is only broken when \(p\) happens but \(q\) doesn't — that's the single F row. If \(p\) never happens (the bottom two rows), the promise was never tested, so we count it as kept (vacuously true). This trips people up because everyday "if" often implies causation; logical "if" does not — it's purely about that one broken-promise case.
Boolean normal forms¶
Any Boolean function — any truth table you can write down — can be captured by a formula, and in fact by a formula in one of two standard shapes. The nice part: you can read either shape straight off the truth table.
- Disjunctive normal form (DNF) — an OR of ANDs (a sum of minterms). Look at each row where the function is true. Write one AND-clause that is true only on that row (use \(x\) where the variable is \(1\), \(\lnot x\) where it's \(0\)). OR all those clauses together. Since the whole thing is true exactly on the rows you picked, it matches the function.
- Conjunctive normal form (CNF) — an AND of ORs (a product of maxfactors). Same idea from the other side: look at each row where the function is false, write one OR-clause that is false only there (this time negate the variables that are \(1\)), and AND them all.
Which to use? Whichever gives fewer clauses. Few true rows → short DNF. Few false rows → short CNF. Either way they describe the same function — they're two encodings of one truth table.
Quantifiers and negation¶
Most real mathematical statements aren't about fixed propositions but about all or some elements of a set. Two symbols carry that load:
- \(\forall x\) — "for all \(x\)" (the universal quantifier). The statement claims something holds no matter which \(x\) you pick.
- \(\exists x\) — "there exists an \(x\)" (the existential quantifier). It claims at least one \(x\) works.
Order matters, and it is not cosmetic. \(\forall x\, \exists y\, P(x,y)\) and \(\exists y\, \forall x\, P(x,y)\) say genuinely different things. The first lets \(y\) depend on \(x\) (each \(x\) gets its own \(y\)); the second demands a single \(y\) that works for every \(x\). "Everyone has a mother" (\(\forall x\,\exists y\)) is true; "there is one person who is everyone's mother" (\(\exists y\,\forall x\)) is false. Swapping adjacent unlike quantifiers changes the meaning — never do it silently.
Negating a quantified statement¶
This is the examinable skill, because so many proofs run by contradiction (assume the negation) and because "the statement is false — show why" is really "prove the negation". The rule is mechanical:
Pushing \(\lnot\) through quantifiers
To negate, flip every quantifier and negate the innermost statement:
\(\forall\) becomes \(\exists\), \(\exists\) becomes \(\forall\), and the \(\lnot\) marches inward until it hits a plain proposition. Inside, De Morgan handles the connectives (\(\lnot(p\land q)\equiv \lnot p \lor \lnot q\), and dually), and an implication negates as \(\lnot(p\implies q)\equiv p \land \lnot q\).
The intuition is worth holding onto: the negation of "all swans are white" is not "all swans are non-white" — it's "some swan is non-white". One counterexample refutes a \(\forall\); to refute an \(\exists\) you must rule out every candidate.
Negate: 'every even number \(>2\) is a sum of two primes'
Symbolically, with \(E\) the even numbers greater than \(2\):
Flip both quantifiers and negate the inside:
In words: "there is an even number greater than \(2\) that is not the sum of any two primes." That is exactly what you would have to exhibit to disprove Goldbach's conjecture — the negation tells you the shape of a counterexample. (Whether one exists is famously open; the point here is only that the mechanical flip produces the right target.)
Proof techniques (a quick toolbox)¶
Part C problems are graded on the argument, so it pays to know which standard skeleton fits a claim before you start writing. Four cover almost everything on this exam (induction is the fifth and gets its own page).
| Technique | Use it when… | The move |
|---|---|---|
| Direct | the claim is a straightforward implication | assume the hypothesis, deduce the conclusion step by step |
| Contrapositive | the hypothesis is hard to use but \(\lnot(\text{conclusion})\) is concrete | prove \(\lnot q \implies \lnot p\) instead of \(p \implies q\) — logically identical |
| Contradiction | the claim asserts something is impossible or unique | assume it's false, derive a plain absurdity |
| Counterexample | you must disprove a \(\forall\) statement | exhibit one instance where it fails — no more is needed |
Contrapositive vs. contradiction — they are not the same
A contrapositive proof of \(p \implies q\) proves the clean statement \(\lnot q \implies \lnot p\) and stops — no contradiction in sight. A proof by contradiction assumes \(p \land \lnot q\) and hunts for any absurdity. Contrapositive is tidier when it applies, so reach for it first; fall back to contradiction when the claim isn't a simple implication (e.g. "\(\sqrt 2\) is irrational" — there's no "if" to contrapose, so you assume it's rational and derive nonsense).
Contrapositive: if \(n^2\) is even then \(n\) is even
Proving this directly is awkward — "\(n^2\) even" doesn't hand you a factor of \(n\). The contrapositive is easy: if \(n\) is odd then \(n^2\) is odd. Write \(n = 2k+1\); then
which is odd. Having proved \(\lnot q \implies \lnot p\), the original \(p \implies q\) follows for free — they are the same statement. \(\square\)