Metamathematics started in the 19th century with the discovery of paradoxes intrinsic to certain axiom systems involving infinite objects; attempts to resolve these paradoxes led to the formulation of set theory, transfinite arithmetics, and more recently to model theory/proof theory.

While of interest to mathematicians, this line of research had so far a small impact on combinatoricians / computer scientists which deal with finite or countable structures. In particular the countable structures we are interested in are often $\omega$-categorical which rules out the possibility of independence results à la Gödel.

So I would like to know if there are examples of interactions of metamathematics with "concrete" combinatorics (by which I mean essentially discrete algebra, structured algorithms and computational complexity), and how these kinds of interaction could possibly materialize given the apparent absence of overlap of the fields.

  • 3
    $\begingroup$ I suggest to have a look at H. Friedman's work. He shows the independence from the axioms of ZFC of many innocuous looking finitistic combinatorial statements. Maybe A. Weiermann's research on phase transitions in logic and combinatorics is also of interest. $\endgroup$ – Martin Berger Apr 1 '14 at 21:42
  • $\begingroup$ Read anything by Edward Kmett or Brent Yorgey. $\endgroup$ – Chad Brewbaker Apr 1 '14 at 22:06
  • 1
    $\begingroup$ @MartinBerger: I know about some finitistic statements independent from $PA$ (Goodstein's theorem, consistency of $PA$) but they don't have a 'combinatorial' flavor to me. On the other hand I don't know about any finitistic statement independent from ZFC, do you have an example? $\endgroup$ – NisaiVloot Apr 1 '14 at 22:24
  • 2
    $\begingroup$ Many of statements in your post are inaccurate (to say the least). E.g. where do you think type-theory came from? Where do you think computability theory came from? Do you know about Erdos' work on infinite combinatorics? What about finite model theory? You should edit the claims and narrow them down to finite combinatorics. $\endgroup$ – Kaveh Apr 2 '14 at 4:28
  • 1
    $\begingroup$ Regarding the interaction between higher infinites and finite combinatorial statements you can check Harvey Friedman's work, e.g. check his book Boolean Relation Theory or FOM threads. He has shown that simple concrete combinatorial statements are independent of ZFC and need large cardinals. He once said in a lecture that he has shown his innocent-looking combinatorial statements to some famous combinatorists and they agreed they are not different from typical statements that they work on. $\endgroup$ – Kaveh Apr 2 '14 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.