Revisions to What are some deep theorems, and why are they considered deep?

replaced http://mathoverflow.net/ with https://mathoverflow.net/

edited Apr 13, 2017 at 12:58

1
2
3

In a comment on his answer (What are some deep theorems, and why are they considered deep?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.

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.

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.

Source Link

answered Aug 17, 2013 at 2:36

Noah Schweber

19.6k
10
121
363

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.

Post Made Community Wiki by Noah Schweber

occurred Aug 17, 2013 at 2:36

Stack Exchange Network

Return to Answer