lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

incompleteness-theorem.html (2601B)

      1 <html>
      2 <head>
      3     <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.15.6/highlight.min.js"></script>
      4     <script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
      5     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.15.6/styles/default.min.css">
      6     <link rel="Stylesheet" type="text/css" href="style.css" />
      7     <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
      8     <script>
      9       document.addEventListener('DOMContentLoaded', function() {
     10         document.querySelectorAll('pre.code').forEach(function(item) {
     11           hljs.highlightBlock(item)
     12         })
     13       });
     14     </script>
     15     <title>incompleteness-theorem</title>
     16 </head>
     17 <body>
     18 <style type="text/css">
     19 nav a {
     20     text-align: left;
     21 }
     22 nav #name {
     23     text-align: right;
     24     float: right;
     25     font-style: italic;
     26 }
     27 </style>
     28     <nav>
     29     <a href="index.html">Index</a>
     30     <span id="name">Alex Balgavy</span>
     31     </nav>
     32     <hr>
     33     <div class="content">
     34     
     35 <div id="Incompleteness theorem"><h2 id="Incompleteness theorem" class="header"><a href="#Incompleteness theorem">Incompleteness theorem</a></h2></div>
     36 <p>
     37 Consider sets of function and predicate symbols:
     38 </p>
     39 <ul>
     40 <li>
     41 F = {0, S, +, ·}
     42 
     43 <li>
     44 P = {&lt;}
     45 
     46 </ul>
     47 
     48 <p>
     49 with as intended model number theory N:
     50 </p>
     51 <ul>
     52 <li>
     53 domain of N is the natural numbers with 0
     54 
     55 <li>
     56 \(0^\mathbb{N} = 0\)
     57 
     58 <li>
     59 \(S^\mathbb{N} (n) = n + 1\)
     60 
     61 <li>
     62 \(+^\mathbb{N} (n,m) = n+m\)
     63 
     64 <li>
     65 \(\mathbb{N}(n,m) = n \cdot m\)
     66 
     67 <li>
     68 \(&lt;^\mathbb{N} = \{ &lt;n,m&gt; | n,m \in \mathbb{N} \text{ such that }n &lt; m \}\)
     69 
     70 </ul>
     71 
     72 <p>
     73 One would like to have complete theory (deduction system) ⊢ for N that allows to derive all formulas that are true in N.
     74 </p>
     75 
     76 <p>
     77 First incompleteness theorem:
     78 </p>
     79 <ul>
     80 <li>
     81 every axiomatizable and sound theory ⊢ of first-order logic
     82 
     83 <li>
     84 for number theory with language &lt;F,P&gt;
     85 
     86 <li>
     87 is incomplete:
     88 
     89 <ul>
     90 <li>
     91 it contains sentences Φ that are true in N, but unprovable in ⊢: N ⊨ Φ, yet ⊬ Φ.
     92 
     93 </ul>
     94 </ul>
     95 
     96 
     97 <p>
     98 Second incompleteness theorem:
     99 </p>
    100 <ul>
    101 <li>
    102 for every axiomatizable theory ⊢ of first-order logic
    103 
    104 <li>
    105 for number theory with language &lt;F,P&gt;
    106 
    107 <li>
    108 that is rich enough to express its own consistency by a sentence Φ⊢
    109 
    110 <li>
    111 it holds that either:
    112 
    113 <ul>
    114 <li>
    115 ⊢ ⊥ (⊢ is inconsistent)
    116 
    117 <li>
    118 ⊬ Φ⊢ (hence ⊢ is incomplete)
    119 
    120 </ul>
    121 <li>
    122 so first-order theories (based on predicate logic) of number theory can't prove their own consistency
    123 
    124 </ul>
    125 
    126     </div>
    127 </body>
    128 </html>