← IA Numbers and Sets – Full Text
These are Zixuan’s notes for Part IA – Numbers and Sets at the University of Cambridge in 2025. The notes are not endorsed by the lecturers or the University, and all errors are my own.
The latest version of this document is available at academic.micfong.space. Please direct any comments to my CRSid email or use the contact details listed on the site.
This document is typeset using Typst. All figures are created using Inkscape.
1 Introduction to Number Systems and Logic
As an introduction to university-level mathematics, we will look at precise definitions, rigorous proofs, and fundamental theorems. To begin with, let us look at the definitions of a statement and a proof.
If were to prove a statement, we need a proof.
We want to prove things because
- we want to know if they are true;
- we want to gain insights into why they are true;
- the proof itself might be cool.
1.1 Number Systems
Notation. These number systems should be fairly familiar:
| the set of natural numbers (positive integers) | |
| the set of integers | |
| the set of rational numbers, i.e. all fractions of the form where and |
Conside the length of the hypotenuse in a right-angled isosceles triangle with side lengths 1. The Pythagorean realized that . To show that exists, we need to construct a new number system , where such that .
1.2 Proofs and Non-proofs
Let us take a look at a few examples of proofs (and non-proofs).
Proof. For any , we have
One of the 3 consecutive integers must be a multiple of 3, and hence the product.
Here is an example of a false proof.
Non-proof. Given a positive integer , which is even, we can write for some .
Then we have , which is even.
Note that we have falsely proven the converse above. Here is a corrected version of the proof:
We have used the technique of proof by contradiction, where we assume the contrary and deduce a contradiction (so the assumption would be false).
We can also prove that something is false, usually by a counterexample.
We write for the statement “if A then B”.
This is in fact 2 assertions:
- and are solutions
- there are no other solutions
Proof.
-
If or , we have or . Hence .
Thus, we have .
-
If , then . So or .
Hence the only solutions are and .
Alternatively, we could write the following:
It is vital that every step is using .
Non-proof. Let be the least positive real number.
Either or or . [This is a trichotony.]
If , then . However, is the least positive real number.
If , then .
Hence .
We assumed a false claim in the proof: there is no least positive real number.
1.3 Basic Logic
If and are assertions, we can write:
- for “”,
- for “”,
- for “”.
1.3.1 Truth Tables
The truth of these assertions depends on the truth of and , and can be summerized in a truth table.
| F | F | F | F | T | T |
| F | T | F | T | T | T |
| T | F | F | T | F | F |
| T | T | T | T | F | T |
Note, e.g., that is equivalent to , by comparing truth tables.
Also, is equivalent to , and hence , and so to . This is called the contrapositive.
A claim may include quantifiers, especially “for all” and “there exists”.
1.3.2 Negating Quantifiers
We have
2 Sets, Functions and Relations
2.1 Sets
2.1.1 Introduction on Sets
A set is a collection of mathematical objects.
Examples include .
The order of elements in a set is immaterial, and elements are counted only once. e.g. , and .
We write if is an element of , and if not.
Two sets are equal if they have the same elements. i.e. if and only if .
A set is a subset of , written or , if every element of is an element of .
is said to be a proper subset of if and . This is also written as .
If is a set and is a property of some elements of , we can write for the subset of comprising those elements for which holds.
If and are sets, then
- their union
- their intersection .
- and are disjoint if .
- their difference .
2.1.2 Properties of Sets
We have a few properties about intersections and unions.
-
we can view intersection as a special case of subset selection:
-
intersection and union are commutative and associative:
-
union is distributive over intersection, i.e.
and intersection is distributive over union:
If are sets, then
To prove statements in Proposition 2.5 and Proposition 2.6, we can rewrite set notation into a combination of inclusion and logical connectives, and then use a truth table to derive the results. Usually, we need to show that and .
Notation. If are sets, then
Similarly,
More generally, given an index set and a collection of sets indexed by , we write
We can extend Definition 2.7 to ordered triples and so on, e.g.
For any set , the power set is the set consisting of all subsets of , i.e.
For example, if , then .
Important. Given a set , we can form for any property . However, we cannot always form , due to the following paradox.
Suppose were a set. Now, if , it implies by definition that .
On the other hand, if , then by our construction.
This is known as Russell’s Paradox. More generally, this comes from the fact that there is no universal set such that . Otherwise, we could form above using the subset notation as .
2.1.3 Finite Sets
Given , we say a set has size if we can write with the elemtns distinct.
2.2 Functions
Given sets and , a function from to is a rule that assigns to every uniquely to an element .
More formally, a function from to is a subset such that for all , there exists exactly one such that . We usually write
and
- with is a function.
- with is not a funciton since it is undefined at .
- with is not a function.
- with is a function.
Following Definition 2.11, for , we say that is the domain of and is the range (or codomain).
If and , then is called the image of , and is called a preimage of .
Moreover, if then the image of under is
If , then the preimage of under is
For the function , the image of is , but the preimage of is .
We also have , and .
The preimage .
We say is injective if , we have . Equivalently, is injective if by the contrapositive.
We say is surjective if , such that .
We say is bijective if it is both injective and surjective.
If is a bijection, then everything in is mapped to exactly once. That is, pairs elements of and .
Observation.
-
is surjective if and only .
For finite sets and , if , then there cannot be a surjective function from to .
-
For finite sets and , there is no injection from to if .
-
For a finite set , , then is injective if and only if is surjective.
-
For a finite set , There is no bijection from to any proper subset of it.
-
A set has size if and only if there is a bijection where .
2.2.1 Examples of Functions
-
A sequence of reals is a function where .
-
The operation on is a function where .
Given a set and , we have the indicator function (or characteristic function) of , defined by
Proof. [for property (4)]
We have
- In general, is not commutative.
- is associative. i.e. if we have , then .
Proof. For example, if with , and with , then
Hence, in general, is not commutative.
Now, for every , we have
Consider with and with .
Indeed, , , so .
Similarly, , , so .
Hence is invertible with inverse .
Important. Consider with , with .
We have but since .
Proof.
-
We shall first consider the necessary condition that, given , there is a map such that .
Necessary condition. If such a were to exist, and such that , then . Hence . Thus must be injective.
Sufficient condition. Now let us consider the sufficient conditions. Conversely, if is injective, we want to show that we can find such that . Consider some .
-
If . let , where the unique element of with .
-
If , then let be anything in the set .
So we have constructed the required function such that , and the condition of being injective is sufficient.
-
-
We can take a step further to consider the conditions for to be invertible, i.e. as well.
Necessary condition. We need , so must be surjective.
Sufficient condition. Conversely, if is surjective, we want to find with . For each , pick some with . This always exists due to surjectivity of , and choose .
Note that our construction of in the two parts are consistent. Hence, the result follows.
2.3 Relations
A relation on a set is a subset .
We write if . We say that and are related by .
- if share the same final digit
- if
- if
- if
- if
There are three properties of a relation that are of special interest.
A relation on is…
- reflexive if , .
- symmetric if , .
- transitive if , .
Let us do a property check over Definition 2.28 on the examples in Example 2.27.
| Example # | 1 | 2 | 3 | 4 | 5 |
| Reflexive | |||||
| Symmetric | |||||
| Transitive |
A relation is an equivalence relation if it is reflexive, symmetric and transitive.
We usually write for the case where and is an equivalence relation.
In Example 2.27, only (1) is an equivalence relation.
Let .
Let if two students are born in the same month. Then is an equivalence relation.
Note that, in the example above, the set is divided into subsets consisting of related elements.
If is an equivalence relation on , then the equivalence class of is denoted by
Proof. Since is reflexive, we have for all . Thus .
It remains to prove that , either or
Suppose that , and let . Then , and so by symmetry, , and . By transitivity, .
Let now , so . Since , by transitivity, . Thus .
Hence if then . By symmetry, we have . Therefore, .
Conversely, given any partition of , there is an equivalence relation whose equivalence classes are precisely the parts of the partition: just define if and lie in the same part.
The map with is the quotient map or the projection map.
On define if . This is an equivalence relation, and note that
so we could regard as a copy of by identifying with .
The quotient map is where .
- , on
- on
- on
We say a binary operation on is
-
commutative if , .
e.g. set intersection is commutative
-
associative if , .
-
distributive over if for another binary operation , , we have
e.g. is distributive over on .
3 How to Count
3.1 Construction of
We shall construct from a set of axioms.
The natural number is a set containing a special element , together with a map, called the successor function:
which maps to its successor [intuitively, this is the “” operation.], such that it satisfies the following axioms.
-
[ is not the successor of anything.]
-
, .
-
Let be a subset of such that
- , and
- ,
then .
Note that Axiom 3.1 (3) is the axiom of induction. We can now write , etc. Also, we can define addition recursively by
Similarly for multiplication, we can define it by
We can show by induction that these satisfy the usual rules of arithmetic, that
- and are commutative and associative
- is distributive over
To prove that , we will need to do the followings:
- induct on
- base case is
i.e.
- prove this by inclusion on
3.2 Induction and Ordering
We can also define an ordering: if for some . We may check by induction that the usual rules hold, i.e. transitivity holds.
A key feature of is that for any distinct , exactly one of or holds. This is called a total order.
We shall show that we cannot get and at the same time. If and . Then such that and . By associativity we have
Hence . By Axiom 3.1 (1), this is a contradiction.
The fact that we have ordering means that we can write down two types of induction.
-
The weak principle of induction (WPI), which is just Axiom 3.1 (3):
If holds, and , then holds .
-
The strong principle of induction (SPI) is based on the ordering above:
If we are given that
- holds,
- , ,
then holds .
Remark. We need ordering since we are effectively saying that to prove , we need for all .
Proof. Let us first show that SPI implies WPI. We are given the assumptions:
- SPI. If holds, and , , then holds .
- WPI’s assumption. holds, and .
We can use (2) to show that holds. Then using (2) again, we can show that holds. Continuing this way, we can show that holds for all . Hence by (1), holds for all , and WPI holds.
Conversely, to see that WPI implies SPI, we define a new predicate as “ holds for all “. Then we can use WPI to show that holds for all , which implies that holds for all .
The above ordering of satisfies a special property called the well-ordering principle (WOP).
Any non-empty subset of has a least element.
i.e. if holds for with , then there exists a least element such that holds.
Proof. Assume that holds for with . Suppose, for contradiction, that there is no least such that holds. Consider .
Certainly is false, because otherwise will be our minimal element. Then holds.
Now, given , suppose is true for all . Then must be false for all , and so must also be false (otherwise will be our minimal element). Hence holds.
Hence by SPI, holds for all , and is false for all , contradicting our assumption that there exists some such that holds.
Consider the following theorem.
Any natural number can be written as a product of primes.
Proof. Let .
We assume and derive a contradiction. By WOP, has a least element . Since is not prime, we can write for some with . By minimality of , both and can be written as a product of primes. Hence can also be written as a product of primes, which is a contradiction.
3.3 Finite Sets
Recall a set has size if we can write with the elements distinct. We write or .
Let us recall the definition of finite sets in Definition 2.10. We say is finite if such that , and is infinite otherwise.
Proof. We shall prove by induction on .
Base case. This is true for since the empty set has exactly one subset, itself.
Inductive step. Suppose the result holds for some . Let be a set of size . Pick some element , and let . Then has size , and by the inductive hypothesis, has exactly subsets.
Now, to form the subsets of , we can take each subset of and either include or exclude . This gives us exactly two choices for each subset of , leading to a total of subsets of .
Hence, by induction, the result holds for all .
So this proposition says that if , then .
3.3.1 Binomial Coefficients
Given , and , we can write for the number of subsets of an -element set that are of size .
is called a binomial coefficient.
In other words,
Note that, by definition, for . Also,
since this counts all subsets of an -element set.
Also we have forall . This is because specifying which elements to pick is equivalent to specifying which elements to leave out.
Moreover,
Consider
Suppose that you are in a group of 8 people. To form a commitee of 3 people, either you are in the commitee, in which case you need to choose 2 more people from the remaining 7, or you are not in the commitee, in which case you need to choose all 3 people from the remaining 7.
This leads to Pascal’s triangle:
where each row starts and ends with a 1, and the remaining entries are the sum of the 2 terms immediately above.
Proof. Given a set of size , there are to pick elements, in order, one by one. But each subset of size is picked in ways in this method.
Hence, the number of subsets of size in is
Note that the formula tells us, for example, that
for large .
For all and , we have
Proof. When we expand , we obtain terms of the form where , and the number of terms of the form in the expansion is , since we must specify brackets from which to pick .
Hence
Thus, for a small , a good approximation to is . [This is called the first-order approximation.]
3.3.2 Inclusion-Exclusion Principle
What can we say about the relationship between sizes of union and intersection of finite sets?
One should have seen the following formulae before:
Let be finite sets. Then
Equivalently,
Remark. This can be proven using indicator functions, using that if then
Proof. Let , say for of the sets . We want to be counted exactly once in the RHS.
Indeed, if ,
Thus the number fo times is counted on the RHS is
4 Elementary Number Theory
4.1 Primes
Given , we say “ divides “ if such that . We write .
For any , and are always factors; all other factors are called proper factors.
Proof. We will prove by induction on .
Base case. The statement is true for .
Inductive step. Let and suppose that the claim holds for all natural numbers . If is prime, we are done. Otherwise, is composite, so there exists such that and . By the inductive hypothesis, both and can be written as a product of primes. Thus, can also be written as a product of primes.
One may naturally wonder if all numbers can be written in only one way as a product of primes (up to ordering). This is indeed the case, as we shall see later.
4.2 Highest Common Factor
Given , a natural number is the highest common factor or the greatest common divisor of and if
- and ;
- for any such that and , we have .
We write or .
The factors of are . The factors of are .
Thus, the common factors of and are , and the highest common factor is . Therefore, .
We will need to show that the highest common factor always exists.
Proof. We will prove this by induction on .
Base case. The statement is true for .
Inductive step. For , suppose the statements holds for all natural numbers . We want to show that it also holds for . i.e. for some with .
If , then .
Otherwise, if , then .
Thus, in either case, we have expressed in the desired form.
Note that and thus obtained are unique: if , then . Since , we have . The only multiple of in this range is , so and hence .
4.3 Euclid’s Algorithm
| INPUT | ||
| STEP 1 | with | |
| STEP 2 | with | |
| STEP 3 | with | |
| STEP | with | |
| STEP | with | |
| OUTPUT |
Note that the algorithm terminates in steps, since .
Proof.
-
We have as . Back-substituting, we get divides , and continuing inductively, we find that divides both and .
-
Given such that and . Thence we have as . Back-substituting, we get divides , and continuing inductively, we find that divides .
We want . We run Euclid’s algorithm:
The answer is the last non-zero remainder. Thus, .
We can reverse the steps of Euclid’s algorithm to express the highest common factor as a linear combination of and .
Continuing from the previous example, we have
Thus, we have expressed as a linear combination of and .
This reversal procedure leads to the following important result.
Proof 1. We can run Euclid’s algorithm with inputs to obtain an output . Then we have for some .
But from step we see that is expressible as a linear combination of and . Substituting this into the previous equation, we can express as a linear combination of and . Continuing inductively, we can write, for some ,
for all . In particular,
for some , by step 1 and 2.
Proof 2. Let be the least positive linear combination of and , i.e. the smallest positive integer of the form for some . We will show that . We shall prove the two conditions in Definition 4.5.
To show (2), observe that given such that and , we have for all . In particular, .
To show (1), suppose that . Then we can write for some ans . Hence is also a positive linear combination of and , contradicting the minimality of . Thus, . Similarly, we can show that .
Therefore, .
Consider whether we have integer solutions to the equation
Since divides , by Bézout’s identity, we can write for some , and thus . Therefore, integer solutions do exist.
Proof.
[] Let . Suppose that there are such that . Since and , we have .
[] Conversely, suppose . By Bézout’s identity, there exist such that . Thus, , giving a solution.
Recall Proposition 4.4. We shall now prove it.
Proof. [For Proposition 4.4]
Suppose but . We wish to show that . Since is prime and , we have . By Bézout’s identity, there exist such that . Multiplying both sides by , we get . Since and , we have .
The other case is similar.
Remark.
-
Similarly for some , by induction on .
-
The statement is false if is not prime. For example, , but and .
Proof. The existence of factorisation follows from Proposition 4.2. To show uniqueness, we will use induction on .
Base case. The statement is true for .
Inductive step. Let and suppose the statement holds for all natural numbers . Suppose that where are all primes. We want to prove that and, after reordering, for all .
Hence . By Proposition 4.4, for some . Since is prime, we have . Without loss of generality, let . Cancelling from both sides, we get , which is a natural number less than . By the inductive hypothesis, we have and, after reordering, for all . Thus, the result holds for .
Consider , which is the set of all numbers of the form where . We can define addition and multiplication as usual. For example,
In we can define what it means to be a “prime”, and both happens to be primes in this sense. However, we can also write as , so the factorisation is not unique.
We shall consider some applications of the fundamental theorem of arithmetic.
-
The factors of are all numbers of the form where , and . We can show that there are others: if, for example, , then we would have a factorisation of involving , contradicting the uniqueness of factorisation.
More generally, the factors of are all numbers of the form where for all .
-
The common factors of and are all numbers of the form where , and . Thus, the highest common factor is .
More generally, if and with for all , then .
-
The common multiples of and are all numbers of the form where , , , , and is any integer. Thus, the lowest common multiple is .
More generally, if and with for all , then .
-
We have another proof of infinite prime numbers due to Erdös.
Proof. Let be all the primes. Since any number is uniquely expressed as a product of primes, consider where for all .
We can rewrite this in the following form:
where for all , and is some integer.
Let . Given a number less than or equal to in the form above, we must have , so there are at most numbers of the form less than or equal to .
If , i.e. , there must be a number less than or equal to that is not of the form above. So this number must have a prime factor not in the list , giving a contradiction.
Note that Euclid’s proof tells us that the th prime is whereas Erdös’ proof tells us that the th prime is . In fact, we know that the th prime is approximately for large (the prime number theorem), which is a much stronger result.
4.4 Modular Arithmetic
We have for some .
Note that we can view as a circular loop of integers , where after we return to .
4.5 Solving Congruences
We cannot divide both sides of a congruence by an integer in general. Thus, we need other methods to solve congruences.
Consider the equation
Note that , so , and so since .
Given , we say that is an inverse of modulo if .
We say that is invertible modulo , or that is a unit modulo , if such a exists.
In , is an inverse of . Hence, both and are units modulo .
But is not a unit modulo since there is no integer such that .
Remark. If is a unit modulo , then
-
its inverse is unique: suppose such that . Then
-
We can write for its inverse.
-
If , then . i.e. we can cancel units, by multiplying both sides by their inverses.
Important. This is not true in general. Consider . Certainly .
We can rephrase this proposition more generally.
Proof.
Consider whether “New Year’s Day” can fall on any day of the week in a year. [Assume a year has 365 days and a week has 7 days.]
Since , so if we put “New Year’s Day” as day 0, and our week has 7 days in it, then we need to solve
i.e. , which has a unique solution for all . Thus, “New Year’s Day” can fall on any day of the week.
We shall now consider equations of the form with , say .
Proof. Suppose . Then , and so and . So if there is a solution, we must have .
Conversely, if , then , , and , and the equation is
Note that . Thus, by the previous corollary, there is a unique solution modulo to this equation.
So if , the congruence has no solution if , and otherwise the solutions are exactly .
-
Consider the equation . Hence , so by Bézout’s theorem,
Thus , and thus .
Let us check the uniqueness of the solution. Suppose . Then . Since , is a unit modulo , and so .
Short form. This might be helpful in tackling problems:
-
Consider :
ans so we reduce to the case of example (1).
4.6 Solving Simultaneous Congruence
Consider this old Chinese problem:
How many soldiers are there in Han Xin’s army, if you let them parade in rows of 3, 2 are left; and if you let them parade in rows of 4, 1 is left?
This is equivalent to solving the simultaneous congruences
so is a solution.
Now consider another case:
This simultaneous congruence has no solution since implies that is even, but implies that is odd.
Now let us consider the general case.
Let be coprime, and . Then there is a unique solution modulo to the simultaneous congruences
i.e. is another solution if and only if .
Proof.
[Existence.] Since , by Bézout’s theorem, there exist such that .
Note that
Hence
[Uniqueness.] Suppose is another solution. i.e.
Remark. The Chinese remainder theorem can be generalised to more than two moduli by induction.
If are pairwise coprime, then the simultaneous congruences
has a unique solution modulo .
4.7 Prime Modular Arithmetic
Let be a natural number.
We denote by the number of integers with such that . That is, is counting the number of units modulo .
is called the Euler totient function.
-
-
When is prime, , and .
-
When are distinct primes, we have , where we are counting the numbers not divisible by either or .
We shall now consider the behaviour of an integer power modulo .
-
Consider modulo : , , , , and so on. We see that the powers of modulo are periodic with period .
-
Consider modulo : , , , , , , , , , , , and so on. We see that the powers of modulo are periodic with period .
Proof. If , then is a unit modulo . Thus iff by cancelling .
Hence the numbers are pairwise incongruent (distinct) modulo , and they are not congruent to modulo either. Therefore, they must be congruent to in some order modulo . Hence
Equivalently,
Since is a unit [it is a prouct of units], we can cancel it to get .
We can generalise this to non-prime moduli.
Proof. Let be the set of units modulo . Note that . Label them . Then are all distinct and invertible modulo [since is a unit], and hence they are up to reordering. Thus,
Equivalently,
Since are all units modulo , so is their product [it is a product of units]. Thus, we can cancel it to get .
Consider modulo for a prime .
When , we have .
When , we have .
Proof.
Proof. As an edge case, this is true for . Let us assume from now on.
Note that the units modulo become in pairs where each pair multiplies to modulo , together with some elements that are self-inverse, i.e. such that .
By Lemma 4.34, the only self-inverse elements are and . Thus the remaining units of come in inverse pairs. Hence,
We may wonder if is a square modulo for some prime .
When , we have .
When , there is no integer such that .
When , we have .
When , there is no integer such that .
Proof.
[] Suppose . By Wilson’s theorem, we have
Since , for some , so is even. Thus, . Hence, is a square modulo .
[] We shall prove by contradiction on the contrapositive. Suppose on the other hand that . [Note that for odd , and this is the only other choice other than .] If were a square modulo , i.e. if there were such that , then by Fermat’s little theorem (Theorem 4.31), we would have
4.8 Public Key Cryptography
When , Fermat’s little theorem (Theorem 4.31) can be read as
Another way is to state that if , then there is a good chance that is prime. If not, then is called a pseudoprime.
Let us agree to write messages as sequences of numbers, say , , …, , , , , and so on. One (say, ) want to send secure messages in an encrypted form in such a way that the intended recipient can decrypt them easily, but an eavesdropper cannot.
We are going to use the RSA (Rivest-Shamir-Adleman) algorithm, which is based on modular arithmetic.
-
To set up the encryption scheme,
-
thinks of two very large primes and .
-
lets and computes the encoding exponent which is coprime to the Euler totient .
-
makes public (this is the public key or encryption scheme).
-
-
To send an encrypted message,
-
slices the messages into blocks of numbers less than .
-
encodes each block as (the ciphertext). This can be computed efficiently using repeated squaring.
-
sends the ciphertext to .
-
-
To decrypt the message,
-
computes the decoding exponent such that (this can be done using the Euclidean algorithm). This step requires knowledge of , which in turn requires knowledge of and for computation within reasonable time.
-
computes for some . By Fermat-Euler theorem (Theorem 4.32), we have since if . Thus, .
-
Remark. Finding without knowing and is equivalent to factoring into and , which is believed to be hard for classical computers on large . This is what makes RSA secure.
It is unknown whether there are efficient algorithms for factoring large integers on quantum computers. If such algorithms exist, they would compromise the security of RSA.
5 The Reals
5.1 Construction of
Recall the construction of using Peano’s axioms in Axiom 3.1. We obtain from by allowing for subtraction. Formally, is the equivalence classes of under the equivalence relation
We can now think of as .
Write 0 for , for and define addition and multiplication on by
The rules of arithmetic can be verified for .
We obtain from by allowing for division. Formally, is the equivalence classes of under the equivalence relation
We write for . We can define on by
We can also define an order on , which has the property that
-
If , then only one of the following holds: , , .
-
If and then .
The ordering on has the useful property that between any 2 rational numbers there is another rational number: if and , then .
Nonetheless, there are gaps in .
Proof. Suppose , and WLOG assume that . If is rational, then we can write for some . Then , so .
But the exponent of 2 in the prime factorisation of is even, while that in is odd, contradicting the fundamental theorem of arithmetic.
Now we shall see an alternative proof.
Proof. Suppose for some with . Then for any , is of the form for some .
Thus if , then . But we have as , so if is sufficiently large,
But for any , is of the form [we replace all even powers of by ], for some . Thus .
So clearly has gaps. We shall express this fact making reference only to , in order to motivate the construction of .
Let be the set of positive rationals such that . We will show that contains no largest number. For any , consider . Then , and by definition , so . Also,
Thus , so has no largest number. Similarly the set has no smallest number.
The real numbers, , are a set with elements and where , equipped with operations and , and an ordering satisfying the following axioms:
-
is commutative and associative with identity , and every has an inverse under .
-
is commutative and associative with identity , and every has an inverse under .
-
is distributive over .
-
, exactly one of the following holds: , , , and , if and then .
-
, if then , and if and then .
-
Given any set of reals that is non-empty and bounded above, there exists a least upper bound of in . [This is the least upper bound axiom.]
Remark.
-
In Definition 5.2, from (1-5) we can check for example that , indeed, if not then , so
so .
-
We may consider as contained in by identifying with .
-
does not satisfy (6), e.g. as shown above.
-
In (6), it is crucial that is non-empty and bounded above. If is empty, then every is an upper bound of , so there is no least upper bound. If is not bounded above, then there is no upper bound, hence no least upper bound.
-
Consider the set .
is an upper bound for , since .
is not an upper bound for , since and .
The LUB is because:
-
is an upper bound of .
-
Every other upper bound of satisfies since .
-
-
Consider the set .
is an upper bound for .
is not an upper bound for .
We have because
-
is an upper bound of .
-
We claim that there is no upper bound such that :
Certainly . So if , then , and with , contradicting the fact that is an upper bound of .
-
Important. If has a greatest element, then .
However, it is not necessary that .
-
Consider .
It is clear that is an upper bound of . We wish to show that .
Corollary 5.7 immediately implies that
Proposition 5.6 and Corollary 5.7 imply that there are no infinitely large or infinitely small real numbers.
Proof. Let . We have is non-empty (since ) and bounded above (since is an upper bound of ). Let , and identify that . We claim that .
Suppose . For , we have
provided we pick a sufficiently small (e.g. ). Thus , contradicting the fact that is an upper bound of .
Suppose . For , we have
provided we pick a sufficiently small (e.g. ). Thus and it is an upper bound, contradicting the fact that .
are all irrational numbers.
We can also construct irrationals from linear combinations of rationals and irrationals, such as . Indeed, if with , then , contradicting the fact that is irrational.
Proof. WLOG assume that . By Corollary 5.7, there exists some such that .
Consider the set . By Axiom of Archimedes 5.6, such that , hence and .
By the Well-ordering Principle 3.6, has a least element, say . Let . Since , we have .
Suppose . Then .
Hence , and as required.
Note that the irrationals is also dense in . Indeed, if we take a non-zero rational with , then is irrational and satisfies .
5.2 Sequences
Sequence limits are important in analysis, and we shall define them rigorously. For a sequence to tend to a limit , it is not enough to show that the terms get closer to .
For example, we would not want to tend to .
And it is also not enough that the terms get arbitrarily close to , in the sense that
For example, we would not want to tend to .
Therefore, we want the sequence to get and stay within of after some point.
We say that the sequence tends to the limit as tends to , if
where the absolute value for is defined by
We think of as the distance between and on our number line. We can also check that the triangle inequality holds:
Remark. We will typically apply the triangle inequality using the the following technique:
-
, i.e. tends to as tends to .
Given , choose (using Axiom of Archimedes 5.6). Then if ,
Hence as .
-
defined by
Given , pick . If , then
Hence as .
-
defined by tends to as tends to .
Let us consider which to choose for a given . We want
so choosing suffices.
Hence as .
-
defined by .
If does not tend to , we write . This means
We claim that . Indeed let , and observe that for any , for all .
In fact, does not converge to any limit . Suppose as for some , let . Then such that , . In particular,
But we also have
which is a contradiction.
Hence diverges. [Divergence does not always mean that the terms tend to or .]
Proof. Suppose and as with . Choose . Then
But then for any ,
which is a contradiction.
Proof. If as , then such that , .
Hence for all .
A sequence is monotonic if it is either increasing or decreasing. That is,
- monotonic increasing: ,
- monotonic decreasing: ,
Proof. Suppose is monotonic increasing and bounded. Then the set is non-empty and bounded above. By the least upper bound axiom, let .
Given , cannot be an upper bound of , so there exists some such that . Then for any ,
since the sequence is increasing. Thus for all , so as .
The case where is monotonic decreasing is similar.
Remark.
-
Note that for an increasing sequence to converge, we only need to know that it is bounded above.
-
Boundedness is necessary: consider . This sequence is increasing, unbounded and does not converge.
-
The monotonic convergence theorem is equivalent to the least upper bound axiom.
-
We can show that every sequence has a monotonic subsequence.
Proof. Suppose . Let . Then such that , . But then for any such ,
contradicting the fact that for all .
Proof. Given , then
Choose , then for any ,
Hence as .
5.3 Series
In the reals, the sum of two numbers is defined, so by induction we can define the sum of finitely many numbers. However, we cannot directly define the sum of infinitely many numbers.
Let be a sequence in . Then
is the th partial sum of the series whose th term is . We write
if the limit exists.
-
The series whose th term is for some is called the geometric series:
Hence for .
-
The series whose th term is is known as the harmonic series:
In general,
Hence
So the partial sums are increasing and unbounded, hence diverges.
-
The series whose th term is :
In general,
Hence
So the partial sums are increasing and bounded above, hence by Monotonic Convergence Theorem 5.23, converges.
In fact, .
5.4 Decimal Expansions
Let be a sequence where each . Then converges to some limit with , since te partial sums are increasing and bounded above by
We say that has decimal expansion . We shall consider whether every with have a decimal expansion.
We can pick to be maximal such that .
Then because and by maximality of .
Then, pick to be maximal such that , and we have by maximality of .
Inductively, we can pick to be maximal such that
so that
Since as , we have
Thus
Remark.
-
Decimal expansions are not unique: for example, .
We show that this happens if and only if the decimal expansion ends in an infinite string of s.
Suppose with and not all equal, then suppose for all for some , and WLOG assume .
Then
We must have , for that if , then .
Also, for all , we have and .
-
A decimal expansion if periodic if, after a finite number of terms, it repeats in blocks, of length say. i.e. such that , .
A periodic decimal is rational, e.g.
Then we have
So .
Conversely, if , then it has a periodic decimal expansion. To see that, we write where with , and . Then
where and .
By Fermat-Euler Theorem 4.32, since , we have
Hence
Since , and has at most digits (by Fermat-Euler), we can write as a -digit number .
Thus and so has a periodic decimal expansion.
5.5 Euler’s Number
We define
By Monotonic Convergence Theorem 5.23, the series converges, since the partial sums are increasing and bounded above by .
If we define , then .
Proof. Suppose were rational, i.e. where and (since ).
But
where
and in general,
So . Thus , contradicting the fact that .
Hence is irrational.
Recall the definitions of Algebraic Numbers 1.3 and Transcendental Numbers 1.4.
-
Every rational number is algebraic, since if , then .
-
is algebraic, since it satisfies .
Proof. We will need two facts about polynomials:
Fact A. For any polynomial , there exists some such that
Indeed, suppose . Then
So
Fact B. A non-zero polynomial of degree has at most real roots.
Write , so that .
Suppose that there is a polynomial of which . Note .
Then by Fact A, there exists some such that
Note
Suppose has degree , i.e.
with .
Notice that for some . So
By Fact B, for at most values of . So for sufficiently large , we have . Hence
Therefore,
This is a contradiction for sufficiently large , since grows faster than .
Remark.
-
Such are called Liouville numbers.
-
This proof does not show that is transcendental, but nonetheless it is known that is transcendental.
-
The same proof shows that any real number that satisfies
is transcendental.
In loose terms, if has a very good rational approximation, then it is transcendental.
5.6 Brief Introduction to Complex Numbers
Some polynomials have no real roots, e.g. . We will define , a complex number, satisfying this equation.
The complex numbers consists of together with operations and defined by
We can view as contained in ny identifying with .
Note that and similarly . We define . Then , so .
Note that is of the form with .
Indeed, .
Remark.
-
obeys all the usual rules of arithmetic. In particualr, if , then there exists some such that .
Indeed, ,given , note that
So
-
Every non-constant polynomial (allowing complex coefficients) has a complex root. This is known as the Fundamental Theorem of Algebra.
6 Countability
We will now discuss the sizes of infinite sets.
We say that a set is countable if is finite or there is a bijection from to .
If is infinite and countable, we say that is countably infinite.
This is to say that is countable if and only if we can list the elements of as
which may or may not terminate.
-
Any finite set is countable by definition.
-
is countable.
-
is countable. We can list the integers as
so we can define a bijection from to by
Proof. If is non-empty, by Well-Ordering Principle 3.6 there is a least element . Remove from and repeat the process to get . This process either terminates (if is finite) or continues indefinitely (if is infinite).
If at some point the process terminates, then we have listed all elements of and so is finite and hence countable.
If the process continues indefinitely, then the map
is well-defined and injective. It is also surjective because if , then and there are less than elements of less than (by construction of the natural numbers), so for some . Thus is a bijection and so is countably infinite.
The following statements are equivalent for a set :
- is countable
- There is an injection
- There is a surjection , or
Proof.
[] Suppose that there is an injection . Then is a bijection from to . By the previous lemma, is countable, so is countable.
[] This is clear if . If is countably infinite, then there is a bijection . The inverse is then a surjection.
[] Suppose and there is a surjection . We can define an injection as follows: for each , let
This is well-defined since is surjective. To see that is injective, suppose that for some . Then by definition of , we have
so . Thus is an injection.
We may thus view countable as saying that a set is at most as big as .
Proof 1. We can list the elements of as follows:
which corresponds to the diagonals in the grid of pairs. This gives a surjection from to , so is countable.
More precisely, define and inductively. For , given , then writing
gives a well-defined sequence which lists all elements of . The map defined by is then a surjection.
Proof 2. From Theorem 6.4, it suffices to construct an injection . Define
To see that is injective, suppose that . Then by the Fundamental Theorem of Arithmetic 4.14, we must have and . Thus is an injection.
Proof. Since is countable, there is an injection . Then the map
where is the injection from Theorem 6.6, is an injection. Thus is countable.
Proof. We me assume that our countable sets are indexed by . Given countable sets , we wish to show that is countable.
For each , since is countable, we can list its elements as
Define by
Note that we need to take the least such that is in to ensure that is well-defined. [This is possible since if is in multiple s, we can just take the least such index.] This is an injection by the same reasoning as in Proof 2 of Theorem 6.6. Thus is countable.
Proof. It suffices to show that the set of all polynomials with integer coefficients is countable, since then is a countable union of finite sets.
In fact, it suffices to show that for each , the set of all polynomials of degree with integer coefficients is countable. This is by Theorem 6.8.
But the map defined by
is an injection. Since is countable, and hence are countable.
Proof. If were countable, we would be able to list all the reals as .
Write each in decimal form in some way
Define by , if , and , if . This has only one decimal representation, and is not on the list, since it differs from each at the -th decimal place.
Thus is uncountable.
This is known as Cantor’s diagonal argument. Note that this shows that is uncountable, and hence any interval in is uncountable.
Note that this is a variant of Cantor’s diagonal argument.
Proof 2. Note that there is an injection from into : write in binary decimal expansion as
with . [Assume that we do not end with an infinite string of s.] Then define by
This is an injection. Since is uncountable by Theorem 6.12, is uncountable by Theorem 6.4.
In fact, Proof 1 shows the following:
Proof. Given any map ,we will show that is not surjective.
Indeed, let . Then but does not belong to the image of , since , the sets and differ in the element , so for all .
Remark.
-
This is reminiscent of Russell’s paradox.
-
This gives another proof that there is no universal set. For suppose there were a universal set . Then , in which case we would have a surjection , contradicting the above theorem.
Let be a family of open pairwise disjoint intervals in . We shall consider whether this family must be countable.
Proof 2. The set is countable, because each such interval contains at least one integer, and the integers are countable.
Similarly, the set is countable as it injects into the set of half-integers, which is countable.
More generally, for each , the set is countable as it injects into the set of integer multiples of , which is countable.
Thus is a countable union of countable sets, and hence countable by Theorem 6.8.
Summary. To show that a set is countable, we can do one of the following:
- list its elements
- inject it into
- use Countable Union of Countable Sets is Countable 6.8
- if is near , consider
To show that a set is uncountable, we can do one of the following:
- use a diagonal argument
- inject any uncountable set into
Intuitively, we think of
- “ bijects with “ as “ and are of the same size”,
- “ injects into “ as “ is at most as big as “,
- “ surjects onto “ as “ is at least as big as “.
For these interpretations to make sense, we need to establish, if “ is at most as big as “, then “ is at least as big as “, etc.
Given non-empty sets and .
Proof.
[] Suppose is injective. Fix . Define by
Then is a surjection.
[] Suppose is a surjection. For each , pick any (this is possible since is surjective). Define by
Then is an injection.
We also need that, if “ is at most as big as “ and “ is at most as big as “, then “ and are of the same size”.
Given sets and .
Proof. For , write for the (if it exists) such that .
Similarly, for , write for the (if it exists) such that .
We call the (possibly finite) ancestor sequence of .
Similarly, define the ancestor sequence of .
Let
and similarly for .
Note that bijects with [observing that every has at least one anscestor, so is equal to for some ]. Similarly, bijects with . Also, (or ) bijects with .
Then the function defined by
is a bijection.
Consider whether there is bijection from to .
Observe that there is an injection from to given by the inclusion map, and there is an injection from to given by
Thus, by Schröder-Bernstein Theorem 6.18, there is a bijection from to .
Remark.
-
It seems natural to say that for any two sets and , either injects into , or injects into . This is true but its proof is beyond the scope of this course.
-
Continuum Hypothesis. a set whose size lies between and . i.e. any subset of is either countable or bijects with .