9 ms·

Some Fundamental Theorems in Mathematics

419 points by postit 8y ago

thearn4 8y ago
I came into the link ready to nitpick the choices (for some reason which I really should examine), but it's actually a nice birds-eye-view of the field that is rare to see. I feel like mathematicians, perhaps more than most, tend to stay siloed within our specialized subtopics.
- gowld 8y ago
  I belive it's because math is such a "clean" field that it doesn't take many people to 'clear' a topic and advance a subfield or branch into sub-subfields. So you don't have a large number of people all rooting around in the same area speaking the same language. With complex sciences like biology, or worse, wet lab experimental science, it takes so much drudgery just to get data to work with, that you can have 100x people working in the same area, trying to cover the data/processing requirements to support theorizing and cataloging discovered entities.
- x3tm 8y ago
  For a fantastic and deep bird eye view my go-to ref is the Princeton companion to mathematics.
- banachtarski 8y ago
  I read the link title and assumed it was referring to things like the "Fundamental Theorem of Algebra" or the "Fundamental Theorem of Number Theory" etc. It was.
- FabHK 8y ago
  A great book in a similar vein is Proofs from THE BOOK by Martin Aigner, Karl H. Hofmann, Günter M. Ziegler. It's a reference to Paul Erdős and his notion of "The Book" in which God had written down the most beautiful and elegant proofs.
amelius 8y ago
This is not a self-contained exposition, and a lot of the interesting implications of the theorems seem to be omitted (why are these theorems fundamental; and fundamental to what?) It begs the question: why not instead post a list of links to Wikipedia articles? That would allow the reader to click through to definitions that they are not familiar with, as well as explore what these theorems are (practically or theoretically) useful for.
throwawaymath 8y ago
The second theorem (the generalized Pythagorean theorem, which uses inner product spaces) feels incomplete to me. The exposition is fine, but I don't think the explanation should have concluded with the regular a^2 + b^2 = c^2 equality. You wouldn't use that in the context of an inner product space. The generalized Pythagorean theorem actually looks like ||x + y||^2 = ||x||^2 + ||y||^2 + 2<x, y>. I think it would be better if there's less editorializing of the equalities and more relating of their abstract forms to their "simple", familiar forms. Otherwise I don't really understand the exercise - if the first page has a theorem involving inner product spaces, this is clearly targeted at people with at least a full course of linear algebra under their belt. Unless the audience is already aware of how that second equality implies the first equality, this explanation doesn't capture the heart of it. As another commenter said, this is not a self-contained exposition (and I don't think it realistically could be). But if it's not going to be self-contained, I think it could be improved by more completely showing how the elegant abstractions imply the things we're already familiar with in a neat way.
- deleted 8y ago
  [deleted]
- chongli 8y ago
  I thought the Pythagorean Theorem assumed that x and y were orthogonal? Then 2<x, y> = 0 This is such a funny coincidence, by the way. My prof literally proved the Pythagorean Theorem on inner product spaces today in class.
- andrepd 8y ago
  The Pythagorean theorem is about orthogonal vectors, so it would just be |x + y|^2 = |x|^2 + |y|^2 Plus the line just above that tells you: let a = |x|, b = |y|, c = |x-y| I don't think they are obscuring anything. I think they are showing how the a b and c in the familiar a^2+b^2=c^2 can be generalised to |x|, |y|, |x-y| for any orthogonal vectors x and y in an inner product space.
- jacobolus 8y ago
  v · w = 0 was one of the premises. Your version is the more general statement usually called the “law of cosines”. Personally I prefer the geometric algebra version: Given any vectors u, v: (u + v)² = uu + uv + vu + vv = u² + 2u·v + v² Where u·v = ½(uv + vu) is just the definition of ·.
waynecochran 8y ago
The Church-Turing Theorem is not really a mathematical theorem; It is more like F = Ma in Physics. It's an empirical result.
- baddox 8y ago
  I don’t think that’s quite the case. The theorem is a mathematical given formalizations of computability (algorithms). Those formalizations were devised to reflect what seems to be the physical limits of computers in the real world, of course. If we discovered more powerful methods of computation in the real world, we would presumably update our mathematical formalizations, but the math behind the current formalizations is correct (in the same way that the math used in Newtonian physics is correct even though we now know that non-Newtonian physics are needed to analyze certain phenomena.
  - waynecochran 8y ago
    It's not a math theorem. From http://mathworld.wolfram.com/Church-TuringThesis.html http://mathworld.wolfram.com/Church-TuringThesis.html There has never been a proof, but the evidence for its validity comes from the fact that every realistic model of computation, yet discovered, has been shown to be equivalent. http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/ChurchTuring.pdf http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/... The Church–Turing Thesis is an extramathematical proposition, not subject to formal proof.
    - baddox 8y ago
      You're right. The thesis is that nothing in the real world can compute a function that a Turing machine cannot, which is not proven (and it's not clear how it even could be proven). What is proven formally is the equivalence of several different formulations.
- contravariant 8y ago
  It's not a theorem, but that's because it's not proven, or can't be proven really. Unless you're referring to the fact that those three definitions coincide, that is a theorem. The statement F=ma is either a definition, axiom or theorem depending on what context you're working in. There are more fundamental (empirically tested) axioms that have F=ma as a consequence. Unless you introduce special relativity, then it becomes false.
