# use diagonalization to prove uncountability

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Sep 24th 2013, 05:18 AM
stribor40
use diagonalization to prove uncountability
I have this problem to solve but I cant get my head wrapped arround it. Most of the tutorials keeps showing example of proving that there is uncountable number of binary functions. I have following problem...
A function from N to N is said to be repeating if f(n) = f(n + 1) for some (n E N).Otherwise, f is said to be nonrepeating. Prove that there are an uncountable number of nonrepeating functions.
Can someone give me some pointers or guide me a little to solve this problem please. I would prefer guidance over the solution becuase i need to know how to solve these kinds of problems using diagonalization.
• Sep 24th 2013, 05:33 AM
emakarov
Re: use diagonalization to prove uncountability
Suppose that there are countably many nonrepeating functions (i.e., sequences). Write them horizontally one under another. Then consider the sequence of numbers on the diagonal and turn it into a sequence that is (1) different from all others written here and (2) nonrepeating.
• Sep 24th 2013, 06:00 AM
stribor40
Re: use diagonalization to prove uncountability
thank you for reply. But what are those non repeating functions??
can you write similar example just to get me going please
• Sep 24th 2013, 06:08 AM
emakarov
Re: use diagonalization to prove uncountability
The definition you gave says that $f(n)$ is repeating if there exists an $n\in\mathbb{N}$ such that $f(n)=f(n+1)$. Correspondingly, $f(n)$ is nonrepeating if $f(n)\ne f(n+1)$ for all $n\in\mathbb{N}$, i.e., the value of $f$ necessarily changes when the argument is increased by 1. Since sequences can be naturally associated with functions from $\mathbb{N}$ to $\mathbb{N}$, we have that

0, 1, 2, 2, 3, 4, 5, 6, ...

is repeating, but

0, 1, 2, 3, 4, 5, 6, 7, ...

is nonrepeating.
• Sep 24th 2013, 07:27 AM
stribor40
Re: use diagonalization to prove uncountability
so if I have something like this....

0, 1, 2, 3, 4, 5, 6, 7, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
2, 3, 4, 5, 6, 7, 8, 9, ...
3, 4, 5, 6, 7, 8, 9, 10 ...

so diagonal is 0,2,4,6....
we pick something that is not 0,2,4,6...

now i have to come up with function that can produce something that is not 0,2,4,6??

Am i close?
• Sep 24th 2013, 07:48 AM
emakarov
Re: use diagonalization to prove uncountability
The sequence you need to come up with should not simply be different from the diagonal (two sequences are different if they differ in at least one position). You need a sequence that differs with the diagonal in every position. Indeed, let's call the functions in the list $f_k(n)$, $k=0,1,\dots$, and let $d(n)=f_n(n)$ be the diagonal. If some $g(n)\ne d(n)=f_n(n)$, then we know that $g\ne f_n$ because $g$ and $f_n$ differ in the $n$th position. You need a $g$ such that $g\ne f_n$ for all $n$, and one way to achieve this is to make $g(n)\ne d(n)$ for all $n$. However, a $g(n)$ like this may be repeating; then nothing has been proved since the list $f_k(n)$ may still contain all nonrepeating functions. Therefore, you need to find a nonrepeating $g$ such that $g(n)\ne d(n)$ for all $n$.
• Sep 24th 2013, 08:30 AM
stribor40
Re: use diagonalization to prove uncountability
yes but how can you know what is going to be in diagonal at nth positions?? how can you assure that every position in diagonal is different?

