Definable Numbers: Countability, Uncountability & Paradoxes

[Hurkyl]

http://en.wikipedia.org/wiki/Definable_number


A definable number is one that satisfies a formula of the form:

"There exists a unique x such that P(x)"

for some logical formula P.


This Wikipedia article asserts that the definable numbers are countable, because the set of all logical formulae is countable. (fine) Then, it continues by concluding that most real numbers are not definable, because the real numbers are uncountable. (...)


It strikes me that there is a problem with this paragraph -- in particular, the measure of countability is coming from two different theories! (Compare to Skolem's paradox)


The second statement:

"the real numbers are uncountable"

is fine -- it's proven straightforwardly by Cantor's diagonal argument, and isn't really questionable. In particular, though, it's a theorem of some particular theory. (Say, second-order ZF)


The first statement:

"the set of all logical formulae is countable"

is also fine -- it's proven straightforwardly by induction on the complexity of the formulae. However, this is not a theorem within the same theory!

To continue with the example, this statement could be made as a theorem in second-order ZF about the possible first-order formulae of ZF. Or, it might be a theorem of some external theory (say, third-order ZF?) about the possible second-order formulae of ZF.

But, it cannot be a theorem of second-order ZF about the possible second-order formulae of ZF! (can it?)


Now, it's a familiar fact that measuring sets in different theories leads to conflicting results -- Skolem's paradox. So, I'm entirely unconvinced by the argument given in Wikipedia that most real numbers are not definable.



But wait, there's more!



Today at work, I was thinking about the axioms of ZF. If we extend the notion of a definable number to that of a definable set, in the obvious way, it seems to me that you would not be able to prove the existence of a set that was not definable! In particular, I conjecture that there does not exist a formula P(x) in ZF for which you can prove:

There exists an x such that P(x)

but such that no definable number satisfies P. The same goes for ZFC, if you replace the axiom of choice with an actual function that selects particular choice functions! (But that would seem to go against the spirit of this exercise...)



Does anyone out there have any further insight they can contribute?

 

[matt grime]

I'm not sure I see what the problem is (but then I'm not a logician). In any model of ZF that contains something called the real numbers, they are countable, but not "countable within the model" - that is cantor's theorem still holds: there is no bijection from N (the set arising from the axiom of infinity) to its power set, even though its power set is "countable".

That doesn't appear to answer anything though.

 

[Hurkyl]

Not answering anything is still an answer... it let's me know I'm probably not overlooking something obvious!

 

[chronon]

I think there is an ambiguity in the Wikipedia article. The definition seems to be that there is a specific, finite system of rules which are to be used in the definition. On the other hand, the implication is that definable numbers represent all numbers that we can define. Both of these will be countable, so we can do a diagonal argument on each of them, to generate a new 'definable' real number. In the first case this shows that we didn't capture all of the 'definable' numbers. In the second case we show that the notion of definable number that we are using isn't really well defined.

 

[slayerchange]

Definable sets and in particular definable numbers is one of the topic in Model Theory .
Please see the definition of the terms "A-definable" , "EmptySet-Definable".
Also please see , for last part of your question , "constructable sets" and their relation between "definable sets" in Algebraicly closed fields and R .

 

[NateTG]

Today at work, I was thinking about the axioms of ZF. If we extend the notion of a definable number to that of a definable set, in the obvious way, it seems to me that you would not be able to prove the existence of a set that was not definable! In particular, I conjecture that there does not exist a formula P(x) in ZF for which you can prove:

There exists an x such that P(x)

but such that no definable number satisfies P. The same goes for ZFC, if you replace the axiom of choice with an actual function that selects particular choice functions! (But that would seem to go against the spirit of this exercise...)

Does anyone out there have any further insight they can contribute?

It may be that you're getting stuck on the noting of 'an undefinable set' rather than collections of undefinable sets. Just because a particular set is undefinable, does not mean that the a collection containing that set is undefinable.

If you allow for 'transcendant'(I'm sure there's a better or more appropriate term) or infinite formulae, such as:
P(x) is true if p(x) is false for all finite formulas p s.t. p only has one solution.

Then it's possible to prove that there are x such that P(x) exists even though it's not possible to specify any particular such x.