nilkn 8y ago
It's amazing to see so many things included and yet so many missing. It really speaks to the breadth and depth of the subject. For instance, for elliptic curves, only a single result is mentioned (their points can be endowed with an abelian group structure), and it's really one of the most basic ideas known about these objects.
- jjoonathan 8y ago
  Right. If I pick one of these subjects where I know, say, 100x more than what is present, and know of the existence of 1000x more than is present, I can't help but multiply the number of subjects in this overview by that that same 1000x, and then my mind explodes.
- romwell 8y ago
  >For instance, for elliptic curves, only a single result is mentioned (their points can be endowed with an abelian group structure), and it's really one of the most basic ideas known about these objects. One might even say it's a fundamental idea. Which is the whole point of the document :) Indeed you are right!
prostitute 8y ago
Fundamental Theorem of Group Homomorphisms: If f is a homomorphism from a group G_1 onto the group G_2, then G_1/ker(f) is isomorphic to G_2 ...and that's the tea.
khawkins 8y ago
The Control Theory (129) section does a real disservice to the field by insinuating it is little more than the study of Kalman filters. While an important model, the core results of control theory are without a doubt stability criterions. The Lyapunov stability criterion is even quite elegant, despite being powerful: A system is asymptotically stable if there exists a function V where for x/=0, V(x)>0 and [Sum]_i (dV/dx_i) (dx_i/dt) < 0.
- jjoonathan 8y ago
  Every single subject in the overview is summarized with similar brutality, yet it still reads like an encyclopedia. There's a lot of math out there.
- theoh 8y ago
  > While an important model, the core results of control theory are without a doubt stability criterions. I'm guessing you mean "while they (kalman filters) are an important model...". What you've written involves a dangling modifier clause, which makes no sense.
triska 8y ago
Thank you for sharing! One thing I noticed is the statement in 20. Logic: An axiom system is neither complete nor provably consistent. I think this would benefit from some rephrasing, because such a system could for example be both complete and provably consistent (in the sense given in the paper) if it were, in fact, inconsistent. Also, IUT is not "Inner-Universal Teichmuller", but rather inter-universal Teichmüller theory.
- btilly 8y ago
  That one also bothered me, because it is very much wrong. The correct result is Any consistent axiom system that describes the natural numbers cannot be complete or provably consistent. You pointed out that an inconsistent axiom system is neither. And at the opposite extreme, Gödel proved that the axioms for the real numbers are provably consistent. (However those axioms do not allow for induction, and therefore do not allow one to describe the natural numbers!)
  - skh 8y ago
    This is incorrect as well. Take the standard model of the integers. Now take all true statements in this model. Let this be your axiom system. It is complete. It is not recursively enumerable and therefore not very useful. You can also have second order systems that are categorical. For instance the second order Peano axioms. I believe they are complete.
    - btilly 8y ago
      Point. But honestly, nobody ever convinced me that second order logic wasn't made up BS. :-) Or that reasoning of a form that can't be verified, even in theory, actually is sensible. (Why yes, I do have Constructivist tendencies, why do you ask?)
      - skh 8y ago
        Before I took Mathematical Logic in graduate school I believed all kinds of nonsense about Godel’s theorems. Even after the class I still had false ideas about what it really meant. It took a while for the the recursively enumerable part to sink in as to why it is important. I’ve heard what you say about second order axiom systems before but I don’t know enough about the subject. I naively think, “Why not just use the Second Order Peano Axioms?”. But people far more knowledgeable than me don’t like them so I defer to their judgement.
