You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Thank you for pointing me to the Kritchman and Raz paper! I actually learned about it from your comment. I found the approach so elegant that I went ahead and formalized their abstract proof of the Second Incompleteness Theorem in my repository today.
To cleanly separate the information-theoretic paradox from the first-order logic boilerplate, I created an abstract PeanoLikeSystem interface. Once Foundation is updated, we can instantiate it for PA. To make the integration work, the interface only requires the following from the formal system:
HBL conditions: A proof inside the system that C o n → ¬ ∃ x , P r ( K ( x ) > L ) (Equation 1 in the KR paper).
Σ 1 -completeness: A proof inside the system for the elimination step: if m = i , the system can compute all simple strings to find the remaining complex one (Equation 2 in the KR paper).
Internal Arithmetic: A proof inside the system of the base Pigeonhole Principle ( m ≥ 1 ) and the basic dichotomy step ( m ≥ i → m ≠ i → m ≥ i + 1 ).
Semantic Soundness: A standard soundness assumption. This allows us to avoid proving the upper counting bound ( m ≤ 2 L + 1 + 1 ) internally; instead, Lean's omega derives the final KR contradiction automatically on the meta-level.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
#758 (comment) by @AlexeyMilovanov
All reactions