4
$\begingroup$

(I'm not normally dealing much with set theory and logic, so excuse me if my choice of words below seems a bit off the traditional terminology.) Where does the following Cantor-inspired argument go wrong?

Let $\Sigma = \{A_0,A_1,A_2,\ldots\}$ be the countable collection of statements with one free variable such that for all $n\ge 0$, $$ \exists!x_n\in [0,1):A_n(x), $$ where by $[0,1)$ I mean the interval. ($\Sigma$ is countable, right? Statements must consist of finitely many characters after all.) Now write $x_n$ in decimals as $$ x_n =\sum_{k=1}^\infty x_n^{(k)}10^{-k} $$ where $x_n^{(k)}\in\{0,1,\ldots,9\}$ for all $k\ge 1$ (we make sure never to write e.g. $0.1$ as $0.099999\ldots$). Now put $$ y^{(k)}=\begin{cases} 1 & \text{if $x_k^{(k)}\neq 1$}\\ 2 & \text{else}. \end{cases} $$ Unsurprisingly, we put $$ y:=\sum_{k=1}^\infty y^{(k)}10^{-k}. $$ Now $y\neq x_n$ for all $n$, just like in Cantor's classical argument. But the above definition of $y\in [0,1)$ should (I think---but this could be where I'm wrong) be possible to formalise in first-order logic. In other words, there exists a statement $A$ such that $y$ is the one and only number in $[0,1)$ such that $A(y)$ is true. Thus $A\in\Sigma$, which is obviously a contradiction.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You are also using an explicit, fixed enumeration of the statements in $\Sigma$, right? $\endgroup$ – Andrés E. Caicedo Jun 28 '14 at 17:04
  • $\begingroup$ Yes, we can just consider the statements to be words in our formal language alphabet and order them lexicographically. $\endgroup$ – Gaussler Jun 28 '14 at 17:06
  • $\begingroup$ You derive a contradiction when you assume $A$ is first-order. What does this tell you about that assumption? $\endgroup$ – Eric Towers Jun 28 '14 at 18:47
  • $\begingroup$ If we are to believe Asaf's answer below, the contradiction does not arrise because $A$ is first-order, but because I assume that it belongs to a family of only countable many statements. However, I can't say I've really understood all of it myself. $\endgroup$ – Gaussler Jun 28 '14 at 19:23
5
$\begingroup$

The statement "can be formalized in first-order logic" is problematic. First-order logic is not just one thing, it is a framework for a lot of things.

You talk about defining an element, so you need to specify the language, the structure and so on. The problem is that you can't quantify over statements, and you have, when you enumerated the statements.

While you can, theoretically, do that within a particular theory (e.g. you can quantify over Godel numbers), the theory needs to have some properties (e.g. the ability to interpret first-order logic internally). And you haven't told us what is the theory.

Even more than just that, if you do manage to have the theory interpret this internally, then you still run into Tarski's theorem which says that the truth is not first-order definable. So you can't quite use a truth predicate for arbitrary formula; so you would have to limit your formulas to a certain class which you can internally define a truth predicate.

If you have done all that, and your theory supports sufficient induction-like arguments, then yes, it is probably doable. But you haven't given us any of the above details.

On the other hand, Cantor's diagonal argument is not in the first-order theory of $\Bbb R$ or any other such structure. It is a set theoretic argument. So it is done in a much broader framework of set theory. This allows us to quantify over sets of real numbers, and preform induction internally to set theory; despite the fact that set theory is a first-order theory.

Why? Because in set theory the sets are the elements of the universe. Much like you can discuss the prime numbers which divide $2^{1379123}-1$ within the theory of arithmetic; you can discuss the subsets of $\Bbb R$ in set theory.

So within set theory, you can formalize all these notions, internally first-order logic, and then talk about this enumeration of formulas and so on, and then define $y$. But this is not done in first-order theory within the structure $[0,1)$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Well, I'm not really enough of an expert to provide those details. I kinda hoped people would see through the probably very wrong formulation and see the real issue at hand here. My answer to your "what theory" question must be something like "any theory where this makes sense". But do I understand you correctly if I conclude from what you say that, once all of these considerations have been done, the issue has vanished? $\endgroup$ – Gaussler Jun 28 '14 at 17:20
  • $\begingroup$ And can you clarify the last sentence about being within the structure of $[0,1)$? $\endgroup$ – Gaussler Jun 28 '14 at 17:25
  • 1
    $\begingroup$ The point is that either you can do it, and the definition is "pretty simple", e.g. they are all of the form $\varphi(n,x)$ where $n$ is a parameter; or you can't do it at all because you can't truly enumerate the formulas. You can only enumerate things which represent the formulas internally. If your language and theory are sufficiently strong then you can faithfully represent the formulas and their logical relation to each other; but if not then you can't do that at all. $\endgroup$ – Asaf Karagila♦ Jun 28 '14 at 17:30
  • 1
    $\begingroup$ As for that last sentence. You can define $\pi$ within the structure $(\Bbb R,0,\sin,\leq)$ as the least number such that $\sin x=0$ and $x>0$. But you can't quite define the number $\pi$ in the language $(\Bbb R,0,1,+,\cdot,\leq)$, because it is a transcendental number; and yet we still know it exists in the structure because we can define it externally using $\sin$ (which we can also prove to exist). The first case corresponds to within the structure, and the second case corresponds to outside the structure. $\endgroup$ – Asaf Karagila♦ Jun 28 '14 at 17:33
  • 1
    $\begingroup$ If the language and your theory are sufficiently strong to interpret first-order logic faithfully, as well talk about decimal expansions somehow, then either $y$ is definable in the case that $\Sigma$ is an internally representable set of formulas (and that you can definably find those $x_n$'s), or you can't define $y$ after all. In the case that you can, you usually have to limit yourself to particular sets of formulas, and not just "any enumeration of formulas". So again, more limitations. $\endgroup$ – Asaf Karagila♦ Jun 28 '14 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.