# Poker and Cantor’s Proof

* The reals are still uncountable *

Dave Patterson is a world-famous expert on computer architecture. He has won many awards, and is a member of the National Academy of Engineering and the National Academy of Sciences. He coined the term “RISC” and later the term “RAID.” He also wrote definitive textbooks on computer architecture, with John Hennessy, including the famous *Computer Architecture: A Quantitative Approach.*.

Today I and Ken want to continue the last discussion on Georg Cantor’s Diagonal Proof. My goal is to try to answer one of the issues raised about this famous proof. I do thank all the commenters for an interesting discussion.

What does this have to do with Dave? He is not a theorist, and may know Cantor’s proof—but certainly is not excited about it. He is very practical-oriented: his most famous work is on the design of **R**educed **I**nstruction **S**et **C**omputing processors.

But Dave is a poker player. When I arrived at Berkeley in the late 1970’s, I wanted to bring one tradition from Yale to Berkeley: playing a “friendly” game of cards on a regular basis. I assumed that my theory colleagues, Dick Karp and others, would be interested in playing. The game I had in mine was low stakes poker. The rules were “dealer’s choice” and modified “pot limit.” The latter means one could make a bet that was bounded by half the current pot. This method of betting was introduced to me by Albert Meyer, and it can lead to exponential increases in bets. This increase makes the game exciting—I felt—and allows for bluffing. Even through the stakes are low, the game can be quite exciting.

In any event I was sure that my theory friends at Berkeley would jump at a chance to put probability theory to a practical test. I was wrong. Every member of the theory group said: not interested, sorry. The sole possible exception was Karp, but poker requires players for much greater than to be fun. I was about to give up when I mentioned it one day to Patterson. Before I knew it all the computer architecture group—well most—had signed up, and a new course was created:

CS 52

When you got the message, “CS 52 this week at X’s house,” you knew the game was on. We played for the two years that I was at Berkeley, and had a great deal of fun. I believe that they still play poker there, although the game has changed to Texas Hold ‘Em and the betting is different. I believe that it is one of my great and lasting contributions to Berkeley Computer Science Department. Perhaps they will put up a plaque that says…

## Show Your Hand

In almost any version of Poker—Texas Hold ‘Em, Stud, Draw, or any other variant—there comes a time when all the bets and raises and re-raises are done. At this point, if you are the person who last bet or raised, you must **show your hand**, that is, must lay your cards on the table. That’s part of the meaning of saying that you have been **called**. Then the other players can either throw their hands away or show their cards and prove that they have a better hand. The winner takes the money.

If you are called you must show your cards. You are not allowed, if called, to say I will show my cards later; or go through the deck and change you hand. The game has come to the showdown—you must show what you have. Not anything else. Any attempt to not do this is considered cheating—do not try this in a real game.

The same principle of showing your hand applies to mathematical proofs. For instance, if you are a Count and thus believe that the reals are countable, then you must be prepared to give a listing of the reals—essentially show your cards. This is where most Counts have trouble: they want to be able to change their “hands.” Tim Gowers said it best when he wrote that he usually asks a Count to present the actual listing. Essentially Tim is *calling* them, and demanding that they show their hand.

Note that this requirement is standard math, and has nothing at all to do with countable sets, uncountable sets, infinities, or the reals. If you are claiming that is rational, you must be prepared to agree that there is some **fixed** and natural numbers, so that

You are not allowed to change the values of and during the proof. Either there is a fixed or there is not.

Another example is Euclid’s classic proof that there are an infinite number of primes. If you believed that there is a largest prime, then you must be prepared to say that is the largest prime. Then, Euclid can use this number to force you to consider

The argument then shows that is either prime or is divisible by a prime , where must be larger than .

An even simpler version of this is the “largest number game.” You name a number and then I have to name a larger one. Again if you think that there is a largest one, you must be prepared to say that the largest one is , say. Then I point out that is larger. Scott Aaronson retold here an old story based on this game:

Two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces “Eighty-three!” The second, mightily impressed, replies “You win.”

## Back To The Proof

If you believe the reals are countable, then you must show your hand. You must fix a listing of the reals:

This is nothing different from picking a pair to show that is rational, that there is a largest prime , or even that there is a largest number . This is the show your hand step. If you disagree with this step in Cantor’s proof, then you must also do the same in the above simple examples. You also must not play Poker by the standard rules.

Once I have seen your hand, the sequence , I can try and find a real that you missed. There are many ways that I can do this. Since I can always construct a real number *based on your sequence, your hand*, that is not any , I win. Your sequence does not contain all the reals.

## Leading Out Versus Check-Raising

Ken on the other hand recalls he did not play a single hand of poker during 5-1/2 years at Oxford, and has picked up poker recently only because of the interest of his son. But he finds that his own angle on Cantor’s theorem, informed by his exposure to finitists at Oxford, fits in well with the poker analogy.

In poker a player whose turn to bet comes first is “under the gun” and often at a disadvantage. Assertively “leading out” with a sizable bet gives opponents more leverage to raise since more of the player’s own money is in the pot. Instead the player is allowed to **check**, i.e. to bet zero, and subsequent players may check until a bet is made. If an opponent bets, then the first player is in the situation of being able to raise, not just call. A raise then is called a **check-raise**.

The math analogy is that asserting the existence of a set that is in some sense more complex than any set previously admitted is a form of leading out. If we’ve only reached a comfort zone with countable sets, then an uncountable set represents a new level of complexity. Indeed, to a finitist, every power-set is a big step up in complexity. If you think a googolplex is a meaningless quantity, then you can only iterate for a few steps before you would pass it.

Leading out with an object on a new level of complexity takes chutzpah. But even a humble finitist may be comfortable with theorems of the form, “If you have an object then I can give you a .” This is like saying “I check”—let someone else bet . If has the same intuitive complexity level as then that is like a call. If is a step up in complexity from , but similar to how was a step up from whatever was “in the pot” already, then is a check-raise.

## The “Humble” Cantor Theorem

Here is a form of Cantor’s Theorem that embodies the check-call or check-raise idea, depending on how it is applied:

Theorem 1Given any mapping from a set into its power set , we can find a subset of that is not in the range of .

*Proof:* Define . We claim that is not in the range of . If it were, then there would exist a such that . But then we have:

is in the set | by definition of | |||

is not in the set | by definition of . |

Since a logical statement can never be equivalent to its negation, this contradicts being in the range of .

Note that the proof itself embodies Cantor’s diagonal argument, but makes no reference to infinite constructions or possibilities, indeed no reference to infinity at all. It is not asserting anything on its own, but reacting to someone else giving an . Since has roughly the same complexity as —both involve the power set—producing is like a call.

What this has done is bring the implied onus of the bettor to show one’s hand into the theorem statement itself. It puts the question to the Count right away. For simplicity, let’s first talk about the power set of being uncountable:

If you think that is countable, then you are giving me a function from to that is

onto. You can’t give me such a function, because I can give you and it will show that you were bluffing.

With a little technical work a Count should be convinced that a bluff on is equivalent to a bluff on . Thus the Count must admit that one can *never* have the cards to win a showdown that the reals are countable, and by “*never*” itself, should come on board that they are uncountable.

## Raising Higher

One nice point about this formulation is that it carries over verbatim to prove the existence of non-r.e. sets. Just take to be the mapping from a Gödel number to the language accepted by the Turing machine , and what tumbles out is the creation of a diagonal language . Since is more complex than any in the sense of being non-r.e., we can call that a check-raise.

How widely can one replace theorems of the form “There exists a ” with “humbler” ones of the form “If you give me an , then I can build a “? Upon producing an they have the same effect. Do the latter kind show the flow of reasoning better?

Going beyond the cardinality of the reals, asserting the existence of certain Large Cardinals is a recognized way of extending ZFC set theory. Remarkably, all that have been studied are linearly ordered under the relation if ZFC + “ exists” proves the consistency of ZFC + “ exists.” That is, they are totally ordered by modulo the equivalence relation if ZFC proves the statement that “ZFC + ` exists’ is consistent ZFC + ` exists’ is consistent.” Moreover there are cases where but (if these cardinals exist at all) .

Thus the large-cardinal axioms represent progressively higher levels of complexity, in our intended intuitive sense. How high a cardinal will you bet on? Are you a SuperCompactUncount? The theorems underlying the relation can by-and-large be given the form, “If you show me a I can build a .” It is interesting to ask how illuminating this theorem structure can be for mathematics closer to home.

## Open Problems

Do these analogies help?

Note that RISC does not mean that the instruction set is reduced in numbers, but rather than each individual instruction carries a reduced workload vis-à-vis a comparable CISC instruction. Can we organize mathematical theorems in an analogous manner? Would “humble” forms make theorems easier to understand?

Is it Texas Hold ‘Em, Texas Hold’Em, Texas HoldEm, Texas Hold Em, Texas Hold-Em, Texas Hold-‘Em, Texas Hold’ Em, Texas Hold ’em, Texas Hold’em, Texas Hold em, Texas Hold-em, Texas Hold-’em, Texas Hold’ em, Texas hold ’em, Texas hold’em, Texas hold em, Texas hold-em, Texas hold-’em, Texas hold’ em, or just Poker?

### Trackbacks

- Poker and Cantor's Proof « Gödel's Lost Letter and P=NP | BBGUniverse
- A Brilliant Idea In Publishing « Gödel’s Lost Letter and P=NP
- Patching A Diagonalization « Gödel’s Lost Letter and P=NP
- Making Choices | Gödel's Lost Letter and P=NP
- Diagonalization Without Sets | Gödel's Lost Letter and P=NP
- A Proof Of The Halting Theorem | Gödel's Lost Letter and P=NP

You are essentially replacing countable with enumerable and I think that is helpful. To construct the diagonal we need an enumeration. Most will agree that countable implies enumerable, but it might not be as clear for some.

At the end what we are concerned is the objects in the function space. If we want to have the full function space then the diagonal is also there so we cannot construct it. On the other hand, if we restrict the power set to nice objects (e.g. computable objects) then Cantor’s argument simply implies that assuming we can enumerate the objects in the function space, the diagonal object with respect to that enumeration is not in the function space. Either we have to admit that we cannot enumerate the objects in the function space or that there are objects which are not in the function space. Another interesting possibility is to consider the space of partial functions (partial reals?) where there is the possibility that there are objects which are neither equal nor unequal.

By the way, in constructive mathematics, classical theorems like Canor’s are stated in the form you mention so they are also constructively true.

My favorite version of the “largest number game” joke is a story I heard from Bob Kaplan. He was running a math circle for young children, and that day’s topic was what the largest number might be. After some discussion, one kid proposed something along the lines of a million billion trillion, at which point another asked “What about a million billion trillion and one?” The first kid then replied, “Well, I was close.”

“Show your (Count) hand” is a fine thesis! Which suggests that it might be feasible to assert an opposing thesis … because in math, physics and engineering, “every day is opposites day” (for you Calvin and Hobbes fans).

Standing proxy for (what I take to be) Doron Zeilberger’s point-of-view, as expressed in his finitarian essay “Opinion 108: The Feeling Is Mutual“, we can argue the contrary thesis “Don’t even bother to show your (Uncount) hand” as follows.

Suppose that Count (very reasonably) requests “Show your (Uncount) hand.” Needless to say, Uncount has no problem in doing so! But Count protests:

It seems (to me) that this particular Count argument is correct-on-the-facts … yet no doubt there are those who are willing to opine otherwise. 🙂

It seems to me that a Count could reply that the bijection you are asking for can’t be described (that is, it’s not a computable function) but that it exists anyway.

This idea seems similar to non-standard models (though I don’t think Counts would relish the comparison). The downward Löwenheim–Skolem theorem says that every first order theory with an infinite model has a countable model. So the first-order theory of the reals has a countable model, and there’s a bijection between the reals in the countable model and the natural numbers. But this bijection can’t be described within the theory.

Re: the nobleman and the triumphant “Eighty-three!”: it may be of interest that the number

eighty-three wins a lot of arguments on the TV show How I Met Your Mother. See

http://en.wikipedia.org/wiki/Barney_Stinson which confirms

“Barney often makes up statistics in order to make his arguments sound credible. When he makes up a statistic, he always uses the figure 83%, which is not lost on his friends. “

I was wondering something very similar to what Gareth Rees suggests, partly influenced by a comment of Andrej Bauer on my blog in which he said that it is sometimes not just useful but actually necessary, when proving a theorem of the form “For every x in X, P(x),” to begin the proof with (something equivalent to), “Let z be in X,” and follow that with a proof of P(z).

Suppose now that we decided that this move was suspect when the set X was sufficiently complex. For example, we might object to Uncount beginning a proof of the statement, “For every function f from N to P(N), f is not a surjection,” with the line, “Let g be a function from N to P(N),” on the grounds that functions from N to P(N) can be very wild, so “fixing” an arbitrary such function is not at all trivial.

I think Count would have to agree that for any function g that you

canspecify, it is possible to find a subset of N that is not in the image of g. But Count would think of this as a proof schema rather than a proof: it’s a way of defeating any specific function, but it doesn’t prove that no such function exists. And in that way Count could cling to the view that nobody has actually shown that the reals are uncountable.The obvious question if one wants to pursue this line is how much of mathematics will be left if one outlaws the “Let” move for, say, second-order quantification. Something that bothers me a bit about it is that I’m not sure what one can do with the countability of the reals if you’re not allowed to say, “Great — so let’s take a bijection g from N to R,” and have merely to assert, as a matter of faith, that one exists. What does that even mean? In fact, I haven’t given the slightest reason for Count to think that one

doesexist — only an indication of a sacrifice that Count might want to contemplate making in order to deny the otherwise unassailable logic of Cantor’s proof.If you are a Count reading this, I beg you not to take it as the slightest support for your views — that would be a serious misunderstanding of what I am saying.

Tim, your post is really excellent, so please let me explore (what I take to be) its main points via a question that is concrete, yet sympathetic to Counts and Uncounts alike.

That question is, what is the cardinality of the set of languages in ? For Uncounts that question is easy: the cardinality of is upper-bounded by the cardinality of the set of Turing machines, which is an enumerable set. But Counts may well be suspicious of this argument, on the grounds that (for all we know) some languages in are recognized solely by Turing machines whose runtime exponents are undecidable.

It is not clear (to me at least) whether our present knowledge of computational complexity suffices to judge which party has the better of this argument. It does seem conceivable (to me) that in coming years the Counts might win a clear, compelling (and shocking!) victory over the Uncounts, by a strategy of exhibiting “Countist” definitions of and having the following attributes: (1) both and are concretely enumerable, (2) and are provably separable, (3) the following separations are all provably undecidable: from , from , and from .

To the best of my (non-expert) understanding, points (1–3) all are wholly compatible with our present understanding of complexity theory, and indeed the work of Juris Hartmanis can be read as suggesting that (3) is plausible and perhaps even likely.

By some such “burning arrow” process, can’t we at least conceive that the Countist point-of-view might earn the respect — even the affection — of complexity theorists? That would be fun! 🙂

And there is precedent for such a shift; a recent example being the respect that Shechtman’s “burning arrow” of quasicrystals has slowly earned from crystallographers, in which a modification of crystallography’s fundamental assumptions has in recent decades required more work in theorem-proving, and a larger mathematical toolkit, while yielding a broader and deeper understanding of the natural world.

At least one Count has been challenged to “show their hand” here: http://scienceblogs.com/goodmath/2009/12/another_cantor_crank_represent.php

And also in the follow-up post: http://scienceblogs.com/goodmath/2010/02/_so_remember_back_in.php

For those whose time is more valuable that reading all of this content, let me summarize. The Count in question, Count John Gabriel, would repeatedly ignore the request to show his hand or argue that he wasn’t required to show skeptics a specific mapping (since he believed he had showed existence through his tree-like construction). I followed up with John Gabriel through personal interactions over email when the commenters at the Chu-Carroll blog pointed their questions at him with no better luck – in fact I was repeatedly insulted by him for trying to be generous and caring and patient.

This is all a short way of suggesting that the demanding Counts “show their hand” probably won’t work as a way of politely communicating and problem-solving with them.

This suggested tree-mapping was exactly what was being argued by some in the prior thread here.

Yes! Could that MrX guy be… John Gabriel?

From the article

>If you start at the root, and enumerate by climbing down the tree breadth

first, you’ll never get to anything with an infinite decimal representation.

I think this is where MrX and Uncounts diverge. When you are trying to “map” things you either start from a) unity and try to add up to “a whole” (Omega, or infinity) – this we call the naturals or b) start with a “a whole” that can be infinitely divided into ever increasing precision, where you have the rationals. The reals end up being defined as *both*, for the main reason that we are trying to map irrationals, which are just a way of saying we are trying to represent with strings or labels something that requires what in our labeling seems can be regarded as infinite “precision” or infinite resolution. In PI for example, we have “3” radius, and 14.15…% percent of another one. Representing the exact % (or decimals) of such “whole” (the radius) is a never ending process. You can never get it right, but we know half the ratio of a circumference to radius exists and is very tangible.

MrX is trying to start from “a whole” a divides it, and no matter how long he tries, he’s not further to getting to the real PI or any other decimal part of rational that at 0% progress. And when you start with 1, or need to create numbers with naturals, you are never 0% close to infinity. Which is why MrX falls back to explaining over and over and over that “infinity doesn’t work this or that way”. He is right. You can never reach to PI from a “a whole”), just as you can never reach infinity from a classic natural’s number definition.

Reals try are a way to deal with SQRT(2) or PI, by saying they must be in between rationals. Like introducing the notion of “milestones” or “pins” within the rationals…we have a name for them, and we know they exist. We just can never get exactly to them. The process of getting closer to the real “irrational” decimals is an infinitely long process. And as we focus on trying to approximate one, we “use up” all our resources (or our “naturals”). And there infinitely many of them.

I look at all this differently. If you define that infinite is an arbitrarily large finite number, the naturals and the rationals (and the irrationals) start to make sense. How? You can approach unity by dividing the hole, and you can approach unity by summing the unities. And you can get as perfectly close as possible to any irrational. You then think of infinity as what happens when you approach a limit, that of an infinite “resolution”, or when unity is so infinitely small that it never adds to “1” or “a whole”, and when you can never approach unity by making smaller “dents” in “a whole”. At this point, we get to where we are, the naturals become (and are as we use them) smallest units that in relation to infinity they always sum 0%, the whole can be divided in slices, in an infinite attempt to get to unity never achieving it, and the irrationals are the reminder that “a whole” can not only be though of a dividing a pie (eg. 1/2 is a number as much as it is a proportion of infinite precision, a cut into two pieces which we understand perfectly well, because the two slides are just very tangible, thus we say 0.5…but we know that in infinite precision the number is really 0.50000… with an infinite number of zeroes to the right, which is just as complicated as saying PI, which is intuitive only if you think it’s a ratio related to a circle, but that doesn’t have any simplification such as saying make “two” from “one”. PI requires we make 14.15…% “infinitely small pebbles” out of 100% “infinitely small pebbles”. But at this precision level, 2 is also 50% “infinitely small pebbles” out of 100% “infinitely small pebbles”, which is as complicated).

When you add in a lot of notion,fancy names, axioms, and everything, and these are somewhat opaque in conversations (because many people do not dedicate life to math, but many think hard about these conversations), you get Counts and Uncounts, crackpots, poker, religious arguments (meaning people that try to express their religious believes about god as valid proof), heated debates, etc.

The tree from MrX never reaches an irrational, because there’s never enough time.But my understanding is that he is correct in the sense that he isn’t doing anything different that what is accepted as proof for the rationals. The rationals enumeration can never get to 1/2 at infinite precision while at the same time reaching 1/3 with infinite precision, just as MrX can’t get to any rational by trying harder and harder. How do I get to the smallest possible number of 1/2 plus it’s smaller “neighbor” in decimals? There’s one except as a though experiment in continuing to add zeroes. And as you dedicate all your life to add zeroes in between that last “1” in a decimal or binary representation (a never ending process) there can is no progress anywhere else.

This is why I think MrX tired and repetitive and stubborn use of the need to describe the “generators” plagues conversations. he is tying to get into not “who me your cards” but “show me how you deal the cards to the players and I will answer you whatever applies to the game you just invented”. And that is also why I believe he states over and over that N = R. And I think that is true in this sense: if the mapping of rationals to naturals is accepted, that means you assume that the infinite process of creating “listing” all fractions can lead to “a whole”. If *that* holds, he has a point in that N = R. The fact there’s PI only means that there is 0.1415…. and the fact that there are infinitely small fractions at point in the “pie cuts”, means that 0.5 is must be thought of as 0.50000… and that 0.1415… and 0.500000….aren’t really much different. if you get past 0.50000…to “a whole” (which…likely means you go down on EACH node infinitely in rationals and reals) you also get past “PI” with the tree for the reals. The fact that you can’t imagine 0.5000…. as something that exists in no way means this isn’t supposed to happen. If you assume your listing is complete, you’d eventually (with infinite steps) reach a whole, and should agree that you have either found the closes possible neighbor of 1/2, which is a complication similar to saying you have found the closes possible neighbor of the no integer part of PI.

Now, here’s what I believe. 2^N is a larger infinity. In our representation of PI, infinity is there as a whole and as a part . Can we add up infinity? Think that the integers represent radius-sized chunks of circumferences. But the 0.1415… part comes from a different approach. It’s coming from the units (or “infinitely small pebbles” that add up to 14.15…% as we look for the smallest pebble, infinitely, to find out how many pebbles we need to document the fraction of radius unaccounted for in the integer part). When we do this, we try get to the unity from the “whole” (because we know that there must be an exact number of pebbles that represent the proportion of the “decimal” radius we are trying to account for, compared to the total number of pebbles in the set of units defined by radius-sized wholes). And thus, as we enter the real of combining the world of “whole parts” (integers) with that of “unity” (naturals). As these two worlds try to be bridged you get what’s probably the most argued topic, with both laymen and mathematicians on the two camps.

Additionally:

1) I think also MrX is right that you can map (but ONLY) the decimal part (to not use “fractional part”, but it should be the same) to the naturals.

2) I think that 2^N is a larger infinite and that Cantor was right in that there are “larger infinities

3) That Cantor’s diagonal argument is flawed if his goal was to prove that decimal (non integer) R is larger than N. And that the proof is also flawed in that the diagonal hi specifically sets up by definition is a subset of R and thus he will just prove that his definition can’t deal with the fact that my list is complete, and he is purposefully (but likely unaware) never looking at my full list).

4) That there was good reason to expect that the Greek person that discovered he couldn’t express 2 ^(1/2) be drowned (he introduces a very uneasy feeling of needing but never achieving infinite precision with number systems).

Finally, one way to look at this is to say that the Rationals (let’s say r-Ationals to differentiate them from fractions <= 1) when nominator can be either smaller or larger than denominator, are actually the real target problem, not the irrationals. The irrationals just point to the need for infinite precision, which is needed across any tree that's supposed to be infinitely deep, or infinite naturals that "must" be though as being able to approach "a whole". Another way of saying this is, can you map the natural to the r-Ationals? In though exercises you can convince yourself of anything. But when you ONE thread to be able to complete the process if given infinite time. You can't map the r-Ationals to N, but you can complete the Reals). The reason appears to me that you'd exhaust the naturals trying to complete the integer part of the r-Ationals, or that you'd exhaust the naturals by setting up the process that Cantor used to map the Q, and that you'd also exhaust the Reals in the tree proposed by MrX as well). Since you need infinite "threads" (one thread goes in the dimension of naturals (or integer parts) and the other infinite threads traverse to each natural to break it down to "unity precision" in infinite steps. In other words, each and every "whole" (integer part) in the r-Ationals can be divided into infinitely smaller portions. Since you have infinite naturals (even if you must think of each as finite), each being divisible into infinitely small chunks, you have Infinity (linear) * Infinite (precision – the construction of MrX tree). And all this just means (as an example) that we as humans can deal with or think of the notion of there being infinite radius-sized elements, while at the same time thinking that that infinite number can, when added up, to a certain number (and proportion) of circumferences (divided by 2). This same reasoning would apply and can be translated to express the same for any irrational (or infinitely precise rational we can define).

I tend to make errors during my presentation. It's a long post, and I am not very "precise" and the language will be confusing to people that really know much more (and know the formal language of logic). I am sorry for that. I hope that those errors do not present a roadblock to try to follow the overall presentation. And for those that see any error as making the hole intelligible, you at least have the satisfaction of being right in thinking of one more person as a nutcrack 🙂 In a sense, we all are, and I am in the campus of those that can't be neither very articulate and elegant.

Cheers and good vibes to Uncounts and Counts…and for the blog owner for being extremely respectful to both sides and sharing his thought to continue to explore these issues.

Federico

How about allowing my comments? What are you afraid of? Let others decide for themselves.

http://www.spacetimeandtheuniverse.com/math/4507-0-999-equal-one-556.html#post27247

This is another well written and interesting post. However, there is something slightly troubling about the precept of showing your cards in existence proofs, with the emphasis on slightly. For example, if you told me there exists real numbers that have no English description, where a description is a finite sequence of letters, and I “called” you, you’d be in the uncomfortable position of presenting to me an indescribable number.

I realize this example is not perfectly analogous to the situation of Cantor’s proof, but at the same time, it’s not blatantly obvious what the difference is.

This is a well-known version of the Richard paradox. As long as it’s agreed how to map “English descriptions” to real numbers, there is no problem in presenting an indescribable number: you just run a diagonal argument.

Right! I’m not saying Cantor’s proof is wrong or that Richard’s paradox is completely analogous to the Cantor situation. Though I like the poker comparison as a way of explaining who has to “show their cards”, there are situations where it’s not immediately clear who called whom. For example, Dr. Lipton says if you are a Count, you must give a listing of the reals. But we wouldn’t make this same demand of those who claim there are elements of the absolute galois group of the rationals other than the identity and conjugation. We do demand an existence proof, which of course Counts cannot provide, but we don’t demand a concrete mapping. All I’m trying to say is, the poker analogy is going to get misused, because in math, you don’t always have to show your cards—sometimes you can prove you have the better hand without actually exposing them.

If I were a Count, I would question whether the set Y that was defined in the proof of Theorem 1 is well defined for infinite sets. But I don’t know how I would argue that it is not well defined.

Can any Counts help me?

Cantor’s proof feels to me like the reasoning behind the summing of a series like 1 – 1 + 1 – 1 + … You can decide the answer is 1 or 0 with valid reasons for both answers. The problem isn’t the reasoning, it’s trying to sum a non-convergent series in the first place. Trying to reason about infinities by manipulating them as if they were finite feels like the same sort of exercise.

Me too… Cantor’s thingie sounds to me like a statement about finite-length sets — for every finite-length set of strings, you can construct a string which isn’t in the set, which A) sounds a bit trivial, in retrospect anyway, and B) hasn’t anything intuitively-obviously to say about the naturals or the reals.

Which apparently means either i’m a crackpot, or i’m not entirely comfortable with induction. Thankfully, there are plenty of pointers in the previous blog entry for me to explore the latter option, for which i’m extremely thankful.

…and somewhat redundant.

> Trying to reason about infinities by manipulating them as if they were finite feels like the same sort of exercise.

But it is not.

The analogy does help a great deal in figuring out why mathematicians don’t understand the flaw. They have it set up from the start. The non-mapping is a definition, not a result. There is no need for a proof at all. It’s pointless to look for a mapping since mathematicians have defined said mapping to be bogus by definition. It’s like declaring one day that 2+2!=4. It’s done by declaration, not because of anything inherent in the system.

The irony is that even in this environment, Cantor’s proof is still flawed. It can only find a number not in a proper subset of N of the list given to him. He can’t get to R rows. He can’t get to Q rows. He can’t get to N rows. He can only get to a subset of N rows.

Second, your proof doesn’t work for finite sets. And with infinite sets, Y is in my list because the way you created it can’t possibly go through all sets in P(X) since you use a custom mapping that is known to not be one to one. Why would anyone care that a mapping that is not one to one is different from one that is? I don’t think you realize that you’re using something other than f(x) when creating Y. The difficulty in explaining this is that you want to contradict f(x) from being a one to one mapping when I’m saying you are using your own mapping g(x) as a mapping that is NOT one to one. It’s like trying to prove that f(x)!=x when you assume such a function exists and then turn around and use it as f(x)=x+1 in your proof to show a contradiction. Sorry, but those proofs don’t impress me much. As another example, would the infinite prime proof work if you declare that you have a list of primes, but then used them as if they did NOT have primes in them, would the proof hold up? No, of course not. So when your proof does essentially the same thing, why should I bother with it at all?

Third, your analogy is basically saying that one must show all their cards, but that R is defined against this very notion when using Dedekind cuts. IOW, with N, you can “show your hand” up to a point and the rest is implied. With reals, Dedekind cuts don’t work that way. So you’re actually imposing arbitrary rules (aka, forcing different generators) to obtain the result that you want instead of seeing if the system imposes this as a result of its other rules. All I ask is to let all players play by the same rules. Let them use the same generators and you’ll have no choice but to map them one to one because the numbers will be produced in pairs.

Finally, the “show your hand” notion doesn’t work. Map using f(e) the even numbers, call this E, to N. Now compare the elements by digit between e and f(e) and none will match. What’s more, there are representations in N not found in E. Do you see the problem? Mappings are fleeting. They only map in very specific ways, not globally. Cantor uses two different mappings and then conclude they are different. Well, DUH! It’s no more impressive than saying that f(e) doesn’t exist above. It’s a completely bogus interpretation of the result. If Cantor gets a new number, it is proof that he only sampled a proper subset (just like the representations of E are a subset of N). It is NOT a proof that |R|>|N| any more than |N|>|E|.

Mr X. I make an offer. If you propose to me a mapping f — it can be any mapping, of your choice — from N to R, I promise not to declare it bogus by definition. What I will do is tell you a real number x that is not equal to f(n) for any natural number n.

If you don’t believe that I can do it, then try me. If you do believe that I can do it, then we basically agree, since that’s all I mean when I say that the reals are uncountable. I just mean that whatever f you give me I can find some real that isn’t equal to any f(n).

If you think that somehow that game is unfair, then the right moral to draw is not that the reals are in fact countable. It’s that mathematicians are talking about this “unfair” game when they say that the reals are uncountable. So if you agree that mathematicians win the unfair game, then your only disagreement is about whether the game itself is worth paying any attention to. If you think it isn’t, then you’re missing out on some interesting mathematics, but I’m sure you can live with that sacrifice.

Dear Tim,

I’m not MrX, so you do not have to answer.

The mapping I suggest is fill in infinite square with random bits with probability 1/2. It is not one to one mapping, but many to one. Then we have countably many rows – indexing reals, and the columns will represent a real number in binary representation 0.fill in column here. If we wish to exclude explicitly the fixed on paper Cantor proof we can exchange rows such that the first row will be 0.1 and the rest will have 0 on the diagonal. We fix the list, do you think it would be fair if given the algorithm to construct the number not in the list we can rearrange rows to show that the constructed number is in the first row? If it is fair then construct any number. Given that number r we start the process with the most significant digit. If the first digit is the same as in constructed one do nothing, otherwise find the first row that has correct digit, and swap it with the first one. Remember this row. Induction step. Suppose that we have constructed number r and the first row coinciding up to n-th digit, and we have looked up m rows so far, than there exist a row below m that coincides with row representing r up to n+1 digit, since there are infinite number of rows below m with exactly same n digits, and half of them has n+1-th digit equal to 0 and half of then equal to 1. By induction any number r is in the list.

I taught in the school that infinity is a limit process (may be a did not get it right). If I follow Cantor, he tells me that I’m missing the last infinite digit. That has no practical consequences whatsoever, but give convenience for some interesting math. So for practical purposes it is as convenient as Newtonian mechanics. and as such there is should be mapping from count world to uncount world, it may be as complicated as mapping from quantum mechanics to the classical one.

This doesn’t make any sense anyway, but you can’t use randomness.

Ok, let’s do it explicite.

We start with infinite square of binary values

Filled at random. Then we construct mapping f: for natural number n we take row and construct real number .

Claim. Any real number is represented by the list.

Proof. Write . We need to show that by rearranging rows the row representing r can be placed first.

1. Find the first row with , swap it with the first row.

2. Induction step. Suppose in the first row we have binary string than find the row with k+1 coinciding digits, e.g. Find the row m’>=m that have the following form and swap it with the first row. Such row always exists since there are infinitely many rows with this properties by construction.

Therefore by induction we can rearrange rows that the first row will represent desired r. Q.E.D.

OK, let me prove something similar by your ingenious method. Let me list just the real numbers in (0,1) with decimal expansions that terminate. I’ll take the nth term in the list to be the reflection of n in the decimal point. For example, the 13th term in the list is 0.13. I claim that all real numbers are included in that list. I’ll prove it inductively. Let r be a real number. Then I first find a number on my list that shares its first digit with r and I swap it with the number that is currently first. Then I find a number on my list that shares its first and second digit with r and swap it with the number that is currently first. I keep on doing this. Therefore, by induction I can find a number with a terminating decimal expansion that is equal to r.

Tim, this version was in the previous post, some people say it is not convincing to them since this numbers terminate, and they assume that real numbers should have infinite length strings. Instead of sarcasm, you may tell what is wrong with the proof. Or what is the place of this logic in the current math. I do not mind it be in the garbage can, especially, for good reason.

By the way I do not see where in your proof the decimal expansion terminates. At the infinite step, again at the last digit? I do not really see where it terminates.

Let’s call the the i-th digit approximation of r, than according to your construction sequence is convergent, and . Where it is wrong?

OK, let’s carefully distinguish between two statements.

1. There is a list of numbers such that every real number in (0,1) is a limit of numbers in that list.

2. There is a list of numbers such that every real number in (0,1) is in that list.

Your proof correctly establishes the first statement. The second statement is false.

I should point out that your use of induction is a bit strange. Could you set it out formally? Statements that one proves by induction take the following form: for every natural number n, some statement about n holds. What is that statement in your case? Is it by any chance, “There exists a number in the list that agrees with r in the first n digits.”? If so, then you correctly establish the following: for every n there exists a number in the list that agrees with r in the first n digits. What you do not establish is this: there exists a number in the list such that for every n that number agrees with r in the first n digits. A statement of the form “for every A there exists B such that P(A,B)” doesn’t imply the (much stronger) statement “there exists B such that, for every A, P(A,B)”.

You are saying there is no infinite natural number, but comfortable with checking infinite digit (nonexistent by the first part of the sentence) in Cantor proof. This is totally not obvious in Cantor proof.

I’m saying 1) 0.1… exist in the list

2) Induction step if 0.r1 r2 … rn …. exist in the list, I will find o.r1 r2 … rn r(n+1) …

And then I apply induction.

This will be my last response.

I do indeed say that there is no infinite natural number. I also say that while a real number has infinitely many digits, it doesn’t have any infinite digits, or any digits infinitely far along. There are infinitely many natural numbers, and they are all finite. No paradox there.

However, perhaps all we are facing is a terminological dispute. I say that there is no one-to-one correspondence between

finitenatural numbers and real numbers in (0,1). Would you agree with that? If so, then our only point of disagreement is on the question of whether there are infinite natural numbers. Or perhaps you deny that a real number can have infinitely many digits. If so, then I’m prepared to grant that real numbers as you conceive them are countable. It’s just that your definition differs from the standard one.I think I completely agree with your comment.

Mr X wrote:

>…(aka, forcing different generators) …

and

> …use the same generators…

Please provide a proof using the language of set theory (ZFC for concreteness) that every (infinte) set has a generator. Otherwise you are just adding an axiom which may not be consistent with the rest of the ZFC axioms and which I suspect is equivalent to the assumption that every set is countable.

does Mr. X invoke a negation of the Axion of Choice? I am looking at posts of the discussion in the previous Blog, Mr X’s argument about generators is very much about ordering of infinite sets.

So I had a look at this link from the a Wikipedia entry on the :

Axiom of Choice , according to which

“There exists a model of ZF¬C in which real numbers are a countable union of countable sets”.

Does this comment help Mr. X?.

Is the notion of the power set of an infinite set well-defined? Or could someone argue that Cantor’s theorem, as presented above, shows that introducing such a concept Creates antinomies in set theory?

Also, the proof as presented above is incomplete. We have to add that if f(x)={x}, then Y is the empty set, and while the reasoning producing the contradiction no longer applies, Y is nevertheless a set in the power set of X that is not in the range of f.

By axiom, yes.

With a finite set, “counting” the power set has some features not there with infinite sets. For example, with a finite set, the subsets that have exactly one element exhaust the set. In contrast, in the power set of natural numbers, for any specified N, we can place the subsets of natural numbers with 0,1,2,…,N elements in a one-to-one onto mapping with the natural numbers. it is precisely the infinite subsets of the natural numbers that present a vulnerability to the Cantor argument. But certainly, it is a not-trivially dismissed doubt to ask whether every single infinite subset of the natural numbers has an **effective** procedure to determine whether a number m is in the set or not. After all an enumerable number of algorithms can produce only an enumerable number of infinite subsets of the natural numbers. If I cannot effectively determine whether an infinite subset of naturals contains y or not, how does the theorem 1 presented above proceed?

I should add, in what sense can a set be said to exist, if one cannot effectively tell whether a element is or is not a member? One would conclude that only an enumerable number of infinite subsets of natural numbers actually exist, the rest are figments of our imagination.

All of mathematics is a “figment of our imagination”…

When one asks the question “is there a bijection from the naturals to the reals”, generally they mean in the context of ZFC. You are free to invent your own formal system in which there is a bijection, but that isn’t answering the question given.

That being said, when you ask if there is a power set for an infinite set, the answer is trivially yes. The axiom of power set in ZFC states that every set has a power set. There is no possible way to refute this, there is no alternative explanation. If you disagree that there is a power set for each set, then you are not working in ZFC, and therefore it will not be possible for you to prove or disprove Cantor’s theorem, which is stated in the context of ZFC.

Isn’t it true that Cantor’s proofs precede the formulation of the ZFC axioms? Therefore perhaps a correct statement is that the power set axiom was added in order to make Cantor’s proof work.

I am an Uncount, but am very sympathetic to John Sidles’ view that we have to explore the “right” axiom set for each purpose.

@Arun

Yes, Cantor’s proof preceeded the ZFC axioms in their final form, but it doesn’t rely on them, per se. It is just a convenient formal system that most mathematicians work with. The one’s that don’t are usually completely cognisant of it and like to keep their options open. The real ‘meat’ of ZFC is in axioms that provide us with vastly larger new sets than we had before. Whereas Cantor’s theorem can be proven in the following fragment of ZFC (this was shown by Lawvere):

1) There is a category of sets and functions

2) Cartesian products of sets exist, and there is a 1-point set

3) Function sets exist

4) Some compatibility conditions between 2) and 3), which aren’t shocking, but for the moment irrelevant.

This is enough to prove Cantor in a more general form, and once one admits the existence of a 2-element set (which with 1)-4) above implies the existence of a power set), in the classical form. No Axiom of Choice is needed, nor are the ‘big guns’ axioms of ZFC.

And apparently one can even do without 3) and 4), and hence power sets, but the statement of the theorem is a little bit different.

Arun, to extend your remarks, to the extent that mysteries confront us when we work with the set of real numbers, yet more severe mysteries confront us when we work with the set of formal languages.

Because (for example) the real numbers are ordered by an algorithm that is natural, concrete, deterministic, finitistic algorithm (that is, by comparing decimal expansions place-by-place) — an algorithm that is endorsed by Counts and Uncounts alike.

Whereas in striking contrast, it is natural (for students and non-experts in particular) to naively conceive the set of formal languages as being similarly endowed with a natural order that is induced (for example) by the runtime exponent of the fastest Turing machine that recognizes each language — and yet there is no such natural ordering (even in principle).

AFAICT, this means that a primary object of study in complexity theory, namely the set of formal languages that are uniformly recognized by Turing machines, has the same cardinality as the reals, and therefore the same Cantorian mysteries) … but has no natural ordering associated to measures of computational complexity — and in this sense the set of formal languages is substantially more mysterious than the set of reals. And this lack of natural run-time ordering poses a major obstruction to experimental investigations in complexity theory (in the style of Doron Zeilberger).

These issues are obliquely mentioned in recent texts like Oded Goldreich’s

P, NP, and NP-completeness(2009, see Section 2.1: Efficient Computation) and Sanjeev Arora’s and Boaz Barak’sComputational Complexity: a Modern Approach(2009, see Chapter 1: The computational model — and why it doesn’t matter), and they are directly addressed in Juris Hartmanis’ monographFeasible computations and provable complexity properties(1978). In particular, it was Hartmanis’ vision thatConsonant with Hartmanis’ point-of-view, the algorithms that simulationists employ typically

areendowed with decidable runtime exponents; thus pragmatically there exist subsets and that are runtime-ordered, and that encompass many/most (perhaps all?) of the algorithms that the STEM enterprise depends upon. In this respect a formal proof of separation of from would have practical importance comparable to a separation of from .In summary, there is (IMHO) very little likelihood that in coming decades the Uncounts will abandon Cantorian axioms, for the pragmatic reason that Uncounts can pursue Zeilberger-style experimental mathematics with considerable success, in consequence of the natural well-ordering of the reals. But there is a substantially greater possibility (IMHO) that in coming decades complexity theorists may modify their conception of formal languages — perhaps even restricting their definition to a set that is countable and runtime-ordered — with a view toward

increasingthe theorem-proving power of complexity theory. And this Hartmanis-style restriction would be a substantial vindication of the Count point-of-view.John, I have been following your questions about the decidability of running time bounds for polynomial-time bounded Turing machines. A few comments:

1) It’s unfair to say that languages cannot be ordered by the running time in which they can be recognized. The famous deterministic/nondeterministic time hierarchies do establish that there is a strict ordering on formal languages with respect to this time measure. Weird things only happen if you are concerned with linear speedups. I understand that when you say “ordering” you mean a decidable one, but claiming that no ordering exists is confusing and makes formal languages sound way stranger than if you said that formal languages do not possess a decidable ordering w.r.t. time.

2) There is no real reason to distinguish between formal languages and real numbers. The ordering on real numbers is computable, provided you can *compute* the numbers. It’s easy to describe a real number such that computing the digits is undecidable.

3) The fact that running time bounds in general are undecidable is no more a hindrance to the design of algorithms than the incompleteness theorems or the computational complexity of proving theorems is a hindrance to the development of mathematics. I share the view of prof. Gowers here: the algorithms we design and the problems we study are what we see as “natural”. This is the heuristic way in which humans weed out the undecidable/intractable problems from consideration.

4) The fact that running time bounds, even polynomial ones, are undecidable does make one wonder if this has anything to do with why P vs NP is so hard. But the fact of the matter is, if we restrict P and NP to P’ and NP’, to use your notation, it doesn’t get any easier, at least at present. We just lack methods to prove lower bounds in powerful models of computation. To my understanding, there is no known method that says anything interesting about P’ and NP’ and doesn’t say the same thing about P and NP.

I do like the point that the undecidability of time bounds seems to make experimental complexity theory ala Zeilberger problematic. Interestingly, that’s a point that Zeilberger seems to miss (look at his opinion in response to Avi Wigderson’s Pvs NP lecture and Scott Aaronson’s response to the opinion). Another problem is that the design space of algorithms, even for restricted models, even for bounded size inputs, is humongous: we’re dealing with double exponentials and above. We do not have any understanding of computation that’s powerful enough to let us reduce lower bound questions to questions about well-formed structures that allow efficient heuristic searches. Maybe that should receive more attention, but I think it does receive attention. For example, the algebraic geometry approach to lower bounds does produce some speedups in computer-checked lower bounds for matrix multiplication of small matrices. But still, no *new* lower bounds have been proven even with the speedups.

Sasho, it’s tough to respond to a post as well-written and thought-provoking as yours … especially because I agree with pretty all of your post’s substantive points. So let’s “up the ante” (increase the bet) by imagining that we are playing a higher-stakes game, namely the “Multiple-Choice Exam” game (henceforth MCE) that is described in Terry Tao’s column “P=NP, relativisation, and multiple choice exams.”

We’ll begin by reflecting that Lipton’s “Show Your Hand” game (henceforth SYH) ends in a stalemate whenever it is played by finitistic yet possibly unscrupulous players, by the following equilibrium strategy: Count shows a finite portion of his list, Uncount shows a portion of his number, Count shows a larger part of his list, Uncount shows a larger portion of his number; it’s clear that this undending (and thus boring!) SYG strategy (when played by two unscrupulous players who both cheat, but only undetectably!) yields no win for either side.

Can we imagine,

even in principle, a similarly finitistic implementation of Terry Tao’s MCE game? That is, a game played by players who perhaps may be cheating, but if so, are cheating only undetectably and with finite resources? Without going into detail, I hereby postulate that the presence of oracles in the MCE rules obstructs any finitistic and verifiable implementation of the MCE game, and it is in this well-posed sense that the sets of languages associated to the complexity classes and are more “wild” than any of the sets associated to SYH.That is why it seems reasonable to regard the ZFC axioms as being reasonably well-suited for playing finitistic games like Cantorian SYH, but perhaps ZFC is less well-suited for playing “wilder” complexity-theoretic games like Terry Tao’s MCE.

Sasho, speaking as someone who admires the clarity of the answers that “Sasho” (is that you?) regularly posts on TCS StackExchange, perhaps you might consider writing an essay analyzing how Tao’s MCE game might be implemented via finitistic Lipton-style SYH resources, and offer that essay as a guest post to Dick and Ken?

Now,

thatwould be aGödel’s Lost Letter andpost that plenty of folks (well me anyway) would read with immense interest and enjoyment! 🙂First, I am no count 😉

But for proving the existence of an object it seems somehow too rigorous to me to require to give it explicitly. For example, let me claim that there is some rational number in the set {e+pi, e-pi}. I can not “show my hand” (pointing to one of these two numbers), but there is at least one rational number among them since otherwise 2e=(e+pi)+(e-pi) would be rational.

So asking a count for a enumeration seems not to be the right way to me. The right way should be to point to the flaws in their proposed proofs.

“…there is at least one rational number among them since otherwise 2e=(e+pi)+(e-pi) would be rational.”

I don’t follow the logic here. Are you asserting that the sum of two irrationals is always rational? Or something else?

Sorry, wanted to say “… some irrational number …”

Now I don’t even know what the claim is any more.

The claim is that there is at least one irrational number in the set {e+pi,e-pi}.

Then I repeat the preceding question — I don’t follow the logic here. Are you asserting that the sum of two irrationals is always rational?

Sorry for the confusion, I’ll do once again:

Claim: There is at least one irrational number in the set {e+pi, e-pi}.

Proof (by contradiction): Assume the claim is false. Then both e+pi and e-pi are rational, so 2e=(e+pi)+(e-pi) is rational too. Contradiction.

Thank you for the clarification, I appreciate it.

I too am no count! But in teaching mathematics (as in teaching any subject) we should have more respect for diversity than simply dividing a class of students into Counts and Uncounts. Students who accept ZFC, but have trouble following the steps of Cantor’s proof, need patient tutoring (as Tim Gowers and other have been so admirably providing to Mr. X). Yet isn’t it true, that students who instinctively seek alternative axioms to ZFC present a

muchtougher teaching challenge? One reasonable syllabus is this:Class I topics:Students who plan to study the ordinary infinities of real and complex analysis and smooth manifolds should just accept ZFC and continue their studies.Class 2 topics:Students who plan to study the wilder infinities of point set topology should thoroughly master every aspect of ZFC.Class 3 topics:Students who plan to study the utterly wild set-theoretic properties of complexity classes — sets that subtly blend infinities, undecidabilities, and oracles — should thoroughly master both every aspect of ZFCandof alternative axiomatic formulations of mathematics.The basis for this syllabus is purely pragmatic: several decades of experience have yielded solid empirical evidence that ZFC is the “right” axiom set for Class I and II mathematics. And yet it is entirely reasonable

notto infer that ZFC provides the “right” axioms for Class III mathematics in general, and complexity theory in particular, because the sets of complexity theory are even wilder in their structure (as Hartmanis’ work shows) than those of point-set topology or any other branch of mathematics.So if it should happen that research in coming decades shows us that ZFC is

notan axiom-set that is particularly well-suited for doing complexity theory … for example if it turn out that isnotprovable in ZFC … then so much the worse for ZFC, and perhaps complexity theorists will lead the way in finding alternative axioms. That would be fun, and good for mathematics too! 🙂I don’t claim to have an adequate expertise on ZFC, and so not in a position to categorize myself as Count or Uncount.

However, I have a very basic question in set theory– how can the set N be infinite when its members (each natural number) are all finite. This seems to me a paradox.

I suppose there is some axiom explaining this situation.

“[Tim Gowers]- There are infinitely many natural numbers, and they are all finite. No paradox there”

Javaid: I’m not sure where you feel the paradox here is? I think the ‘five’ trick is handy here; just replace the word ‘infinity’ by ‘5’ in your question:

‘How can the set ‘5’ have 5 members when each of its members has less than five members?’

Beyond this there are some surprisingly subtle questions lurking, namely precisely what ‘infinite’ means. There are two standard definitions – ‘a set is infinite if it isn’t finite’ (which is to say, it can’t be one-to-one mapped onto some finite number), and ‘a set is infinite if it can be one-to-one mapped onto a proper subset of itself’ (this idea is called ‘Dedekind-infinite’), and while the natural numbers are infinite under either definition, there are mathematical models where there are sets that are infinite by the first definition but that don’t have one-to-one mappings onto a proper subset.

You’re essentially right, though, to say ‘I suppose there is some axiom explaining this situation’ – that axiom is, unsurprisingly, called

The Axiom Of Infinity, and at its heart it states ‘the set of all natural numbers exists’. The other axioms of ZF aren’t enough to show this, because they all take finite things to other finite things, so we need this axiom to tell us thatsomeinfinite thing exists.Once you know that, then it’s relatively straightforward to show that the natural numbers are infinite by the first definition; if they were finite, then there would be some finite number n so that the naturals could be mapped one-to-one onto n. But then the subset of the natural numbers {0, 1, …, n} could be mapped one-to-one onto n, and the pigeonhole principle forbids this because this subset has n+1 members. It’s straightforward to show the naturals are infinite by the second definition, too: consider the set of all even numbers {0, 2, 4, …}. This set is a proper subset of the naturals (for instance, ‘1’ doesn’t appear in it), but it can be mapped one-to-one onto the naturals (by the obvious mapping 0->0, 2->1, 4->2, etc).

Ans “… at least one irrational number …”

Suppose I ask you whether or not it’s raining outside. You go and look, and then we have the following discussion:

You: Yes, Richard, it’s raining outside.

Me: Uh… according to what paradigm?

You: What? You asked whether it’s raining, and I am telling you that it’s raining. Rain is falling from the sky.

Me: Look, until you specify the paradigm you’re working with, you may as well be speaking in Greek.

You: God damn it, my paradigm is the English language! [Opens a dictionary and points at the word “rain”] See? It. Is. Raining.

Me [looking blanker than ever]: Yes, I’m not deaf you know. I hear the words you’re saying, and I do recognise them as English. I’m not stupid. But you still haven’t specified any paradigm whatseoever which will allow me to draw any conclusions about the current state of the weather.

You: Right. [Grabs me by the scruff of the neck and drags me out into the garden] Do you know why your head feels wet? And why you can’t see properly through your glasses? Because it is raining. That is why.

Me [sitting in a puddle, soaked to the skin]: Ok, but under what paradigm is this?

Etc.

That was how I felt arguing with Mr X about his “generators”, on the previous thread. As far as I can tell, he has imported a notion from somewhere else, which was totally absent in the orginal question. He then declares this to form an absolutely insuperable obstacle to all versions of Cantor’s argument, without giving any account of what it means, or what would be required to address the problem it presents.

If Mr X is going to rely on the theory of “generators” again in this thread, he first needs to provide a formal mathematical definition of what it means to say that “A is a generator of B”. Then maybe we can understand where the difficulty lies.

I’ve read a lot of arguments against Cantor’s Theorem and I’ve never been convinced by any of them that Cantor’s Theorem is invalid.

However, the Counts’ arguments did help to convince me that infinity can’t possibly exist. Here’s my proof of this: There is no greater number than infinity, if it exists, since it is greater than every other number. But by Cantor’s Theorem, there are different levels of infinity. Contradiction. Hence, infinity can’t possibly exist.

I think this is probably what Counts are really thinking when they see Cantor’s Theorem. They just don’t like its conclusion.

I looked at your proof, and got the strange realization that formally it applies just as well to, say, the number 5 as to infinity. The parts that according to ZFC are true of infinite cardinal numbers, are also true of numbers >= 5, and vice versa.

“There is no greater number than infinity, if it exists, since it is greater than every other number.”

Note that infinity is not a number, per se. Infinity does have the property that it is larger than every real number. Your “proof” is making the assumption that each “different level of infinity” as you call them are in fact real numbers. This does indeed prove that you can’t pinpoint any infinity on the number line, but it doesn’t say anything about the existence or nonexistence of infinite ordinals, such as |N| or |R|.

> There is no greater number than infinity, if it exists, since it is greater than every other number.

What does it mean for a number to be greater or less than infinity?

Operations from N does not apply to cardinal numbers.

Just as it turned out to be fruitful to doubt Euclid’s Fifth Postulate, I think it may be fruitful to cast doubt on the axioms that are stood up (e.g., ZFC Power Set axiom) to buttress Cantor’s argument.

Actually, Euclid’s Fifth Postulate was never “doubted”. For one thing: it doesn’t make any sense to “doubt” an axiom. You can only doubt its usefulness. Only, mathematicians used to believe that Euclid’s Fifth Postulate was a theorem. It became an axiom when they eventually discovered the non-Euclidean geometries. Similarly you can do away with the axiom of infinity, or just discard the power set axiom, just as you like. As a result, of course, Cantor’s argument will melt away.

I’m not a Count per se (my objection has always been that Cantor’s proof merely proves that the set of computable reals is not recursively enumerable and nothing more – maybe the reals are indeed uncountable).

If someone’s expected to show their hands, it’s the Uncounts. How many uncomputable reals have been named? How many such reals can be plugged in the “proof schema” that Gowers describes above and a deduction can be expected to work?

> If someone’s expected to show their hands, it’s the Uncounts.

I’m afraid I’m unable to raise my hand more than a finite number of times. Hence the axiom of infinity.

> How many uncomputable reals have been named?

I’m afraid the number of available names is countable. Hence the axiom of power set.

Maybe these axioms don’t reflect accurately your own vision of the world, but the problem is… “raising one’s hand” is a concept Cantor forgot to define. I guess that was due to his genius.

The axioms are irrelevant. As I said above (and nobody has ever seemed to disagree with this), the proof works only with numbers that can be named. If you can’t inspect the number, you can’t construct the diagonal.

I am done with this thread.

I do disagree strongly, like all those who didn’t bother to reply. Relevancy doesn’t belong to math but to the applied sciences.

Note that RISC does not mean that the instruction set is reduced in numbers, but rather than each individual instruction carries a reduced workload vis-à-vis a comparable CISC instruction.This is not quite correct. Patterson and Ditzel’s paper explicitly talks about removing addressing modes, as opposed to just simplification and normalization. It also talks about “the number of instructions” of CISC, not just their complexity. They also highlight that compilers use only a small portion in numbers of the instruction set.

Reading the article it is pretty clear they had in mind both a simplification and the concomitant reduction in the number of instructions, for example by eliminating legacy instructions.

I think it would be more accurate to say that “notice that reduced in RISC refers both to reduced numbers and reduced

complexityof the instruction set.”/nitpick

This has been an outstanding

Gödel’s Lost Letter andtopic precisely because both theUncountandCountpoints-of-view have much in their factor.When we construe the

Uncountpoint-of-view broadly it amounts to “Prove strong theorems by correct proofs from well-posed axioms” … which is good adviceprima facie.When we construe the

Countpoint-of-view broadly it amounts to “Conceive improved axioms with a view toward enabling stronger/ broader/ deeper theorems” … which too is good adviceprima facie.The Uncount point-of-view can be systematically learnt by studying “yellow” textbooks and solving problem sets. It’s harder to learn the Uncount point-of-view (for which by definition textbooks haven’t yet been written, no axioms being available) but inspiration can be gained by studying the history of mathematics (and physics and engineering), and from tackling practical problems. This sort of inspiration provide what von Neumann called:

From a purely engineering (and purely hopeful) point-of-view, we can look forward in decades to come \emph{Count/ Uncount} collaborations in which:

• regenerative medicine that is

directedrather than spontaneous,• molecular and systems biology that is observational rather than experimental,

• quantum imaging technologies that sustain the

yearly doubling cadenceof the past five decades,• quantum dynamical frameworks that are

Kählerrather than Hilbert, and• complexity theoretic classes that are

verifiablerather than oracular.Each of these advances will require contributions alike from

Count-minded researchers (in reengineering and repurposing starting axioms and assumptions) and fromUncount-minded researchers (in rigorously working through the implications of the revised axioms and assumptions).That is why narrow arguments to the effect that “[Only] the

Uncountstyle of theorem-proving is correct!” or “[Only] theCountstarting axioms are correct!” regrettably overlook (IMHO) the marvelous opportunities that open to us whenbothcommunities prosper and collaborate.And so, my appreciation and thanks go to all who have contributed to this fine discussion! 🙂

I may be overthinking this one, but I suspect that this post is the fifth in a series of posts that generates a royal flush in hearts.

If that is not the case: Never mind.

If that is the case, I am invoking Rule 7 of the Showdown to buy some time while I muse over declaring my hand:

“If there is a side pot, the winner of that pot should be decided before the main pot is awarded. If there are multiple side pots, they are decided and awarded by having the pot with the players starting the deal with the greatest number of chips settled first, and so forth.”

It feels like most of the confusion I’ve seen in the various comments to both this post and the previous one (as opposed to the various fascinating questions relating to constructibility, etc.) has less to do with Cantor’s proof than it does with the very notion of real number itself. I wonder if a lot of this is because real numbers are the first ‘essentially infinitary’ objects that people are likely to come across; individual naturals and rationals, etc, are all finite at core, and while ‘the set of all naturals’ is ostensibly an infinite object, for most non-set-theorists it can be worked with by dealing with individual numbers and thus left in the realm of the comfortably finite. By contrast, of course, each _individual_ real is an inherently infinitary thing; it’s a map from N to 2 (or N to N, or… pick your favorite definition of ‘real’), and not just a map from some finite initial section of N to 2 (the ‘binary tree’ that showed up in the previous post) but a map from _all_ of N. That makes the set of all reals, then, a collection of inherently-infinitary objects and throws a mental block in the way of people who, if not expecting a collection of elements to be readily comprehensible, at least expect individual elements _in_ the collection to ‘behave’.

My hypothesis is that it’s more a trait of someone who resists the very idea of a “this is impossible” result. If you google for the person who previously argued for the branching-tree theory on another site, then you’ll find that they also dispute the undefined-ness of division by zero, etc.

While googling the term “infinity”, I was reminded of a picture of a message board next to a small, rural church.

The message board read: “Google does not have all the Answers.”

Every real number on the list will have an equal number of 0’s and 1’s (since the requirement is that 0’s are just as likely as 1’s). Clearly, the set of real numbers include numbers that do not have an equal number of 0 and 1 digits (in fact, “most” would not) – and therefore a “large” number of reals would not appear on this allegedly complete list of real numbers.

For example, would a Liouville number:

0.110001000000000000000001000…

ever appear on this list? No, because as we sample more digits, the 0’s become an ever increasing portion – instead of converging to be equal to the number of 1’s.

Actually “most” would, as real numbers with “unequal” numbers of 0’s and 1’s (in the sense of limit fraction) are non-normal, and the set of non-normal numbers has Lebesgue measure 0. In particular the normal numbers are still uncountable. The set of real numbers with “unequal” numbers of 0’s and 1’s is also uncountable, though.

Let’s begin our story with this statement from the Queen of Hearts Post (What If Cantor’s Proof is Wrong?):

“Cantor’s proof is correct, but if you have trouble understanding it, or know it is wrong, please keep reading. Please. I would like to engage you.”

Follow the “Proof” pointer to this statement:

“Let T be a set consisting of all infinite sequences of 0s and 1s. By its definition, this set must contain not only the sequences included in S, but also s0, which is just another sequence of 0s and 1s. However, s0 does not appear anywhere in S. Hence, T cannot coincide with S.”

Say What?

The proof just contradicted itself:

“Doesn’t (All infinite sequences of 0s and 1s = Every possible permutation)?

How did he pull that diagonal rabbit out of his hat?

Cantor put us in a square box and then used the diagonal to create a rectangular one.

Throw in your 2 cents worth: Why not use infinity as an exponent?

Fast forward to the current Ace of Hearts Post:

“With a little technical work a Count should be convinced that a bluff on (2^N) is equivalent to a bluff on (R). Thus the Count must admit that one can never have the cards to win a showdown that the reals are countable, and by “never” itself, should come on board that they are uncountable.”

Sounds like those no-count Counts are in big trouble now.

Flibbertigibbet. Maybe, he just took a shot across my bow.

Throw in another 2 cents worth: Give me a minute, I am thinking.

What am I missing other than a whole lot of technical work?

Current Picture: Royal Flush in Hearts on the table. Two functions in the hole, X and Y.

Big Picture: countable = manageable.

Googled “ordinal” and saw the picture above this caption:

Representation of the ordinal numbers up to ωω. Each turn of the spiral represents one power of ω.

Should have picked on that earlier from the Ten of Hearts Post (Empirical Humility).

They already use the “big ordinal” as an exponent.

Is the universe rotating?

Got to go, but still thinking.

In the meantime, here are my hole cards and something to think about, if you haven’t thought about it one way or the other already:

Let (a,b) be an unordered set of points on the same line:

X(a,b) = 1, if a = b, otherwise, X(a,b) = 0

Y(a,b) = 0, if a = b, otherwise, Y(a,b) = 1

Same line, different dimensions, different identity functions; maybe.

“Cantor’s proof is strange. It is short, brilliant, important, and yet not believed by some. I find this intriguing: what makes this proof so disputed? What makes it the most discussed proof on the web? In short why is it so hard to believe?”

On one of many philosophical levels, whether or not Cantor’s Proof is right or wrong is not as interesting as the kind of discussion it generates about what we choose to believe. Philosophers of Science have to thread the needle between ambiguity and ambivalence. Therein, lies one challenge.

A more pragmatic answer comes from the Jack of Hearts Post (Whose Complexity is It Anyway?):

Given an emerging “wicked” problem with cardinals, Cantor may have found a fiendishly simple solution using ordinals. Just like Ike, he enlarged the problem.

Folks like Kronecker and the Church Lady may claim he was dancing with the Devil. If angels dance on the heads of pins and Maxwell’s Demons are doing their thing in space, who knows what lurks on the number line?

Be a “fin” or an “infin”; can we agree there is only one string of all ones and one of all zeroes in the world of permutations?

* Some technical details about the Jack of Hearts metaphor for those who do not care to play poker:

1. The Jack of Hearts is a one-eyed Jack (profile rather than frontal view of the face). Amateurs use it as a wild card sometimes. In that sense, it is a jack of all trades like the chief of operations.

2. In the picture, the Jack of Hearts is part of a Royal Flush. In professional poker, it is an unbeatable hand. In amateur games, it can be beaten by five of a kind, if the dealer has declared a wild card. Purists do not like wild card games.

3. In Texas Hold-em, the cards would be laying on the table for everyone to see and everyone can use them with two down cards “in the hole” only they can see. Don’t know much else about Texas Hold-em.

By comparing a proof with a game like poker, you automatically introduce a constructivist bias in the question posed: “Do you believe it or not?” Games are finitist in essence, so Cantor’s proof inevitably appears as irrelevant in this context.

I suppose if one wanted to see yet more discussion on an issue like this, you might simplify things even further and discuss the notion that 1 = 0.999…. The algebraic proof feels vaguely similar to me (my non-math partner just called it “elegant and delightful” on seeing it for the first time), tends to generate similar criticisms, and is subject to the same “show your hand” counter (if you think they are different, then exactly what is that nonzero difference d?).

For something so disputatious, it might be helpful to very explicitly lay out the definition (of real number decimal expansion) and present short numbered argument steps, so as to focus discussion more finely, as I did over on my math blog: http://www.angrymath.com/2011/11/arguing-infinite-decimals.html

haha funny,

a set-believer and cantor sectarian asking for showing ones hand, that is what i called forward defense. you asking the other one, what you neverever did, and what you never could: show me your empty set, you infinity, sorry your infinities, your funny finished unfinished what so ever…yeah well: show me YOUR hand!

hello? anybody out there? you can´t , you have only your lousy axioms of impossible states, where you can ALWAYS hide YOUR cards.

you are allowed to construct a new number, but the other side has to keep still? why? these are doublestandards, nothing else, its a dumbsmart version of the hare and the hedgehog. and you are of course not the rabbit, right?

i child can tell you, whats wrong with your biased cards, mister pokerface. but thats not the point.

by the way, i am finding the countability of infinities exactely that interesting as the question how many angle fits to the point of a needle. (this was a problem of several of your predecessors).

so this is rather not a statement about what is wrong or what is right. i think talking with cantorian is like talking with marxists, its impossible, its a closed system of folie a deux…..

and i thought that mathematics is the last area of real truth, but its in fact a horde of the hardest believer ever. even the contrarian are not better, its the choice between the devil and the deep blue sea.

regards

ps: your hand please 🙂

Not sure if you are trolling or just acting ridiculously stupid.

Anyway.

> show me your empty set

Axiom of empty set

> you infinity

Axiom of infinity

> you have only your lousy axioms of impossible states

I am not sure what states are you talking about, but axioms are not lousy. In fact, they are quite nice and useful.

> i am finding the countability of infinities exactely that interesting as the question how many angle fits to the point of a needle

….

> so this is rather not a statement about what is wrong or what is right

A statement about uncountability of has been proven within ZFC, which means that it’s true (assuming that a logic system is sound).

+1

“by the way, i am finding the countability of infinities exactely that interesting as the question how many angle fits to the point of a needle.”

For clique of size n, n-1 angles.

okay:

axiom of empty set:

wikipedia

“there is a something such that no something is a member of it.”

this is just utter nonsense, but yeah, you know a something that is different, okay, fine. i´ve never seen such a something nor is it even possible as an abstract concept: you try to define a bottom in the middle of nowhere. you try to stop at the “ding an sich”, by saying there is a something where you can´t go below. but that is just catching clouds.

you can say there is a something that contains a member, that is a part of this something. but this could never be ´no something´.

maybe, everything could be a counterpart to “no thing”, but i really don´think so. because every thing is also a windegg.

same to axiom of infinity, which included the axiom of empty set. which also includes the “definition” (haha) of an in-“definition”, called set:

wikipedia :

there is a something (the something which is postulated to be infinite*), such that ´there is a something such that no something is a member of it` is in I and such that whenever any x is a member of I, the something formed by taking the union of x with its singleton {x} is also a member of I.

* hahaha

in germay that is called hegelei. (hegelian trashtalk)

so the very basis of set theory is already a dogbiting in its own tail, defines something (set), which could contain nothing. but is also infinite by definition. strange…

there is another german philospher called heidegger who tried that with language. ( das nichts nichtet, das sein seint). gödel knew very well, why he never published his gottesbeweis.

you can play your funny games, but what you are doin has nothing to do with the base of math.

“A statement about uncountability of \mathbb R has been proven within ZFC, which means that it’s true (assuming that a logic system is sound).”

no. assuming that THIS logic system is sound, but it is not.

you talk about f.e. \mathbb N and really think, that this construct (as a set) exist. no.

you can call a few numbers with a feature called \mathbb N like a feature called BLUE , but there no blue that contains anything, so the same to the so called \mathbb N. you set´lian are all lost in undefinable definitions.

you all try to eat the menuecard, so enjoy your meal.

thats not bad at all, it is funny. but annoying, if you claim any “something” in the grounds of math and confuse generations of young people again and again and again….

> this is just utter nonsense, but yeah, you know a something that is different, okay, fine. i´ve never seen such a something nor is it even possible as an abstract concept: you try to define a bottom in the middle of nowhere.

. This is a perfectly correct statement in ZFC, syntactically and semantically. You only call it nonsense because you can’t understand it.

> there is a something (the something which is postulated to be infinite*)

Once again, perfectly valid statement in ZFC.

> so the very basis of set theory is already a dogbiting in its own tail, defines something (set), which could contain nothing. but is also infinite by definition. strange…

…. you do realize that empty set is not an infinite set? ZFC postulates that set can be empty, or it can be finite, or it can be infinite.

> you can play your funny games, but what you are doin has nothing to do with the base of math.

Please tell us more about your views on “the base of math”.

> assuming that THIS logic system is sound, but it is not.

Prove that it’s not then.

> you talk about f.e. \mathbb N and really think, that this construct (as a set) exist

It does exists. Look up the Peano arithmetic.

Anyway, by your absolutely ridiculous typing/grammar and your nick I can guess that you are 17? I don’t really like playing the age/background card, but who are you to discuss the foundations of mathematics in such a stubborn manner? You never doubted your intellectual capabilities, you stated all your thoughts as facts. Do you really think it’s appropriate for you to do so?

Sorry, that should have been:

> god exist, look up the bible….

Within the context of Bible god might as well exist, I can’t say for certain, I have not read the book.

> there is no empty set. if you think, that such a phenomenon exists, you go wrong. no doubt about. end of discussion.

There is such thing as an empty set and I successfully defined it. It’s not a phenomenon, it’s a set. Which exists. And which is extremely useful.

I couldn’t agree more. Actually, a math theory should be viewed as a program for the brain. It’s only a tool, just like a microscope or a telescope can be. Confusing theory with reality is IMHO a sign of mental disorder from which, I’m afraid, some of us seem to be suffering.

Now I understand why some mathematicians are finitist, constructivist or intuitionist: it would do them too much harm to think otherwise. But even the most finite and “reasonable” theories shouldn’t be mistaken for reality – and this is probably why the P?NP problem is so hard to solve.

Finitists think that their theory is more useful, which is a valid point, perhaps, I cannot judge them. But they for sure are not asking to “show them an empty set”.

> I can’t say for certain that the train I used today is real, but I don’t care, it got me from one place to another.

This is a valid point, though I don’t mean “reality” in the absolute but relative to the tools that are used to describe it.

> But they for sure are not asking to “show them an empty set”.

Fortunately, most of them don’t… and this is quite good news. 🙂

I don’t think “reality” is a good term here, but that is a philosophical discussion, I don’t really want to get into that. What’s really important is that theories are being used because they are _useful_. Nobody cares if they are “real” or not. I can’t say for certain that the train I used today is real, but I don’t care, it got me from one place to another. Because the engineers used _useful_ math (as opposed to “real” math).

Make sure to send a link to this discussion to a school, you will be applying to. They’ll approve.

Actually, it so happens that the empty set exists. Moreover it’s a very useful concept. For instance, it can be used as an accurate modeling of the set of your sound statements.

My previous comment was aimed at knorke94, of course. 🙂

“ps: your hand please”

As far as I can guess in Texas hold-em, I lock in a winning hand with x = nine of hearts and I don’t need y, unless maybe it is a hi-lo version. Depending on the rules, I might wheel with y = deuce of clubs.

Combat Tip for the Day comes from Wikipedia and a master of metaphors:

The Gordian Knot is a legend of Phrygian Gordium associated with Alexander the Great. It is often used as a metaphor for an intractable problem solved by a bold stroke (“cutting the Gordian knot”):

“Turn him to any cause of policy,

The Gordian Knot of it he will unloose,

Familiar as his garter” (Shakespeare, Henry V, Act 1 Scene 1. 45–47)”

Might be possible to avoid some knotty problems, if the rings are elastic enough.

i am neither a finitist nor infinitarian, finitism AND ´in´-finitism is from a higher point of view the same kind of missunderstandings.

they both try to do the same thing but in a lightly different manner, that´s all.

a sounding concept has to overcome this dualism. and that will be fore sure the end of “independent” math. and the beginning of a deeper understanding.

but that´s right:

if you would forced me to do a decision, i would prefere ultrafinitism. but only for one reason:

they are not that out of touch with reality than the trans-whatsoevers.

but what i really think, that we just do not know, what numbers really are.

with the help from dedekind, cantor, zermelo and others, we know now what they are not.

pretty exactely not that, what this set theorists and a few more were talking about.

and yes you can use wrong concepts for doing the right things. but if you don´t know that you were doing that, then everything is complicated as hell.

YOU cannnot beat me, because I am prepeared for the unpreapeared. you don´t. you are a believer. i am not. i don´t know nothing at all, exept a very(!) few things about the territory and the map. and that there is at least someone who tries to handle both AND is part of both v.v.

you first have to kill a lot of believes in unbelievable “somethings”. but you do not know that, therefore this will become a little bit complicated.

dear mister lipton,

why don´t you delete anything i wrote?

and is it not a kind of bad style, that one cannot see, that you did it? but yes, okay, it´s your blog, its your turn.

if i am wrong about the deletion and it was just through an oversight, please forget my whingeing.

i don´t want to bother you any longer. i am not on a mission. just want to know what is going on and therefore just want to have a walk in the lion´s den. i do not doubt, that dedekind, cantor, peano and others found a new game, maybe exiting, but this was only a irritating step to an understanding, what in essence the numbers neither are. (sorry once again for my lousy english).

regards

ps:

what about your paw ? haha , just kidding

you lionrabbits are the good guys 🙂 right?

no, your are the right guys.

good?

Nice! I love Cantor/Godel math 🙂 I found this through the poker tag; I take a slightly different approach to the mathematics of poker:

http://topologicoceans.wordpress.com/2011/07/02/thermodynamics-and-poker/