4 ms·

I wonder if the set of undescribable numbers is well defined at all. It seems to run into the same problem as the "minimum un-interesting number is interesting"

by ketzu 4y ago

I wonder if the set of undescribable numbers is well defined at all. It seems to run into the same problem as the "minimum un-interesting number is interesting" as a function chosing a number from that set would be a finite description of that number, removing it from the set. (This already happens if you could select a finite subset of those numbers, as finite numbers could be ordered and you could just select the minimum.) edit: Hm... thinking about it. The finitely-many-symbols argument also only holds if you consider finitely many interpretations of those symbols and if there actually are only finitely many symbols.

mckeed 4y ago
That's the point though, right? Without Choice, there need be no way to select a number or subset from the set, so there's no paradox.
hilbertseries 4y ago
https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number
- mannerheim 4y ago
  There are uncomputable numbers which can still be defined. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
  - deleted 4y ago
    [deleted]
  - Beldin 4y ago
    See also this Numberphile video on numbers, including algebraic, computable, transcendental, and talking about numbers beyond those. https://m.youtube.com/watch?v=5TkIe60y2GI https://m.youtube.com/watch?v=5TkIe60y2GI
LegionMammal978 4y ago
It's not too mind-boggling: we can describe the set as a whole without any issues, we just can't uniquely describe any particular number in the set. That doesn't stop us from generalizing over all numbers in the set, or even over all numbers in a describable subset, such as "the set of all undescribable primes".
- ketzu 4y ago
  > we can describe the set as a whole without any issues But it does not mean the set is well defined. The description is not necessarily clear an unambigious. It might not be consistent under the generalizations we come up with. > "the set of all undescribable primes" Interesting example, because the set is trivially empty under the assumption that we can describe any finite natural number by writing down its decimal expansion. (Based on that you can either argue that the primes are a subset of the natural numbers or that the primes are countable.) I see no reason to believe that "undescribable" is a well defined property so far.
  - LegionMammal978 4y ago
    > But it does not mean the set is well defined. The description is not necessarily clear an unambigious. It might not be consistent under the generalizations we come up with. Well, obviously such a set must be defined relative to whatever system you're using to describe the numbers. But once you have it, you can simply declare that a number is in your set if and only if there does not exist a finite description in your system of choice. (In other words, you enumerate the countable many finite descriptions in your system, put them in the set, then define the new set as the complement.) How is that ambiguous? > Interesting example, because the set is trivially empty under the assumption that we can describe any finite natural number by writing down its decimal expansion. (Based on that you can either argue that the primes are a subset of the natural numbers or that the primes are countable.) Whoops, you're right, all integers are describable. Perhaps I should amend that to "the set of all undescribable real numbers with a prime integer part", or something along those lines.
    - 4y ago
planede 4y ago
I think the resolution is along the lines of this: * ZFC does not have a unique model that satisfies the axioms. * Each of those models have different "undescribable numbers" with different properties. But it was a long time I touched model theory, and it was just an optional extra course at uni. https://en.wikipedia.org/wiki/Model_theory https://en.wikipedia.org/wiki/Model_theory
resource0x 4y ago
To me, the expression "The set of undescribable numbers" is meaningless. While discussing plausible-sounding, but meaningless, linguistic constructs like this, we descend to the intellectual level of chatGPT. My conjecture is that one can design a prompt to chatGPT such that the output would become a decent PhD thesis with no internal contradictions, but a complete BS otherwise.
librexpr 4y ago
I think if we take "description of a number" to mean "ZF formula that uniquely picks out that number", then that cannot be defined, because a formula picks out a number when it is true for that number and false for all others, but by Tarski[0], the truth predicate cannot be defined inside the logic itself. So "the set of all numbers which cannot be described" cannot be talked about using ZF. However, there is a way around it, by taking as axiom that ZF is consistent, choosing some model M of ZF, and then talking about the set S of numbers inside M that cannot be described. [0] https://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem https://en.wikipedia.org/wiki/Tarski%27s_undefinability_theo...
- actually_a_dog 4y ago
  Bingo. The issue here is that ZF and ZFC are both first order theories. They can only talk about things that can be defined within them, not things that cannot be defined within them. The wiki article talks about that where it says: > Informally, the theorem says that the concept of truth of first-order arithmetic statements cannot be defined by a formula in first-order arithmetic. This implies a major limitation on the scope of "self-representation". It is possible to define a formula True(n){\displaystyle True(n)} whose extension is T∗,{\displaystyle T^{*},} but only by drawing on a metalanguage whose expressive power goes beyond that of L.L. For example, a truth predicate for first-order arithmetic can be defined in second-order arithmetic. However, this formula would only be able to define a truth predicate for formulas in the original language L.L. To define a truth predicate for the metalanguage would require a still higher metametalanguage, and so on.

by ketzu 4y ago

mckeed 4y ago

That's the point though, right? Without Choice, there need be no way to select a number or subset from the set, so there's no paradox.

hilbertseries 4y ago

https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number

mannerheim 4y ago
There are uncomputable numbers which can still be defined. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
- deleted 4y ago
  [deleted]
- Beldin 4y ago
  See also this Numberphile video on numbers, including algebraic, computable, transcendental, and talking about numbers beyond those. https://m.youtube.com/watch?v=5TkIe60y2GI https://m.youtube.com/watch?v=5TkIe60y2GI

LegionMammal978 4y ago

It's not too mind-boggling: we can describe the set as a whole without any issues, we just can't uniquely describe any particular number in the set. That doesn't stop us from generalizing over all numbers in the set, or even over all numbers in a describable subset, such as "the set of all undescribable primes".

ketzu 4y ago
> we can describe the set as a whole without any issues But it does not mean the set is well defined. The description is not necessarily clear an unambigious. It might not be consistent under the generalizations we come up with. > "the set of all undescribable primes" Interesting example, because the set is trivially empty under the assumption that we can describe any finite natural number by writing down its decimal expansion. (Based on that you can either argue that the primes are a subset of the natural numbers or that the primes are countable.) I see no reason to believe that "undescribable" is a well defined property so far.
- LegionMammal978 4y ago
  > But it does not mean the set is well defined. The description is not necessarily clear an unambigious. It might not be consistent under the generalizations we come up with. Well, obviously such a set must be defined relative to whatever system you're using to describe the numbers. But once you have it, you can simply declare that a number is in your set if and only if there does not exist a finite description in your system of choice. (In other words, you enumerate the countable many finite descriptions in your system, put them in the set, then define the new set as the complement.) How is that ambiguous? > Interesting example, because the set is trivially empty under the assumption that we can describe any finite natural number by writing down its decimal expansion. (Based on that you can either argue that the primes are a subset of the natural numbers or that the primes are countable.) Whoops, you're right, all integers are describable. Perhaps I should amend that to "the set of all undescribable real numbers with a prime integer part", or something along those lines.
  - 4y ago

planede 4y ago

I think the resolution is along the lines of this: * ZFC does not have a unique model that satisfies the axioms. * Each of those models have different "undescribable numbers" with different properties. But it was a long time I touched model theory, and it was just an optional extra course at uni. https://en.wikipedia.org/wiki/Model_theory https://en.wikipedia.org/wiki/Model_theory

resource0x 4y ago

To me, the expression "The set of undescribable numbers" is meaningless. While discussing plausible-sounding, but meaningless, linguistic constructs like this, we descend to the intellectual level of chatGPT. My conjecture is that one can design a prompt to chatGPT such that the output would become a decent PhD thesis with no internal contradictions, but a complete BS otherwise.

librexpr 4y ago

I think if we take "description of a number" to mean "ZF formula that uniquely picks out that number", then that cannot be defined, because a formula picks out a number when it is true for that number and false for all others, but by Tarski[0], the truth predicate cannot be defined inside the logic itself. So "the set of all numbers which cannot be described" cannot be talked about using ZF. However, there is a way around it, by taking as axiom that ZF is consistent, choosing some model M of ZF, and then talking about the set S of numbers inside M that cannot be described. [0] https://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem https://en.wikipedia.org/wiki/Tarski%27s_undefinability_theo...

actually_a_dog 4y ago
Bingo. The issue here is that ZF and ZFC are both first order theories. They can only talk about things that can be defined within them, not things that cannot be defined within them. The wiki article talks about that where it says: > Informally, the theorem says that the concept of truth of first-order arithmetic statements cannot be defined by a formula in first-order arithmetic. This implies a major limitation on the scope of "self-representation". It is possible to define a formula True(n){\displaystyle True(n)} whose extension is T∗,{\displaystyle T^{*},} but only by drawing on a metalanguage whose expressive power goes beyond that of L.L. For example, a truth predicate for first-order arithmetic can be defined in second-order arithmetic. However, this formula would only be able to define a truth predicate for formulas in the original language L.L. To define a truth predicate for the metalanguage would require a still higher metametalanguage, and so on.