Suppose that we can count the non-repeating sequences. Something like this:
$\begin{array}{*{20}{c}}{{f_1}}&|&{{x_{1,1}}}&{{x_{ 1,2}}}&{{x_{1,3}}}&{{x_{1,4}}}& \cdots \\{{f_2}}&|&{{x_{2,1}}}&{{x_{2,2}}}&{{x_{2,3}}}&{{ x_{2,4}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}\\{{f_n}}&|&{{x_{n,1}}}&{{x_{n,2}}}& \cdots &{{x_{n,n}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}
\end{array}$

We define a new sequence in which $d_1$ can be any valid term so long as $d_1\ne x_{1,1}$.

Next define $d_2$ so that $d_2\ne x_{2,2}~\&~d_2\ne d_1$.

If $n\ge 3$ define $d_n$ so that $d_n\ne x_{n,n}~\&~d_n\ne d_{{n-1}$.
(we leave aside any issues of enough different terms).

Now the $(d(n))$ sequence is non-repeating so by supposition it was counted among the $f$'s.
BUT it differs from any $f_n$ at $x_{n,n}$ (the diagonal position).
So it cannot be any one of the $f$'s contrary to the assumption that we can count the non-repeating sequences..
• Sep 24th 2013, 08:51 AM
emakarov
Re: use diagonalization to prove uncountability
Quote:

Originally Posted by stribor40
yes but how can you know what is going to be in diagonal at nth positions?? how can you assure that every position in diagonal is different?

Different from what? Please express yourself unambiguously.

Are you asking how to come up with g(n) that is different from a given d(n)? Well, if you give somebody a number 10 and ask them to give you back a different number, they can surely do it. What if you need to teach a computer how to do it (i.e., return a different number)? Are you able to write an algorithm (informally, not using any particular programming language) that returns a number different from the one it is given?

To be honest, I believe every kindergarten student who knows some numbers (he/she does not even have to know how to count) knows how to give a different number. This makes me think that you are asking something different, which brings me to the original question: Different from what?
• Sep 24th 2013, 09:05 AM
stribor40
Re: use diagonalization to prove uncountability
i think i am just confused on how to line up all these functions and numbers in each line
• Sep 24th 2013, 09:38 AM
emakarov
Re: use diagonalization to prove uncountability

0, 1, 2, 3, 4, 5, 6, 7, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
2, 3, 4, 5, 6, 7, 8, 9, ...
3, 4, 5, 6, 7, 8, 9, 10 ...

d is indeed 0, 2, 4, 6, ..., so we can take g(n) to be d(n) + 1, i.e., g is 1, 3, 5, 7, ... This way g is different from $f_0$ because $g(0)=1\ne0=d(0)=f_0(0)$. Similarly, g is different from $f_1$ because $g(1)=3\ne2=d(1)=f_1(1)$. That is, g differs from the 0th sequence in the 0th element, it differs from the 1st sequence in the 1st element and so on. In general, $g(n)\stackrel{\text{def}}{=}d(n)+1\ne d(n)=f_n(n)$, so g differs from $f_n$ in the nth element. There are as many places where g can be different from $f_n$'s as there are functions in the list, so g can be different from all of them. This is the key idea of the proof.

So far this is just a proof that the number of integer sequences is uncountable. I agree that diagonal arguments are mind-twisting. (Maybe this is because if we have a family of functions $f_k(n)$, we are used to considering a fixed function $f_k$ at different arguments n or different functions $f_k$ at a fixed argument n. That is, we are used to changing either k or n separately in $f_k(n)$, and we are less used to changing them in a coordinated manner, as in the definition of $d(n)=f_n(n)$.) However, you need to understand it thoroughly before going further.

In your problem, the list contains just the nonrepeating functions. This does not mean that the diagonal is nonrepeating (i.e., there may be two neighbor arguments n and n + 1 where d takes the same values). So, if we define g(n) = d(n) + 1, g may be repeating. The challenge is not only to make g differ from d everywhere, but also make it nonrepeating.
• Sep 24th 2013, 09:44 AM
stribor40
Re: use diagonalization to prove uncountability
ok i will take this example and try to digest it. I appreciate your time and effort in guiding me in this problem
• Sep 24th 2013, 04:45 PM
stribor40
Re: use diagonalization to prove uncountability
i this part i have been looking at it and it makes sense. you are choosing each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one. This all makes sense because when you actually not involving any numbers. Problem becomes when you actually have to produce actual function that satisfy "each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one" requirements..
• Sep 24th 2013, 04:58 PM
Plato
Re: use diagonalization to prove uncountability
Quote:

Originally Posted by stribor40
i this part i have been looking at it and it makes sense. you are choosing each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one. This all makes sense because when you actually not involving any numbers. Problem becomes when you actually have to produce actual function that satisfy "each to be not equal for xi,i and at same time if bigger or equal than 3 it is not same as previous one" requirements..

I have no idea why my post showed up under your name. But here it is again:
yes but how can you know what is going to be in diagonal at nth positions?? how can you assure that every position in diagonal is different?

Suppose that we can count the non-repeating sequences. Something like this:
$\begin{array}{*{20}{c}}{{f_1}}&|&{{x_{1,1}}}&{{x_{ 1,2}}}&{{x_{1,3}}}&{{x_{1,4}}}& \cdots \\{{f_2}}&|&{{x_{2,1}}}&{{x_{2,2}}}&{{x_{2,3}}}&{{ x_{2,4}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}\\{{f_n}}&|&{{x_{n,1}}}&{{x_{n,2}}}& \cdots &{{x_{n,n}}}& \cdots \\ \vdots &|&{}&{}& \vdots &{}&{}
\end{array}$

We define a new sequence in which $d_1$ can be any valid term so long as $d_1\ne x_{1,1}$.

Next define $d_2$ so that $d_2\ne x_{2,2}~\&~d_2\ne d_1$.

If $n\ge 3$ define $d_n$ so that $d_n\ne x_{n,n}~\&~d_n\ne d_{{n-1}$.
(we leave aside any issues of enough different terms).

Now the $(d(n))$ sequence is non-repeating so by supposition it was counted among the $f$'s.
BUT it differs from any $f_n$ at $x_{n,n}$ (the diagonal position).
So it cannot be any one of the $f$'s contrary to the assumption that we can count the non-repeating sequences..
• Sep 26th 2013, 08:37 AM
stribor40
Re: use diagonalization to prove uncountability
When you have numbers...

0, 1, 2, 3, 4, 5, 6, 7, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
2, 3, 4, 5, 6, 7, 8, 9, ...
3, 4, 5, 6, 7, 8, 9, 10 ...

How does chosing something different from diagonal (0,2,4,6..) to something 1,5,7,9...ensuring that is different from everything else in the list (regardless of being repeating or non repeating)
• Sep 26th 2013, 08:46 AM
Plato
Re: use diagonalization to prove uncountability
Quote:

Originally Posted by stribor40
When you have numbers...
How does chosing something different from diagonal (0,2,4,6..) to something 1,5,7,9...ensuring that is different from everything else in the list (regardless of being repeating or non repeating)

I have my doubts that you really understand the diagonal argument.