What Is the Most Surprising Result in Mathematics?
math.stackexchange.com
math.stackexchange.com
* Bi-color the edges of a (countably) infinite complete graph. There is a mono-chromatic (countably) infinite complete induced sub-graph.
* Between any two rationals there are uncountably many irrationals, and between any two irrationals there are only countably many rationals.
* There is an extension of Lesbesgue measure on R^2 that is isometry invariant, finitely additive, and defined for all subsets. (This can't be extended to R^3 - that's the real point of Banach-Tarksi)
* There is a 3D object with infinite surface area but finite volume. You can't paint the surface, but you can fill it with paint, then empty it out.
* The 3D version of the Jordan–Schönflies Theorem (an "obvious" strengthening of the Jordan Curve Theorem) is wrong.
And just for fun:
* 2=4 (See http://www.solipsys.co.uk/new/TwoEqualsFour.html)
(Added in edit: I suspect this will shortly fall foul of PG's auto-detection of flame wars - it has many more comments than points)
Well, that's not surprising if you know there are only countably many rational in total. That itself may accunted as surprising (and is mentioned in the parent).
Let me add to them.
If you can put a set into one-to-one correspondence with the counting number (which are 1, 2, 3, and so on) then we call the set "countable" or "countably infinite". Examples include (but are not limited to):
* The even counting numbers: 2, 4, 6, 8, 10, and so on;
* The integer squares: 0, 1, 4, 9, 16, 25, and so on;
* The primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on;
* The rational numbers (fractions);
* Finite strings made from a finite collection of symbols;
... and more. You may choose to think about how matchings can be made between each of these and the counting numbers, or each with the others - some ingenuity required.
However, there are infinite collections that cannot be put into one-to-one correspondence with the counting numbers. Examples include:
* Infinite non-terminating strings of 0s and 1s;
* The reals;
* All sets (finite and infinite) of counting numbers;
... and more.
Such infinite collections, since they cannot be matched up with the counting numbers, are called "Uncountably Infinite Sets".
To prove that such collections can never be matched up with the counting numbers is a typical exercise for 1st year undergrads in mathematics, or for precocious mathematics enthusiasts. I first met it when I was about 8 years old and reading Martin Gardner. The usual proof is Cantor's "Diagonalisation Argument"[0][1], and you can find a version of that here:
http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html
That includes a genuine proof of the existence of a set that is infinite, and cannot be put in one-to-one correspondence with the counting numbers.
Still, many people find that unconvincing. I personally prefer Cantor's first argument that there exist transcendental numbers, which is equivalent. Here it is, adapted to show that any list of numbers is incomplete. You'll need to concentrate:
Take any list of numbers: c_0, c_1, c_2, etc.
Take any interval [a0,b0], and cross out numbers from your list until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off numbers, and each time you find one in your current interval, take a sub-interval to exclude it.
The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of points. This sequence is bounded above, so it has an upper bound. Consider the least upper bound.
This cannot be on your original list, because everything was, at some point, excluded. Hence your original list cannot be complete.
And in case you think I can only ever construct one missing number, I can actually construct infinitely many missing numbers. At each stage instead of taking just one sub-interval, I take two subintervals, each excluding the number from your list.
I'm intending to write all this up soon, so if you're interested, I can let you read a draft as a way of improving your understanding, and giving me an attentive proof-reader.
[0] Not to be confused with the diagonal path in the argument that the fractions are countable.
[1] http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
For contrast, the real numbers, although also infinite, are "uncountable" - any way you start counting, there are real numbers that you will /never/ reach.
For instance, infinite sequences of bits are uncountable: for suppose that there's any list s_1, s_2, ... of infinite sequences of zeroes and ones. Let x be a sequence that has 0 on i-th position if i-th sequence on the list has 1 on the i-th position, and 1 otherwise. Then x is not on the list: for suppose x would be on the list as some s_n. Then by definition, x has 0 on n-th position if s_n has 1 on n-th position, and 1 otherwise, but s_n is x, a conradiction.
For example, if you consider a list:
1: 01011001010100... 2: 01110001001001... 3: 11010110100110... 4: 10010110101010...
and further elements, then x would start with 1010...
Let me give a concrete example. A minor of a graph is any graph that you can get from the first by deleting points, deleting edges, or contracting points and joining edges. See https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... for a theorem which says that any family of graphs that is closed under taking minors (ie if G is in the family, then every minor of G is as well) can be characterized by a finite set of forbidden minors. Any graph without a minor in the forbidden set, is in the family.
The best known example of such a family is planar graphs. Those are graphs that you can draw in the plane without crossings. The forbidden minors are K_5 (5 points, all connected to each other) and K_3_3 (2 groups of 3 points, every point in each group connects to the every point in the other). Any graph without either of those as minors, is planar.
So, given any family of graphs that is closed under taking minors, we must have a concrete set of forbidden minors. Furthermore it turns out that given a finite set of forbidden minors, we can use them create a polynomial-time algorithm for recognizing whether a given graph is in the family.
Here is where it gets strange.
Given a family of graphs, we do not have a procedure to produce the forbidden minors. Such a procedure would be wonderful - it would let us do interesting things like solve the Halting problem! That is, of course, an impossible thing to do. This proves that there is, in fact, no such procedure. So we have proved existence of finite, concrete lists, yet proved that in general it is impossible to construct said lists.
It gets worse. There are many interesting families of graphs which are closed under minors, many of which we do not have any decision procedure for at all! (For example graphs embeddable in 3-dimensions without anywhere embedding a knot.)
So we've proven the existence of finite answers to concrete mathematical problems. Yet cannot produce those answers. In general we can NEVER produce those answers. Yet we know that they exist.
Now for the philosophy question: in what sense do those unfindable, unverifiable answers actually exist?
Now, the thing is: since we don't know the minors, we don't know the algorithm. In other words, we just non-constructively proved that some problem can be solved in polynomial time. We only proved that algorithm exists, we just don't know what it is.
At some level these are just proofs that lower-bound the size of the set of instances, and it may be possible to convert any such argument in to one that is more directly measuring the count of instances. In practice however they tend to go through using bounds which are derived from measurable to arguments on random variables, so the conversion is less obvious to me.
I wish my copy of DGL wasn't 2 hours away or I'd dig up one.
(Edit: Wikipedia to the rescue! The "second example" on this page goes through using Markov's Bound on distributions http://en.wikipedia.org/wiki/Probabilistic_method)
For example, we do know the minors for 'graph is planar'. We somehow found it and verified it to be correct. So, we know that some of them, at least, exist. The others, I think, would be in "The Book" (https://en.wikipedia.org/wiki/Paul_Erd%C5%91s#Personality) until they are found. So, those answers do exist in the same sense that The Book exists.
And after they are found, they definitley exist and of course will be called trivial :-)
I don't really see anything philosophically interesting here. Such a feeling probably arises from a misinterpretation of the halting problem here:
> it would let us do interesting things like solve the Halting problem! That is, of course, an impossible thing to do. This proves that there is, in fact, no such procedure.
No such procedure to do it generally.
If you're not familiar with that, Constance Reid's Hilbert! contains a surprisingly readable history of this debate for non-mathematicians, disguised as a biography. For another accessible popular reference, The Mathematical Experience walks through this in a variety of levels of detail (you get out of it what you have the background to get out of it, but it is enjoyable anyways).
> Let me give a concrete example.
Please don't think I'm trivializing your point. I agree that it's deep and thought provoking.
But I hope that you don't mind me pointing out that your wording gave me a smile.
Well, you can't calculate BusyBeaver(n), but they've found the first few Busy Beaver numbers anyway.
We know it's not true because: http://www.math.hmc.edu/funfacts/ffiles/30002.3-5.shtml
Briefly, "Any differentiable symmetry of the action of a physical system has a corresponding conservation law".
The extension of this theorem in QED, The Ward-Takahashi Identity, is also incredibly astounding, if a bit obtuse if you're not well versed in renormalizable field theories.
I have an ever growing contempt for over-eager stack overflow editors.
It's a fine discussion to have, but StackOverflow wants their site to be about actual questions, not "what's your favorite X" type discussions, which seems like a legitimate preference.
E.g. "if the moon was made of cheese, then P=NP" is considered true. This would have been funny if this kind of proofs wasn't used in proofs of basic facts of set theory, e.g. the theorem about empty set being a subset of any set.
I am glad there are people trying to address these issues with a new logic, such as relevance logic, though almost every mathematician I know is fully reconciled with the former type of logic without questioning it.
Edit: fixed quotation marks
On top of that it's been closed since 2011 and nobody saw it fit to be re-opened. Not to mention having 100+ answers. How that's constructive is a wild guess.
But at least it's made some smile or catch them offguard.
On a related note, there's a blog post on the SO blog concerning closed questions, pretty interesting stuff.
"It is only relevant to a small geographic area". No, the question is just as relevant in Louisiana, Lithuania and Liberia.
"It is only relevant to a specific moment in time". No, the question is just as relevant now as it was 50 years ago and will be in 50 years.
"It is an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet". No, it an extraordinarily broad mathematical question that clearly has appeal to a very large, worldwide audience.
In western society there are almost always checks on the use of power. A policeman was too violent when making an arrest? He can be reprimanded or fired. Politician accepted a bribe? He could be locked up. Businessmen colluded to keep prices high? They could be fined heavily.
The 'justice' of our system is so pervasive that we take it for granted, which means it can be very frustrating to experience the unjust use of power without possibility of redress. This case is a minor example, but it must feel like a slap in the face to the person who posted this question on Stack Exchange.
I like questions like this being closed, particularly if they draw out a ton of useful information like this one. Maybe my pain could be eased a little if they had some better boilerplate explanations. To me "Not constructive" in this case is just misleading, wrong and rude.
- The Gauss theorem still looks weird to me, that the shape doesn't matter, all it matters is what's contained inside (http://en.wikipedia.org/wiki/Divergence_theorem)
- The Carmichael function (which is a generalization of Euler's theorem which is a generalization of Fermat's little theorem) http://en.wikipedia.org/wiki/Carmichael_function
\[\lim_{n \to \infty}{q_n}^{1/n}=e^{\pi^2/(12\ln2)}\]
The number on the right is called the Khinchin–Lévy constant.
You can use MathJax to render the LaTeX in this comment with the bookmarklet available here: http://checkmyworking.com/misc/mathjax-bookmarklet/
The technical description can be found starting at page 567 of [0], though the Google Books preview has some important pages missing.
[0] Stephen Wiggins - Introduction to Applied Nonlinear Dynamical Systems and Chaos http://books.google.com/books?id=GYcOfuZDOKMC&lpg=PA565&ots=...
[1] The key attributes of chaos are described in http://en.wikipedia.org/wiki/Chaos_theory#Chaotic_dynamics
to give some related knowledge, all matrices can be decomposed into direct sums of shifts and scales. this is the base of the jordan normal form [1]. infinite matrices can certainly encapsulate chaos.
The key is the metric on the bi-infinite sequence space. Differing in the digit closest to the decimal point on either side gives a distance of 1/2, differing one digit further out is 1/4, then 1/8, 1/16, and so on (the total distance is the sum; the maximum distance between two sequences is 2 if they differ in every digit.) So two sequences are "close" to one another if their middle digits are all the same.
This gives you the key attributes of chaos:
(1) Sensitive Dependence on Initial Conditions. Two sequences can be identical for BIG_NUM digits on each side of the decimal point, and then completely different outside of that area. This means their initial distance apart is roughly 1/2^BIG_NUM. But after BIG_NUM multiply-by-two operations, the trajectories have diverged to a distance of around 2.
(2) Topological Mixing. A similar construction to above -- select the first N digits of a sequence to make it fall into a particular neighborhood, and the next M digits to make it fall into a different neighborhood after the appropriate number of bitshifts. This can be done for any pair of neighborhoods.
(3) Density of periodic orbits. Pick any point X in the space, and a distance epsilon. Construct a periodic orbit that gets within epsilon of X simply by taking the central digits of X (using log_2(epsilon) to select how many digits) and repeating those digits.
There you have it -- chaos as a result of a single bitshift operation on bi-infinite sequences, with no addition or other operations.
When you write a number down in (say) base 10, what you're really doing is writing it as a sum of [small thing] x [power of 10]. So, e.g., 1234 means 1 x 10^3 + 2 x 10^2 + 3 x 10^1 + 4 x 10^0. "Small thing" means "non-negative integer, less than the base". And of course you can do this in bases other than 10.
[EDIT: previous paragraph had a stupid mistake in it; thanks, grannyg00se, for catching it!]
But when you do this, the exponents may be large numbers; in particular, they may be larger than the base. So consider the following operation, given a non-negative integer and a base: write the integer as a sum of [small] x [power of base], and then do the same thing to the exponents, and to the exponents in that, etc., until you've got rid of all the numbers >= the base.
OK. Now here's a process you can carry out. Take a number. Write it "strongly in base 2" according to the procedure above. Now change all the 2s to 3s, generally making the number much much bigger. Now subtract 1.
Now write it "strongly in base 3" again, change all the 3s to 4s, and subtract 1. And again: 4 -> 5, subtract 1. 5 -> 6, subtract 1.
If you try this on some not-too-large number, you'll notice that the base-increasing operation typically increases the number hugely, whereas of course subtracting 1 decreases it just a little bit.
So here's Goodstein's theorem: start with any number you like and carry out this process; eventually the numbers will stop increasing and you'll end up at 0.
(Surprise #1: what a ridiculous idea! Obviously the numbers are increasing really really fast; how can they end up at zero?)
It turns out that Goodstein's theorem is actually rather easy to prove, using a bit of machinery from set theory. There's a generalization of the natural numbers called the ordinals, and doing it properly requires some theorems about them, but here's the idea. Replace all the bases with "infinity". Assume some simple rules for comparing expressions full of infinities (e.g., if a<b then (anything finite) x infinity^a < infinity^b); then every time you subtract 1 and re-express your number "strongly in base b", the corresponding thing full of infinities decreases. And of course when you replace all the bases with infinity, the "increase the base by 1" operation does nothing. And now -- and this is the bit that actually needs some set theory -- it turns out that you can't have an infinite decreasing sequence of these things-full-of-infinities (they're "well-ordered"). Which means that eventually you have to end up at zero.
(Surprise #2: this is, even when the details are filled in, a startlingly short proof for such a surprising theorem.)
All that stuff involving infinities is a bit weird, though. Can't we find a nice proof that works entirely in terms of ordinary finite integers? Once you formalize what "works entirely in terms of ordinary finite integers" means, it turns out that the answer is no! Goodstein's theorem is not provable from the "Peano axioms" describing the natural numbers; you need something stronger to prove it. Such as, in this case, set theory.
(Surprise #3: that something so innocuous requires such powerful mathematical machinery to resolve.)
Which was one of my first steps into Category Theory, as Set is a proper category[3].
[1] https://en.wikipedia.org/wiki/Russell%27s_paradox
[2] https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...
I believe this should be 1 x 10^3 + 2 x 10^2 + 3 x 10^1 + 4 x 10^0
You could redefine "prime" to include 1 if you wanted to without changing the fundamental truth of important results about the natural numbers. It would just mean you'd have to phrase many of them in a slightly more roundabout way, e.g. with "suppose x is a prime number not equal to 1" needing to appear in key theorems where before "suppose x is prime" sufficed. (Perhaps some other theorems might be more concise, although I'd be surprised if there were a net benefit -- the community has probably had this debate a bunch of times before settling on the current consensus.)
Definitions are chosen to be convenient for the purposes of communication, there's nothing inherently true or false about them. An argument for one definition being better than another might involve demonstrating that mathematical results people care about can be stated more clearly, concisely and efficiently using your alternative definition. The recent tau vs pi controversy providing an amusing example :)
You could refactor "prime" to allow 1, provided you refactor all the call sites to work with that new definition too. Consensus seems to be that this refactoring would add LOC and reduce code readability, probably leading to someone submitting a patch soon after with a "prime-but-not-one" function and using that everywhere.
Do remember that math is a bunch of rules that are made up by people to capture certain abstract concepts, and to understand patterns and relationships between those abstract concepts. So although it might feel like a "kludge" to you, that's just the way math is. You can make up whatever rules you like, and some rules exclude "inconvenient results", leading to a deeper understanding, and thus are more widely adopted by other mathematicians.
Within this ring, the integers are divided into four sets: Zero, a (unique) value which when multiplied by anything yields itself; the Units {1, -1}, which are the elements with multiplicative inverses; the Primes {2, 3, 5, 7, ...}, which are the elements which cannot be written as the product of two non-Zero non-Units; and the Composites {4, 6, 8, 9, ...} consisting of everything else.
Units could be considered primes. It would make some things more convenient and others less convenient. For example, a prime decomposition of an element would really be a prime decomposition and not "up to a unit"; on the other hand, a proper statement of its uniqueness would be more bulky.
Ultimately mathematicians decided that it's much more convenient to not consider units to be prime. It does seem to be a matter of convention, with no deep significance to it.
Javascript: function q(n,k){ var t = 0; for( var j = 2; j <= n; j++ )t += 1/k - q(Math.floor(n/j),k+1); return t; } function p(n){ return q(n,1) - q(n-1,1);}
If you check out values of p(n) for n = 1...16, you'll see you get 0,1,1,.5,1,0,1,.3333333,.5,0,1,0,1,0,0,.25
So notice what p returns here - if n is prime, p(n) is 1. If n is a prime power p^a, its 1/a (hence 16 = 2^4 -> 1/4).
And if n is 1? Then p(n) is 0.
In fact, q(n,1) is a tidy (but slow to compute) expression of the Riemann Prime Counting Function: http://mathworld.wolfram.com/RiemannPrimeCountingFunction.ht....
This doesn't prove anything about the "definition of prime numbers", of course - definitions are social things. But 1 does behave differently from the primes in this function that seems to do nothing at all but explicitly identify primes.
Nothing rigorous here, of course, but I think it's a fun, quick-to-code-and-play-with example.
[1]: https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.h...
In a number theory course around 1990, I remember reading papers from the 60s which would explicitly note whether the counts of primes that they were using were starting from 1 or 2. You can define them as not notable mathematicians, but working mathematicians in number theory still had not completely standardized 50 years ago.
Now for more fun, sit down with a group of mathematicians and ask whether they consider 0 to be a natural number. :-)
(The answer you get will vary by field. But none will consider it a particularly important question.)
However the last vestiges of the question about what definition was most natural didn't get settled until surprisingly recently.
"closed as too localized by t.b., Zev Chonoles Sep 5 '11 at 22:18
This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question."
There is also Green's Theorem: http://en.wikipedia.org/wiki/Green%27s_theorem
By the way, Gauss conjectured it at the tender age of 14...
Uncountable sets are the foundation for a large portion of modern math but the sense in which they "really exist" is at least interesting.
Not really mathematics but close enough: The fact that a Rule 110 cellular automaton is Turing complete really fascinates me as well.
2^(2^(2^...-1)-1)-1 seems prime for all nestings, but the numbers get enormous fast
John Conway's "surreal numbers" create all math from an empty set
Fractals ('nuf said)
Can you explain this. I read your expression (with infinite nesting) as x=2^(x-1), whose solutions are 1 and 2.
Looking at it as a series, I see: 2-1=1 2^(2-1)-1=1 2^(2^(2-1)-1)-1=1 2^(2^(2^...-1)-1)-1=1
Also, assuming that a sequence does have the properties you describe (always prime, and gets large very fast), it seems like that sequence would either have to be hard to compute, or unknown to all of the mathematicians working on finding large primes.
Are you supposed to start with 2^2 - 1 = 3; then 2^3 - 1 = 7; 2^7 - 1 = 127; etc? Those do seem to be all prime.
Of course, all the cool kids nowadays use e^(iτ) = 1. ;)
2pie^(pi/2e^(pi/2e^(pi/2...und zu weiter...e^(pi/2i)))
and within an epsilon neighborhood of NOT the author's, and NOT of his contemporaneous Cauchy's and Fourier's Prime Meridian, but its primary protagonist's Observatory Greenwich.
By Capt J Luc Picard's Bigger Theorem:
if an entire holomorphic process has an essential singularity at w, then within any open set epsilon neighborhood containing lit'l rill w, takes on all possible values, with at most a single exception, infinitely often- the necessary pathological(1) attending entropic heat, ignorance, indifference and state sanctioned `algebraically' indiscriminate `transcendent' stupidity among all possible colliding events abruptly attenuates to less than epsilon by the renormalization resonance of Philius' corporeal holotropism of the weighed measure of all possible events and Fourier's common denominator being identical with the simultaneity in the conservation of the contour integral's representation of both signal and noise of all possible events' -all coincident and of arbitrary duration- their unstable equilibrium catalyzes over and precipitates the synch jaunt with nicely holomorphic Philius' lit'l rill flywheel into actually winning the bet, Fogg fists repugnant Fix's despicable state-sanctioned stupid and recklessly endangering souless `algebraic' orthotropic tyranny into a bloody nose, and gets the real girl, and really conformally reforms into the really really rich.
(0) `Lazy' -parsed, inert Inertia:
Inertia does not contain within itself the slightest suggestion of a regular rising and falling of the contents of life; it offers itself at every movement with the same freshness and efficiency; by its far reaching effects and by reducing things to one and the same standard value, that is by leveling out countless fluctuations, mutual alterations of distances and proximity of oscillations and equilibrium, it levels out what would otherwise impose far-reaching change upon the possibilities for the individual's activities and experiences. Inertia is a real object as well as the integration of all objects. However its pure notion may be, inertia appears as the warm spring of life, flows into the schemata of all things, allowing them to blossom and unfold their very essence, no matter how diverse or antagonistic.
Inertia tends towards a point at which, as a pure symbol, it completely absorbs all exchange and measurement, all static constants and dynamic processes.
It is the facilitator creating contact with one another. Know such unique qualities of inertia, for the development of the rhythmical and specific objective styles of life, because the incomparable depth of their opposition illustrates the remarkable actuality of unique inertia being all their common factor. Inertia is the only scalar-independent intrinsic reference and so the ONLY absolute frame of reference from the absolute constant speed of light, as well anything else's inertia, anything else's matter for that matter.
The perception which is in more agreement to natural law, is not only in agreement with reality but is reality. Natural law perception of reality, but so too also perceptive -is sentient- being reality. In their realm the feelings that inertia excites possess a psychological similarity with this.
In so far as inertia becomes the absolutely commensurate expression and equivalent of all values that arise to abstract heights way above the whole broad diversity of objects; it becomes the center in which the most opposed, the most estrange, and the most separable of things find their common denominator.
(1) Le tour du monde en quatre-vingts jours was written during difficult times, both for France and for Verne. It was during the Franco-Prussian War (1870-1871) in which Verne was conscripted as a coastguard, the French army losing every single campaign to the newly united German/Prussian Hohenzollern ubermenchen blot und stahl; and Jules was having money difficulties (his previous works were not paid royalties), his father had died recently, and he had witnessed a shockingly horrible state-ordered public execution which had markedly damaged him.
Ingnorant of those qualities transcendental, you will suffer those chaotic consequences algebraic."
(2) "Imagination is the one weapon in the war against orthotrope reality". -- Jules de Gaul, linux fortuna