Introduction to University Mathematics (2026-27): Appendix: Notes for two in-person lectures

These are the notes for the two in-person lectures at the start of the year. The lectures won't follow this word-for-word, but will cover roughly this material in roughly this order.

For most courses, you can expect the in-person lectures to cover all of the material on the synopsis. This course is unusual, and the in-person lectures will cover some (but by no means all) of the definitions above, with some new connections between topics, and some more examples.

Lecture 0

Definition
A natural number is a member of the sequence 0, 1, 2, 3, ... obtained by starting from 0 and adding 1 successively.

We write $\mathbb{N}$ for the set of all natural numbers $\lbrace 0,1,2,3,\dots\rbrace$

Definition
A set $A$ is said to be a subset of a set $S$ if every element of $A$ is an element of $S$. We write $A \subseteq S$.

Definition
The power set of a set $A$, denoted $\mathcal{P}(A)$ is the set of all subsets of $A$. It's a set of sets.

$\mathcal{P}(\mathbb{N})=\{ \varnothing, \{0,1\}, \{n\in\mathbb{N}: \text{$n$ is prime}\},\{3\},\dots \}$ where the "$\dots$" is doing a lot of work.

A function from $X$ to $Y$ is an assignment of precisely one value in $Y$ for each value in $X$.

Can we have $f:\mathcal{P}(\mathbb{N})\rightarrow \mathbb{N}$ by taking each subset to its "least element"?

Not quite, because this doesn't tell us what to do with $\varnothing$. The function $f$ that takes subsets of the naturals to their least element and takes the empty set to 0 is well-defined, due to the Well-Ordering Principle, which states that every non-empty subset of $\mathbb{N}$ has a least element.

Definition
Given a function $f$ from $X$ to $Y$, we say that the function is

injective if whenever $f(x_1)=f(x_2)$ then $x_1=x_2$.
surjective if for every $y\in Y$ there is an $x\in X$ such that $f(x)=y$.
bijective if it's both injective and surjective.

The function above is surjective but not injective.

Proof.
for all $n$, $f(\{n\})=n$ (so it's surjective) but also $f(\{n,n+1\})=n$ (so it's not injective).
$\square$

Is there a surjective function $f:\mathbb{N}\rightarrow \mathcal{P}(\mathbb{N})$ ?

No!

Proof.
Suppose for contradiction that $f$ is surjective, and consider the set $\displaystyle R=\lbrace n\in \mathbb{N} : n \notin f(n)\rbrace$

$f$ is surjective, so $\exists x \in \mathbb{N}$ such that $f(x)=R$. Is $x\in R$?

If $x\in R$, then by definition of $R$, $x\notin f(x)$. But $f(x)=R$ so $x\notin R$.

Similarly, if $x\notin R$ then $x\notin f(x)$ so, $x$ meets the condition to be in $R$, so $x$ should be in $R$.

We have a contradiction.
$\square$

So we cannot have a bijection from $\mathbb{N}$ to $\mathcal{P}(\mathbb{N})$.

Definition
Two sets $S$ and $T$ are said to have the same cardinality if and only if there exists a bijection from $S$ to $T$.

We've seen that $\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$ do not have the same cardinality. Some cardinalities are assigned names or numbers;

$\varnothing$ has cardinality $0$.
$\{1,2,3,\dots,n\}$ has cardinality $n$.
$\mathbb{N}$ has cardinality $\aleph_0$.
$\mathcal{P}(\mathbb{N})$ has cardinality $\mathfrak{c}$ (the cardinality of $\mathbb{R}$, proof in Analysis).

We can replace $\mathbb{N}$ in the proof above with any set $S$ to show that $S$ and $\mathcal{P}(S)$ do not have the same cardinality.

The sequence of sets $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$, $\mathcal{P}(\mathcal{P}(\mathbb{N}))$, $\dots$ is an infinite sequence of infinite sets, no two of which have the same cardinality.

Lecture 1

Definition
Given sets $A$ and $B$, the Cartesian product, denoted $A \times B$, is given by
$\displaystyle
A \times B = \left\{ (a,b) : a \in A \ \text{and}\ b \in B \right\}.
$

Definition
Let $X$ and $Y$ be sets. A function $f$ from $X$ to $Y$ is a subset of $X\times Y$ such that $\displaystyle \forall x\in X\quad \exists ! y\in Y \quad\text{s.t.}\quad (x,y)\in f.$

Definition
A relation $R$ on a set $S$ is a subset of $S \times S$. If $(a,b)\in R$, we write $aRb$.

