1
$\begingroup$

Coming across diagonalization, I was thinking of other methods to disprove the existence of a bijection between reals and naturals. Can any method that shows that a completely new number is created which is different from any real number in the list disprove the existence of a bijection?

For example, assume we have a full list in some order of real numbers. Take two adjacent numbers and calculate their average, which adds a digit to the end of the number. That number is not on the list. Does this suffice?

$\endgroup$
1
  • 1
    $\begingroup$ Cantor's first proof was not by the now familiar diagonalization. It had the basic structure you mention, producing a "new" real from any supposed listing. $\endgroup$ – André Nicolas Jan 20 '16 at 12:44
2
$\begingroup$

There is no reason why the average should not be on the list. Remember that the rational numbers are countable.

$\endgroup$
2
$\begingroup$

In general, yes. The idea behind diagonalization is to show that given a countable list of real numbers we can find another which is not on that list.

How you do it is practically irrelevant. As long as you can prove the number you obtain is not on the list, that's fine.

The question is, can you prove that? In your method, there's no guarantee that the number is not on the list. The list is infinite and the average is just of two numbers on that list.

$\endgroup$
1
$\begingroup$

Your idea for a falsification is correct, however your method has to show that your new number is not already part of your list.

If you were right with your example, then there would also be no bijection between rational numbers and natural numbers, but there is (which can be proved by diagonalization).

Your example of taking the average of two numbers works also for the rational numbers, the new number is going to be rational again:

$$ \frac{\frac{p_1}{q_1}+\frac{p_2}{q_2}}{2} = {\frac{p_1}{2*q_1}+\frac{p_2}{2*q_2}} = {\frac{p_1}{q_1+q_1}+\frac{p_2}{q_2+q_2}} \tag{1}$$

Since $p$ and $q$ are natural numbers and addition is compatible both for natural and rational numbers the average of two rational numbers is therefore still rational.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.