Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

All mathematicians are used to thinking that certain theorems are deep, and we would probably all point to examples such as Dirichlet's theorem on primes in arithmetic progressions, the prime number theorem, and the Poincaré conjecture. I am planning to give a talk on the history of "depth" in mathematics, and for that reason I would like to have a longer list of examples and, if possible, some thoughts about what makes them deep.

Most examples, I expect, will be from after 1800, but I am also interested in examples before that date.

When it comes to the meaning of "depth," I am interested in both specific and general explanations. In specific cases, one might point to the introduction of unexpected methods, such as analysis in Dirichlet's theorem, or differential geometry in the Poincaré conjecture, which are not implicit in the statement of the theorem. In most cases, it is probably not provable that these methods are necessary (e.g. there are "elementary" proofs of Dirichlet's theorem), but in some cases it is provable, by general theorems of logic. Both types of explanation are welcome.

Update. I am a little surprised that nobody mentioned reverse mathematics, which seems to offer a precise sense in which certain theorems are "equally deep." For example, on pages 36--37 of Simpson's Subsystems of Second Order Arithmetic there is a list of 14 theorems, including the Brouwer fixed point theorem and Riemann integrability of continuous functions, which are equally deep in a precise sense. Admittedly, these are not the deepest theorems around, but they're not shallow either. Later in the book one finds other results of equal, but greater, depth. How do MO members view such results?

share|improve this question
4  
I have flagged the moderators for CW –  Yemon Choi Aug 16 '13 at 20:57
19  
"Deep" usually means "I do not understand its proof". –  Anton Petrunin Aug 16 '13 at 21:22
6  
@AntonPetrunin Or sometimes "Celebrities told me this is a Big Deal" –  Yemon Choi Aug 16 '13 at 21:25
6  
@Anton and Yemon: if you sincerely believe that "depth" is bogus, or only apparent, some debunking examples would be appreciated. –  John Stillwell Aug 16 '13 at 21:38
14  
@JohnStillwell My concern is that people use the word too often and without due care, and beauty is in the eye of the beholder. There are many results whose proofs seem too hard or arcane for me to follow, but does that make them "deeper" than, say, the Hahn-Banach theorem, or the Central Limit Theorem? –  Yemon Choi Aug 16 '13 at 21:49
show 7 more comments

16 Answers

There are many possible meanings of word "deep" one can detect in the common speech. I'll list three good and three bad but I do not pretend the list is anywhere near complete.

1) Very difficult (Fermat-Wiles, Carleson, Szemeredi, etc.). These theorems usually stand as testing tools for our methods and we can measure the development of the field by how easily they can be derived from the "general theory". Their "depth" in this sense deteriorates with time albeit slowly.

2) Ubiquitous (Dirichlet principle, maximum principles of all kinds). They may be easy to prove but form the very basis of all our mathematical thinking. This depth can only grow with time.

3) Influential (Transcedence of $e$, Furstenberg's multiple recurrence). This meaning relates not as much to the statement as to the proof. Some new connection is discerned, some new technical tool becomes available, etc.

1') With an ugly proof (4 color, Kepler's conjecture). They usually reflect our poor understanding of the matter

2') Standard black boxes used without understanding ("By a deep theorem of..." something trivial and requiring no such heavy tool follows). They are used to produced junk papers on a conveyor belt and create high citation records.

3') Hot (I'll abstain from giving an example here to avoid pointless discussions). They reflect the current fashions and self-promotion.

share|improve this answer
add comment

As a very concrete example of a deep theorem different from the ones you've already mentioned, I'd nominate the Atiyah-Singer Index theorem and its more general cousins for consideration in your talk.

One basic advantage is that a heuristic introduction to this theorem is easily possible in a few minutes: just discuss two possible definitions of the Brouwer degree of a smooth map $f:M \to M$ on a compact finite dimensional smooth manifold $M$. First, there's the analytic definition which counts the number of inverse images weighted by the sign of the Jacobian. Then, there's the topological definition involving the action of $f$ on the orientation class. The fact that these two definitions give you the same integer is somewhat of a miracle even in this "simple" setting to an audience unfamiliar with the area. This motivates the vast generalization provided by the AS index theorem!

