3
$\begingroup$

There are only countably many things you can express with a finite number of words. This implies that any uncountable set has to contain uncountably many elements which you cannot define by any finite means. Each of those elements must have an infinite definition that you cannot compress to something finite.

Note that this is not just about countability of computable numbers. Even the most exotic numbers we can think of (e.g. Chaitin's constant) are countable because their definition is finite.

Is this reasoning correct?

$\endgroup$
10
  • $\begingroup$ Are you saying that the real numbers don't exist? $\endgroup$
    – John Douma
    Commented Sep 1, 2022 at 23:41
  • $\begingroup$ @JohnDouma, heh, well, mostly they admit no description. :) $\endgroup$
    – paul garrett
    Commented Sep 1, 2022 at 23:42
  • 3
    $\begingroup$ One issue with this is with the word "description"/"definition". What counts as a valid definition of a number? Consider the following: "The smallest integer not definable in under a million words." Is that a valid definition? If not, what goes wrong? $\endgroup$
    – Akiva Weinberger
    Commented Sep 2, 2022 at 0:01
  • 3
    $\begingroup$ Someone smarter than me wrote this: mathoverflow.net/questions/44102/… $\endgroup$
    – Akiva Weinberger
    Commented Sep 2, 2022 at 21:23
  • 1
    $\begingroup$ Also related: karagila.org/2015/name-that-number $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 3, 2022 at 19:20

1 Answer 1

Reset to default
4
$\begingroup$

One issue with this is with the word "description"/"definition". What counts as a valid definition of a number? Consider the following: "The smallest positive integer not definable in under a million words." Is that a valid definition? If not, what goes wrong?

Suppose we run Cantor's argument on the definable reals, as follows. List all valid definitions of reals in order of length (use alphabetical order for definitions of the same length). Consider the real whose Nth digit is a 0 if the Nth digit of the Nth definable real is 1, and a 1 otherwise. Is this definable? Have I just defined it? (The issue with this is precisely the same as in my previous comment.) For more, look up the Berry paradox and Richard's paradox…

as well as Wikipedia's page on definable numbers.

Short resolution is: while we can define increasingly strong notions of definability, there is no ultimate notion of definability. If you hand me a definition system, I can create a stronger one that can define more numbers. If $D$ is a definition system, then the phrase "The smallest integer not definable in $D$ under a million words" is not a definition in $D$, but perhaps is a valid definition in a larger system $D'$. Each definition system on its own can only define countably many numbers, though.

$\endgroup$
4
  • 1
    $\begingroup$ "The concept 'computable' is in a certain definite sense 'absolute', while practically all other familiar metamathematical concepts (e.g. provable, definable, etc.) depend quite essentially on the system to which they are defined." - Gödel $\endgroup$
    – Akiva Weinberger
    Commented Sep 2, 2022 at 1:50
  • $\begingroup$ But the set of definition systems should be countable, too. So even the set of all numbers you can define within any definition system should be countable, no? $\endgroup$
    – RobinLinus
    Commented Sep 2, 2022 at 10:46
  • 1
    $\begingroup$ @RobinLinus I'm curious how you justify the set of definition systems being countable. $\endgroup$
    – Akiva Weinberger
    Commented Sep 2, 2022 at 20:54
  • $\begingroup$ The set of anything you can somehow express with a finite number of symbols is countable. So the set of finite definition systems must be countable too. Assuming (incompressible) infinite definition systems just repeats the original question. $\endgroup$
    – RobinLinus
    Commented Sep 4, 2022 at 19:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .