[cyborgx7]

An interesting thing about the quote you highlighted is that it's already true about the set of real numbers itself. The set of real numbers that can be precisely, individually identified is a countable subset of all real numbers. That means the vast majority of real numbers, an uncountable amount of them, can not be individually defined and thought about.

[dwohnitmok]

This is subtle and a simple counting argument (definable means satisfies a finite formula, there are only countably many finite formulas, there are uncountably many reals, therefore there must be undefinable reals) doesn't work, because "definable in ZFC" is not something that is formalizable in ZFC and so the usual set-theoretic counting arguments don't work.

So it is in fact possible and consistent with ZFC that all reals are definable.

See: https://mathoverflow.net/questions/44102/is-the-analysis-as-...

[bubblyworld]

Thanks, that's a wonderful link and a nice puzzle to think about. The best intuition I have for it is that since the predicate "isDefinableReal(x)" is not itself definable in first-order set theory, there is no way to construct the set of all definable reals in the first place. Thus saying it's countable is basically meaningless - what, exactly, is countable?

[drdeca]

If you use ZFC+Consistent(ZFC) as your meta-theory, and within it consider a model of ZFC, then surely one can consider the set (in the meta theory) of sentences which pick out a unique real number in the model, and then the set of real numbers in the model which are picked out by some sentence? It might not be a set that belongs to the model, but it’s a set in the meta-theory, right?

And, I imagine that the set of real numbers of the meta theory could be (in the meta theory) the same set as the set of real numbers in the model?

[bubblyworld]

You can do this, but things get strange in the meta-theory. Some models of ZFC are countable according to the meta-theory! And some of them have models of the reals that are countable according to the meta-theory. There's no contradiction here, because what the meta-theory thinks "countable" means has nothing to do with what the inner model thinks "countable" means.

(for an extreme example of this, by the Löwenheim–Skolem theorem there are countable models of ZFC)

So you can do what you are suggesting, and you will of course get a countable set of reals (or what are reals according to the inner model), but they might not be countable according to the inner model. They might not even be a set according to the inner model, and there are even inner models that think you've got all of the reals!

(see https://mathoverflow.net/questions/351659/set-of-definable-r... pretty heavy reading)

So the statement "the set of definable reals is countable" is nonsense - you're talking about things that live in different universes of meaning.

[drdeca]

I think there should be models of ZFC in which the set of reals of the model is, in the meta-theory, the same object as the set of reals of the meta-theory.

And I think by virtue of this, the statement should have meaning.

As like, a statement in the meta-language that models of ZFC which have as their sets of reals, the (according to the meta-theory) set of reals, that the set of reals definable within ZFC, is a countable set of the meta-theory.

Also, did someone downvote your comment?? I don’t know why if so. It seems a productive comment to me.

[bubblyworld]

They can have the same set of reals (by construction, for instance) but they won't behave the same way as sets (the membership relation will be different). I think you need to be very clear about what you are doing here.

By definition an inner model consists of some domain (a set of sets) and some choice of mappings from all the function/relation symbols of ZFC to functions/relations on this domain, satisfying the axioms of ZFC.

You are suggesting to enumerate every formula of ZFC, evaluate them against this inner model, and take the set of all reals that are uniquely picked out by some formula (according to the model).

The trouble is that even though you can make the set of reals the same, your chosen interpretation of all the functions/relations will not match the meta-theory, and in fact cannot match it (i.e. the meta-theory cannot provably construct an inner model like this, by Tarski's undefinability of truth theorem).

So you will get a set of reals, and they will be reals according to the meta-theory too, but the meta-theory cannot relate this set to the definable reals of the meta-theory.

As far as I can see this is the strongest statement you can actually prove: "the set of reals in any inner model of ZFC uniquely definable by a formula (according to the interpretation of the inner model) is countable (according to the interpretation of the meta-theory)".

> Also, did someone downvote your comment??

Someone did, yeah, but I don't mind =) I probably sound like a crackpot to the uninitiated.

[danwills]

That is very interesting I agree, and certainly any list of descriptions/identifiers must be countable, though I wonder if there's any validity in descriptions that describe things in aggregate?

It's certainly a brain-bender that even in the unit interval if we imagine filling in all the the rationals and then adding in the describable-irrationals like PI/4, sqrt(2)/2 and so on.. that this still does not even come close to covering the unit interval - or any interval - of Real numbers! My imagination sees a line with a heck of a lot of dots on it, but still knowing that there clearly still uncountably-more values that are not covered/described! Amazing! The continuum (Real numbers) is such a fascinating concept!

[nyrikki]

Almost all real numbers are normal numbers, which don't even have a finite representation.

Sure you can assign them to an arbitrary set, but you don't have access to the value.

It is a hay in the haystack problem, where you really only have access to the needles, not the hay.

[gowld]

It's even more extreme than that!

Take the (uncountable) set of Real numbers. Remove the normal numbers, which is almost all of them in the sense that the probability that "a uniformly randomly chosen real number is normal (and therefore also undescribable)" is 1. The remaining set of numbers, which has measure 0 in the Real numbers, is still uncountable, meaning that the proability of randomly choosing a describable number in that set is again 0.

I'm not sure how deep this chain can go. Google AI says "only 1 steps" but it's not admiting the case described in this comment.

[LegionMammal978]

> Almost all real numbers are normal numbers, which don't even have a finite representation.

Plenty of normal numbers have a finite representation from which digits can be efficiently extracted. E.g., Champernowne's constant (in any base) is normal, and you can find its digits with a relatively simple algorithm.

All computable reals can similarly have their digits extracted by some algorithm or another, even though it may take a long time. I wouldn't call that "not having access to the value". Of course, uncomputable numbers are a different story, but they have nothing to do with normality in any base.

And of course, radix representations are not the only way to evaluate real numbers. E.g., you could represent them with simple continued fractions (which would still allow addition, multiplication, comparison, etc.), and then you could write out any quadratic irrational with a periodic expansion.

[nyrikki]

"almost all" or "almost everywhere" is in italics because I mean it in the measure theory sense.

Meaning it holds for all elements of a set except for a subset that has measure zero.

Yes some normal numbers are in the constructable reals, but it is a measure zero subset.

You are putting your hand in the haystack and only finding needles, finding the hay in the haystack is the problem here.

[LegionMammal978]

Almost all reals are uncomputable. Also, almost all reals are absolutely normal. But the two concepts have nothing to do with each other.

> Yes some normal numbers are in the constructable reals, but it is a measure zero subset.

Almost all irrational computable reals (in the sense of natural density) will be normal, for any sane enumeration. Just because a real number is computable doesn't mean it's less likely to be normal.

[nyrikki]

Note I intentionally didn't invoke uncomputable, because computable is a highly constrained definition, and in this case is a circular refrence.

> All computable reals can similarly have their digits extracted by some algorithm or another, even though it may take a long time.

It was an intentional abstraction to avoid a self referencing claim, not to say that they are equivalent to anything.

The nice thing about constructible reals is after the construction you can typically forget how you constructed them, be that through Axioms, Cauchy sequences, Dedekind cuts etc...

The computable reals by definition can be computed to within any desired precision by a finite, terminating algorithm. That is why I said it is begging the question.

> Almost all irrational computable reals (in the sense of natural density) will be normal, for any sane enumeration. Just because a real number is computable doesn't mean it's less likely to be normal.

While some have Conjectured claims close to this, looking into why there have been no proofs for even a single number that was not explicitly created to be normal in any base may be a good lens in to the hay-in-the-haystack problems I was refrencing.

From: "Distribution Modulo One and Diophantine Approximation (Cambridge Tracts in Mathematics, Series Number 193)" Page 81, section 4.1 "Equivalent definitions of normality"

> Lemma 4.3: Let b and r be integers greater than or equal to 2. If a real number is simply normal to base b^r, then it is simply normal to base b.

That there may exclude many of what appear to be simply normal numbers from actual ones. As a graduate level text that book may be a bit expensive for what it is, but a good reference in my experience.

The 'Normal' property that is the full measure set of the reals is far more constrained than natural density. Which is why it is so surprising that is is the property of almost all of them.

That is why it was offered as a lens, specifically one that was worked on before computability as a subject, as an intentional way to gain distance from the almost intractable polysemy problems there.

[gbacon]

My intuition about the question is related: the set of all Turing machines (algorithms) is countable, but the set of all languages (problems to solve) is uncountable. If you take mathematics to be the bigger, uncountable picture, it’s mostly chaos, but if you limit consideration to algorithms, then it’s mostly order.

[Viliam1234]

> the set of all languages (problems to solve) is uncountable

The set of all problems that can be described by a finite description is countable. Why would we care about the rest of them?

[jibal]

Because we're theorists.

[seanhunter]

That is not true. Algebraic numbers for example are an uncountably infinite subset of the real numbers that can be precisely individually identified.

[cyborgx7]

According to Wikipedia, there are countably many algebraic numbers, and that makes intuitive sense to me as well. Do you have a source that the set of algebraic numbers is uncountable?

[seanhunter]

I am probably wrong