Retra 8y ago
>There is no apparent “fundamental theorem” of AI, (except maybe Marvin Minsky’s ”The most efficient way to solve a problem is to already know how to solve it.” Personally, I consider Richard Feynman's method (1. Write down the problem. 2. Think real hard. 3. Write down the solution.) to be just as fundamental. The reason being that steps 1 and 3 are actually very important. Step 1 asks that you model the problem you're solving, otherwise you might solve some other problem instead. Step 3 asks that you model the domain of solutions. This helps ensure that it is possible for solutions to even exist. One of the big problems with unresolved and open-ended philosophical quandaries is that people never specify what they expect a solution to look like. Like if you don't expect a solution to look like a string of plain words, and instead expect it to look like some mystical revelation, then you can't honestly expect to get an intelligent resolution communicated to you. I'd also say it is integral to understanding the difference between simply solving a problem and intentionally solving a problem.
uptownfunk 8y ago
As a math major, this makes me giddy. It's like a family reunion, all my old friends in one place.
js8 8y ago
Other lists in the similar spirit: http://www.cs.ru.nl/~freek/100/ http://www.cs.ru.nl/~freek/100/ https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
skh 8y ago
Number 20 in logic is incorrect. It’s surprising how often this is misstated. There are lots of complete axiom systems. Indeed, take as your axioms all true statements in a given model. Voila, you now have a complete axiom system. It’s not just a useful one but it is complete. What isn’t complete is a recursively enumerable axiom system that contains arithmetic of the standard model of integers. Overall it is a nice list and well done. EDIT: Deleted a sentence that was pointed out to me that was wrong in the context of the assumptions made in the paper.
- deleted 8y ago
  [deleted]
- romwell 8y ago
  >Number 20 in logic is incorrect. >What isn’t complete is a recursively enumerable axiom system that contains arithmetic of the standard model of integers. That's exactly what #20 says. The "axiom system" there, by definition, includes Peano axioms (2nd sentence of #20).
  - skh 8y ago
    I didn’t read that part but the statement is still wrong. Take as your model the standard model of integers. Collects all true statements of this model. Make this your axiom system. It is now complete and contains the first order Peano Axioms.
    - gnulinux 8y ago
      Then that system is not finitely axiomatizable (there are infinitely many truths in that model) so the original claim is still true. It's true for all finitely axiomatized theories.
      - skh 8y ago
        The author of the article does not stipulate that the axiom system has to be recursively enumerable. From the article: We assume it to contain the basic Peano axioms of arithmetic. An axiom system is complete, if every true statement can be proven within the system. The theorem in the article is true for recursively enumerable axioms systems that contain first order arithmetic. EDIT: Note that the second order Peano Axioms are categorical but not recursively enumerable. This is also an axiomatic system that has finitely many axiom schema.
romwell 8y ago
A supremely amazing collection! Succinctly written, and a joy to read. The curation is fantastic. Some would disagree with the choices, but the task was herculean. (e.g. geometric group theory is not really represented there - but one can't expect to have all of mathematics in 60 pages!) I ended up going through the list, categorizing these theorems into know/don't know/should know categories. Time well spent. ----------- Mandatory "Hey, there's a typo there" note: In #77: HOMFLYPT polynomial's list of authors is missing Y: David N. Yetter, a professor in Kansas State University. Hope this omission will be fixed! I learned knot theory and did research with Yetter in 2007 (which resulted in a paper on Vassiliev Invariants, a subject also mentioned in #77); that was a pivotal point in my life. Besides mathematics, Yetter's other major interests, to my knowledge, are Orthodox Christianity and anime.
tmyklebu 8y ago
This list is fun, but it's a little bit sloppy: - The central limit theorem relies on the mean and variance of your random variable existing; there are random variables for which mean and variance don't exist. - The definition of "measure-preserving" in the ergodic theorem statement is missing the measure. - dim (ran A)^perp = dim ker A^T can be strengthened by dropping the dim's. If v in ker A^T, then A^T v = 0. Pick any Ax in ran A; then <v, Ax> = <A^T v, x> = <0, x> = 0, so v is in (ran A)^perp. - Others pointed out that 20 looks busted. - The definition of Haar measure needs to fix the measure of some nonzero-measure set, or "unique" needs to be replaced with "unique up to scaling" otherwise the theorem isn't true. - "Sounders Mac Lane" - 25: x_0 came out of nowhere; it's unclear from the text which "invertible" is meant; the basin of convergence for Newton's method for finding a local continuation can be very small indeed. - 36: Why is the adjoint of A named T^*? - 46: You need some assumptions about f.
- FabHK 8y ago
  I think you're being a bit harsh. The central limit theorem does hold for iid rv (independent identically distributed random variables) with finite mean and variance. Now, those assumptions can be relaxed (the rv need not be independent, but they can't be too dependent, and they need not have finite variance, but they can't be too "far out"), and some of the pertinent proofs are only a few decades old; but you can hardly expect a survey with 135 proofs to cover all the subtleties. Some of the other points may be more egregious howlers, but, again, come on - this is not the definite reference for any one of those theorems.
  - tmyklebu 8y ago
    There's more than enough neat stuff I don't know in there. Unfortunately it's tough to trust a source with so many errors in the stuff I do know. I wasn't aware of any CLT for iid random variables with infinite variance. Do you have references?
    - FabHK 8y ago
      Check Valentin Petrov Limit Theorems of Probability Theory. Here [1] is a CLT for RV with infinite variance, Prop 3.1.12, but notice the (larger) scaling coefficient (1/sqrt(n log n)). Also see the second answer on SO here [2]. [1] https://web.stanford.edu/~montanar/TEACHING/Stat310A/lnotes.pdf https://web.stanford.edu/~montanar/TEACHING/Stat310A/lnotes.... [2] https://stats.stackexchange.com/questions/169611/the-role-of-variance-in-central-limit-theorem https://stats.stackexchange.com/questions/169611/the-role-of... EDIT to add: Having said that, the Lindeberg-Feller and the Lyuapunov formulation of the CLT do require finite variance, so maybe I was too quick in stating that that assumption can be relaxed.
dclowd9901 8y ago
Does anyone have a cheat sheet of sorts for the symbols and syntax used in these?
- jordigh 8y ago
  It doesn't work like that. Some of the same symbols are used in two different places with vastly different meanings, even within this paper. To give an imperfect programming language analogy, imagine that every symbol is implicitly defined and has lexical scope. The grammar is as far from being context-free as possible. What may sometimes look like individual symbols to you are in fact a collection of inseparable symbols with its own semantic parse.
  - pantalaimon 8y ago
    That's not really helpful. I struggle with the same problem, in fact the notation intimidates me to a point where I decided to forego getting deeper into theoretical computer science and haunts me every time I try to read a paper. A resource that would explain formal mathematical notation would be great, much like a dictionary. You can't google those symbols properly either.
    - jordigh 8y ago
      Did you know what the words meant? Can you read this and except for the symbols understand everything else? I don't think the symbols are the problem. They're a very superficial obstacle, at least in this paper. This isn't meant as a put-down. It's just that I really do think the actual material requires a lot more preparation that consists in a lot more than just learning the definition of the symbols. I could rewrite the whole paper using only text and no symbols. The symbols are just shorthand for English words. I don't think if I were to replace all of the symbols with the English words that they stand for, you would be much closer to understanding.
      - dclowd9901 8y ago
        "The symbols are just shorthand for English words." OK, so then why would it be so difficult to produce a veritable cheat sheet to aide in reading a proof?
luminati 8y ago
Naive question: How would one go about learning all about this (or even a subset of this) for the mathematically inclined working engineer? Where does one even start? Just take each theorem from each section and try to follow through the proof? What are the prerequisites required?
- joe_the_user 8y ago
  There are standard texts on the various topics listed in the contents. There are online texts on these topics as well as free to download texts. To learn everything, get a math degree or self-study the curriculum of one. The prerequisite is basically calculus. The thing about this text is it seems like a more or less random list of theorems - it lists one theory, I think, Zorn's lemma, under topology where Zorn's lemma is more a set-theory-link-to-topology (one of the guises of the Axiom of choice, really). Which to say it has next-to-nothing on point-set topology proper. Other theory listings seem just as random. So I couldn't what order you'd follow trying to learn everything specifically here.
- jacobolus 8y ago
  The theorems in this list are in many cases central topics in 1+ semester courses, and aren’t really worth worrying about out of context. Overall you are looking at more than 5 years of full-time (40 hours/week) study, maybe more than 10 years. Unless you have extensive background reading and writing proofs, self-study is not likely to be very effective. You could conceivably make your way through with textbooks and the help of an expert tutor/mentor. For most people the easiest method would be to enroll in an undergraduate mathematics degree at a decent university. If you wanted to make your way through more of the topics in this list than an undergraduate degree covered, you could follow-up by enrolling in a PhD program.
angel_j 8y ago
Some Fundamental Theorems in Mathematics are bigger than others. Some Fundamental Theorems in Mathematics' Mothers are bigger than other Fundamental Theorems in Mathematics' Mothers.
weerd 8y ago
From #113, Artificial Intelligence The lebowski theorem of machine superintelligence: No AI will bother after hacking its own reward function. once the AI has figured out the philosophy of the “Dude” in the Cohen brothers movie Lebowski, also repeated mischiefs does not bother it and it “goes bowling”. I'm relieved to learn that this is a theorem. :D
- HONEST_ANNIE 8y ago
  The Lebowski theorem: "No superintelligent AI is going to bother with a task that is harder than hacking its reward function" is surprisingly deep. You can see the theory in action in human history. We have drives programmed by evolution, but we try to to shortcut them. Drugs are deliberate hack for example. TV, entertainment and games can provide rewards faster than effort towards real life goals. We fully understand that there is difference between the drive's purpose and what we do, but but we don't actually value the purpose of our reward function, only the reward. Catholic church tries to insist that people should limit sexual pleasure to the purpose it was created (by god or evolution) but people don't listen.
1024core 8y ago
I think it's a great list but the typos bothered me. To me, they seem to indicate sloppiness; and if there is sloppiness, could the mathematical results be sloppy too? e.g., on page 2 itself: "Anticipated by Babylonians Mathematicians in examples..." "Let f be a function of one variables..."
graycat 8y ago
Gorgeous. IIRC S. Eilenberg once said "Elegance in mathematics is directly proportional to what you can see in it and inversely proportional to the effort required to see it.". This Knill book is elegant. Topic by topic for a wide range of pure and well polished applied math, Knill is able and does go right to the most important results and for each gives a short outline of the needed definitions and of a proof, usually with good references to full details, and then states the theorem precisely. Net, for nearly any topic in pure/applied math, go there first. For many of the topics, I studied them carefully from some of the best sources, but just on a short scan this Knill book often has a better treatment, e.g., has a super nice, simple, practical statement of a fundamental theorem in Fourier series, a super nice statement of the Lebesgue decomposition from the Radon-Nikodym theorem, some nice stuff from Zorn's lemma, and much more, e.g., often some historical notes. I have to like the connection with Zorn's lemma: At one point I went to a lecture at Indiana University and to the tea before, and an older professor introduced himself as Max Zorn. Since the previous summer I'd taken a course in axiomatic set theory on an NSF summer program at Vanderbilt, I was nearly floored! All I could do was blurt out, "What did Paul Cohen prove?". The next day Zorn gave me his copy of Cohen's paper. I still have it! At one point I saved FedEx by pleasing two guys from crucial investor General Dynamics by doing a revenue projection with the differential equation y'(t) = k y(t) (b - y(t)) with y(0), k, and b given. So, the solution is a lazy S curve that starts at t = 0 at y(0) and as t increases rises, has an inflection point, and rises from below asymptotically to b. So, it is a case of growth to a market size of b. With y(t) the current revenue and (b - y(t)) the market revenue yet to be obtained, has the growth rate y'(t) proportional to the current revenue y(t) (number of current customers talking) and the remaining customers (hearing the talking) (b - y(t)). So, it's a simple model of viral growth. Well, Knill has this differential equation with b = 2 for a case of biological growth!
deleted 8y ago
[deleted]
Topolomancer 8y ago
I love Oliver Knill! Not only does he have very broad mathematical interests, he also has this crazy YouTube Channel (https://www.youtube.com/user/knill101/videos https://www.youtube.com/user/knill101/videos) where he sometimes uses a synthetic voice (!) to give talks---supposedly because he cannot talk as fast as he wants to. He really is quite an interesting charactern!
maxiepoo 8y ago
The Topos theory example is completely wrong though? > For example, if E is the topos of sets, then the slice category is the category of pointed sets: the objects are then sets together with a function selecting a point as a “base point”. There's no object X where E/X is pointed sets. If you take the co-slice of a one point set 1\E that would be the category of pointed sets. The right way to think about E/X is that its objects are "families of sets indexed by X", because a function f : Y -> X defines for each x in X a set f^{-1}(x). If you know about dependent types, this is basically a type dependent on X.
krambs 8y ago
Can you really trust any mathematician's judgment who doesn't use serial commas? ;)

419 points by postit 8y ago

I came into the link ready to nitpick the choices (for some reason which I really should examine), but it's actually a nice birds-eye-view of the field that is rare to see. I feel like mathematicians, perhaps more than most, tend to stay siloed within our specialized subtopics.

gowld 8y ago
I belive it's because math is such a "clean" field that it doesn't take many people to 'clear' a topic and advance a subfield or branch into sub-subfields. So you don't have a large number of people all rooting around in the same area speaking the same language. With complex sciences like biology, or worse, wet lab experimental science, it takes so much drudgery just to get data to work with, that you can have 100x people working in the same area, trying to cover the data/processing requirements to support theorizing and cataloging discovered entities.
x3tm 8y ago
For a fantastic and deep bird eye view my go-to ref is the Princeton companion to mathematics.
banachtarski 8y ago
I read the link title and assumed it was referring to things like the "Fundamental Theorem of Algebra" or the "Fundamental Theorem of Number Theory" etc. It was.
FabHK 8y ago
A great book in a similar vein is Proofs from THE BOOK by Martin Aigner, Karl H. Hofmann, Günter M. Ziegler. It's a reference to Paul Erdős and his notion of "The Book" in which God had written down the most beautiful and elegant proofs.

amelius 8y ago

This is not a self-contained exposition, and a lot of the interesting implications of the theorems seem to be omitted (why are these theorems fundamental; and fundamental to what?) It begs the question: why not instead post a list of links to Wikipedia articles? That would allow the reader to click through to definitions that they are not familiar with, as well as explore what these theorems are (practically or theoretically) useful for.

throwawaymath 8y ago

The second theorem (the generalized Pythagorean theorem, which uses inner product spaces) feels incomplete to me. The exposition is fine, but I don't think the explanation should have concluded with the regular a^2 + b^2 = c^2 equality. You wouldn't use that in the context of an inner product space. The generalized Pythagorean theorem actually looks like ||x + y||^2 = ||x||^2 + ||y||^2 + 2<x, y>. I think it would be better if there's less editorializing of the equalities and more relating of their abstract forms to their "simple", familiar forms. Otherwise I don't really understand the exercise - if the first page has a theorem involving inner product spaces, this is clearly targeted at people with at least a full course of linear algebra under their belt. Unless the audience is already aware of how that second equality implies the first equality, this explanation doesn't capture the heart of it. As another commenter said, this is not a self-contained exposition (and I don't think it realistically could be). But if it's not going to be self-contained, I think it could be improved by more completely showing how the elegant abstractions imply the things we're already familiar with in a neat way.

deleted 8y ago
[deleted]
chongli 8y ago
I thought the Pythagorean Theorem assumed that x and y were orthogonal? Then 2<x, y> = 0 This is such a funny coincidence, by the way. My prof literally proved the Pythagorean Theorem on inner product spaces today in class.
andrepd 8y ago
The Pythagorean theorem is about orthogonal vectors, so it would just be |x + y|^2 = |x|^2 + |y|^2 Plus the line just above that tells you: let a = |x|, b = |y|, c = |x-y| I don't think they are obscuring anything. I think they are showing how the a b and c in the familiar a^2+b^2=c^2 can be generalised to |x|, |y|, |x-y| for any orthogonal vectors x and y in an inner product space.
jacobolus 8y ago
v · w = 0 was one of the premises. Your version is the more general statement usually called the “law of cosines”. Personally I prefer the geometric algebra version: Given any vectors u, v: (u + v)² = uu + uv + vu + vv = u² + 2u·v + v² Where u·v = ½(uv + vu) is just the definition of ·.

waynecochran 8y ago

The Church-Turing Theorem is not really a mathematical theorem; It is more like F = Ma in Physics. It's an empirical result.

baddox 8y ago
I don’t think that’s quite the case. The theorem is a mathematical given formalizations of computability (algorithms). Those formalizations were devised to reflect what seems to be the physical limits of computers in the real world, of course. If we discovered more powerful methods of computation in the real world, we would presumably update our mathematical formalizations, but the math behind the current formalizations is correct (in the same way that the math used in Newtonian physics is correct even though we now know that non-Newtonian physics are needed to analyze certain phenomena.
- waynecochran 8y ago
  It's not a math theorem. From http://mathworld.wolfram.com/Church-TuringThesis.html http://mathworld.wolfram.com/Church-TuringThesis.html There has never been a proof, but the evidence for its validity comes from the fact that every realistic model of computation, yet discovered, has been shown to be equivalent. http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/ChurchTuring.pdf http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/... The Church–Turing Thesis is an extramathematical proposition, not subject to formal proof.
  - baddox 8y ago
    You're right. The thesis is that nothing in the real world can compute a function that a Turing machine cannot, which is not proven (and it's not clear how it even could be proven). What is proven formally is the equivalence of several different formulations.
contravariant 8y ago
It's not a theorem, but that's because it's not proven, or can't be proven really. Unless you're referring to the fact that those three definitions coincide, that is a theorem. The statement F=ma is either a definition, axiom or theorem depending on what context you're working in. There are more fundamental (empirically tested) axioms that have F=ma as a consequence. Unless you introduce special relativity, then it becomes false.

nilkn 8y ago

It's amazing to see so many things included and yet so many missing. It really speaks to the breadth and depth of the subject. For instance, for elliptic curves, only a single result is mentioned (their points can be endowed with an abelian group structure), and it's really one of the most basic ideas known about these objects.

jjoonathan 8y ago
Right. If I pick one of these subjects where I know, say, 100x more than what is present, and know of the existence of 1000x more than is present, I can't help but multiply the number of subjects in this overview by that that same 1000x, and then my mind explodes.
romwell 8y ago
>For instance, for elliptic curves, only a single result is mentioned (their points can be endowed with an abelian group structure), and it's really one of the most basic ideas known about these objects. One might even say it's a fundamental idea. Which is the whole point of the document :) Indeed you are right!

prostitute 8y ago

Fundamental Theorem of Group Homomorphisms: If f is a homomorphism from a group G_1 onto the group G_2, then G_1/ker(f) is isomorphic to G_2 ...and that's the tea.

khawkins 8y ago

The Control Theory (129) section does a real disservice to the field by insinuating it is little more than the study of Kalman filters. While an important model, the core results of control theory are without a doubt stability criterions. The Lyapunov stability criterion is even quite elegant, despite being powerful: A system is asymptotically stable if there exists a function V where for x/=0, V(x)>0 and [Sum]_i (dV/dx_i) (dx_i/dt) < 0.

jjoonathan 8y ago
Every single subject in the overview is summarized with similar brutality, yet it still reads like an encyclopedia. There's a lot of math out there.
theoh 8y ago
> While an important model, the core results of control theory are without a doubt stability criterions. I'm guessing you mean "while they (kalman filters) are an important model...". What you've written involves a dangling modifier clause, which makes no sense.

triska 8y ago

Thank you for sharing! One thing I noticed is the statement in 20. Logic: An axiom system is neither complete nor provably consistent. I think this would benefit from some rephrasing, because such a system could for example be both complete and provably consistent (in the sense given in the paper) if it were, in fact, inconsistent. Also, IUT is not "Inner-Universal Teichmuller", but rather inter-universal Teichmüller theory.

