Timeline for Applications of infinite graph theory
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2017 at 16:34 | comment | added | Qfwfq | Isn't the proof itself of KIL itself almost a tautology? | |
| Sep 23, 2010 at 16:08 | comment | added | John Stillwell | @Pete: Yes, the BW theorem is definitely at the easy end of the spectrum of results that follow from KIL. I mentioned it only as one of many results, some of which are much less obvious, that have the same logical strength as KIL. Steve Simpson's book Subsystems of Second-order Arithmetic gives many more such results. Another one I like is the Brouwer fixed point theorem. | |
| Sep 23, 2010 at 9:49 | comment | added | Pete L. Clark | @John: thanks for your comment. I thought a bit more about the proof of Bolzano-Weierstrass, and while I do see a place to apply KIL, I would have thought that in this case the conclusion was obvious. So I think I'm still missing out on the real connection between BW and KIL. Or are you just saying that BW is one of many results in which one can see, if one is so inclined, an infinite, finitely branching tree which necessarily contains an infinite path, and that this path exists is useful? | |
| Sep 22, 2010 at 22:05 | comment | added | John Stillwell | Pete, I see Bolzano-Weierstrass and the completeness theorem as instances of KIL because in both one finds a desired object as an infinite branch in a tree. In Bolzano-Weierstrass one finds a limit point of an infinite set in [0,1] via the "tree" of subintervals obtained by bisection. In the completeness theorem one tries to falsify a formula by building a tree of subformulas. If all branches terminate, one gets a proof; if not, an infinite branch gives a falsifying assignment. One book that proves completeness this way, IIRC, is Smullyan's First-order Logic. | |
| Sep 22, 2010 at 21:29 | comment | added | Pete L. Clark | @JS: I knew about König's infinity lemma before -- I use it in an article on factorization to give a (third!) proof that ACC on principal ideals implies the existence of factorizations into irreducibles. But I don't know about the relationship between KIL and most of the applications you give: I find the prospect of a connection to Bolzano-Weierstrass and Godel Completeness especially intriguing. Could you perhaps say a little more and/or give references for this? Thanks very much. | |
| Sep 22, 2010 at 21:06 | history | answered | John Stillwell | CC BY-SA 2.5 |