-6
$\begingroup$

I just read an interesting book: "Classical and nonclassical logics", Princeton Univ. Press (2005) by Eric Schechter. On p. 208 he writes:

Also for simplicity of notation, we have chosen an alphabet that is only countably infinite. That alphabet is adequate for most applications of logic, but some logicians prefer to allow uncountable alphabets as well. (Imagine an even larger infinite computer keyboard, with real numbers written on the key caps!)

My question: How could the manufacturer write a real number except the few which have their own names like $2$ or $\sqrt3$ or $1/4$ or $\pi$?

If a student would ask me, I really could not answer since the real numbers written on the key caps have to be individuals, i.e., it is not sufficient to distinguish each one from some "given" real numbers but each one must differ from all other real numbers. How can that be possible by finite strings of symbols on the key caps? I assume consent that infinite strings of symbols don't carry any information that could be with sufficient completeness conveyed to the typist.

$\endgroup$

closed as off-topic by Tommi Brander, Amy B, Mark Fantini, Daniel Hast, Daniel R. Collins Nov 28 '17 at 18:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic because it is a mathematical question as contrasted with a question about mathematics education. For a Stack Exchange site for mathematical questions please see Mathematics." – Tommi Brander, Amy B, Mark Fantini, Daniel Hast, Daniel R. Collins
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Isn't this question more appropriately asked at Mathematics Stack Exchange? $\endgroup$ – Joel Reyes Noche Nov 28 '17 at 1:41
  • $\begingroup$ There it would immediately be deleted. $\endgroup$ – Wilhelm Nov 28 '17 at 9:17
  • $\begingroup$ Why would it be deleted on Math Stack Exchange? $\endgroup$ – Amy B Nov 28 '17 at 9:38
  • 5
    $\begingroup$ It seems like it needs comment that this is only a hypothetical/theoretical thought experiment. No such keyboard is actually constructable. Not even the simpler countably infinite one. $\endgroup$ – Daniel R. Collins Nov 28 '17 at 18:04
  • 2
    $\begingroup$ @Wilhelm: That's why you study formal logic; to learn how to use it. The relevant applications -- e.g. model theory in sets -- make it clear how you would use a language with an uncountable alphabet. $\endgroup$ – Hurkyl Nov 28 '17 at 20:49
3
$\begingroup$

So, here are two assumptions that I think are built into your question.

  1. The manufacturer is writing on the keys with only a finite, or perhaps countable alphabet of symbols.

  2. The manufacturer can only fit a finite number (maybe unboundedly large) of symbols on each key.

If assumption one fails, then you could just give each real number a symbol, and be done with it.

If assumption two fails, you could name each real number by its perhaps infinitely long decimal expansion.

If both assumptions hold, then the answer is "They can't". This is because, as Cantor proved a while back, there are uncountably many real numbers. But there are only countably many finite strings of symbols over a given finite (or countable) alphabet.

The manufacturer's best bet, if they want to do this systematically, might be to write on each key a computer program that prints out the decimal representation of the real number that key is supposed to produce. This would get you the computable numbers, a larger set of reals than just algebraic numbers plus common transcendentals like π. But, there remain some reals with names that can't be represented this way, like Chaitin's Ω, so this still isn't optimal.

However, there is no optimal solution. Suppose there were. Then we could add a key which said "the real whose first digit is the first digit of the alphabetically least real from the old keyboard, plus one (or minus one, if the first digit is 9), whose second digit is the same as the second digit of the alphabetically second-least real from the old keyboard, and so on", and in that way add a key which denotes a real not denoted by any key on the first keyboard (it can't be denoted by the first key, because it differs in the first digit from that real, it can't be denoted by the second, because it differs in the second digit...). So, since we've added a key, the original keyboard was not optimal. Contradiction, and our assumption must have been false.

I'm slightly fudging things for simplicity in the previous paragraph by pretending that decimal representations are unique. But you could run the same argument but on a scheme where they are unique by using e.g. continued fractions.

