Prove by induction that the function is injective

In summary, the conversation discusses the proof that the set of real numbers is not countable. This is shown by defining a function that maps elements in the set of infinite binary sequences to real numbers. The function is proven to be injective and a contradiction is reached by assuming that the set of real numbers is countable.
  • #1
evinda
Gold Member
MHB
3,836
0
Hi! (Wave)

The set $\mathbb{R}$ of real numbers is not countable.

Proof:

We define the function $F: \{0,1\}^{\omega} \to \mathbb{R}$ with the formula:

$$(a_n)_{n \in \omega} \in \{0,1\}^{\omega} \mapsto F((a_n)_{n \in \omega})=\sum_{n=0}^{\infty} \frac{2a_n}{3^{n+1}}$$

Show that $F$ is 1-1 and thus if $\mathbb{R}$ is countable then the set $\{0,1\}^{\omega}$ would also be, that is a contradiction.So we pick $(a_n)_{n \in \omega}, (b_n)_{n \in \omega} \in \{0,1\}^{\omega}$ with $F((a_n)_{n \in \omega})=F((b_n)_{n \in \omega}) \Rightarrow \sum_{n=0}^{\infty} \frac{2a_n}{3^{n+1}}=\sum_{n=0}^{\infty} \frac{2b_n}{3^{n+1}}$We will show that it holds using induction.At the base case, we assume that $a_0 \neq b_0$, let $a_0=0, b_0=1$.
So we have $\sum_{n=1}^{\infty} \frac{2a_n}{3^{n+1}}=\frac{2}{3}+\sum_{n=1}^{\infty} \frac{2b_n}{3^{n+1}}$

How could we find a contradiction? (Thinking)
 
Physics news on Phys.org
  • #2
Here's a proof that your function is injective:

syxyr9.png
 
  • #3
johng said:
Here's a proof that your function is injective:

I see.. (Nod)
Like that we have shown that the function $F: \{ 0,1 \}^{\omega} \to \mathbb{R}$ with the formula $(a_n)_{n \in \omega} \in \{0,1\}^{\omega} \mapsto F((a_n)_{n \in \omega})=\sum_{n=0}^{\infty} \frac{2a_n}{3^{n+1}}$ is injective.
Now we suppose that $\mathbb{R}$ is countable. That means that there is an injective function $g: \mathbb{R} \to \omega$.
Since $F: \{ 0,1 \}^{\omega} \to \mathbb{R}$ is injective, do we deduce that $g \circ F: \{0,1\}^{\omega} \to \omega$ is injective, that is a contradiction since then that would mean that $\{0,1\}^{\omega}$ is countable, i.e. that $\{0,1\}^{\omega} \sim \omega$ ? (Thinking)
 

FAQ: Prove by induction that the function is injective

What is the definition of an injective function?

An injective function is a function where each input has a unique output. This means that for every input, there is only one corresponding output.

How is induction used to prove that a function is injective?

Induction is a mathematical proof technique that is used to show that a statement holds for all natural numbers. In order to prove that a function is injective, we use mathematical induction to show that the function holds for all natural numbers.

What is the basis step in an inductive proof?

The basis step is the first step in an inductive proof where we show that the statement holds for the smallest natural number, usually 0 or 1.

What is the inductive hypothesis in a proof of injectivity by induction?

The inductive hypothesis is the assumption that the statement holds for a particular natural number, n. In order to prove that the statement holds for n+1, we use the inductive hypothesis to show that it also holds for n+1.

Why is it important to prove that a function is injective?

It is important to prove that a function is injective because it guarantees that each input has a unique output, which is necessary for certain mathematical operations and functions to work correctly. It also ensures that the function can be reversed or inverted, which is useful in many applications.

Similar threads

Back
Top