<p>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.</p>

<p>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 <em>à la Gödel</em>.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-01T21:42:25.013Z
I suggest to have a look at [H. Friedman](https://u.osu.edu/friedman.8/)'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](http://cage.ugent.be/~weierman/phase.html) is also of interest.
Martin Berger
CC BY-SA 3.0
2014-04-01T22:06:05.713Z
Read anything by Edward Kmett or Brent Yorgey.
Chad Brewbaker
CC BY-SA 3.0
2014-04-01T22:24:45.267Z
@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?
NisaiVloot
CC BY-SA 3.0
2014-04-02T04:28:15.387Z
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_.
Kaveh
CC BY-SA 3.0
2014-04-02T04:33:45.780Z
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](https://u.osu.edu/friedman.8/foundational-adventures/boolean-relation-theory-book/) 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.
Kaveh
CC BY-SA 3.0
2014-04-02T12:14:58.637Z
@Kaveh: yes, I know these fields, as well as other well-developed fields like graph theory but most of their results lie on the "abstract" side, so I wouldn't include them in what I called concrete combinatorics. Also I wouldn't equate the latter with "finite" combinatorics, there are many questions about finite objects that don't seem to exhibit structure and/or tractability. Finally, I am aware of the connection between finite model theory and computational complexity but it has only delivered few results so far if I'm correct. Also, thanks for suggesting Friedman's work, I will have a look.
NisaiVloot
CC BY-SA 3.0
2014-04-02T13:08:32.407Z
@PilarLoof The book that Kaveh also links to gives many examples.
Martin Berger
<big-picture>
Interaction between metamathematics and combinatorics?
NisaiVloot
# Interaction between metamathematics and combinatorics?

(Asked by: username_0 on 2014-04-01)

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.

**Tags:** big-picture

> **Comments:**
> **username_1**: I suggest to have a look at [H. Friedman](https://u.osu.edu/friedman.8/)'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](http://cage.ugent.be/~weierman/phase.html) is also of interest.  
> **username_2**: Read anything by Edward Kmett or Brent Yorgey.  
> **username_0**: @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?  
> **username_3**: 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_.  
> **username_3**: 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](https://u.osu.edu/friedman.8/foundational-adventures/boolean-relation-theory-book/) 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.  
> **username_0**: @username_3: yes, I know these fields, as well as other well-developed fields like graph theory but most of their results lie on the "abstract" side, so I wouldn't include them in what I called concrete combinatorics. Also I wouldn't equate the latter with "finite" combinatorics, there are many questions about finite objects that don't seem to exhibit structure and/or tractability. Finally, I am aware of the connection between finite model theory and computational complexity but it has only delivered few results so far if I'm correct. Also, thanks for suggesting Friedman's work, I will have a look.  
> **username_1**: @PilarLoof The book that username_3 also links to gives many examples.  

---

## 0 answers