share|improve this answer
3  
Funny, I would almost switch analytic/topological in your description. I think of the analytic as, pull back a volume (differential) form, then integrate it, and the topological as counting $f^{-1}(p)$ weighted by the action of $f$ on the orientation class of a tiny sphere around $f$ (which of course is your sign-of-the-Jacobian). –  Allen Knutson Aug 16 '13 at 20:26
1  
@AllenKnutson that really is funny, since the one I called analytic requires (some) smoothness as stated whereas the one I called topological does not. –  Vidit Nanda Aug 16 '13 at 20:34
1  
I saw a nice talk once that worked its way up to the Atiyah-Singer index theorem starting with the angles in a triangle adding up to pi. Then generalize to sphere, then to Gauss-Bonnet, then ... –  John D. Cook Aug 17 '13 at 21:49
    
Something should be called analytic, if it involves differentiation, shouldn't it? –  Kofi Aug 18 '13 at 15:12
3  
@Allen: these conventions of index theory confused me as well at first but actually they seem to make sense after a while. Analytical index is related to kernel of some differential operator, which involves solving differential equations, an obviously analytical task. On the other hand, topological index only involves algebraic topology. Of course, differential forms can appear if you work within de Rham setting but this is not necessary -- one can prefer to work with K-theory instead, a purely topological object. –  Marek Aug 20 '13 at 9:48
add comment

I can think of at least three different meanings I routinely ascribe to the word "deep" in mathematics:

  • A theorem is deep if its proof requires some fundamental new way of thinking;

  • A theorem is deep if the range of its consequences is much larger than might be obvious at a first glance; or

  • A theorem is deep if it helps define - perhaps by providing a strong dividing line? - a new kind of structure.

There is of course massive overlap between each of these notions, and many other meanings of "deep" that make sense in math. But let me stick with these three for a moment.

Certainly, one obviously deep result - deep in all three senses - is Goedel's Incompleteness Theorem. But let me give another one from mathematical logic, which is more recent and, if less accessible mathematically, perhaps more directly important to proving theorems in a wide range of areas: the Forcing Theorem of Paul Cohen.

