Read on Twitter
Saharon Shelah and number 4, a thread.
Shelah is an incredibly prolific mathematician working mostly in mathematical logic who has (co-)authored around 1500 papers so far. His other superpower is the ability to discover number 4 where it has absolutely no reason to be. 1/32
Shelah is an incredibly prolific mathematician working mostly in mathematical logic who has (co-)authored around 1500 papers so far. His other superpower is the ability to discover number 4 where it has absolutely no reason to be. 1/32
Example 1. "There are just 4 second order quantifiers".
In first-order logic, one is allowed to form statements about structures, such as graphs, groups, fields,
etc., with only quantification over elements allowed. 2/32
In first-order logic, one is allowed to form statements about structures, such as graphs, groups, fields,
etc., with only quantification over elements allowed. 2/32
So you can say "exists x, ..." or "for all x, ..." with x ranging over the elements of the structure M, but you can't say "for all subsets of M, ..." or "for all binary relations on M, ...", etc. Allowing such
quantifiers puts us in the context of _second order logic_. 3/32
quantifiers puts us in the context of _second order logic_. 3/32
It was well-known in logic and computer science that one can express more complicated properties by quantifying over binary relations on M rather than just over the unary ones. But can we say even more quantifying over ternary relations? 4/32
And how does this compare to quantifying over functions, bijections, or any other infinitely many possible types of relations on M one can think of? In his 1973 paper Shelah proved that there are exactly 4 (four) possible types of second order quantifiers. 5/32
They are: first-order logic (no quantification over any type of subsets is allowed), monadic (you can quantify over subsets of M, but not over relations on M of any higher arity), bijections on M, and full second order logic (arbitrary relations on M of any arity). 6/32
Allowing quantification over any other type of relations you can think of will have exactly the same expressive power as one of these four (a technical detail: as long as it itself can be defined as a first-order property). 7/32
See Saharon's paper for the details:
https://link.springer.com/article/10.1007/BF02787572 8/32
https://link.springer.com/article/10.1007/BF02787572 8/32
Example 2. "Cardinal arithmetic"
This is a famous example from set theory. When talking about cardinalities of infinite sets, one wouldn't expect number 4 to appear, right? 9/32
This is a famous example from set theory. When talking about cardinalities of infinite sets, one wouldn't expect number 4 to appear, right? 9/32
Cantor famously proved that the number of subsets of any set is larger than its own cardinality, or symbolically: for every cardinal κ, κ<2^κ. 10/32
Later work of Gödel and Cohen's method of forcing made it seem that not much else about cardinal arithmetic could be proved in ZFC, the standard axioms of set theory - see Easton's theorem https://en.wikipedia.org/wiki/Easton%27s_theorem 11/32
However, it turned out that for the so-called _singular_ cardinals (cardinals that can be approximated by a smaller number of smaller cardinals) there is a number of new fascinating inequalities, and here is a remarkable one proved by Shelah: 12/32
As Shelah writes himself after receiving the Bolyai Prize in Mathematics in 2000, "almost all who saw it for the
first time were convinced this is a typographical error" and "Why the hell is it four?" ("YOU CAN ENTER CANTOR’S PARADISE!" https://arxiv.org/pdf/math/0102056.pdf). 13/32
first time were convinced this is a typographical error" and "Why the hell is it four?" ("YOU CAN ENTER CANTOR’S PARADISE!" https://arxiv.org/pdf/math/0102056.pdf). 13/32
It follows from the "PCF theory" that he introduced in the 70's, PCF stands for "possible cofinalities". It studies combinatorial questions around the cofinality of the ultraproducts of ordered sets, and is the subject Shelah's
famous book "Cardinal Arithmetic". 14/32
famous book "Cardinal Arithmetic". 14/32
In case you are not motivated to read 500 pages, Shelah wrote a short survey "Cardinal arithmetic for skeptics", https://arxiv.org/abs/math/9201251. Personally, I'm puzzled why there aren't more memes on math twitter about this kind of results. 15/32
Example 3. "Four linear orders to reach the power set."
This is another application of the PCF theory that I was lucky to work on with Saharon, motivated by some questions in model theory. 16/32
This is another application of the PCF theory that I was lucky to work on with Saharon, motivated by some questions in model theory. 16/32
In an analysis class, real numbers are defined as (Dedekind) cuts of the rationals. A cut is a partition of the rational numbers into two sets R(ed) and B(lue) such that all elements of R are less than all elements of B, and R contains no greatest element. 17/32
The same definition makes sense for an arbitrary linear order. Then, given an infinite cardinal κ, let ded(κ) be the supremum of the number of cuts over all linear orders of size κ. As the construction of the reals from the rationals shows, ded(ℵₒ) = 2^ℵₒ. 18/32
For an arbitrary κ, we have ded(κ) ≤ 2^κ (as every cut (R,B) is determined by a subset R) and κ<ded(κ). Then under the Generalized Continuum Hypothesis we have ded(κ) = 2^κ always, so consistently ded(κ) is just the exponentiation function. 19/32
On the other hand, Mitchell proved that for some κ it is consistent with ZFC that ded(κ) is strictly smaller than 2^κ (more precisely, for any κ of uncountable cofinality there is a cardinal preserving Cohen extension with this property). 20/32
At this point one might expect that basically anything about the relationship of ded(κ) and 2^κ except for the obvious inequality might be independent from ZFC. Well, not quite! 21/32
We show that for any infinite cardinal κ,
2^κ ≤ ded(ded(ded(ded(κ)))).
So you can always reach the cardinality of the powerset by iterating the "number of cuts" function 4 (four) times! 22/32
2^κ ≤ ded(ded(ded(ded(κ)))).
So you can always reach the cardinality of the powerset by iterating the "number of cuts" function 4 (four) times! 22/32
See our paper https://arxiv.org/abs/1308.3099 for the details, there are many questions remaining about ded(κ). (This function is also
important in model theory due to its connection to NIP structures, but that's a different story.) 23/32
important in model theory due to its connection to NIP structures, but that's a different story.) 23/32
Example 4. "Stability spectrum"
Model theory is a port, but also studies definable subsets of structures, like algebraic geometry studies algebraic varieties (definable sets in fields) or semialgebraic geometry studies definable sets in the field of reals. 24/32
Model theory is a port, but also studies definable subsets of structures, like algebraic geometry studies algebraic varieties (definable sets in fields) or semialgebraic geometry studies definable sets in the field of reals. 24/32
Definable sets form a Boolean algebra, which by Stone duality https://en.wikipedia.org/wiki/Stone_duality is associated to a certain totally disconnected topological space, called the space of types in model theory. 25/32
Its points are ultrafilters in this algebra - the maximal consistent collections of definable sets, or intuitively "idealized" elements of the structure that might not be present in it, but can always be found in an elementary extension. 26/32
One can measure the complexity of a theory by how complicated its definable sets are. For example, for integers with addition and multiplication, definable sets are "Gödelian" - hopelessly complicated and encode most of modern mathematics. 27/32
The complexity of the Boolean algebra of definable sets is reflected by its dual space of types, and the simplest possible invariant of a topological space is its size. So a theory is viewed as tame, or _stable_, if its type spaces are as small as possible. 27/32
More precisely, given a first-order theory T and an infinite cardinal κ, let f_T(κ) be the supremum of the number of types over all models of T of size κ. Then f_T(κ)≥κ for all κ, and T is stable if for some κ we have f_T(κ)=κ. 29/32
Shelah proved that for any countable theory T whatsoever, there are only 4 (four) possibilities for the function κ→f_T(κ)
-- they are κ, κ + 2^ℵₒ, κ^ℵₒ, and if neither of these then f_T(κ)>κ for all infinite κ! (And in fact, ≥ded(κ) in this case.) 30/32
-- they are κ, κ + 2^ℵₒ, κ^ℵₒ, and if neither of these then f_T(κ)>κ for all infinite κ! (And in fact, ≥ded(κ) in this case.) 30/32
This is called the Stability Spectrum theorem https://en.wikipedia.org/wiki/Stability_spectrum and is one of the many striking results in another important 800-page book of Saharon: 31/32
This is probably an appropriate number of examples for
this thread, so let me just reiterate the question: why the hell is it 4?
Thanks for bearing with and sharing my first twitter thread despite all the timeline chaos it has created!
32/32
this thread, so let me just reiterate the question: why the hell is it 4?
Thanks for bearing with and sharing my first twitter thread despite all the timeline chaos it has created!
32/32
