Skip to main content

Posts

Showing posts from July, 2024

Calkin-Wilf Tree

I gave this talk at CMI STEMS final camp 2024. Definitions Before proceeding, we must be clear about what our title means. What do you mean by Counting? What do we mean by the term counting? We are going to prove that Rational numbers are countable . That is, there is a bijection between natural numbers and rational numbers. A bijective function $f:X\rightarrow Y$ is a one-to-one (injective) and onto (surjective) mapping of a set $X$ to a set $Y$. Note that every bijection from set $X$ to a set $Y$ also has an inverse function from set $Y$ to set $X$. But how are we going to create the bijection? We will first create a bijection between the Natural numbers and Positive rationals. Let $f(1),f(2),\dots $ be the mapping from natural numbers from $\Bbb{N}\rightarrow +\Bbb{Q}$. Then, note that there is also a bijection from $\Bbb{N}\rightarrow -\Bbb{Q}$ by simply mapping $i\in \Bbb{N}\rightarrow -f(i)$. And to create the bijection from $g:\Bbb{N} \rightarrow \Bbb{Q}$, c