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.
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.