Unit 1 - Number and Algebra
Required Prior Knowledge
Questions
Define
a) The natural numbers \(\mathbb{N}\)
b) The integers \(\mathbb{Z}\)
c) The positive integers \(\mathbb{Z}^{+}\)
d) The rational numbers \(\mathbb{Q}\)
e) The real numbers \(\mathbb{R}\)
Solutions
Get Ready
Questions
What is the opposite (negation) of each of the following statements:
a) The wall is taller than 10m
b) The man has 3 children
c) The quadrilateral is a square
d) \(n\) is an integer
e) \(n\) is even
Solutions
Notes
To show that a statement is true, we can show that the negation of the statement (the opposite statement) leads to a logical contradiction and so cannot be true.
This is known as reductio ad absurdum (reduction to absurdity). It is a logical approach to an argument that can be used mathematically in the form of Proof by Contradiction.
Examples and Your Turns
Example
Prove, by contradiction, that the sum of a rational number and an irrational number is irrational.
Your Turn
Prove, by contradiction, that the sum o an integer and a non-integer rational number is a non-integer.
Your Turn
Prove, by contradiction, that the sum of two even numbers is an even number.
Your Turn
Prove, by contradiction, that if \(3a+9b=1\) then not both \(a\) and \(b\) are integers.
Your Turn
Prove that \(\log_{2}3\) is irrational.
Your Turn
Prove by contradiction that if \(n^{3}\) is even then \(n\) is even.
Notes
There are two very famous and very old proofs in Mathematics that rely on proof by contradiction. These date back to the Ancient Greeks, and form a basis for much of modern Mathematics in terms of approach. Euclid’s Elements was a groundbreaking work which set the path of Mathematical proof for the next two millenia.
Examples
Example
Prove that \(\sqrt{2}\) is irrational.
Proof
Suppose that \(\sqrt{2}\) is a rational number.
That is $$\sqrt{2}=\frac{m}{n}\text{, where }m,n\in\mathbb{Z}\text{ and }\operatorname{hcf}\left(m,n\right)=1$$
Therefore$$\begin{align}2&=\left(\frac{m}{n}\right)^{2}=\frac{m^{2}}{n^{2}}\\2n^{2}&=m^{2}\\ &\implies m^{2}\text{ is even}\\ &\implies m\text{ is even}\\ &\implies m=2k\text{ for some }k\in\mathbb{Z}\end{align}$$Hence$$\begin{align}2n^{2}&=\left(2k\right)^{2}\\2n^{2}&=4k^{2}\\n^{2}&=2k^{2}\\ &\implies n^{2}\text{ is even}\\ &\implies n\text{ is even}\end{align}$$Thus both \(m\) and \(n\) are even.
This contradicts \(\operatorname{hcf}\left(m,n\right)=1\).
So, by contradiction, \(\sqrt{2}\) is irrational.
Example
Prove that there are infinitely many prime numbers.
Proof
Suppose there are finitely many prime numbers. This means we can list ALL the prime numbers.
Let \(P=\left\{p_{1},p_{2},p_{3},\dots,p_{n}\right\}\) be the set of ALL prime numbers.
Consider the new number $$m=p_{1}\times p_{2}\times p_{3}\times \dots \times p_{n}+1$$The number \(m\) is not divisible by \(p_{i}\) for any \(i\). That is it is not divisible by any of the primes in \(P\) as it always leaves a remainder of \(1\) when divided by any of these primes.
By the Fundamental Theorem of Arithmetic, every number is either a prime number, or a product of prime numbers.
There are two cases
Case 1
\(m\) is a prime number not contained in \(P\).
This contradicts \(P\) being the set of ALL prime numbers as there is another prime not in the set (namely \(m\)).
Case 2
\(m\) is a product of primes not included in \(P\), since it is not divisible by any primes in \(P\).
This contradicts \(P\) being the set of ALL prime numbers as there is another prime not in the set (namely the prime factors of \(m\)).
Thus, by contradiction, since \(P\) cannot be the list of all prime numbers, there must be infinitely many prime numbers.
Key Facts
Use this applet to generate a prompt for a Key Fact that you need to know for the course. The idea is that you should KNOW these key facts in order to be able to solve problems.