btilly 8y ago
That one also bothered me, because it is very much wrong. The correct result is Any consistent axiom system that describes the natural numbers cannot be complete or provably consistent. You pointed out that an inconsistent axiom system is neither. And at the opposite extreme, Gödel proved that the axioms for the real numbers are provably consistent. (However those axioms do not allow for induction, and therefore do not allow one to describe the natural numbers!)
- skh 8y ago
  This is incorrect as well. Take the standard model of the integers. Now take all true statements in this model. Let this be your axiom system. It is complete. It is not recursively enumerable and therefore not very useful. You can also have second order systems that are categorical. For instance the second order Peano axioms. I believe they are complete.
  - btilly 8y ago
    Point. But honestly, nobody ever convinced me that second order logic wasn't made up BS. :-) Or that reasoning of a form that can't be verified, even in theory, actually is sensible. (Why yes, I do have Constructivist tendencies, why do you ask?)
    - skh 8y ago
      Before I took Mathematical Logic in graduate school I believed all kinds of nonsense about Godel’s theorems. Even after the class I still had false ideas about what it really meant. It took a while for the the recursively enumerable part to sink in as to why it is important. I’ve heard what you say about second order axiom systems before but I don’t know enough about the subject. I naively think, “Why not just use the Second Order Peano Axioms?”. But people far more knowledgeable than me don’t like them so I defer to their judgement.

