Hacker News Reader

Comment by jinpa_zangpo | Hacker News Reader

I believe the definition of this set is contradictory. The set is defined as all numbers that cannot be described with a finite number of symbols. But that set must have a member whose value is closest to zero. So you can describe at least one member of this supposedly indescribable set.

View on HN

I believe you are mistaken. This set of numbers is just the set of reals minus the countable infinity of finitely representable numbers. This set should still be densely ordered and so for any member that could be chosen from this set, there is an infinite number of elements closer to zero.

> But that set must have a member whose value is closest to zero

This is not true for real numbers with the usual "less-than" relation. In fact, considering real numbers, no open subset of R admits a lower member.

According to Zorn's lemma, there exist some order relation where your assertion is true, but I seem to remember from my math course a few (!) years ago that Zorn's lemma is equivalent to the axiom of choice.

According to the well-ordering theorem which is equivalent to the axiom of choice (and Zorn's lemma), you can well-order any set. That's usually when people start doubting the axiom of choice because, well, that's quite unintuitive. There is a joke about it which has already been posted here.

You can well order any set, but you need to have the "right" ordering to do so. As your parent is pointing out, the usual ordering on the reals is not a well ordering, and one cannot achieve a well ordering of the reals using that ordering.

This doesn't work for rational numbers either. Take any rational a/b, then 0 < a/(2b) < a/b is both closer to zero, and it is also a rational number.

> But that set must have a member whose value is closest to zero.

Must it?

"Let x be the smallest element of the half-open interval (0, 1]" isn't really something that you can say *.

* Assuming the standard ordering of reals; sure you can say it's defined for some well-order, but then you require the Axiom of Choice anyway.

> But that set must have a member whose value is closest to zero.

Must it? Is there a real number closest to zero?

It would at least require some careful setup to be coherent. Like you won't be able to define "the least positive integer that can't be uniquely described in fewer than fifteen words". Basically your language won't be consistent if it allows you to talk about things that can / can't be uniquely described in the language itself.

My disagreement about this post is: I don't see what it has to do with the axiom of choice. The only "choice" used here is that this nonempty set of non-describable numbers (if indeed we can define it at all) contains at least one element. That's a tautology and doesn't require choice.

Also, the author may be interested in Skolem's paradox: in particular, if the theory of the real numbers is consistent, then there must be a construction with only countably many reals, and so if I understand correctly, they would all be describable.

The definition of this set is contradictory, but not for the reason you've suggested. Rather, it is impossible to construct the set of numbers which can be defined by a finite string of symbols, due to Richard's paradox:

http://en.wikipedia.org/wiki/Richard's_paradox

Hence, it is also impossible to construct the complement of this set. In fact, Richard's "diagonal argument" chooses precisely the sort of number we ought not to be able to choose, according to the blog post (but again, this just shows the set is not well-defined).

"the member whose value is closest to zero" is described by those 14 symbols within the speech marks. As you say, the definition is contradictory.

Except no such member need exist. For example, there is no number that corresponds to the description "the smallest positive real number greater than 0".

Edit: note that even "the smallest positive rational number greater than 0" doesn't exist, even though the rationals are merely countably infinite.

This (no smallest positive element of Q) is sensible. But how can you have a procedure that requires making an infinite number of choices?[1] It's not an algorithm; they have to terminate.

1. Wikipedia explanation of the axiom of choice.

I was only pointing out the problem with your argument not arguing that the AoC is necessary or intuitive.

Also, algorithms that don't terminate are still algorithms - especially if they keep emitting pieces of a solution, instead of producing the whole solution at the end.

For example, here is an algorithm for printing all of the natural numbers:

  i <- 0
  while true:
    print(i) 
    i <- successor(i)

Finally, computability is not typically considered necessary for a mathematical construct to exist or be useful. Just like geometry sometimes studies shapes that can't be constructed in the physical world, other kinds of mathematics sometimes studies concepts that can't be computed (at least not given known models of computation).

Reply on news.ycombinator.com