Conceptually, the proof requires a shift in perspective, away from the earlier sense of models of $ZFC$ being built "canonically" (a la $L$) and towards a more flexible, multiverse-like view (admittedly, here, I'm imposing my own opinions to some extent). Cohen himself has written about how he discovered his proof, and its contrasts, metamathematically, with earlier work in set theory: see http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.rmjm/1181070010. Also, see http://www.jstor.org/stable/20059988 by Kanamori.

As to its consequences: As a direct consequence of Cohen's theorem, set theory changed overnight, almost literally; and soon problems from algebra and topology were found which had "hidden" set-theoretic aspects. Even then, it took years for the full power of the theorem to sink in: first iterated forcing (Tenenbaum/Solovay on Suslin trees, I believe, and later the consistency of Martin's Axiom) and class forcing (esp. Easton's (Big) Theorem) expanded the universe of "things forcing can do;" then, the discovery of strong forcing axioms, and their connections with large cardinals and descriptive set theory, changed things again. And there is no reason to believe that this is the end of the story.

Finally, the discovery of forcing led to the study of "generic" reals/sets, the combinatorics of forcing posets themselves, outer models of ZFC, etc. - a wide range of new, interesting structures which either could not be defined, or were not of interest, without the forcing theorem.


I'm not sure how directly useful this is to your question - the forcing theorem is not the sort of thing an audience for a math history talk can be guaranteed to be able to understand - but hopefully, it is useful to some extent.

share|improve this answer
    
+1 for elaborating on your own interpretation of "deep" and thus justifying your choice of answer –  Yemon Choi Aug 16 '13 at 22:04
add comment

Here are some examples from around or before 1800 that come to my mind.

  1. The reciprocity theorem for quadratic residues.

  2. The description by Gauss of the arithmetic-geometric mean in terms of elliptic integrals.

  3. The fundamental theorem of algebra.

  4. Euler-Lagrange formula in the calculus of variations.

share|improve this answer
2  
From approximately era, I'd also include Lagrange's Four-square Theorem. It's not so easy (apparently a proof eluded Fermat) and although the statement only refers to the naturals, underneath it connects with then-new ideas like unique factorization domains, quaternions etc. It also suggests the general Waring problem and there are still many open problems regarding G(k). –  Oliver Nash Aug 16 '13 at 22:20
add comment

How about the unsolvability of the quintic? The idea of studying an object by looking at how it sits inside a larger, "complete" version of itself is surely one of the most important ideas in modern mathematics, and on the algebraic side began with this result. I think the gradual discovery of connections between classical Galois theory and differential equations (http://www.math.huji.ac.il/~kamensky/lectures/diffgalois.pdf), Riemannian manifolds (Galois Groups vs. Fundamental Groups), and pure category theory (http://ncatlab.org/nlab/show/Galois%20topos) (to give a small sampling) is clear evidence of the depth of this result.

(Sadly, this is not quite pre-1800.)

share|improve this answer
add comment

The way I understand the word "deep" is that a deep theorem should reveal some important and non-obvious mathematical fact, and its proof should not be straightforward, simple, or obvious.

All these adjectives—"important", "obvious", "straightforward", "simple"—are subjective. So the assessment of a theorem as deep (or not) can change with time, and can vary from mathematician to mathematician.

A theorem whose "depth" is widely recognized across time and place is typically one whose importance has stood the test of time and whose proof has resisted many attempts at simplification. Good examples might be the main theorems of class field theory (Artin reciprocity, say), the Feit–Thompson odd-order theorem, and the Weil conjectures (Deligne's theorem).

For examples of theorems whose depth might be debated, or whose depth may have changed over time, you can probably pick almost any famous theorem from a long time ago whose proof is now considered easy. If you were to propose that the Pythagorean theorem or the irrationality of √2 were deep (or not deep), you could probably get a lively debate going. In one of Serge Lang's textbooks, he says something to the effect that Galois theory is a nice topic to teach because it very quickly gives an "impression of depth." Implicitly, I believe that Lang is saying that he doesn't think that Galois theory is very deep—perhaps because the proofs are too simple?—but that to a student it might appear to be deep because the results are famous, and the students will not find the statements or proofs trivial.

share|improve this answer
3  
My impression is that for a certain way of mathematical thought, there are "profound trivialities" (Yoneda lemma springs to mind, I'm sure there should be more) which such people might well call "deep", even though the proofs are simple –  Yemon Choi Aug 16 '13 at 22:33
4  
I have heard more than once that "deep results become great definitions". Forcing this idea a little bit, the proof of the irrationality of $\sqrt 2$ leads us to the definition of irrational numbers, just as Euclid's theorem led to the definition of Euclidian domains and UFD's. BTW, I first heard the phrase applied to the Heine-Borel theorem, the statement that every open covering of a closed and bounded set of $\mathbb R^n$ has a finite open subcover, which eventually became de definition of a compact set. I don't know if that qualifies as a deep result, but it was certainly "influential". –  Pablo Zadunaisky Aug 17 '13 at 20:34
    
@Pablo: I would add that the Pythagorean theorem became the definition of inner product. –  John Stillwell Aug 18 '13 at 16:11
1  
Other possible "profound trivialities" include Schur's lemma in representation theory, and linearity of expectation in probability theory. –  Timothy Chow Aug 19 '13 at 2:11
add comment

I want to mention a few examples from homotopy theory:

1) Bott periodicity (1957): This states (in a form) that the homotopy groups of the infinite unitary group $U = colim \, U(n)$ are $2$-periodic and the homotopy groups of $O = colim\, O(n)$ are $8$-periodic. This theorem is from 1957, but there is still no easy proof, although there are a lot of proofs (see also this mathoverflow question). I think, having a lot of proofs, but no easy one is a sign for depth. Another sign is that this is actually quite surprising: Why should homotopy groups be periodic??

2) Hopf invariant $1$ (1960): This says that the Hopf maps $S^3\to S^2$, $S^7\to S^4$ and $S^{15}\to S^8$ are the only maps between spheres of Hopf invariant $1$. This actually implies that the only (homotopy) spheres which have trivial tangent bundle are $S^0$, $S^1$ ,$S^3$ and $S^7$. Furthermore, it also implies that $\mathbb{R}$, $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$ are the only finite-dimensional division algebras over $\mathbb{R}$. Not only these applications indicate depth, but also that for this question the Adams spectral sequence was developed and also for a similar question Adams operations.

3) The nilpotence theorem (1988): One version says that a "self-map" of a finite CW-complex $f: \Sigma^kX\to X$ is stably nilpotent if the induced map $MU_*(f): MU_*X \to MU_*Y$ in complex bordism is $0$. Here, $f$ is stably nilpotent if some suspension $\Sigma^m f^n: \Sigma^{kn+m} X \to \Sigma^m X$ of some iteration of $f$ is null-homotopic. This is quite surprising: Why should complex bordism detect something like that? The nilpotence theorem implies directly that every map between spheres $S^k \to S^m$ for $m\neq k$ is stably nilpotent. It has also an amazing number of other consequences in stable homotopy theory. There is essentially only one proof known today (as far as I am aware of), which is quite complicated.

One could mention also a lot of theorems from geometric topology, like the Poincare conjecture(s). As Fields medal work is probably always deep, I don't want to bore you with that. Also Gromov was already mentioned as a source of a deep theorem. He has quite a bunch of these. One of my favorites is the h-principle, which is also quite surprising, comes in many facets and has a number of different (quite non-trivial) proofs.

Number theory is also full of deep theorems. The main theorems of class field theory come to my mind. The first versions of these were proven by Takagi in 1920 -- probably then one of the deepest theories/theorems in mathematics. The whole Langlands program is, of course, even deeper.

share|improve this answer
add comment

I believe that Gromov's theorem that groups of polynomial growth have a nilpotent subgroup of finite index is an extremely deep result. It meets almost all criteria.

  1. The proof involved new and original ideas like Gromov-Hausdorff convergence of rescaled Cayley graphs.
  2. It relied on nontrivial results (Tits alternative and Montgomery-Zippin).
  3. There is still no truly easy proof. Although Kleiner has found a way to get a linear representation avoiding Montgomery-Zippin, his proof is still nontrivial and geometric, not algebraic.

Gromv's result is used in many contexts and I think his proof is one of the reasons combinatorial group theory became geometric group theory.

share|improve this answer
add comment

I recall Tim Gowers (rough) definition of depth in mathematics, on Dick Lipton's blog:

"I agree with those who have commented that depth and logical strength are different things. I would define depth (imprecisely) in something like the way that a computer scientist talks about depth of a circuit: a result is deep if it depends on a breakthrough idea that depends on a breakthrough idea that depends on a breakthrough idea that depends on a breakthrough idea that depends on a breakthrough idea that …"

See: http://rjlipton.wordpress.com/2011/02/03/infinite-objects-and-deep-proofs/#comment-10600, and Lipton's original post (there) about ``Infinite Objects And Deep Proofs".

share|improve this answer
1  
That is a really great description! It has some visual appeal if you replace "depends on" with "is deeper than"… –  Dirk Aug 17 '13 at 18:25
1  
That seems more like a property of the proof then the theorem. –  user1708 Aug 18 '13 at 12:51
add comment

I feel this may be a cut below some of the other amazingly deep theorems already mentioned, but I think a case can be made in favor of Steinitz's Theorem: the 1-skeletons (vertex-edge graphs) of convex polyhedra are exactly the 3-connected planar graphs. Steinitz's original proof also proved that any 3-connected graph can be realized with integer coordinates, a claim that is false in four dimensions: there exist fundamentally irrational 4-polytopes. Steinitz's proof requires integer coordinates with an exponential number of bits (exponential in $n$, the number of vertices), but the graph-drawing community has since lowered this to $O(n)$ bits.
     WikipediaImage
The Koebe-Andreev-Thurston Theorem shows that all these planar 3-connected graphs can be realized by very specialized convex polyhedra: those with a midsphere representation:
     KAT
David Eppstein and Elena Mumford have extended Steinitz's theorem to orthogonal polyhedra:
     Eppstein


Steinitz's 1922 Theorem is the source for much of the subsequent development of the connections between the geometry and the combinatorics of polytopes.

share|improve this answer
add comment

Noether's theorem is a very deep result, even if the proof is rather simple. The relationship between symmetry and conservation laws is far from obvious, and it gives a tremendous amount of insight into the world around us.

share|improve this answer
add comment

Kolmogorov-Arnold-Moser (KAM) theorem in the study of perturbed Hamiltonian systems. This landmark theorem clarified a major point in the field, and answered in positive the question of existence of systems which are neither ergodic, nor integrable, but rather "near integrable" in some appropriate sense. It also dispelled the long held belief that arbitrary small perturbations can convert an integrable system into an ergodic one ("Ergodic Hypothesis"). The result was exactly the opposite of this belief.

The theorem spawned a whole subfield (KAM Theory) which still is very active.

share|improve this answer
add comment

In a comment on his answer (What are some deep theorems, and why are they considered deep?), njguliyev argues that "all complete classification theorems seem deep to me." This is generally something I agree with; but equally deep, I feel, are theorems showing that no "complete classification" is possible. Obviously, One's Mileage May Vary as the meaning of "complete classification" is not fixed, but here are a few non-classification theorems from logic that cover a wide range of notions of "complete classification," all of which I feel are deep results (or collections of deep results):

  • Much of Saharon Shelah's work in model theory falls into this category. To quote from "A guide to classical and modern model theory" by Marcja and Toffalori (pg. 226), "The Shelah strategy was to determine a series of successive key properties (simplicity, stability, superstability, and so on) concerning complete theories and having a twofold role: in fact, each of them allows a new significant step towards classifiability, while its negation excludes any hope of classification." One specific example is his Main Gap Theorem, which shows that for any countable complete theory $T$, either $T$ has exactly $2^\kappa$ many models of cardinality $\kappa$ for each $\kappa$, or the number of models of $T$ of cardinality $\aleph_\alpha$ is strictly below $\beth_{\omega_1}(\vert\alpha\vert)$ (which will usually be far below $2^{\aleph_\alpha}$). Intuitively, in the former case there are simply "too many" models of $T$ for there to be a classification theory.

  • In descriptive set theory, Greg Hjorth proved a powerful dichotomy result that (roughly) shows that given a Polish group action on a Polish space, either the orbit equivalence relation has a nice classification in terms of countable structures, or is "turbulent" and hence strongly unclassifiable; see http://www.jstor.org/stable/20749622?seq=3.

  • In computability theory, the paper "Computable structure and non-structure theorems" (http://link.springer.com/article/10.1023%2FA%3A1021758312697#page-1) by Goncharov and Knight, studies classifiability of computable structures in effective ways. The "computable structure theorems" they seek are simple descriptions of computable structures in a given (usually elementary) class, up to isomorphism or some other equivalence relation (e.g., computable isomorphism). There are several possible approaches to this, and the paper examines three. The simplest is that a collection of computable structures is unclassifiable if there is no computable bound on the Scott rank of members in the collection; examples of classes which admit no computable classification in this include sense linear orders and Boolean algebras. There is also a nice metatheorem (3.6), that (for an appropriate class $K$) if there are computable members of $K$ of arbitrarily high computable rank, then there is a computable member of $K$ with noncomputable rank (i.e., rank $\omega_1^{CK}$, the first non-computable ordinal).

There are, of course, far more non-classifiability theorems from outside logic, but I don't know enough about them to list interesting examples.

share|improve this answer
add comment

The spectral theorem for self-adjoint operators.

ADDED: I am not a native English speaker and therefore most times I try to give shorter answers. But after seeing some comments I feel I have to add some more explanation.

The reason I chose this theorem is neither "I do not understand its proof" nor "Celebrities told me this is a Big Deal". The abovementioned theorem characterizes unbounded self-adjoint operators (i.e. pairs of a domain and a mapping) in terms of families (classes) of projections (bounded everywhere defined operators!) so that the domain of an unbounded operator is explicitly determined as a set of points satisfying a single convergence condition.

Among the theorems of type "I fully understand its proof" (rephrasing Anton Petrunin's comment) the existence and uniqueness theorem for classic Sturm-Liouville problem is another example.

I call them "deep", because I cannot imagine myself creating such connections between so different types of mathematical objects. On the contrary, the statement and the (idea of) proof of the Hahn-Banach theorem (mentioned by Yemon Choi), for instance, seems quite straightforward to me.

share|improve this answer
1  
"And why are they considered deep?" –  Yemon Choi Aug 16 '13 at 20:56
    
Actually all complete classification theorems seem deep to me. Like the classification of compact two-dimensional manifolds, for example. –  user26107 Aug 16 '13 at 21:06
    
Thank you for adding some justification. –  Yemon Choi Aug 16 '13 at 21:24
    
Or numbers smaller than 10... –  Igor Rivin Aug 16 '13 at 23:46
    
I am sorry, but I had to say "all complete characterization theorems". –  user26107 Aug 17 '13 at 9:52
add comment

Just a few elementary suggestions I don't have the time to elaborate on:

  • The first deep result in linear algebra is the Jordan normal form. Arguably the difficulty of its proof is not out of proportion to the complexity of the result itself (Jordan blocks are messy), but it is not straightforward from the viewpoint from which the theorem is usually presented (i. e., basic linear algebra, not quiver representation theory); I recall trying my hands at bad approaches for quite a long time until reading up the proof years ago (trying to split off direct addends IIRC was one of them).

  • The structure theorem for finitely generated abelian groups and the fact that subgroups of finitely generated free abelian groups are free. Of course, from the right viewpoint, this generalizes to the structure theorem for modules over a PID, and that also covers the Jordan normal form. (Unfortunately, this is not how things are usually presented in undergraduate education. And the PID generalization is still far from trivial.)

  • Still in linear algebra, I found the commuting blocks determinant formula surprisingly nontrivial to prove. It is not deep, but deeper than expected.

  • The Nielsen-Schreier theorem. Similarly, the Shirshov-Witt theorem. I can't say they are used very often, but they are very natural.

  • The Littlewood-Richardson rule, even now as it has received a 2-page proof after 50 years (and many longer proofs).

  • The Robinson-Schensted(-Knuth) correspondence is still considered mysterious and badly understood (see e. g. my question a few days ago). Most tableau operations introduced long after it (jeu de taquin, promotion) seem to be more manageable. Since Fomin, Roby, Steinberg and others, we know of various analogues, alternative descriptions and simplifications, but it seems that from whatever perspective you look at it, there are some things that don't fit. This is admittedly more a case of fedja's 1' situation, but people seem to not regard it as that.

  • Basics of Lie algebra theory (Engel's theorem, Lie's theorem) are still not trivial (remember the hackery used to apply a nonnegative-sum-of-squares argument over an arbitrary field of characteristic $0$ ?).

  • I always found the basics of semisimple algebras (double centralizer theorem, Artin-Wedderburn) mysterious and their proofs unmotivated. Whether this is a matter of depth or my lack of understanding is a different question.

share|improve this answer
add comment

I typically interpret "deep" as implying a contrast between how little work you have to put into a theorem (e.g. the complexity of the relevant axioms and preliminary definitions) and how much work you get out of it (e.g. how useful it is for proving other desired results or how much insight it provides into previously confusing ideas).

In this sense, the "deepest" theorem I know about is Lawvere's Theorem, which is the main theorem in his 1969 paper Diagonal Arguments and Cartesian Closed Categories.

The theorem states that, in a cartesian closed category, if an object (type) $A$ possesses a point-surjective funtion onto (parametrizes) the type $Y^A$ of arrows (functions) $A \to Y$ for some object $Y$, then every $e:Y \to Y$ has a fixed point (i.e. a point $y:1 \to Y$ such that $e \circ y = y$).

Point-surjectivity, for an arrow $f : A \to B$, means that for every point $b : 1 \to B$ (a term of type B), there is a point $a : 1 \to A$ (a term of type A) such that $f \circ a = b$.

The proof of the theorem critically depends on associating to each function $A \to Y$ a term of type $A$ (a kind of generalized Gödel numbering) and then passing the function coded for by $a : 1 \to A$ itself as an argument. The result is then used to construct a fixed point for an arbitrary $e : Y \to Y$.

Typical applications of the theorem use its contrapositive and an object known not to have this "fixed-point property" to show that there can be no surjective functions from some type $A$ to a function type with domain $A$, which can be interpreted as queries that return values in some type $Y$ known not to have the fixed-point property; a common choice is the two-term type $2$. Then the type $2^A$ can be interpreted as the type of propositions about terms of type $A$, and the theorem refutes the possibility of parameterizing propositions about terms of type $A$ by terms of type $A$.

Applications include:

Russell's Paradox: We can apply the theorem to a category formed from terms and proofs in a first-order theory like naive set theory; we take $A$ to be the type of sets and $Y$ to be $2$, the type of truth values; then the nonexistence of a parametrization of (first-order) properties of sets by sets is just Russell's Paradox - since a consistent theory requires the existence of $\neg : 2 \to 2$, which switches the two truth values and thus has no fixed point, we can't consistently associate a set to each definable property of sets, so we must use some kind of restricted comprehension.

Cantor's Theorem: This one follows immediately from considering the category of sets and functions; $A$ is any set and $Y$ is the two element set (which we can again call "$2$").

I won't go into detail about Tarski's Theorem, Gödel's Incompleteness Theorems, or the Halting Problem because I'm lazy; all of these are essentially applications of the general idea that no type is big enough to encode all of the propositions about itself.

share|improve this answer
1  
    
For Gödel Incompleteness in Lawverean spirit see Todd Trimble's page ncatlab.org/toddtrimble/published/…. –  David Corfield Aug 17 '13 at 8:00
3  
I think "deep" as the OP wants it is NOT about theorems with easy proofs and lots of consequences; maybe mathoverflow.net/questions/5357 is more about this. This thread is about theorems with HARD proofs that are still very important and useful (which contrasts the usual situation, at least in algebra, where the really useful theorems tend to have relatively simple proofs). –  darij grinberg Aug 17 '13 at 12:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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