$\endgroup$
  • $\begingroup$ It is obviously impossible to read an infinitely long decimal expansion as I mentioned already in the question. How would you give each real number a symbol? "But there are only countably many finite strings of symbols over a given a finite (or countable) alphabet." That's why I ask. There seem to be many logicians who support the counterfactual claim: There exists an alphabetically ordered uncountable list (since an alphabet is a list). $\endgroup$ – Wilhelm Nov 28 '17 at 9:14
  • $\begingroup$ "The manufacturer is writing on the keys with only a finite, or perhaps countable alphabet of symbols." Of course. Otherwise we would not be in need of an uncountable language but already have it. "The manufacturer can only fit a finite number (maybe unboundedly large) of symbols on each key." Of course, because we cannot read an infinite string even if it was there."If both assumptions hold, then the answer is 'They can't'." That's my opinion too. But before I accept your answer I would wait some time such that logicians claiming the contrary can support their position. $\endgroup$ – Wilhelm Nov 28 '17 at 9:24
  • 1
    $\begingroup$ Well, if we assume a key for each real number and "enough" space to write it, why not draw a line that has exactly this real number as length in a chosen unit (cm, m, whatever). That should be just as impossible as everything else, but would solve the trouble with the finite alphabet of symbols the manufacturer can use. $\endgroup$ – Dirk Nov 28 '17 at 10:18
  • $\begingroup$ @Dirk Liebhold: We need not only the number or its length but also its meaning in a language. Otherwise we could only push the keys like the famous monkey. $\endgroup$ – Wilhelm Nov 28 '17 at 19:45
  • $\begingroup$ @Wilhelm: Formal languages don't have "meaning"; they only have syntax and grammar. Assigning meaning to the language usually done by an interpretation. $\endgroup$ – Hurkyl Nov 28 '17 at 20:46
5
$\begingroup$

Schechter is talking about infinitary logic (see the Wikipedia and Stanford Encyclopedia of Philosophy entries), although Schechter's "infinite computer keyboard" comment is meant to be picturesque and not mathematically precise.

See also Keisler's 1970 paper Logic with the quantifier "there exist uncountably many" and David Marker's Fall 2007 A Primer on Infinitary Logic and Dickmann's 1975 book Large Infinitary Languages (book reviewed here). Incidentally, Dickmann's book deals with large cardinal infinitary languages, in case you were wondering just how far down the uncountable rabbit hole logicians have gone with this stuff. (Answer: Further than you can probably imagine.)

Finally, the google search infinitary languages brings up a lot of relevant hits.

$\endgroup$
  • $\begingroup$ Although Schechter's "infinite computer keyboard" comment is meant to be picturesque and not mathematically precise there are logicians insisting that it is possible to use an uncountable language in precise logic. Therefore I ask. I know most of the literature you quoted but I have never seen a hint how a less prominent real number than those defined by series or sequences could be "used". $\endgroup$ – Wilhelm Nov 27 '17 at 21:33
  • 2
    $\begingroup$ @Wilhelm: It sounds like you're interested in the philosophical implications of this, which is going to get tangled up in what "used" means and how we determine what "used" means, etc. For some extreme existence issues, see my answer here. $\endgroup$ – Dave L Renfro Nov 28 '17 at 11:56
  • $\begingroup$ It's not the philosophy but the application that I am interested in. A language is something to be applied. A language over an uncountable alphabet cannot be applied unless we know how uncountably many symbols have to be put together in a meaningful way. $\endgroup$ – Wilhelm Nov 28 '17 at 19:42
5
$\begingroup$

I assume you mention the real numbers because you are considering the case where the set of real numbers is taken to be your alphabet.

In this case, the "keyboard manufacturer's" job is simple; every key is labeled with a single symbol.

The point you're missing is that, if you take you take the real numbers to be your alphabet, they are the very symbols you use to write with.


It may help to understand why one might want to use an uncountable alphabet. One might get the impression that strings over an alphabet are meant to model human writing, and while that's one application, it is by no means the only one.

A different example would be to axiomatically define the notion of a "real vector space". A typical method would be to define a language consisting of:

  • The usual logical symbols
  • The constant symbol $\vec{0}$ (the "zero vector")
  • The binary function symbol $+$ (the operation of "vector addition")
  • For every real number $r$, the unary function symbol "$r \cdot {}$" (the operation of "scalar multiplication by $r$")

and formally write out the axiom schema for the real vector spaces in this language:

  • The axiom $a+(b+c) = (a+b)+c$
  • For every real numbers $r,s,t$ with $r+s=t$, include the axiom $t \cdot a = r \cdot a + s \cdot a$
  • ... and so forth

One's first tendencies might be to try and include in the axioms a minimalist axiomatization of the real numbers, but that's missing the point — the real numbers here are a given, and the point of this theory is to define what a "real vector space" is, not what a "real number" is.

Also, there are important mathematical reasons for having the theory presented in this particular form; e.g. it shows that "real vector space" is an example of a thing called a universal algebra.

$\endgroup$
  • $\begingroup$ How do you know what symbol corresponds to what number? How would you distinguish a completely unrelated set of symbols from symbols corresponding to real numbers? An alphabet is what is alphabetically ordered. Otherwise you cannot know the the place where to hit the keys and to find the letters. Further you are missing the fact that there are only countably many finite symbols (whether defined by pixels or paited by hand.) $\endgroup$ – Wilhelm Nov 28 '17 at 8:58
  • $\begingroup$ @Wilhelm: You know what symbol corresponds to what number because the symbol is the number. An alphabet is a set, not an ordered set. And you are missing the fact that there are uncountably many symbols. The premise is "the real numbers are the alphabet", not "the alphabet is some finite collection of pictographs I've chosen a priori and assume everyone always uses when discussing strings of symbols, even if they say they are using a different alphabet". An alphabet is a mathematical object, not a "physical" one, whatever that might mean. $\endgroup$ – Hurkyl Nov 28 '17 at 17:39
  • $\begingroup$ A symbol is not a number. An alphabet is an alphabetically or lexically ordered set, namely a list or sequence of symbols that serves to form words while almost all real numbers cannot be defined let alone be chosen. The real numbers are definitvely not an alphabet. $\endgroup$ – Wilhelm Nov 28 '17 at 19:31
  • 1
    $\begingroup$ In mathematics we often highlight some essential feature of an object, and leave out others. Certainly alphabets with order are interesting, but alphabets without order are also interesting. $\endgroup$ – Steven Gubkin Nov 28 '17 at 22:18
  • 1
    $\begingroup$ @Wilhelm: No, the alphabet is, for example, "real numbers". The alphabet is not "binary strings" or "grids" or "atoms and molecules" (although that last is uncountable, by current physical theories). The alphabet is "real numbers". And there really isn't any trouble at all for logicians to work with such alphabets and discuss theories; to wit in this very post I've had absolutely no difficulty clearly and unambiguously specifying not only strings over an uncountable language, but I've even specified uncountably many strings.... $\endgroup$ – Hurkyl Dec 2 '17 at 19:54
1
$\begingroup$

Well if you are imagining a keyboard with an infinite amount of keys, you would want to imagine an infinite amount of space to write the number on each key. So the unnamed real numbers would contain infinite space to write.

But how would the typist distinguish them? Well how does the mathematician distinguish them?

By their position. We don't read off the digits but locate them in the place where they belong.

So each key and its neighbor would have the ability to have a key between them. And likewise for those keys.

If we are imagining; here this is what this means. If each key were a distinct entity holding position to another key with nothing between them, it would be countable.

So in our imagining we have to come up with a mechanism to make the numbers infinitely dense. So using the definition of this in real numbers we will place a key inbetween two other keys as needed.

Not sure if this is the point of the analogy or the imagining exercise, but as analogy it breaks down; if we don't add room for that infinite density of real numbers.

And so in the imagining we create a contraption that looks like a keyboard from afar but if we stare at the spaces between the keys is different. Much like real numbers look like integers, until we look more closely and find we have to squeeze more and more in the spaces between each named thing.

$\endgroup$
  • $\begingroup$ It is certainly not possible to find individual real numbers by their positions. $\endgroup$ – Wilhelm Nov 27 '17 at 21:39
  • $\begingroup$ I am confused on your comment and I think individual may be the word confusing me. I can find a real number $\frac{\sqrt{3}-\sqrt{2}}{2}$ being the real number half way between the real numbers $\sqrt{3}$ and $\sqrt{2}$. That is a position relative to other real numbers. So can you clarify your comment. $\endgroup$ – Jeffery Thompson Nov 27 '17 at 22:09
  • $\begingroup$ You can find a real number that has a finite description like that in your example and those in the examples in my question. But almost all real numbers have no finite description since the set of finite descriptions is countable. $\endgroup$ – Wilhelm Nov 28 '17 at 9:14
  • $\begingroup$ But they have a magnitude and a position on the number line that is absolute. We just don't have a symbolic way of representing they still have a position in the space. We could make something of that length and fix it from 0 to the real number. Its position exists, we lack the symbols to describe it. I also need to think about the count-ability of the construction, because if I use uncountable members in my construction algorithm it should be uncountable, but I need to think on this. $\endgroup$ – Jeffery Thompson Nov 28 '17 at 15:03
  • $\begingroup$ The chance to hit a real number on the number line is zero. Further we need not only to hit a number but we have to know the meaning of that number and to apply it it in a meaningful way. $\endgroup$ – Wilhelm Nov 28 '17 at 19:47

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