Definition
A relation $R$ on a set $S$ is an equivalence relation if it is reflexive ($\forall x,\, xRx$), symmetric ($\forall x,y,\, xRy \Rightarrow yRx$), and transitive ($\forall x,y,z,\, (xRy \wedge yRz) \Rightarrow xRz$).

For an equivalence relation, we might write $a\sim b$ instead of $aRb$.

Example
The equivalence relation on $\mathbb{R}$ given by $x\sim y$ if and only if $x-y\in \mathbb{Z}$.

(You might wonder which other sets $A \subseteq \mathbb{R}$ give an equivalence relation via $x\sim y \Leftrightarrow x-y\in A$.)

Definition
Given an equivalence relation $\sim$ on a set $S$, and given $x \in S$, the equivalence class of $x$, denoted $[x]$, is the subset
$\displaystyle
[x] = \left\{ y\in S : y \sim x \right\}.
$

Note that if $x\sim y$ then the sets $[x]$ and $[y]$ are equal (they have the same elements; prove this with the definition of an equivalence relation).

Definition
Given an equivalence relation $\sim$ on a set $S$, the quotient set $S/\!\sim$ is the set of equivalence classes
$\displaystyle S/\!\sim \, = \lbrace [x] : x \in S \rbrace $
It's a set of sets.

Example
Let $S=\mathbb{N}\times \mathbb{N}$ be the set of ordered pairs of natural numbers. Define an equivalence relation $(a,b)\sim (c,d)$ if and only if $a+d=b+c$.

Then the equivalence class $[(2,3)]$ has elements like $(2,3)$ and $(34,35)$ and $(1728,1729)$. Informally the thing they have in common is the difference between the two components. The quotient set $S/\!\sim$ has a lot in common with the set $\mathbb{Z}$ that you know and love.

We can define an addition operation on the equivalence classes by $\displaystyle [(a,b)] \oplus [(c,d)] = [(a+c,b+d)].$ Note that this is well-defined because choosing a different representative of $[(a,b)]$ doesn't change the equivalence class on the right-hand side.

Example
For the equivalence relation given by $x\sim y \Leftrightarrow x-y\in \mathbb{Z}$, the quotient set $\mathbb{R}/\!\sim$ is sometimes written as $\mathbb{R}/\mathbb{Z}$. The equivalence classes can each be represented as $[x]$ for some $x \in [0,1)$.

The equivalence classes inherit an addition operation from $\mathbb{R}$, because $[x] \oplus [y]=[x+y]$ is well-defined.

But $[x] \otimes [y] = [x \times y]$ would not be well-defined. Counter-example; $[0.1]\otimes[0.1]=[0.01]$ but $[1.1]\otimes[0.1]=[0.11]$

Example
For any function $f\colon X\rightarrow Y$, we can define an equivalence relation on $X$ by $x\sim y$ if and only if $f(x)=f(y)$.

Reflexive; $\forall x, x\sim x$ is true because $\forall x, f(x)=f(x)$.
Symmetric; $\forall x, y$ if $x\sim y$ then $f(x)=f(y)$ so $f(y)=f(x)$, which means $y\sim x$.
Transitive; $\forall x, y, z$, if $x\sim y$ and $y\sim z$ then $f(x)=f(y)$ and $f(y)=f(z)$ so $f(x)=f(z)$ which means $x\sim z$.

For this equivalence relation, we can define a new function $F\colon X/\!\sim\, \rightarrow\, f(X)$ by setting $F([x])=f(x)$.

This new function is well-defined because, no matter which representative of $[x]$ we choose, they all have the same value of $f$.

Claim: $F$ is a bijection.
Proof.
(Injective): if $F([x])=F([y])$ then $f(x)=f(y)$ so $x\sim y$ and therefore $[x]=[y]$.

(Surjective): I changed the codomain from $Y$ to $f(X)$. Every function is surjective onto its image.
$\square$

As a specific example, let $X=\mathbb{R}$ and $Y=\mathbb{C}$ with $f(x)=e^{2\pi \mathrm{i}x}$. Then the equivalence relation induced on $\mathbb{R}$ is precisely the one above where $x\sim y$ if and only if $x-y\in \mathbb{Z}$.

We have shown that $F\colon \mathbb{R}/\!\sim\, \rightarrow f(\mathbb{R})$ is a bijection, and here $f(\mathbb{R})$ is the unit circle and $\mathbb{R}/\!\sim$ is usually written $\mathbb{R}/\mathbb{Z}$.

Therefore $\mathbb{R}/\mathbb{Z}$ is in bijection with the unit circle.

As you progress through the degree, you'll see this strategy again and again, moving to a quotient set to simplify and understand many different objects. When a function isn't injective, we just quotient all our problems away!

Last modified: Wednesday, 16 September 2026, 9:19 AM