[Notes](#fn1): Problem Class, 19 Oct 2020

# [Notes](#fn1): Problem Class, 19 Oct 2020 > Group 11 -- Problem Class, MATH40001/40009 IUM > Stergios M. Antonakoudis (stergios@imperial.ac.uk) Welcome to IUM Problem Class Group 11. \ Today's class: **Problem Sheet 1 of Part II.** [^1]: *These notes[^1] are typed up and created during and for the purposes of the discussion in the online session of Problem Class Group 11 for IUM on MS Teams, similarly to the use of a 'whiteboard' in an actual class.* --- ## A brief overview: ==natural numbers== * $\mathbb{N} = \{0,1,2,3, \ldots\}$ denotes the set of natural numbers. * We use the ==**Peano Axioms**== to formally define $\mathbb{N}$. > "[...] it is best to force yourself to assume nothing and use only statements that are known to be true via axioms or statements that follow from these axioms." -- Lecture notes, IUM --- ## Peano Axioms ### Idea > "The idea of Peano was to formalize natural numbers starting with ==a set containing a distinguished element called zero==, together with ==a successor function $\nu$== of the set into itself *generating all other natural numbers* everyone is familiar with." -- Lecture notes, IUM ### Axioms The natural numbers $\mathbb{N} are a set with the following properties * (P1) There exists a distinguished element $0\in \mathbb{N}$. * (P2) There exists a map $\nu : \mathbb{N} \rightarrow \mathbb{N}$ called the successor map. * (P3) There exists no element $n$ such that $\nu(n)=0$. * (P4) The map $\nu$ is injective, *i.e. for all $n_1,n_2 \in \mathbb{N}$ if $n_1\neq n_2$, then $\nu(n_1)\neq \nu (n_2)$.* * (P5) ==Let $A \subset \mathbb{N}$, such that $0 \in A$ and $\forall n \in A,\; \nu(n)\in A$, then $A=\mathbb{N}$.== > (P5) is the *Principle of mathematical induction*. --- ## Questions --- ## Problems to discuss: ==1, 2, 3, 4, 5== --- ### ==Problem 5== Show that there is a unique function $R: \mathbb{N} \rightarrow \mathbb{N}$ such that $R(0)=n_0$, for given $n_0 \in \mathbb{N}$ and $\forall n \in \mathbb{N},\; R(\nu(n)) = \nu(R(n))$. ### ==Solution 5== Let $R_1$ and $R_2$ be two such functions; and consider the set $A := \{\; n \in \mathbb{N}\; | \; R_1(n)=R_2(n)\;\}$. * $0 \in A$ because $R_1(0)=R_2(0)=n_0$. * If $n \in A$, then $R_1(n)=R_2(n)$, which implies that $\nu(R_1(n))= \nu(R_2(n))$ and hence $R_1(\nu(n))=R_2(\nu(n))$; therefore, $\nu(n) \in A$. * By (P5), we conclude that $A = \mathbb{N}$. In other words, $R_1=R_2$. **QED** ### ==Problem 4(b)== If $n \in \mathbb{N}$ and $n \neq 0$, then $n= \nu(n')$ for some $n' \in \mathbb{N}$. ### ==Solution 4(b)== Let $A=\{ n \in \mathbb{N}\; | \; n=0 \text{ or } n=\nu(n') \text{ for some } n' \in \mathbb{N}\;\}$. GOAL: Prove that $A = \mathbb{N}$. * $0 \in A$ by construction. * Let $n \in A$, then $\nu(n) \in A$ (again by construction!) Therefore, by (P5) $A=\mathbb{N}$. **QED**