Skip to content

The Proof Theory Blog

⊢ ∃x (D(x) → ∀yD(y))

Menu
  • Home
  • About
  • Contribute
  • Resources
Menu

A question from a colleague about non-well-founded proofs

Posted on November 28, 2023December 5, 2023 by Sam Sanders

The following explanation was given to a math colleague concerning nonstandard models:

if Con(PA) fails in a non-standard model, it means it contains a
“proof of non-standard length” of a contradiction from PA.  With a
little work, one can externalise that to some non-well-founded “proof
tree”, which has at each node a possibly-non-standard formula (which
in turn externalises to some not-necessarily-well-founded syntax
tree), where each step will genuinely follow from earlier steps by
some standard rule of proof, but the whole tree will be
non-well-founded, and hence not an actual proof.

Said colleague had the following question regarding this explanation:

I find this non-well-founded approach an enlightening way of viewing incompleteness.  I checked in a book by Peter Smith on Goedel’s theorems, but it does not seem to discuss this particular aspect (possibly he views it as equivalent to discussion around \omega-completeness).  Do you know of any book that would place non-well-foundedness center-stage?

1 thought on “A question from a colleague about non-well-founded proofs”

  1. Anupam Das says:
    November 29, 2023 at 6:45 pm

    I have been using that example in several of my talks in the last few years! (See, e.g. slide 31 of my talk at WoLLIC last year). I don’t know of this being discussed in any book, but this viewpoint was known to (some) logicians in the mid-20th century.

    Mints in 1978 developed his continuous cut-elimination at least in part for application to non-wellfounded proofs; indeed as a result, as he says in the abstract, “this permits us to apply [continuous cut-elimination] in the theory of models”. Some investigation connecting non-wellfounded proof trees and non-standard models has occurred in a (bizarrely titled) 1975 paper of Kriesel, Mints and Simpson, which Mints credited as an inspiration for his continuous cut-elimination.

    Since the ’70s I am unaware of further applications/developments between non-wellfounded proofs and nonstandard models, but the former have seen a resurgence of interest in the last 30 years, in particular in computer science.

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Meta

  • Register
  • Log in
  • Entries RSS
  • Privacy Policy

Search

© 2026 The Proof Theory Blog | Powered by Minimalist Blog WordPress Theme
The Proof Theory Blog uses cookies, but you can opt-out if you wish. For further information see our privacy policy. Cookie settingsAccept
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT