I agree, every single interesting and fascinating question on stack exchange sites seems to have been closed for some reason or another. This overzealous closing of anything slightly outside the box is really tiresome.
Anything outside the box belongs on another site. They have a format that works for them and rules to follow.
We're not being forced to use only Stack Exchange sites for our non-HN posts.
This was closed over a year after the question was asked, because it already had ~100 answers and they wanted to avoid being spammed with more answers. "Too localized" was just the closest reason they could find to close it with. Seems pretty reasonable.
This one seems reasonable to me; it's a blog or mailing list discussion topic, not really a specific mathematics question. Although phrased as a question, it's obviously a rhetorical one; what the asker really means is, "I would like to start a discussion in which everyone lists their favorite examples of surprising mathematics results".
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.
In a class I took once, the professor presented a theorem he was going to prove (I think it was "surface groups are subgroup separable"). He told us "the story goes that when the great mathematician, Serre, heard about this theorem, he was so surprised he dropped his fork".
As a non mathematician the most surprising for me is that 1 is not a prime number. It still feels like a kludge because it produces inconvenient results to have 1 a prime - so let's just exclude it.
One has properties that are significantly different than the primes. Doesn't it make sense that if it behaves differently than the primes that it isn't a prime, but something else?
One also has the properties that are iconic of primes: its only factors are one and itself. We went out of are way to exclude it, by using a less natural definition of prime numbers, because of how often we would have to say primes greater than 1.
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.)
cperciva answered this according to the modern algebraic understanding in response to the parent. 1 is definitely not prime when you more fully categorize the elements of sets by their algebraic properties: the existence of units is a less singular phenomenon in other algebraic structures.
Yes. More abstractly, prime numbers are those that generate prime ideals. This is a definition which generalizes to much more complex algebraic structures.
However the last vestiges of the question about what definition was most natural didn't get settled until surprisingly recently.
One reason to not have 1 be prime, is otherwise the prime factorization of natural numbers would not be unique. This property of unique prime factorization is not simply "convenient", it is used to derive a large number of other important results.
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.
This isn't a surprising result though, it's a surprising (to you) definition.
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 :)
As a programming analogy: imagine mathematics is a big codebase and "prime" is a commonly-used function defined within that codebase.
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.
The problem arises when people make the mistake of thinking that number theory naturally lives in the non-negative integers; its natural embodiment is the entire ring of integers.
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 also have the property that they cannot be written as the product of two non-zero non-units. There's no important reason for Units and Primes to be disjoint sets.
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.
The property of being invertible is very important. It may seem trivial in the context of the integers, but it's far more significant when you broaden your outlook to other rings.
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.
My answer would be that there are existence proofs for things that we cannot produce examples of. (There are actually many such proofs, but at some point I stopped being shocked.) And furthermore there exist existence proofs for classes of things, at least some of the examples of which we can NEVER verify without adding new axioms to our axiom system!
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 for the philosophy question: in what sense do those unfindable, unverifiable answers actually exist?
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.
If you're familiar with the history of constructivism and the corresponding foundational debates (never truly resolved) of the early 20th century, then it is clear what I am referring to.
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).
This is closely related to proof by the probabilistic method, which shows up quite often in pattern recognition literature and combinatorics (Erdös was fond of it). This method says that instead of even proving the exact existence of something (despite missing any examples) you simply prove that the probability of its existence is positive (and thus cannot be zero).
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.
They aren't necessarily unfindable, there just isn't a generic method of obtaining them.
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 :-)
There's one thing worth mentioning here. There's an algorithm that checks if a graph has given minor. If you fix a minor once and for all, the algorithm that checks if graph contains a fixed minor has polynomial complexity. Together with Robertson-Seymour theorem, it implies that for any family closed upon taking minors, the problem of determining whether given graph belongs to it, is solvable in polynomial time: just check if it contains forbidden minors. Each minor can be tested in polynomial time, and there are finitely of them, so the whole algorithm works in polynomial time.
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.
Material implication and the fact that logic based on it is considered OK.
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.
p => q sort of means, if you assume p, you can get q by flawless reasoning. It is actually true that when you assume someting false you can get from it to any conclusion by correct reasoning. The path between cheese moon and P=NP might be hard to imagine but it probably leads through 1=0 somewhere and you have o properly define what you mean by moon, cheese, and made of.
My favorite surprising result in mathematics is that you can create chaos in the mathematical sense [1] with a bi-infinite binary sequence and the bitshift operation. Essentially, "multiplying by two" is chaotic in the right circumstances.
The technical description can be found starting at page 567 of [0], though the Google Books preview has some important pages missing.
multiplying by two, and adding I presume. makes sense.
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.
There's actually no adding. Just multiplying by two. That's what makes the result so surprising.
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.
>2^(2^(2^...-1)-1)-1 seems prime for all nestings, but the numbers get enormous fast
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.
The issue is that we have no proof that they are primes in general, and they become large so quickly that verifying their primehood is (currently) impossible.
Gödel's incompleteness theorems came as something of an unwelcome surprise to those who, at the time, were hoping to put David Hilbert's program into practice.
Poised inert(0) being mathematically ameliorated with those processes constant including Fourier's common denominator assuaging all cycles of all myriad things, and of at most a single exceptionally egregious serious error, genteel aplomb in action, while abruptly hazarding the whole ball of wax, London gentleman's Reform Club wagerer closed contour circumnavigates eastward around a steaming Victorian Whitechapel® worshipful churchwarden's lit'l chimney("Caminetto") simmering essential singularity, where right of state police Scotland Yard's criminal suspicion and under-cover investigation of Philius Fogg's first err'd then favorite and NOT his discovered saving redemption, rather obsequious servant/valet Passepartout's essential human artifice required singularity: the International Date Line, is not only imaginary(2):
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.
* 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.
Not a mathematician, but "uncountably many" sounds like a loaded phrase unique to the field of mathematics. How does "uncountably many" differ from "infinitely many"? Are we not sure that it goes on forever or do we know that it's just an extremely large finite set?
The natural numbers (1, 2, 3, etc.) are of course "infinite" - however, they are also "countable". (For any natural number you pick, if you count long enough, you'll eventually get to it.) That doesn't mean you'll ever have counted /all/ the natural numbers, but you can count to any arbitrary one.
For contrast, the real numbers, although also infinite, are "uncountable" - any way you start counting, there are real numbers that you will /never/ reach.
It is a precise term with a precise meaning. You can look it up and found many, many explanations online, some of which will be right, few of which will be truly helpful.
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:
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.
For a set S being uncountable means that for any list of elements s_1, s_2, ... of S, there will always be some element of S that's not on the list.
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.
Everyone has already answered with what a countable set is, so I would just add that the answer to your second question is uncountable sets are always infinite in size. Any extremely large set would be finite and so countable.
Between any two rationals there are uncountably many irrationals, and between any two irrationals there are only countably many rationals.
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).
And of course SO police closed this very interesting topic killing many potential very interesting posts. That is despite people liking it, discussing it and upvoting it.
I am sorry for this a bit off-topic comment but I really hope there will be more voices against this moronic policy.
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.
If you start making exceptions to rules then you're going to end up causing even more strife. I'm willing to pay the price to not get "what's the best programming language for X" style questions on SO (for example).
On a related note, there's a blog post on the SO blog concerning closed questions, pretty interesting stuff.
The trouble is that the proportion of quality content that ends up getting closed for arbitrary, capricious, and downright infuriating reasons (just read the text of the "explanation" in this case) is enormous. Often when looking for answers on Stack Overflow I find all of the useful answers are closed. This makes no sense and reflects the stubborn attitudes of the decision makers there, nothing else.
out of curiosity,do you have an example of useful answers that are closed? I've found a lot of interesting answers that are closed, but not really "useful" in the SO sense: something that answers a specific question.
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.
Sure, but in this case the moderators were clearly wrong for closing the the question for being 'too localised':
"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.
Fourth, actually. Indeed, this eases my opinion :) Since I was reading diagonally I think my eye moved away to Cauchy's Integral Formula, since I have worked a little in the complex field. Thanks for pointing this out ;)
I was surprised by the Khinchin–Lévy constant. For almost any real number, if you take the sequence of convergents of its continued fraction, $\frac{p_1}{q_1}$, $\frac{p_2}{q_2}$, ..., this is true:
One of my favourites, which isn't on the first page there (I didn't look beyond that) but contains three surprises, is Goodstein's theorem. It has the nice extra feature that it can be explained pretty simply, so here goes.
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.)
thank you for this example. I'm always looking for examples where very theoretic elements of math bubble up into "practical" things (although here it's a bit esoteric).
My favorite one is Russel's Paradox[1], which actually became the proof that there is no such thing as the Set of all Sets (under traditional set theory[2]).
Which was one of my first steps into Category Theory, as Set is a proper category[3].
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.
101 comments
[ 2.5 ms ] story [ 173 ms ] threadI 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.
Edit: fixed quotation marks
[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.
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.
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.
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.
- 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
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?
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).
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 :-)
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
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.
> 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.
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.
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.
[1] http://en.wikipedia.org/wiki/Jordan_normal_form
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.
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.
Not really mathematics but close enough: The fact that a Rule 110 cellular automaton is Turing complete really fascinates me as well.
http://en.wikipedia.org/wiki/0.999...
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 t...
* 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)
For contrast, the real numbers, although also infinite, are "uncountable" - any way you start counting, there are real numbers that you will /never/ reach.
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 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...
https://news.ycombinator.com/item?id=5232822
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).
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.
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.
"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.
Of course, all the cool kids nowadays use e^(iτ) = 1. ;)
\[\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/
Uncountable sets are the foundation for a large portion of modern math but the sense in which they "really exist" is at least interesting.
http://plato.stanford.edu/entries/paradox-skolem/
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.)
I believe this should be 1 x 10^3 + 2 x 10^2 + 3 x 10^1 + 4 x 10^0
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...
[3] http://en.wikipedia.org/wiki/Category_of_sets
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.
By the way, Gauss conjectured it at the tender age of 14...