Retra 8y ago

>There is no apparent “fundamental theorem” of AI, (except maybe Marvin Minsky’s ”The most efficient way to solve a problem is to already know how to solve it.” Personally, I consider Richard Feynman's method (1. Write down the problem. 2. Think real hard. 3. Write down the solution.) to be just as fundamental. The reason being that steps 1 and 3 are actually very important. Step 1 asks that you model the problem you're solving, otherwise you might solve some other problem instead. Step 3 asks that you model the domain of solutions. This helps ensure that it is possible for solutions to even exist. One of the big problems with unresolved and open-ended philosophical quandaries is that people never specify what they expect a solution to look like. Like if you don't expect a solution to look like a string of plain words, and instead expect it to look like some mystical revelation, then you can't honestly expect to get an intelligent resolution communicated to you. I'd also say it is integral to understanding the difference between simply solving a problem and intentionally solving a problem.

uptownfunk 8y ago

As a math major, this makes me giddy. It's like a family reunion, all my old friends in one place.

js8 8y ago

Other lists in the similar spirit: http://www.cs.ru.nl/~freek/100/ http://www.cs.ru.nl/~freek/100/ https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK

skh 8y ago

Number 20 in logic is incorrect. It’s surprising how often this is misstated. There are lots of complete axiom systems. Indeed, take as your axioms all true statements in a given model. Voila, you now have a complete axiom system. It’s not just a useful one but it is complete. What isn’t complete is a recursively enumerable axiom system that contains arithmetic of the standard model of integers. Overall it is a nice list and well done. EDIT: Deleted a sentence that was pointed out to me that was wrong in the context of the assumptions made in the paper.

deleted 8y ago
[deleted]
romwell 8y ago
>Number 20 in logic is incorrect. >What isn’t complete is a recursively enumerable axiom system that contains arithmetic of the standard model of integers. That's exactly what #20 says. The "axiom system" there, by definition, includes Peano axioms (2nd sentence of #20).
- skh 8y ago
  I didn’t read that part but the statement is still wrong. Take as your model the standard model of integers. Collects all true statements of this model. Make this your axiom system. It is now complete and contains the first order Peano Axioms.
  - gnulinux 8y ago
    Then that system is not finitely axiomatizable (there are infinitely many truths in that model) so the original claim is still true. It's true for all finitely axiomatized theories.
    - skh 8y ago
      The author of the article does not stipulate that the axiom system has to be recursively enumerable. From the article: We assume it to contain the basic Peano axioms of arithmetic. An axiom system is complete, if every true statement can be proven within the system. The theorem in the article is true for recursively enumerable axioms systems that contain first order arithmetic. EDIT: Note that the second order Peano Axioms are categorical but not recursively enumerable. This is also an axiomatic system that has finitely many axiom schema.

romwell 8y ago

A supremely amazing collection! Succinctly written, and a joy to read. The curation is fantastic. Some would disagree with the choices, but the task was herculean. (e.g. geometric group theory is not really represented there - but one can't expect to have all of mathematics in 60 pages!) I ended up going through the list, categorizing these theorems into know/don't know/should know categories. Time well spent. ----------- Mandatory "Hey, there's a typo there" note: In #77: HOMFLYPT polynomial's list of authors is missing Y: David N. Yetter, a professor in Kansas State University. Hope this omission will be fixed! I learned knot theory and did research with Yetter in 2007 (which resulted in a paper on Vassiliev Invariants, a subject also mentioned in #77); that was a pivotal point in my life. Besides mathematics, Yetter's other major interests, to my knowledge, are Orthodox Christianity and anime.

tmyklebu 8y ago

This list is fun, but it's a little bit sloppy: - The central limit theorem relies on the mean and variance of your random variable existing; there are random variables for which mean and variance don't exist. - The definition of "measure-preserving" in the ergodic theorem statement is missing the measure. - dim (ran A)^perp = dim ker A^T can be strengthened by dropping the dim's. If v in ker A^T, then A^T v = 0. Pick any Ax in ran A; then <v, Ax> = <A^T v, x> = <0, x> = 0, so v is in (ran A)^perp. - Others pointed out that 20 looks busted. - The definition of Haar measure needs to fix the measure of some nonzero-measure set, or "unique" needs to be replaced with "unique up to scaling" otherwise the theorem isn't true. - "Sounders Mac Lane" - 25: x_0 came out of nowhere; it's unclear from the text which "invertible" is meant; the basin of convergence for Newton's method for finding a local continuation can be very small indeed. - 36: Why is the adjoint of A named T^*? - 46: You need some assumptions about f.

FabHK 8y ago
I think you're being a bit harsh. The central limit theorem does hold for iid rv (independent identically distributed random variables) with finite mean and variance. Now, those assumptions can be relaxed (the rv need not be independent, but they can't be too dependent, and they need not have finite variance, but they can't be too "far out"), and some of the pertinent proofs are only a few decades old; but you can hardly expect a survey with 135 proofs to cover all the subtleties. Some of the other points may be more egregious howlers, but, again, come on - this is not the definite reference for any one of those theorems.
- tmyklebu 8y ago
  There's more than enough neat stuff I don't know in there. Unfortunately it's tough to trust a source with so many errors in the stuff I do know. I wasn't aware of any CLT for iid random variables with infinite variance. Do you have references?
  - FabHK 8y ago
    Check Valentin Petrov Limit Theorems of Probability Theory. Here [1] is a CLT for RV with infinite variance, Prop 3.1.12, but notice the (larger) scaling coefficient (1/sqrt(n log n)). Also see the second answer on SO here [2]. [1] https://web.stanford.edu/~montanar/TEACHING/Stat310A/lnotes.pdf https://web.stanford.edu/~montanar/TEACHING/Stat310A/lnotes.... [2] https://stats.stackexchange.com/questions/169611/the-role-of-variance-in-central-limit-theorem https://stats.stackexchange.com/questions/169611/the-role-of... EDIT to add: Having said that, the Lindeberg-Feller and the Lyuapunov formulation of the CLT do require finite variance, so maybe I was too quick in stating that that assumption can be relaxed.

dclowd9901 8y ago

Does anyone have a cheat sheet of sorts for the symbols and syntax used in these?

jordigh 8y ago
It doesn't work like that. Some of the same symbols are used in two different places with vastly different meanings, even within this paper. To give an imperfect programming language analogy, imagine that every symbol is implicitly defined and has lexical scope. The grammar is as far from being context-free as possible. What may sometimes look like individual symbols to you are in fact a collection of inseparable symbols with its own semantic parse.
- pantalaimon 8y ago
  That's not really helpful. I struggle with the same problem, in fact the notation intimidates me to a point where I decided to forego getting deeper into theoretical computer science and haunts me every time I try to read a paper. A resource that would explain formal mathematical notation would be great, much like a dictionary. You can't google those symbols properly either.
  - jordigh 8y ago
    Did you know what the words meant? Can you read this and except for the symbols understand everything else? I don't think the symbols are the problem. They're a very superficial obstacle, at least in this paper. This isn't meant as a put-down. It's just that I really do think the actual material requires a lot more preparation that consists in a lot more than just learning the definition of the symbols. I could rewrite the whole paper using only text and no symbols. The symbols are just shorthand for English words. I don't think if I were to replace all of the symbols with the English words that they stand for, you would be much closer to understanding.
    - dclowd9901 8y ago
      "The symbols are just shorthand for English words." OK, so then why would it be so difficult to produce a veritable cheat sheet to aide in reading a proof?

luminati 8y ago

Naive question: How would one go about learning all about this (or even a subset of this) for the mathematically inclined working engineer? Where does one even start? Just take each theorem from each section and try to follow through the proof? What are the prerequisites required?

joe_the_user 8y ago
There are standard texts on the various topics listed in the contents. There are online texts on these topics as well as free to download texts. To learn everything, get a math degree or self-study the curriculum of one. The prerequisite is basically calculus. The thing about this text is it seems like a more or less random list of theorems - it lists one theory, I think, Zorn's lemma, under topology where Zorn's lemma is more a set-theory-link-to-topology (one of the guises of the Axiom of choice, really). Which to say it has next-to-nothing on point-set topology proper. Other theory listings seem just as random. So I couldn't what order you'd follow trying to learn everything specifically here.
jacobolus 8y ago
The theorems in this list are in many cases central topics in 1+ semester courses, and aren’t really worth worrying about out of context. Overall you are looking at more than 5 years of full-time (40 hours/week) study, maybe more than 10 years. Unless you have extensive background reading and writing proofs, self-study is not likely to be very effective. You could conceivably make your way through with textbooks and the help of an expert tutor/mentor. For most people the easiest method would be to enroll in an undergraduate mathematics degree at a decent university. If you wanted to make your way through more of the topics in this list than an undergraduate degree covered, you could follow-up by enrolling in a PhD program.

angel_j 8y ago

Some Fundamental Theorems in Mathematics are bigger than others. Some Fundamental Theorems in Mathematics' Mothers are bigger than other Fundamental Theorems in Mathematics' Mothers.

weerd 8y ago

From #113, Artificial Intelligence The lebowski theorem of machine superintelligence: No AI will bother after hacking its own reward function. once the AI has figured out the philosophy of the “Dude” in the Cohen brothers movie Lebowski, also repeated mischiefs does not bother it and it “goes bowling”. I'm relieved to learn that this is a theorem. :D

HONEST_ANNIE 8y ago
The Lebowski theorem: "No superintelligent AI is going to bother with a task that is harder than hacking its reward function" is surprisingly deep. You can see the theory in action in human history. We have drives programmed by evolution, but we try to to shortcut them. Drugs are deliberate hack for example. TV, entertainment and games can provide rewards faster than effort towards real life goals. We fully understand that there is difference between the drive's purpose and what we do, but but we don't actually value the purpose of our reward function, only the reward. Catholic church tries to insist that people should limit sexual pleasure to the purpose it was created (by god or evolution) but people don't listen.

1024core 8y ago

I think it's a great list but the typos bothered me. To me, they seem to indicate sloppiness; and if there is sloppiness, could the mathematical results be sloppy too? e.g., on page 2 itself: "Anticipated by Babylonians Mathematicians in examples..." "Let f be a function of one variables..."

graycat 8y ago

Gorgeous. IIRC S. Eilenberg once said "Elegance in mathematics is directly proportional to what you can see in it and inversely proportional to the effort required to see it.". This Knill book is elegant. Topic by topic for a wide range of pure and well polished applied math, Knill is able and does go right to the most important results and for each gives a short outline of the needed definitions and of a proof, usually with good references to full details, and then states the theorem precisely. Net, for nearly any topic in pure/applied math, go there first. For many of the topics, I studied them carefully from some of the best sources, but just on a short scan this Knill book often has a better treatment, e.g., has a super nice, simple, practical statement of a fundamental theorem in Fourier series, a super nice statement of the Lebesgue decomposition from the Radon-Nikodym theorem, some nice stuff from Zorn's lemma, and much more, e.g., often some historical notes. I have to like the connection with Zorn's lemma: At one point I went to a lecture at Indiana University and to the tea before, and an older professor introduced himself as Max Zorn. Since the previous summer I'd taken a course in axiomatic set theory on an NSF summer program at Vanderbilt, I was nearly floored! All I could do was blurt out, "What did Paul Cohen prove?". The next day Zorn gave me his copy of Cohen's paper. I still have it! At one point I saved FedEx by pleasing two guys from crucial investor General Dynamics by doing a revenue projection with the differential equation y'(t) = k y(t) (b - y(t)) with y(0), k, and b given. So, the solution is a lazy S curve that starts at t = 0 at y(0) and as t increases rises, has an inflection point, and rises from below asymptotically to b. So, it is a case of growth to a market size of b. With y(t) the current revenue and (b - y(t)) the market revenue yet to be obtained, has the growth rate y'(t) proportional to the current revenue y(t) (number of current customers talking) and the remaining customers (hearing the talking) (b - y(t)). So, it's a simple model of viral growth. Well, Knill has this differential equation with b = 2 for a case of biological growth!

deleted 8y ago

[deleted]

Topolomancer 8y ago

I love Oliver Knill! Not only does he have very broad mathematical interests, he also has this crazy YouTube Channel (https://www.youtube.com/user/knill101/videos https://www.youtube.com/user/knill101/videos) where he sometimes uses a synthetic voice (!) to give talks---supposedly because he cannot talk as fast as he wants to. He really is quite an interesting charactern!

maxiepoo 8y ago

The Topos theory example is completely wrong though? > For example, if E is the topos of sets, then the slice category is the category of pointed sets: the objects are then sets together with a function selecting a point as a “base point”. There's no object X where E/X is pointed sets. If you take the co-slice of a one point set 1\E that would be the category of pointed sets. The right way to think about E/X is that its objects are "families of sets indexed by X", because a function f : Y -> X defines for each x in X a set f^{-1}(x). If you know about dependent types, this is basically a type dependent on X.

krambs 8y ago

Can you really trust any mathematician's judgment who doesn't use serial commas? ;)