CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Gödel's completeness theorem - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"c0374be6-4546-4e49-875b-15ea9061f70a","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Gödel's_completeness_theorem","wgTitle":"Gödel's completeness theorem","wgCurRevisionId":1251767484,"wgRevisionId":1251767484,"wgArticleId":12450,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","CS1 German-language sources (de)","Webarchive template wayback links","Theorems in the foundations of mathematics","Metatheorems","Model theory","Proof theory","Works by Kurt Gödel"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Gödel's_completeness_theorem","wgRelevantArticleId":12450,"wgIsProbablyEditable":true, "wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q902052","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics": true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar", "ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/3/34/Completude_logique_premier_ordre.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="415"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/3/34/Completude_logique_premier_ordre.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="277"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="222"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Gödel's completeness theorem - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Gödel_s_completeness_theorem rootpage-Gödel_s_completeness_theorem skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=G%C3%B6del%27s+completeness+theorem" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=G%C3%B6del%27s+completeness+theorem" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=G%C3%B6del%27s+completeness+theorem" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=G%C3%B6del%27s+completeness+theorem" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Preliminaries" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Preliminaries"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Preliminaries</span> </div> </a> <ul id="toc-Preliminaries-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Statement" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Statement"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Statement</span> </div> </a> <button aria-controls="toc-Statement-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Statement subsection</span> </button> <ul id="toc-Statement-sublist" class="vector-toc-list"> <li id="toc-Gödel's_original_formulation" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Gödel's_original_formulation"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Gödel's original formulation</span> </div> </a> <ul id="toc-Gödel's_original_formulation-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-More_general_form" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#More_general_form"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>More general form</span> </div> </a> <ul id="toc-More_general_form-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Model_existence_theorem" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Model_existence_theorem"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Model existence theorem</span> </div> </a> <ul id="toc-Model_existence_theorem-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-As_a_theorem_of_arithmetic" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#As_a_theorem_of_arithmetic"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>As a theorem of arithmetic</span> </div> </a> <ul id="toc-As_a_theorem_of_arithmetic-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Consequences" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Consequences"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Consequences</span> </div> </a> <ul id="toc-Consequences-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Relationship_to_the_incompleteness_theorems" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Relationship_to_the_incompleteness_theorems"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Relationship to the incompleteness theorems</span> </div> </a> <ul id="toc-Relationship_to_the_incompleteness_theorems-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Relationship_to_the_compactness_theorem" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Relationship_to_the_compactness_theorem"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Relationship to the compactness theorem</span> </div> </a> <ul id="toc-Relationship_to_the_compactness_theorem-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Completeness_in_other_logics" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Completeness_in_other_logics"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Completeness in other logics</span> </div> </a> <ul id="toc-Completeness_in_other_logics-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Proofs" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Proofs"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Proofs</span> </div> </a> <ul id="toc-Proofs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>Further reading</span> </div> </a> <ul id="toc-Further_reading-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Gödel's completeness theorem</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 17 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-17" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">17 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-cv mw-list-item"><a href="https://cv.wikipedia.org/wiki/%D0%93%D1%91%D0%B4%D0%B5%D0%BB%C4%95%D0%BD_%D1%82%D1%83%D0%BB%D0%BB%D0%B8%D0%BB%C4%95%D1%85_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B8" title="Гёделĕн туллилĕх теореми – Chuvash" lang="cv" hreflang="cv" data-title="Гёделĕн туллилĕх теореми" data-language-autonym="Чӑвашла" data-language-local-name="Chuvash" class="interlanguage-link-target"><span>Чӑвашла</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/G%C3%B6delova_v%C4%9Bta_o_%C3%BAplnosti_predik%C3%A1tov%C3%A9_logiky" title="Gödelova věta o úplnosti predikátové logiky – Czech" lang="cs" hreflang="cs" data-title="Gödelova věta o úplnosti predikátové logiky" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/G%C3%B6delscher_Vollst%C3%A4ndigkeitssatz" title="Gödelscher Vollständigkeitssatz – German" lang="de" hreflang="de" data-title="Gödelscher Vollständigkeitssatz" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Teorema_de_completitud_de_G%C3%B6del" title="Teorema de completitud de Gödel – Spanish" lang="es" hreflang="es" data-title="Teorema de completitud de Gödel" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%82%D8%B6%DB%8C%D9%87_%D8%AA%D9%85%D8%A7%D9%85%DB%8C%D8%AA_%DA%AF%D9%88%D8%AF%D9%84" title="قضیه تمامیت گودل – Persian" lang="fa" hreflang="fa" data-title="قضیه تمامیت گودل" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_compl%C3%A9tude_de_G%C3%B6del" title="Théorème de complétude de Gödel – French" lang="fr" hreflang="fr" data-title="Théorème de complétude de Gödel" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B4%B4%EB%8D%B8%EC%9D%98_%EC%99%84%EC%A0%84%EC%84%B1_%EC%A0%95%EB%A6%AC" title="괴델의 완전성 정리 – Korean" lang="ko" hreflang="ko" data-title="괴델의 완전성 정리" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Teorema_di_completezza_di_G%C3%B6del" title="Teorema di completezza di Gödel – Italian" lang="it" hreflang="it" data-title="Teorema di completezza di Gödel" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9E%D7%A9%D7%A4%D7%98_%D7%94%D7%A9%D7%9C%D7%9E%D7%95%D7%AA_%D7%A9%D7%9C_%D7%92%D7%93%D7%9C" title="משפט השלמות של גדל – Hebrew" lang="he" hreflang="he" data-title="משפט השלמות של גדל" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/G%C3%B6del_teljess%C3%A9gi_t%C3%A9tele" title="Gödel teljességi tétele – Hungarian" lang="hu" hreflang="hu" data-title="Gödel teljességi tétele" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Volledigheidsstelling_van_G%C3%B6del" title="Volledigheidsstelling van Gödel – Dutch" lang="nl" hreflang="nl" data-title="Volledigheidsstelling van Gödel" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E3%81%AE%E5%AE%8C%E5%85%A8%E6%80%A7%E5%AE%9A%E7%90%86" title="ゲーデルの完全性定理 – Japanese" lang="ja" hreflang="ja" data-title="ゲーデルの完全性定理" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Teorema_da_completude_de_G%C3%B6del" title="Teorema da completude de Gödel – Portuguese" lang="pt" hreflang="pt" data-title="Teorema da completude de Gödel" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F_%D0%BE_%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B5" title="Теорема Гёделя о полноте – Russian" lang="ru" hreflang="ru" data-title="Теорема Гёделя о полноте" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%93%D0%B5%D0%B4%D0%B5%D0%BB%D0%BE%D0%B2%D0%B0_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%BF%D0%BE%D1%82%D0%BF%D1%83%D0%BD%D0%BE%D1%81%D1%82%D0%B8" title="Геделова теорема о потпуности – Serbian" lang="sr" hreflang="sr" data-title="Геделова теорема о потпуности" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93%D0%B5%D0%B4%D0%B5%D0%BB%D1%8F_%D0%BF%D1%80%D0%BE_%D0%BF%D0%BE%D0%B2%D0%BD%D0%BE%D1%82%D1%83" title="Теорема Геделя про повноту – Ukrainian" lang="uk" hreflang="uk" data-title="Теорема Геделя про повноту" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%AE%8C%E5%A4%87%E6%80%A7%E5%AE%9A%E7%90%86" title="哥德尔完备性定理 – Chinese" lang="zh" hreflang="zh" data-title="哥德尔完备性定理" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q902052#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/G%C3%B6del%27s_completeness_theorem" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:G%C3%B6del%27s_completeness_theorem" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/G%C3%B6del%27s_completeness_theorem"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/G%C3%B6del%27s_completeness_theorem"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/G%C3%B6del%27s_completeness_theorem" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/G%C3%B6del%27s_completeness_theorem" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&oldid=1251767484" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=G%C3%B6del%27s_completeness_theorem&id=1251767484&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FG%25C3%25B6del%2527s_completeness_theorem"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FG%25C3%25B6del%2527s_completeness_theorem"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=G%C3%B6del%27s_completeness_theorem&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q902052" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Fundamental theorem in mathematical logic</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">For the subsequent theories about the limits of provability, see <a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">Gödel's incompleteness theorems</a>.</div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Completude_logique_premier_ordre.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/34/Completude_logique_premier_ordre.png/400px-Completude_logique_premier_ordre.png" decoding="async" width="400" height="138" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/34/Completude_logique_premier_ordre.png/600px-Completude_logique_premier_ordre.png 1.5x, //upload.wikimedia.org/wikipedia/commons/3/34/Completude_logique_premier_ordre.png 2x" data-file-width="621" data-file-height="215" /></a><figcaption>The formula (<a href="/wiki/Universal_quantification" title="Universal quantification">∀</a><i>x</i>. <i>R</i>(<i>x</i>,<i>x</i>)) <a href="/wiki/Material_conditional" title="Material conditional">→</a> (∀<i>x</i><a href="/wiki/Existential_quantification" title="Existential quantification">∃</a><i>y</i>. <i>R</i>(<i>x</i>,<i>y</i>)) holds in all <a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">structures</a> (only the simplest 8 are shown left). By Gödel's completeness result, it must hence have a <a href="/wiki/Natural_deduction" title="Natural deduction">natural deduction</a> proof (shown right).</figcaption></figure> <p><b>Gödel's completeness theorem</b> is a fundamental theorem in <a href="/wiki/Mathematical_logic" title="Mathematical logic">mathematical logic</a> that establishes a correspondence between <a href="/wiki/Semantics" title="Semantics">semantic</a> truth and syntactic <a href="/wiki/Provability_logic" title="Provability logic">provability</a> in <a href="/wiki/First-order_logic" title="First-order logic">first-order logic</a>. </p><p>The completeness theorem applies to any first-order <a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">theory</a>: If <i>T</i> is such a theory, and φ is a sentence (in the same language) and every model of <i>T</i> is a model of φ, then there is a (first-order) proof of φ using the statements of <i>T</i> as axioms. One sometimes says this as "anything true in all models is provable". (This does not contradict <a href="/wiki/G%C3%B6del%27s_incompleteness_theorem" class="mw-redirect" title="Gödel's incompleteness theorem">Gödel's incompleteness theorem</a>, which is about a formula φ<sub>u</sub> that is unprovable in a certain theory <i>T</i> but true in the "standard" model of the natural numbers: φ<sub>u</sub> is false in some other, "non-standard" models of <i>T</i>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>) </p><p>The completeness theorem makes a close link between <a href="/wiki/Model_theory" title="Model theory">model theory</a>, which deals with what is true in different models, and <a href="/wiki/Proof_theory" title="Proof theory">proof theory</a>, which studies what can be formally proven in particular <a href="/wiki/Formal_system" title="Formal system">formal systems</a>. </p><p>It was first proved by <a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Kurt Gödel</a> in 1929. It was then simplified when <a href="/wiki/Leon_Henkin" title="Leon Henkin">Leon Henkin</a> observed in his <a href="/wiki/Ph.D._thesis" class="mw-redirect" title="Ph.D. thesis">Ph.D. thesis</a> that the hard part of the proof can be presented as the Model Existence Theorem (published in 1949).<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Henkin's proof was simplified by <a href="/wiki/Gisbert_Hasenjaeger" title="Gisbert Hasenjaeger">Gisbert Hasenjaeger</a> in 1953.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Preliminaries">Preliminaries</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=1" title="Edit section: Preliminaries"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are numerous <a href="/wiki/Deductive_system" class="mw-redirect" title="Deductive system">deductive systems</a> for first-order logic, including systems of <a href="/wiki/Natural_deduction" title="Natural deduction">natural deduction</a> and <a href="/wiki/Hilbert-style_deduction_system" class="mw-redirect" title="Hilbert-style deduction system">Hilbert-style systems</a>. Common to all deductive systems is the notion of a <i>formal deduction</i>. This is a sequence (or, in some cases, a finite <a href="/wiki/Tree_structure" title="Tree structure">tree</a>) of formulae with a specially designated <i>conclusion</i>. The definition of a deduction is such that it is finite and that it is possible to verify <a href="/wiki/Algorithm" title="Algorithm">algorithmically</a> (by a <a href="/wiki/Computer" title="Computer">computer</a>, for example, or by hand) that a given sequence (or tree) of formulae is indeed a deduction. </p><p>A first-order formula is called <i><a href="/wiki/Validity_(logic)" title="Validity (logic)">logically valid</a></i> if it is true in every <a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">structure</a> for the language of the formula (i.e. for any assignment of values to the variables of the formula). To formally state, and then prove, the completeness theorem, it is necessary to also define a deductive system. A deductive system is called <i>complete</i> if every logically valid formula is the conclusion of some formal deduction, and the completeness theorem for a particular deductive system is the theorem that it is complete in this sense. Thus, in a sense, there is a different completeness theorem for each deductive system. A converse to completeness is <i><a href="/wiki/Soundness_theorem" class="mw-redirect" title="Soundness theorem">soundness</a></i>, the fact that only logically valid formulas are provable in the deductive system. </p><p>If some specific deductive system of first-order logic is sound and complete, then it is "perfect" (a formula is provable if and only if it is logically valid), thus equivalent to any other deductive system with the same quality (any proof in one system can be converted into the other). </p> <div class="mw-heading mw-heading2"><h2 id="Statement">Statement</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=2" title="Edit section: Statement"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>We first fix a deductive system of first-order predicate calculus, choosing any of the well-known equivalent systems. Gödel's original proof assumed the Hilbert-Ackermann proof system. </p> <div class="mw-heading mw-heading3"><h3 id="Gödel's_original_formulation"><span id="G.C3.B6del.27s_original_formulation"></span>Gödel's original formulation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=3" title="Edit section: Gödel's original formulation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The completeness theorem says that if a formula is logically valid then there is a finite deduction (a formal proof) of the formula. </p><p>Thus, the deductive system is "complete" in the sense that no additional inference rules are required to prove all the logically valid formulae. A converse to completeness is <i><a href="/wiki/Soundness_theorem" class="mw-redirect" title="Soundness theorem">soundness</a></i>, the fact that only logically valid formulae are provable in the deductive system. Together with soundness (whose verification is easy), this theorem implies that a formula is logically valid <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> it is the conclusion of a formal deduction. </p> <div class="mw-heading mw-heading3"><h3 id="More_general_form">More general form</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=4" title="Edit section: More general form"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The theorem can be expressed more generally in terms of <a href="/wiki/Logical_consequence" title="Logical consequence">logical consequence</a>. We say that a sentence <i>s</i> is a <i>syntactic consequence</i> of a theory <i>T</i>, denoted <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\vdash s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊢</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\vdash s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb8d918c0eca121c4fccc66c1e453786976865b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.437ex; height:2.176ex;" alt="{\displaystyle T\vdash s}"></span>, if <i>s</i> is provable from <i>T</i> in our deductive system. We say that <i>s</i> is a <i>semantic consequence</i> of <i>T</i>, denoted <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\models s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊨</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\models s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b0c41a2dbfb785fc9a094719e098e991c3f5c370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:2.843ex;" alt="{\displaystyle T\models s}"></span>, if <i>s</i> holds in every <a href="/wiki/Model_(mathematical_logic)" class="mw-redirect" title="Model (mathematical logic)">model</a> of <i>T</i>. The completeness theorem then says that for any first-order theory <i>T</i> with a <a href="/wiki/Well-order" title="Well-order">well-orderable</a> language, and any sentence <i>s</i> in the language of <i>T</i>, </p> <style data-mw-deduplicate="TemplateStyles:r996643573">.mw-parser-output .block-indent{padding-left:3em;padding-right:0;overflow:hidden}</style><div class="block-indent">if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\models s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊨</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\models s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b0c41a2dbfb785fc9a094719e098e991c3f5c370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:2.843ex;" alt="{\displaystyle T\models s}"></span>, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\vdash s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊢</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\vdash s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb8d918c0eca121c4fccc66c1e453786976865b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.437ex; height:2.176ex;" alt="{\displaystyle T\vdash s}"></span>.</div> <p>Since the converse (soundness) also holds, it follows that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\models s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊨</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\models s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b0c41a2dbfb785fc9a094719e098e991c3f5c370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:2.843ex;" alt="{\displaystyle T\models s}"></span> <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\vdash s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊢</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\vdash s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb8d918c0eca121c4fccc66c1e453786976865b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.437ex; height:2.176ex;" alt="{\displaystyle T\vdash s}"></span>, and thus that syntactic and semantic consequence are equivalent for first-order logic. </p><p>This more general theorem is used implicitly, for example, when a sentence is shown to be provable from the axioms of <a href="/wiki/Group_theory" title="Group theory">group theory</a> by considering an arbitrary group and showing that the sentence is satisfied by that group. </p><p>Gödel's original formulation is deduced by taking the particular case of a theory without any axiom. </p> <div class="mw-heading mw-heading3"><h3 id="Model_existence_theorem">Model existence theorem</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=5" title="Edit section: Model existence theorem"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The completeness theorem can also be understood in terms of <a href="/wiki/Consistency" title="Consistency">consistency</a>, as a consequence of Henkin's <a href="/wiki/Consistency#Henkin's_theorem" title="Consistency">model existence theorem</a>. We say that a theory <i>T</i> is <i>syntactically consistent</i> if there is no sentence <i>s</i> such that both <i>s</i> and its negation ¬<i>s</i> are provable from <i>T</i> in our deductive system. The model existence theorem says that for any first-order theory <i>T</i> with a well-orderable language, </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r996643573"><div class="block-indent">if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> is syntactically consistent, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> has a model.</div> <p>Another version, with connections to the <a href="/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem theorem</a>, says: </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r996643573"><div class="block-indent">Every syntactically consistent, <a href="/wiki/Countable" class="mw-redirect" title="Countable">countable</a> first-order theory has a finite or countable model.</div> <p>Given Henkin's theorem, the completeness theorem can be proved as follows: If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\models s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊨</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\models s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b0c41a2dbfb785fc9a094719e098e991c3f5c370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:2.843ex;" alt="{\displaystyle T\models s}"></span>, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\cup \lnot s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>∪</mo> <mi mathvariant="normal">¬</mi> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\cup \lnot s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3b474334592bc6d9396060790224742794ed09" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.86ex; height:2.176ex;" alt="{\displaystyle T\cup \lnot s}"></span> does not have models. By the contrapositive of Henkin's theorem, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\cup \lnot s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>∪</mo> <mi mathvariant="normal">¬</mi> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\cup \lnot s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3b474334592bc6d9396060790224742794ed09" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.86ex; height:2.176ex;" alt="{\displaystyle T\cup \lnot s}"></span> is syntactically inconsistent. So a contradiction (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \bot }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">⊥</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bot }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f282c7bc331cc3bfcf1c57f1452cc23c022f58de" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \bot }"></span>) is provable from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\cup \lnot s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>∪</mo> <mi mathvariant="normal">¬</mi> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\cup \lnot s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b3b474334592bc6d9396060790224742794ed09" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.86ex; height:2.176ex;" alt="{\displaystyle T\cup \lnot s}"></span> in the deductive system. Hence <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (T\cup \lnot s)\vdash \bot }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>T</mi> <mo>∪</mo> <mi mathvariant="normal">¬</mi> <mi>s</mi> <mo stretchy="false">)</mo> <mo>⊢</mo> <mi mathvariant="normal">⊥</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (T\cup \lnot s)\vdash \bot }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a75b6e0b0ffe190726d3a8760c309bd49938da97" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.188ex; height:2.843ex;" alt="{\displaystyle (T\cup \lnot s)\vdash \bot }"></span>, and then by the properties of the deductive system, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\vdash s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊢</mo> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\vdash s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb8d918c0eca121c4fccc66c1e453786976865b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.437ex; height:2.176ex;" alt="{\displaystyle T\vdash s}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="As_a_theorem_of_arithmetic">As a theorem of arithmetic</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=6" title="Edit section: As a theorem of arithmetic"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The model existence theorem and its proof can be formalized in the framework of <a href="/wiki/Peano_arithmetic" class="mw-redirect" title="Peano arithmetic">Peano arithmetic</a>. Precisely, we can systematically define a model of any consistent effective first-order theory <i>T</i> in Peano arithmetic by interpreting each symbol of <i>T</i> by an arithmetical formula whose free variables are the arguments of the symbol. (In many cases, we will need to assume, as a hypothesis of the construction, that <i>T</i> is consistent, since Peano arithmetic may not prove that fact.) However, the definition expressed by this formula is not recursive (but is, in general, <a href="/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_sets_of_natural_numbers" title="Arithmetical hierarchy">Δ<sub>2</sub></a>). </p> <div class="mw-heading mw-heading2"><h2 id="Consequences">Consequences</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=7" title="Edit section: Consequences"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An important consequence of the completeness theorem is that it is possible to <a href="/wiki/Enumerable_set" class="mw-redirect" title="Enumerable set">recursively enumerate</a> the semantic consequences of any <a href="/wiki/Effectively_computable" class="mw-redirect" title="Effectively computable">effective</a> first-order theory, by enumerating all the possible formal deductions from the axioms of the theory, and use this to produce an enumeration of their conclusions. </p><p>This comes in contrast with the direct meaning of the notion of semantic consequence, that quantifies over all structures in a particular language, which is clearly not a recursive definition. </p><p>Also, it makes the concept of "provability", and thus of "theorem", a clear concept that only depends on the chosen system of axioms of the theory, and not on the choice of a proof system. </p> <div class="mw-heading mw-heading2"><h2 id="Relationship_to_the_incompleteness_theorems">Relationship to the incompleteness theorems</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=8" title="Edit section: Relationship to the incompleteness theorems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">Gödel's incompleteness theorems</a> show that there are inherent limitations to what can be proven within any given first-order theory in mathematics. The "incompleteness" in their name refers to another meaning of <i>complete</i> (see <a href="/wiki/Model_theory#Using_the_compactness_and_completeness_theorems" title="Model theory">model theory – Using the compactness and completeness theorems</a>): A theory <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> is complete (or decidable) if every sentence <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> in the language of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> is either provable (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\vdash S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊢</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\vdash S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/434226084ad1468f130e5a59e49774e29f3e282d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.846ex; height:2.176ex;" alt="{\displaystyle T\vdash S}"></span>) or disprovable (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\vdash \neg S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>⊢</mo> <mi mathvariant="normal">¬</mi> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T\vdash \neg S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46918d9319edc1e8a5bc40239cde8d92efb9d45c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.396ex; height:2.176ex;" alt="{\displaystyle T\vdash \neg S}"></span>). </p><p>The first incompleteness theorem states that any <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> which is <a href="/wiki/Consistent" class="mw-redirect" title="Consistent">consistent</a>, <a href="/wiki/Effectively_computable" class="mw-redirect" title="Effectively computable">effective</a> and contains <a href="/wiki/Robinson_arithmetic" title="Robinson arithmetic">Robinson arithmetic</a> ("<i>Q</i>") must be incomplete in this sense, by explicitly constructing a sentence <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> which is demonstrably neither provable nor disprovable within <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>. The second incompleteness theorem extends this result by showing that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> can be chosen so that it expresses the consistency of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> itself. </p><p>Since <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> cannot be proven in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>, the completeness theorem implies the existence of a model of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> in which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> is false. In fact, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> is a <a href="/wiki/Arithmetical_hierarchy" title="Arithmetical hierarchy">Π<sub>1</sub> sentence</a>, i.e. it states that some finitistic property is true of all natural numbers; so if it is false, then some natural number is a counterexample. If this counterexample existed within the standard natural numbers, its existence would disprove <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> within <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>; but the incompleteness theorem showed this to be impossible, so the counterexample must not be a standard number, and thus any model of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> in which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{T}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{T}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f065368172f8e0d3167d59dbb03c41a3c8dd3ccc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.814ex; height:2.509ex;" alt="{\displaystyle S_{T}}"></span> is false must include <a href="/wiki/Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">non-standard numbers</a>. </p><p>In fact, the model of <i>any</i> theory containing <i>Q</i> obtained by the systematic construction of the arithmetical model existence theorem, is <i>always</i> non-standard with a non-equivalent provability predicate and a non-equivalent way to interpret its own construction, so that this construction is non-recursive (as recursive definitions would be unambiguous). </p><p>Also, if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> is at least slightly stronger than <i>Q</i> (e.g. if it includes induction for bounded existential formulas), then <a href="/wiki/Tennenbaum%27s_theorem" title="Tennenbaum's theorem">Tennenbaum's theorem</a> shows that it has no recursive non-standard models. </p> <div class="mw-heading mw-heading2"><h2 id="Relationship_to_the_compactness_theorem">Relationship to the compactness theorem</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=9" title="Edit section: Relationship to the compactness theorem"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The completeness theorem and the <a href="/wiki/Compactness_theorem" title="Compactness theorem">compactness theorem</a> are two cornerstones of first-order logic. While neither of these theorems can be proven in a completely <a href="/wiki/Effectively_computable" class="mw-redirect" title="Effectively computable">effective</a> manner, each one can be effectively obtained from the other. </p><p>The compactness theorem says that if a formula φ is a logical consequence of a (possibly infinite) set of formulas Γ then it is a logical consequence of a finite subset of Γ. This is an immediate consequence of the completeness theorem, because only a finite number of axioms from Γ can be mentioned in a formal deduction of φ, and the soundness of the deductive system then implies φ is a logical consequence of this finite set. This proof of the compactness theorem is originally due to Gödel. </p><p>Conversely, for many deductive systems, it is possible to prove the completeness theorem as an effective consequence of the compactness theorem. </p><p>The ineffectiveness of the completeness theorem can be measured along the lines of <a href="/wiki/Reverse_mathematics" title="Reverse mathematics">reverse mathematics</a>. When considered over a countable language, the completeness and compactness theorems are equivalent to each other and equivalent to a weak form of choice known as <a href="/wiki/Weak_K%C5%91nig%27s_lemma" class="mw-redirect" title="Weak Kőnig's lemma">weak Kőnig's lemma</a>, with the equivalence provable in RCA<sub>0</sub> (a second-order variant of <a href="/wiki/Peano_arithmetic" class="mw-redirect" title="Peano arithmetic">Peano arithmetic</a> restricted to induction over Σ<sup>0</sup><sub style="margin-left:-0.6em">1</sub> formulas). Weak Kőnig's lemma is provable in ZF, the system of <a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel set theory</a> without axiom of choice, and thus the completeness and compactness theorems for countable languages are provable in ZF. However the situation is different when the language is of arbitrary large cardinality since then, though the completeness and compactness theorems remain provably equivalent to each other in ZF, they are also provably equivalent to a weak form of the <a href="/wiki/Axiom_of_choice" title="Axiom of choice">axiom of choice</a> known as <a href="/wiki/Boolean_prime_ideal_theorem#The_ultrafilter_lemma" title="Boolean prime ideal theorem">the ultrafilter lemma</a>. In particular, no theory extending ZF can prove either the completeness or compactness theorems over arbitrary (possibly uncountable) languages without also proving the ultrafilter lemma on a set of the same cardinality. </p> <div class="mw-heading mw-heading2"><h2 id="Completeness_in_other_logics">Completeness in other logics</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=10" title="Edit section: Completeness in other logics"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The completeness theorem is a central property of <a href="/wiki/First-order_logic" title="First-order logic">first-order logic</a> that does not hold for all logics. <a href="/wiki/Second-order_logic" title="Second-order logic">Second-order logic</a>, for example, does not have a completeness theorem for its standard semantics (though does have the completeness property for <a href="/wiki/Henkin_semantics" class="mw-redirect" title="Henkin semantics">Henkin semantics</a>), and the set of logically valid formulas in second-order logic is not recursively enumerable. The same is true of all higher-order logics. It is possible to produce sound deductive systems for higher-order logics, but no such system can be complete. </p><p><a href="/wiki/Lindstr%C3%B6m%27s_theorem" title="Lindström's theorem">Lindström's theorem</a> states that first-order logic is the strongest (subject to certain constraints) logic satisfying both compactness and completeness. </p><p>A completeness theorem can be proved for <a href="/wiki/Modal_logic" title="Modal logic">modal logic</a> or <a href="/wiki/Intuitionistic_logic" title="Intuitionistic logic">intuitionistic logic</a> with respect to <a href="/wiki/Kripke_semantics" title="Kripke semantics">Kripke semantics</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Proofs">Proofs</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=11" title="Edit section: Proofs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Gödel's <a href="/wiki/Original_proof_of_G%C3%B6del%27s_completeness_theorem" title="Original proof of Gödel's completeness theorem">original proof of the theorem</a> proceeded by reducing the problem to a special case for formulas in a certain syntactic form, and then handling this form with an <i>ad hoc</i> argument. </p><p>In modern logic texts, Gödel's completeness theorem is usually proved with <a href="/wiki/Leon_Henkin" title="Leon Henkin">Henkin</a>'s proof, rather than with Gödel's original proof. Henkin's proof directly constructs a <a href="/wiki/Term_model" class="mw-redirect" title="Term model">term model</a> for any consistent first-order theory. James Margetson (2004) developed a computerized formal proof using the <a href="/wiki/Isabelle_(theorem_prover)" class="mw-redirect" title="Isabelle (theorem prover)">Isabelle</a> theorem prover.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Other proofs are also known. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">Gödel's incompleteness theorems</a></li> <li><a href="/wiki/Original_proof_of_G%C3%B6del%27s_completeness_theorem" title="Original proof of Gödel's completeness theorem">Original proof of Gödel's completeness theorem</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=13" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFBatzoglou2021" class="citation arxiv cs1">Batzoglou, Serafim (2021). "Gödel's Incompleteness Theorem". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2112.06641">2112.06641</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.HO">math.HO</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=G%C3%B6del%27s+Incompleteness+Theorem&rft.date=2021&rft_id=info%3Aarxiv%2F2112.06641&rft.aulast=Batzoglou&rft.aufirst=Serafim&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span> (p.17). Accessed 2022-12-01.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLeon_Henkin1949" class="citation journal cs1">Leon Henkin (Sep 1949). "The completeness of the first-order functional calculus". <i><a href="/wiki/The_Journal_of_Symbolic_Logic" class="mw-redirect" title="The Journal of Symbolic Logic">The Journal of Symbolic Logic</a></i>. <b>14</b> (3): 159–166. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2267044">10.2307/2267044</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2267044">2267044</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:28935946">28935946</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Journal+of+Symbolic+Logic&rft.atitle=The+completeness+of+the+first-order+functional+calculus&rft.volume=14&rft.issue=3&rft.pages=159-166&rft.date=1949-09&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A28935946%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2267044%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F2267044&rft.au=Leon+Henkin&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGisbert_F._R._Hasenjaeger1953" class="citation journal cs1">Gisbert F. R. Hasenjaeger (Mar 1953). "Eine Bemerkung zu Henkin's Beweis für die Vollständigkeit des Prädikatenkalküls der Ersten Stufe". <i>The Journal of Symbolic Logic</i>. <b>18</b> (1): 42–48. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2266326">10.2307/2266326</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2266326">2266326</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:45705695">45705695</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Journal+of+Symbolic+Logic&rft.atitle=Eine+Bemerkung+zu+Henkin%27s+Beweis+f%C3%BCr+die+Vollst%C3%A4ndigkeit+des+Pr%C3%A4dikatenkalk%C3%BCls+der+Ersten+Stufe&rft.volume=18&rft.issue=1&rft.pages=42-48&rft.date=1953-03&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A45705695%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2266326%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F2266326&rft.au=Gisbert+F.+R.+Hasenjaeger&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJames_Margetson2004" class="citation report cs1">James Margetson (Sep 2004). <a rel="nofollow" class="external text" href="http://afp.sourceforge.net/entries/Completeness-paper.pdf">Proving the Completeness Theorem within Isabelle/HOL</a> <span class="cs1-format">(PDF)</span> (Technical Report). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060222105036/http://afp.sourceforge.net/entries/Completeness-paper.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2006-02-22.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=Proving+the+Completeness+Theorem+within+Isabelle%2FHOL&rft.date=2004-09&rft.au=James+Margetson&rft_id=http%3A%2F%2Fafp.sourceforge.net%2Fentries%2FCompleteness-paper.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=14" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGödel1929" class="citation thesis cs1"><a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Gödel, K</a> (1929). <a rel="nofollow" class="external text" href="http://ubdata.univie.ac.at/AC05181322"><i>Über die Vollständigkeit des Logikkalküls</i></a> (Thesis). Doctoral dissertation. University Of Vienna.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=%C3%9Cber+die+Vollst%C3%A4ndigkeit+des+Logikkalk%C3%BCls&rft.inst=University+Of+Vienna&rft.date=1929&rft.aulast=G%C3%B6del&rft.aufirst=K&rft_id=http%3A%2F%2Fubdata.univie.ac.at%2FAC05181322&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span> The first proof of the completeness theorem.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGödel1930" class="citation journal cs1 cs1-prop-foreign-lang-source"><a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Gödel, K</a> (1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls". <i><a href="/wiki/Monatshefte_f%C3%BCr_Mathematik" title="Monatshefte für Mathematik">Monatshefte für Mathematik</a></i> (in German). <b>37</b> (1): 349–360. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01696781">10.1007/BF01696781</a>. <a href="/wiki/JFM_(identifier)" class="mw-redirect" title="JFM (identifier)">JFM</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:56.0046.04">56.0046.04</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123343522">123343522</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Monatshefte+f%C3%BCr+Mathematik&rft.atitle=Die+Vollst%C3%A4ndigkeit+der+Axiome+des+logischen+Funktionenkalk%C3%BCls&rft.volume=37&rft.issue=1&rft.pages=349-360&rft.date=1930&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A123343522%23id-name%3DS2CID&rft_id=https%3A%2F%2Fzbmath.org%2F%3Fformat%3Dcomplete%26q%3Dan%3A56.0046.04%23id-name%3DJFM&rft_id=info%3Adoi%2F10.1007%2FBF01696781&rft.aulast=G%C3%B6del&rft.aufirst=K&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span> The same material as the dissertation, except with briefer proofs, more succinct explanations, and omitting the lengthy introduction.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHans_Hermes1973" class="citation book cs1"><a href="/wiki/Hans_Hermes" title="Hans Hermes">Hans Hermes</a> (1973). <i>Introduction to Mathematical Logic</i>. Hochschultext (Springer-Verlag). London: Springer. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3540058192" title="Special:BookSources/3540058192"><bdi>3540058192</bdi></a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1431-4657">1431-4657</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Mathematical+Logic&rft.place=London&rft.series=Hochschultext+%28Springer-Verlag%29&rft.pub=Springer&rft.date=1973&rft.issn=1431-4657&rft.isbn=3540058192&rft.au=Hans+Hermes&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del%27s+completeness+theorem" class="Z3988"></span> Chapter 5: <i>"Gödel's completeness theorem"</i>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del%27s_completeness_theorem&action=edit&section=15" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Stanford_Encyclopedia_of_Philosophy" title="Stanford Encyclopedia of Philosophy">Stanford Encyclopedia of Philosophy</a>: "<a rel="nofollow" class="external text" href="http://plato.stanford.edu/entries/goedel/">Kurt Gödel</a>"—by <a href="/wiki/Juliette_Kennedy" title="Juliette Kennedy">Juliette Kennedy</a>.</li> <li>MacTutor biography: <a rel="nofollow" class="external text" href="http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Godel.html">Kurt Gödel.</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20051013055626/http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Godel.html">Archived</a> 2005-10-13 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li>Detlovs, Vilnis, and Podnieks, Karlis, "<a rel="nofollow" class="external text" href="http://www.ltn.lv/~podnieks/">Introduction to mathematical logic.</a>"</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Metalogic_and_metamathematics" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Metalogic" title="Template:Metalogic"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Metalogic" title="Template talk:Metalogic"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Metalogic" title="Special:EditPage/Template:Metalogic"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Metalogic_and_metamathematics" style="font-size:114%;margin:0 4em"><a href="/wiki/Metalogic" title="Metalogic">Metalogic</a> and <a href="/wiki/Metamathematics" title="Metamathematics">metamathematics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0;padding-left:2.0em;padding-right:2.0em;"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cantor%27s_theorem" title="Cantor's theorem">Cantor's theorem</a></li> <li><i><a href="/wiki/Entscheidungsproblem" title="Entscheidungsproblem">Entscheidungsproblem</a></i></li> <li><a href="/wiki/Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li> <li><a href="/wiki/Consistency" title="Consistency">Consistency</a></li> <li><a href="/wiki/Effective_method" title="Effective method">Effective method</a></li> <li><a href="/wiki/Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a> <ul><li><a href="/wiki/Foundations_of_geometry" title="Foundations of geometry">of geometry</a></li></ul></li> <li><a class="mw-selflink selflink">Gödel's completeness theorem</a></li> <li><a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">Gödel's incompleteness theorems</a></li> <li><a href="/wiki/Soundness" title="Soundness">Soundness</a></li> <li><a href="/wiki/Completeness_(logic)" title="Completeness (logic)">Completeness</a></li> <li><a href="/wiki/Decidability_(logic)" title="Decidability (logic)">Decidability</a></li> <li><a href="/wiki/Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a></li> <li><a href="/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem theorem</a></li> <li><a href="/wiki/Metatheorem" title="Metatheorem">Metatheorem</a></li> <li><a href="/wiki/Satisfiability" title="Satisfiability">Satisfiability</a></li> <li><a href="/wiki/Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a></li> <li><a href="/wiki/Type%E2%80%93token_distinction" title="Type–token distinction">Type–token distinction</a></li> <li><a href="/wiki/Use%E2%80%93mention_distinction" title="Use–mention distinction">Use–mention distinction</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Mathematical_logic" title="Template:Mathematical logic"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Mathematical_logic" title="Template talk:Mathematical logic"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Mathematical_logic" title="Special:EditPage/Template:Mathematical logic"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Mathematical_logic" style="font-size:114%;margin:0 4em"><a href="/wiki/Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Axiom" title="Axiom">Axiom</a> <ul><li><a href="/wiki/List_of_axioms" title="List of axioms">list</a></li></ul></li> <li><a href="/wiki/Cardinality" title="Cardinality">Cardinality</a></li> <li><a href="/wiki/First-order_logic" title="First-order logic">First-order logic</a></li> <li><a href="/wiki/Formal_proof" title="Formal proof">Formal proof</a></li> <li><a href="/wiki/Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li> <li><a href="/wiki/Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a></li> <li><a href="/wiki/Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li> <li><a href="/wiki/Logical_consequence" title="Logical consequence">Logical consequence</a></li> <li><a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li> <li><a href="/wiki/Theorem" title="Theorem">Theorem</a></li> <li><a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (<a href="/wiki/Category:Theorems_in_the_foundations_of_mathematics" title="Category:Theorems in the foundations of mathematics">list</a>)<br /> and <a href="/wiki/Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a class="mw-selflink selflink">Gödel's completeness</a> and <a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li> <li><a href="/wiki/Tarski%27s_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li> <li><a href="/wiki/Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li> <li>Cantor's <a href="/wiki/Cantor%27s_theorem" title="Cantor's theorem">theorem,</a> <a href="/wiki/Cantor%27s_paradox" title="Cantor's paradox">paradox</a> and <a href="/wiki/Cantor%27s_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li> <li><a href="/wiki/Compactness_theorem" title="Compactness theorem">Compactness</a></li> <li><a href="/wiki/Halting_problem" title="Halting problem">Halting problem</a></li> <li><a href="/wiki/Lindstr%C3%B6m%27s_theorem" title="Lindström's theorem">Lindström's</a></li> <li><a href="/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li> <li><a href="/wiki/Russell%27s_paradox" title="Russell's paradox">Russell's paradox</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional" scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Classical_logic" title="Classical logic">Classical logic</a></li> <li><a href="/wiki/Logical_truth" title="Logical truth">Logical truth</a></li> <li><a href="/wiki/Tautology_(logic)" title="Tautology (logic)">Tautology</a></li> <li><a href="/wiki/Proposition" title="Proposition">Proposition</a></li> <li><a href="/wiki/Inference" title="Inference">Inference</a></li> <li><a href="/wiki/Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li> <li><a href="/wiki/Consistency" title="Consistency">Consistency</a> <ul><li><a href="/wiki/Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li> <li><a href="/wiki/Argument" title="Argument">Argument</a></li> <li><a href="/wiki/Soundness" title="Soundness">Soundness</a></li> <li><a href="/wiki/Validity_(logic)" title="Validity (logic)">Validity</a></li> <li><a href="/wiki/Syllogism" title="Syllogism">Syllogism</a></li> <li><a href="/wiki/Square_of_opposition" title="Square of opposition">Square of opposition</a></li> <li><a href="/wiki/Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li> <li><a href="/wiki/Boolean_function" title="Boolean function">Boolean functions</a></li> <li><a href="/wiki/Logical_connective" title="Logical connective">Logical connectives</a></li> <li><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional calculus</a></li> <li><a href="/wiki/Propositional_formula" title="Propositional formula">Propositional formula</a></li> <li><a href="/wiki/Truth_table" title="Truth table">Truth tables</a></li> <li><a href="/wiki/Many-valued_logic" title="Many-valued logic">Many-valued logic</a> <ul><li><a href="/wiki/Three-valued_logic" title="Three-valued logic">3</a></li> <li><a href="/wiki/Finite-valued_logic" title="Finite-valued logic">finite</a></li> <li><a href="/wiki/Infinite-valued_logic" title="Infinite-valued logic">∞</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/First-order_logic" title="First-order logic">First-order</a> <ul><li><a href="/wiki/List_of_first-order_theories" title="List of first-order theories"><span style="font-size:85%;">list</span></a></li></ul></li> <li><a href="/wiki/Second-order_logic" title="Second-order logic">Second-order</a> <ul><li><a href="/wiki/Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li> <li><a href="/wiki/Higher-order_logic" title="Higher-order logic">Higher-order</a></li> <li><a href="/wiki/Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li> <li><a href="/wiki/Free_logic" title="Free logic">Free</a></li> <li><a href="/wiki/Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li> <li><a href="/wiki/Predicate_(mathematical_logic)" title="Predicate (mathematical logic)">Predicate</a></li> <li><a href="/wiki/Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Set</a> <ul><li><a href="/wiki/Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li> <li><a href="/wiki/Class_(set_theory)" title="Class (set theory)">Class</a></li> <li>(<a href="/wiki/Urelement" title="Urelement">Ur-</a>)<a href="/wiki/Element_(mathematics)" title="Element (mathematics)">Element</a></li> <li><a href="/wiki/Ordinal_number" title="Ordinal number">Ordinal number</a></li> <li><a href="/wiki/Extensionality" title="Extensionality">Extensionality</a></li> <li><a href="/wiki/Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li> <li><a href="/wiki/Relation_(mathematics)" title="Relation (mathematics)">Relation</a> <ul><li><a href="/wiki/Equivalence_relation" title="Equivalence relation">equivalence</a></li> <li><a href="/wiki/Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li> <li>Set operations: <ul><li><a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li> <li><a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a></li> <li><a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">complement</a></li> <li><a href="/wiki/Cartesian_product" title="Cartesian product">Cartesian product</a></li> <li><a href="/wiki/Power_set" title="Power set">power set</a></li> <li><a href="/wiki/List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Countable_set" title="Countable set">Countable</a></li> <li><a href="/wiki/Uncountable_set" title="Uncountable set">Uncountable</a></li> <li><a href="/wiki/Empty_set" title="Empty set">Empty</a></li> <li><a href="/wiki/Inhabited_set" title="Inhabited set">Inhabited</a></li> <li><a href="/wiki/Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li> <li><a href="/wiki/Finite_set" title="Finite set">Finite</a></li> <li><a href="/wiki/Infinite_set" title="Infinite set">Infinite</a></li> <li><a href="/wiki/Transitive_set" title="Transitive set">Transitive</a></li> <li><a href="/wiki/Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li> <li><a href="/wiki/Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li> <li><a href="/wiki/Fuzzy_set" title="Fuzzy set">Fuzzy</a></li> <li><a href="/wiki/Universal_set" title="Universal set">Universal</a></li> <li><a href="/wiki/Universe_(mathematics)" title="Universe (mathematics)">Universe</a> <ul><li><a href="/wiki/Constructible_universe" title="Constructible universe">constructible</a></li> <li><a href="/wiki/Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li> <li><a href="/wiki/Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="/wiki/Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="/wiki/Map_(mathematics)" title="Map (mathematics)">Map</a> <ul><li><a href="/wiki/Domain_of_a_function" title="Domain of a function">domain</a></li> <li><a href="/wiki/Codomain" title="Codomain">codomain</a></li> <li><a href="/wiki/Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li> <li><a href="/wiki/Injective_function" title="Injective function">In</a>/<a href="/wiki/Surjective_function" title="Surjective function">Sur</a>/<a href="/wiki/Bijection" title="Bijection">Bi</a>-jection</li> <li><a href="/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li> <li><a href="/wiki/Isomorphism" title="Isomorphism">Isomorphism</a></li> <li><a href="/wiki/G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li> <li><a href="/wiki/Enumeration" title="Enumeration">Enumeration</a></li> <li><a href="/wiki/Large_cardinal" title="Large cardinal">Large cardinal</a> <ul><li><a href="/wiki/Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li> <li><a href="/wiki/Aleph_number" title="Aleph number">Aleph number</a></li> <li><a href="/wiki/Operation_(mathematics)" title="Operation (mathematics)">Operation</a> <ul><li><a href="/wiki/Binary_operation" title="Binary operation">binary</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a> <ul><li><a href="/wiki/Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li> <li><a href="/wiki/Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li> <li><a href="/wiki/General_set_theory" title="General set theory">General</a></li> <li><a href="/wiki/Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li> <li><a href="/wiki/Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li> <li><a href="/wiki/Naive_set_theory" title="Naive set theory">Naive</a></li> <li><a href="/wiki/New_Foundations" title="New Foundations">New Foundations</a></li> <li><a href="/wiki/Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li> <li><a href="/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li> <li><a href="/wiki/Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li> <li><a href="/wiki/Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Formal_system" title="Formal system">Formal systems</a> (<a href="/wiki/List_of_formal_systems" title="List of formal systems"><span style="font-size:85%;">list</span></a>),<br /><a href="/wiki/Formal_language" title="Formal language">language</a> and <a href="/wiki/Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li> <li><a href="/wiki/Arity" title="Arity">Arity</a></li> <li><a href="/wiki/Automata_theory" title="Automata theory">Automata</a></li> <li><a href="/wiki/Axiom_schema" title="Axiom schema">Axiom schema</a></li> <li><a href="/wiki/Expression_(mathematics)" title="Expression (mathematics)">Expression</a> <ul><li><a href="/wiki/Ground_expression" title="Ground expression">ground</a></li></ul></li> <li><a href="/wiki/Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a> <ul><li><a href="/wiki/Extension_by_definitions" title="Extension by definitions">by definition</a></li> <li><a href="/wiki/Conservative_extension" title="Conservative extension">conservative</a></li></ul></li> <li><a href="/wiki/Finitary_relation" title="Finitary relation">Relation</a></li> <li><a href="/wiki/Formation_rule" title="Formation rule">Formation rule</a></li> <li><a href="/wiki/Formal_grammar" title="Formal grammar">Grammar</a></li> <li><a href="/wiki/Well-formed_formula" title="Well-formed formula">Formula</a> <ul><li><a href="/wiki/Atomic_formula" title="Atomic formula">atomic</a></li> <li><a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li> <li><a href="/wiki/Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li> <li><a href="/wiki/Open_formula" title="Open formula">open</a></li></ul></li> <li><a href="/wiki/Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li> <li><a href="/wiki/Formal_language" title="Formal language">Language</a></li> <li><a href="/wiki/Metalanguage" title="Metalanguage">Metalanguage</a></li> <li><a href="/wiki/Logical_connective" title="Logical connective">Logical connective</a> <ul><li><a href="/wiki/Negation" title="Negation">¬</a></li> <li><a href="/wiki/Logical_disjunction" title="Logical disjunction">∨</a></li> <li><a href="/wiki/Logical_conjunction" title="Logical conjunction">∧</a></li> <li><a href="/wiki/Material_conditional" title="Material conditional">→</a></li> <li><a href="/wiki/Logical_biconditional" title="Logical biconditional">↔</a></li> <li><a href="/wiki/Logical_equality" title="Logical equality">=</a></li></ul></li> <li><a href="/wiki/Predicate_(mathematical_logic)" title="Predicate (mathematical logic)">Predicate</a> <ul><li><a href="/wiki/Functional_predicate" title="Functional predicate">functional</a></li> <li><a href="/wiki/Predicate_variable" title="Predicate variable">variable</a></li> <li><a href="/wiki/Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li> <li><a href="/wiki/Formal_proof" title="Formal proof">Proof</a></li> <li><a href="/wiki/Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a> <ul><li><a href="/wiki/Existential_quantification" title="Existential quantification">∃</a></li> <li><a href="/wiki/Uniqueness_quantification" title="Uniqueness quantification">!</a></li> <li><a href="/wiki/Universal_quantification" title="Universal quantification">∀</a></li> <li><a href="/wiki/Quantifier_rank" title="Quantifier rank">rank</a></li></ul></li> <li><a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a> <ul><li><a href="/wiki/Atomic_sentence" title="Atomic sentence">atomic</a></li> <li><a href="/wiki/Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li> <li><a href="/wiki/Signature_(logic)" title="Signature (logic)">Signature</a></li> <li><a href="/wiki/String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li> <li><a href="/wiki/Substitution_(logic)" title="Substitution (logic)">Substitution</a></li> <li><a href="/wiki/Symbol_(formal)" title="Symbol (formal)">Symbol</a> <ul><li><a href="/wiki/Uninterpreted_function" title="Uninterpreted function">function</a></li> <li><a href="/wiki/Logical_constant" title="Logical constant">logical/constant</a></li> <li><a href="/wiki/Non-logical_symbol" title="Non-logical symbol">non-logical</a></li> <li><a href="/wiki/Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li> <li><a href="/wiki/Term_(logic)" title="Term (logic)">Term</a></li> <li><a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a> <ul><li><a href="/wiki/List_of_mathematical_theories" title="List of mathematical theories"><span style="font-size:85%;">list</span></a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><span class="nowrap">Example <a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic<br />systems</a> <span style="font-size:85%;">(<a href="/wiki/List_of_first-order_theories" title="List of first-order theories">list</a>)</span></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li>of <a href="/wiki/True_arithmetic" title="True arithmetic">arithmetic</a>: <ul><li><a href="/wiki/Peano_axioms" title="Peano axioms">Peano</a></li> <li><a href="/wiki/Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li> <li><a href="/wiki/Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li> <li><a href="/wiki/Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li> <li><a href="/wiki/Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li> <li><a href="/wiki/Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li> <li>of the <a href="/wiki/Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a> <ul><li><a href="/wiki/Tarski%27s_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li> <li>of <a href="/wiki/Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a> <ul><li><a href="/wiki/Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li> <li><a href="/wiki/Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li> <li>of <a href="/wiki/Foundations_of_geometry" title="Foundations of geometry">geometry</a>: <ul><li><a href="/wiki/Euclidean_geometry" title="Euclidean geometry">Euclidean</a>: <ul><li><a href="/wiki/Euclid%27s_Elements" title="Euclid's Elements"><i>Elements</i></a></li> <li><a href="/wiki/Hilbert%27s_axioms" title="Hilbert's axioms">Hilbert's</a></li> <li><a href="/wiki/Tarski%27s_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li> <li><a href="/wiki/Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul> <ul><li><i><a href="/wiki/Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></i></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Formal_proof" title="Formal proof">Formal proof</a></li> <li><a href="/wiki/Natural_deduction" title="Natural deduction">Natural deduction</a></li> <li><a href="/wiki/Logical_consequence" title="Logical consequence">Logical consequence</a></li> <li><a href="/wiki/Rule_of_inference" title="Rule of inference">Rule of inference</a></li> <li><a href="/wiki/Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li> <li><a href="/wiki/Theorem" title="Theorem">Theorem</a></li> <li><a href="/wiki/Formal_system" title="Formal system">Systems</a> <ul><li><a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic</a></li> <li><a href="/wiki/Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li> <li><a href="/wiki/Hilbert_system" title="Hilbert system">Hilbert</a> <ul><li><a href="/wiki/List_of_Hilbert_systems" class="mw-redirect" title="List of Hilbert systems">list</a></li></ul></li></ul></li> <li><a href="/wiki/Complete_theory" title="Complete theory">Complete theory</a></li> <li><a href="/wiki/Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="/wiki/List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li> <li><a href="/wiki/Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li> <li><a href="/wiki/Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li> <li><a href="/wiki/Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li> <li><a href="/wiki/Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a> <ul><li><a href="/wiki/Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li> <li><a href="/wiki/Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li> <li><a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a> <ul><li><a href="/wiki/Elementary_equivalence" title="Elementary equivalence">equivalence</a></li> <li><a href="/wiki/Finite_model_theory" title="Finite model theory">finite</a></li> <li><a href="/wiki/Saturated_model" title="Saturated model">saturated</a></li> <li><a href="/wiki/Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li> <li><a href="/wiki/Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li> <li><a href="/wiki/Non-standard_model" title="Non-standard model">Non-standard model</a> <ul><li><a href="/wiki/Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li> <li><a href="/wiki/Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a> <ul><li><a href="/wiki/Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li> <li><a href="/wiki/Categorical_theory" title="Categorical theory">Categorical theory</a></li> <li><a href="/wiki/Model_complete_theory" title="Model complete theory">Model complete theory</a></li> <li><a href="/wiki/Satisfiability" title="Satisfiability">Satisfiability</a></li> <li><a href="/wiki/Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li> <li><a href="/wiki/Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li> <li><a href="/wiki/Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a> <ul><li><a href="/wiki/Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li> <li><a href="/wiki/Tarski%27s_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li> <li><a href="/wiki/Kripke%27s_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li> <li><a href="/wiki/T-schema" title="T-schema">T-schema</a></li> <li><a href="/wiki/Transfer_principle" title="Transfer principle">Transfer principle</a></li> <li><a href="/wiki/Truth_predicate" title="Truth predicate">Truth predicate</a></li> <li><a href="/wiki/Truth_value" title="Truth value">Truth value</a></li> <li><a href="/wiki/Type_(model_theory)" title="Type (model theory)">Type</a></li> <li><a href="/wiki/Ultraproduct" title="Ultraproduct">Ultraproduct</a></li> <li><a href="/wiki/Validity_(logic)" title="Validity (logic)">Validity</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Church_encoding" title="Church encoding">Church encoding</a></li> <li><a href="/wiki/Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li> <li><a href="/wiki/Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li> <li><a href="/wiki/Computable_function" title="Computable function">Computable function</a></li> <li><a href="/wiki/Computable_set" title="Computable set">Computable set</a></li> <li><a href="/wiki/Decision_problem" title="Decision problem">Decision problem</a> <ul><li><a href="/wiki/Decidability_(logic)" title="Decidability (logic)">decidable</a></li> <li><a href="/wiki/Undecidable_problem" title="Undecidable problem">undecidable</a></li> <li><a href="/wiki/P_(complexity)" title="P (complexity)">P</a></li> <li><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a></li> <li><a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li> <li><a href="/wiki/Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li> <li><a href="/wiki/Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li> <li><a href="/wiki/Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li> <li><a href="/wiki/Recursion" title="Recursion">Recursion</a></li> <li><a href="/wiki/Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li> <li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Abstract_logic" title="Abstract logic">Abstract logic</a></li> <li><a href="/wiki/Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li> <li><a href="/wiki/Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li> <li><a href="/wiki/Category_theory" title="Category theory">Category theory</a></li> <li><a href="/wiki/Concrete_category" title="Concrete category">Concrete</a>/<a href="/wiki/Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li> <li><a href="/wiki/Category_of_sets" title="Category of sets">Category of sets</a></li> <li><a href="/wiki/History_of_logic" title="History of logic">History of logic</a></li> <li><a href="/wiki/History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a> <ul><li><a href="/wiki/Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li> <li><a href="/wiki/Logicism" title="Logicism">Logicism</a></li> <li><a href="/wiki/Mathematical_object" title="Mathematical object">Mathematical object</a></li> <li><a href="/wiki/Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li> <li><a href="/wiki/Supertask" title="Supertask">Supertask</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><b><span class="nowrap"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics_blue-p.svg" class="mw-file-description"><img alt="icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/16px-Nuvola_apps_edu_mathematics_blue-p.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/24px-Nuvola_apps_edu_mathematics_blue-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/32px-Nuvola_apps_edu_mathematics_blue-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span> </span><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></b></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Gödel%27s_completeness_theorem&oldid=1251767484">https://en.wikipedia.org/w/index.php?title=Gödel%27s_completeness_theorem&oldid=1251767484</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Theorems_in_the_foundations_of_mathematics" title="Category:Theorems in the foundations of mathematics">Theorems in the foundations of mathematics</a></li><li><a href="/wiki/Category:Metatheorems" title="Category:Metatheorems">Metatheorems</a></li><li><a href="/wiki/Category:Model_theory" title="Category:Model theory">Model theory</a></li><li><a href="/wiki/Category:Proof_theory" title="Category:Proof theory">Proof theory</a></li><li><a href="/wiki/Category:Works_by_Kurt_G%C3%B6del" title="Category:Works by Kurt Gödel">Works by Kurt Gödel</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:CS1_German-language_sources_(de)" title="Category:CS1 German-language sources (de)">CS1 German-language sources (de)</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 17 October 2024, at 23:58<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=G%C3%B6del%27s_completeness_theorem&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-mzm7s","wgBackendResponseTime":157,"wgPageParseReport":{"limitreport":{"cputime":"0.374","walltime":"0.586","ppvisitednodes":{"value":1123,"limit":1000000},"postexpandincludesize":{"value":83232,"limit":2097152},"templateargumentsize":{"value":1145,"limit":2097152},"expansiondepth":{"value":11,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":40821,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 378.322 1 -total"," 32.55% 123.134 5 Template:Navbox"," 29.51% 111.647 1 Template:Reflist"," 24.93% 94.303 1 Template:Short_description"," 23.10% 87.406 1 Template:Metalogic"," 20.56% 77.785 1 Template:Cite_arXiv"," 13.59% 51.402 2 Template:Pagetype"," 8.69% 32.859 3 Template:Main_other"," 8.20% 31.039 1 Template:SDcat"," 8.05% 30.466 1 Template:Mathematical_logic"]},"scribunto":{"limitreport-timeusage":{"value":"0.192","limit":"10.000"},"limitreport-memusage":{"value":4933486,"limit":52428800},"limitreport-logs":"table#1 {\n [\"size\"] = \"tiny\",\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-qfk9f","timestamp":"20241122141235","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"G\u00f6del's completeness theorem","url":"https:\/\/en.wikipedia.org\/wiki\/G%C3%B6del%27s_completeness_theorem","sameAs":"http:\/\/www.wikidata.org\/entity\/Q902052","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q902052","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-10-14T00:27:13Z","dateModified":"2024-10-17T23:58:07Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/3\/34\/Completude_logique_premier_ordre.png","headline":"fundamental theorem in mathematical logic"}</script> </body> </html>