Avoiding actual infinities

Carl Gauss is of course beyond famous, but he had a view of infinity that was based on old ideas. He once wrote in a letter to Heinrich Schumacher in 1831:

so protestiere ich zuvörderst gegen den Gebrauch einer unendlichen Größe als einer vollendeten, welcher in der Mathematik niemals erlaubt ist. Das Unendliche ist nur eine façon de parler, indem man eigentlich von Grenzen spricht, denen gewisse Verhältnisse so nahe kommen als man will, während anderen ohne Einschränkung zu wachsen gestattet ist.

Today we want to show that the famous diagonal argument can be used without using infinite sets. Read more…

And whose theorem is it anyway?

Georg Cantor, Felix Bernstein, and Ernst Schröder are each famous for many things. But together they are famous for stating, trying to prove, and proving, a basic theorem about the cardinality of sets. Actually the first person to prove it was none of them. Cantor had stated it in 1887 in a sentence beginning, “One has the theorem that…,” without fanfare or proof. Richard Dedekind later that year wrote a proof—importantly one avoiding appeal to the axiom of choice (AC)—but neither published it nor told Cantor, and it wasn’t revealed until 1908. Then in 1895 Cantor deduced it from a statement he couldn’t prove that turned out to be equivalent to AC. The next year Schröder wrote a proof but it was wrong. Schröder found a correct proof in 1897, but Bernstein, then a 19 year old student in Cantor’s seminar, independently found a proof, and perhaps most important, Cantor himself communicated it to the International Congress of Mathematicians that year.

Today I want to go over proofs of this theorem that were written in the 1990’s not the 1890’s. Read more…

A cautionary tale

Karl Sundman was a Finnish mathematician who solved a major open problem in 1906. His solution would have been regarded as paradigm-“shifty” had it been a century or so earlier. It employed power series to represent the solutions of equations, namely the equations of the 3-body problem famously left unsolved by Isaac Newton. The tools of analysis needed to regard a convergent power series as defining a valid real number had been well accepted for a century, and the explicit giving of series and convergence proof even met the demands of mathematical constructivism of his day.

Today Ken and I want to explain why that problem is nevertheless still considered open, even though Sundman solved it over a hundred years ago.

This is a cautionary tale: For some problems there are solutions and there are solutions. There are solutions that make you famous and there are solutions that no one cares about. Unfortunately for Sundman his solution, which is correct mathematically, is the latter type; hence, his lack of fame—did you know about him? He did win honors from the top French and Swedish academies of science for this and other work in mechanics, and he has a Moon crater and an asteroid named for him. Read more…

How to find approximate page rank fast, among other things

Jennifer Chayes is the current director of a research lab in Cambridge—that is Cambridge Massachusetts—for a company called Microsoft. She is famous for her own work in many areas of theory, including phase transitions of complex systems. She is also famous for her ability to create and manage research groups, which is a rare and wonderful skill.

Today Ken and I wish to talk about how to be “shifty” in algorithm design. There is nothing underhanded, but it’s a different playing field from what we grew up with. Read more…

An approach to complexity lower bounds?

 Book source

Kurt Gödel did it all, succinctly. His famous 1938 paper “The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis” was ${1\frac{1}{3}}$ pages long. Since the Proceedings of the National Academy of Sciences was printed on single-column pages in fairy large type, it would have been under one page in FOCS or STOC format. Only Leonid Levin has famously been that succinct.

Today Ken and I wish to advance another approach on complexity questions based on succinctness and Gödel’s brilliant idea. We have covered succinctness before, but now our angle is more arithmetical.

Taking a conjecture about identities to college

Alex Wilkie is a Fellow of the Royal Society, and holds the Fielden Chair in Mathematics at the University of Manchester. Ken knew him at Oxford in 1981—1982 and again from 1986. In 1993 Wilkie won the Karp Prize of the Association of Symbolic Logic, equally with Ehud Hrushovski. This is named not after Dick Karp but rather Carol Karp, a mathematical logician in whose memory the prize was endowed.

Today I wish to talk about logical theories, motivated by some questions from Bill Gasarch and others.