0

The most common way to construct R is as a set of equivalence classes of Cauchy sequences, where two sequences are considered equivalent if their term-wise difference converges to zero. These Cauchy sequences can be described in mathematical language, obviously, lets say set theory and second order logic. Now, imagine an algorithm like this:

  1. Start with an ordered list of allowed symbols in our language (all the most commonly used symbols in mathematical notation).
  2. Enumerate all these strings, starting with the strings of length 1, then length 2, then 3, in the order of the ordered list.
  3. Some of these strings will be nonsense, like "{{a. ∀∀∀", some of them will be meaningful mathematical expressions, and some of them will be Cauchy sequences. However, when a (first) string corresponding to a Cauchy sequence appears we can send it to 1, and then when a second such string appears (presuming it is not in an equivalence class of Cauchy sequences that has appeared before), we can send it to 2, and so on ....

This is clearly countable, the set of all strings is countable. It will also reach every cauchy sequence unless there are cauchy sequences that cannot be described in any mathematical language. What is wrong with this argument?

David G. Stork
  • 29,774
hmmmmmmm
  • 153
  • 3
    "It will also reach every cauchy sequence unless there are cauchy sequences that cannot be described in any mathematical language." Why shouldn't there be any of these? Indeed, what your argument proves is (a precise version of the statement) that there always will be, regardless of what language we use, reals which are undefinable in that language. – Noah Schweber Apr 03 '21 at 21:25
  • 3
    That said, note more generally that we have to be very careful about any arguments around definability. For example, Tarski's undefinability theorem shows in a sense that there is no "once-and-for-all" notion of definability. This defeats an argument that we should be able to definably diagonalize against the set of definable numbers. – Noah Schweber Apr 03 '21 at 21:28
  • That is very interesting. Do you have any particular resource I could conduct to learn more about this? – hmmmmmmm Apr 03 '21 at 21:42
  • 1
    The general study of definability in mathematical structures is model theory (which is not to say that it has a monopoly on the topic, to be fair), which is a subfield of mathematical logic. There are several introductory texts on the topic; my personal favorite introduction is the relevant part of the book Computability and Logic (despite the title) by Boolos, Burgess, and Jeffrey, which I read prior to more serious texts like Marker's book (which is wonderful except for its many typoes) or Chang/Keisler (which is a bit dry). – Noah Schweber Apr 03 '21 at 21:45
  • 1
    All of the above focuses on one particular type of definability, namely that coming from first-order logic. But there are other logics out there; the general study of logics beyond first-order logic is abstract model theory. This is however a sufficiently advanced topic that it should only be studied after classical model theory is solidly understood. In particular, it also brings in a lot of set theory which is a whole separate issue. (Incidentally, it's worth noting that while Tarski's undefinability theorem is stated for first-order logic specifically it's actually much more general.) – Noah Schweber Apr 03 '21 at 21:46
  • 1
    Possibly also of interest: Skolem's paradox – Karl Apr 03 '21 at 21:52
  • Okay thank you a lot. I will look more into this. – hmmmmmmm Apr 03 '21 at 21:57

0 Answers0