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.

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.

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

Re: use diagonalization to prove uncountability

The definition you gave says that $\displaystyle f(n)$ is repeating if there exists an $\displaystyle n\in\mathbb{N}$ such that $\displaystyle f(n)=f(n+1)$. Correspondingly, $\displaystyle f(n)$ is nonrepeating if $\displaystyle f(n)\ne f(n+1)$ for all $\displaystyle n\in\mathbb{N}$, i.e., the value of $\displaystyle f$ necessarily changes when the argument is increased by 1. Since sequences can be naturally associated with functions from $\displaystyle \mathbb{N}$ to $\displaystyle \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.

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?

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 $\displaystyle f_k(n)$, $\displaystyle k=0,1,\dots$, and let $\displaystyle d(n)=f_n(n)$ be the diagonal. If some $\displaystyle g(n)\ne d(n)=f_n(n)$, then we know that $\displaystyle g\ne f_n$ because $\displaystyle g$ and $\displaystyle f_n$ differ in the $\displaystyle n$th position. You need a $\displaystyle g$ such that $\displaystyle g\ne f_n$ for all $\displaystyle n$, and one way to achieve this is to make $\displaystyle g(n)\ne d(n)$ for all $\displaystyle n$. However, a $\displaystyle g(n)$ like this may be repeating; then nothing has been proved since the list $\displaystyle f_k(n)$ may still contain all nonrepeating functions. Therefore, you need to find a nonrepeating $\displaystyle g$ such that $\displaystyle g(n)\ne d(n)$ for all $\displaystyle n$.

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:

$\displaystyle \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 $\displaystyle d_1$ can be any valid term so long as $\displaystyle d_1\ne x_{1,1}$.

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

If $\displaystyle n\ge 3$ define $\displaystyle d_n$ so that $\displaystyle d_n\ne x_{n,n}~\&~d_n\ne d_{{n-1}$.

(we leave aside any issues of enough different terms).

Now the $\displaystyle (d(n))$ sequence is non-repeating so by supposition it was counted among the $\displaystyle f$'s.

BUT it differs from any $\displaystyle f_n$ at $\displaystyle x_{n,n}$ (the diagonal position).

So it cannot be any one of the $\displaystyle f$'s contrary to the assumption that we can count the non-repeating sequences..

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?

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

Re: use diagonalization to prove uncountability

I assume that natural numbers start with 0. In your example

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 $\displaystyle f_0$ because $\displaystyle g(0)=1\ne0=d(0)=f_0(0)$. Similarly, g is different from $\displaystyle f_1$ because $\displaystyle 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, $\displaystyle g(n)\stackrel{\text{def}}{=}d(n)+1\ne d(n)=f_n(n)$, so g differs from $\displaystyle f_n$ in the nth element. There are as many places where g can be different from $\displaystyle 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 $\displaystyle f_k(n)$, we are used to considering a fixed function $\displaystyle f_k$ at different arguments n or different functions $\displaystyle f_k$ at a fixed argument n. That is, we are used to changing either k or n separately in $\displaystyle f_k(n)$, and we are less used to changing them in a coordinated manner, as in the definition of $\displaystyle 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.

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

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..

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:

$\displaystyle \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 $\displaystyle d_1$ can be any valid term so long as $\displaystyle d_1\ne x_{1,1}$.

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

If $\displaystyle n\ge 3$ define $\displaystyle d_n$ so that $\displaystyle d_n\ne x_{n,n}~\&~d_n\ne d_{{n-1}$.

(we leave aside any issues of enough different terms).

Now the $\displaystyle (d(n))$ sequence is non-repeating so by supposition it was counted among the $\displaystyle f$'s.

BUT it differs from any $\displaystyle f_n$ at $\displaystyle x_{n,n}$ (the diagonal position).

So it cannot be any one of the $\displaystyle f$'s contrary to the assumption that we can count the non-repeating sequences..

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)

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.

Please study that webpage.