2010 | OriginalPaper | Buchkapitel
Combinatorics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this final chapter we look at another field that came to maturity in the 20th century: combinatorics. Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics. Here we emphasize the parts that link nicely to topics from earlier chapters, but without completely sacrificing the distinctive features of the subject. Combinatorics is often called “finite mathematics” because it studies finite objects. But there are infinitely many finite objects, and it is sometimes convenient to reason about all members of an infinite collection at once. In fact, combinatorics pioneered this idea with the use of
generating functions
(already seen in Section 10.6). Other important infinite principles in combinatorics are the
infinite pigeonhole principle
and the
Kőnig infinity lemma
. We illustrate these first by some classical proofs in number theory and analysis, then in the 20thcentury fields of
graph theory
and
Ramsey theory
. Ramsey theory leads us to a proof of the Paris–Harrington theorem, mentioned in Section 24.8 as a theorem that
cannot
be proved in the strictly finite reasoning of PA. Infinite reasoning is likewise essential for graph theory. The field had its origins in topology, and it is still relevant there, but it has expanded extraordinarily far in other directions. Graph theory today is exploring the boundaries of finite provability first exposed by Gödel’s incompleteness theorem.