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>Knaster–Tarski 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":"f9808483-bbf4-469e-a59e-199dee49cf39","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Knaster–Tarski_theorem","wgTitle":"Knaster–Tarski theorem","wgCurRevisionId":1254306963,"wgRevisionId":1254306963,"wgArticleId":181417,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","All articles with unsourced statements","Articles with unsourced statements from February 2024","CS1: long volume value","Articles containing proofs","Order theory","Fixed points (mathematics)","Fixed-point theorems","Theorems in the foundations of mathematics"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName": "Knaster–Tarski_theorem","wgRelevantArticleId":181417,"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":"Q609612","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","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","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar", "ext.centralauth.centralautologin","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%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 name="viewport" content="width=1120"> <meta property="og:title" content="Knaster–Tarski theorem - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Knaster%E2%80%93Tarski_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/Knaster%E2%80%93Tarski_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-Knaster–Tarski_theorem rootpage-Knaster–Tarski_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=Knaster%E2%80%93Tarski+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=Knaster%E2%80%93Tarski+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=Knaster%E2%80%93Tarski+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=Knaster%E2%80%93Tarski+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-Consequences:_least_and_greatest_fixed_points" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Consequences:_least_and_greatest_fixed_points"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Consequences: least and greatest fixed points</span> </div> </a> <ul id="toc-Consequences:_least_and_greatest_fixed_points-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Weaker_versions_of_the_theorem" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Weaker_versions_of_the_theorem"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Weaker versions of the theorem</span> </div> </a> <ul id="toc-Weaker_versions_of_the_theorem-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Proof" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Proof"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Proof</span> </div> </a> <ul id="toc-Proof-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Computing_a_Tarski_fixed-point" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Computing_a_Tarski_fixed-point"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Computing a Tarski fixed-point</span> </div> </a> <ul id="toc-Computing_a_Tarski_fixed-point-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Application_in_game_theory" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Application_in_game_theory"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Application in game theory</span> </div> </a> <ul id="toc-Application_in_game_theory-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">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-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">8</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">9</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">10</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">Knaster–Tarski 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 10 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-10" 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">10 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Fixpunktsatz_von_Tarski_und_Knaster" title="Fixpunktsatz von Tarski und Knaster – German" lang="de" hreflang="de" data-title="Fixpunktsatz von Tarski und Knaster" 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_Knaster-Tarski" title="Teorema de Knaster-Tarski – Spanish" lang="es" hreflang="es" data-title="Teorema de Knaster-Tarski" 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-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Knaster-Tarski" title="Théorème de Knaster-Tarski – French" lang="fr" hreflang="fr" data-title="Théorème de Knaster-Tarski" 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/%ED%83%80%EB%A5%B4%EC%8A%A4%ED%82%A4_%EA%B3%A0%EC%A0%95%EC%A0%90_%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_Knaster-Tarski" title="Teorema di Knaster-Tarski – Italian" lang="it" hreflang="it" data-title="Teorema di Knaster-Tarski" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Twierdzenie_Knastera-Tarskiego_o_punkcie_sta%C5%82ym" title="Twierdzenie Knastera-Tarskiego o punkcie stałym – Polish" lang="pl" hreflang="pl" data-title="Twierdzenie Knastera-Tarskiego o punkcie stałym" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Teorema_de_Knaster%E2%80%93Tarski" title="Teorema de Knaster–Tarski – Portuguese" lang="pt" hreflang="pt" data-title="Teorema de Knaster–Tarski" 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%9A%D0%BD%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%A2%D0%B0%D1%80%D1%81%D0%BA%D0%BE%D0%B3%D0%BE" 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-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%9A%D0%BD%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%A2%D0%B0%D1%80%D1%81%D1%8C%D0%BA%D0%BE%D0%B3%D0%BE" 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%85%8B%E7%BA%B3%E6%96%AF%E7%89%B9-%E5%A1%94%E6%96%AF%E5%9F%BA%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/Q609612#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/Knaster%E2%80%93Tarski_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:Knaster%E2%80%93Tarski_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/Knaster%E2%80%93Tarski_theorem"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Knaster%E2%80%93Tarski_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=Knaster%E2%80%93Tarski_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/Knaster%E2%80%93Tarski_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=Knaster%E2%80%93Tarski_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=Knaster%E2%80%93Tarski_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/Knaster%E2%80%93Tarski_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/Knaster%E2%80%93Tarski_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=Knaster%E2%80%93Tarski_theorem&oldid=1254306963" 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=Knaster%E2%80%93Tarski_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=Knaster%E2%80%93Tarski_theorem&id=1254306963&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%2FKnaster%25E2%2580%2593Tarski_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%2FKnaster%25E2%2580%2593Tarski_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=Knaster%E2%80%93Tarski_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=Knaster%E2%80%93Tarski_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/Q609612" 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">Theorem in order and lattice theory</div> <p>In the <a href="/wiki/Mathematics" title="Mathematics">mathematical</a> areas of <a href="/wiki/Order_theory" title="Order theory">order</a> and <a href="/wiki/Lattice_theory" class="mw-redirect" title="Lattice theory">lattice theory</a>, the <b>Knaster–Tarski theorem</b>, named after <a href="/wiki/Bronis%C5%82aw_Knaster" title="Bronisław Knaster">Bronisław Knaster</a> and <a href="/wiki/Alfred_Tarski" title="Alfred Tarski">Alfred Tarski</a>, states the following: </p> <dl><dd><i>Let</i> (<i>L</i>, ≤) <i>be a <a href="/wiki/Complete_lattice" title="Complete lattice">complete lattice</a> and let f : L → L be an <a href="/wiki/Monotonic_function#In_order_theory" title="Monotonic function">order-preserving (monotonic) function</a> w.r.t. ≤ . Then the <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">set</a> of <a href="/wiki/Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed points</a> of f in L forms a complete lattice under ≤ .</i></dd></dl> <p>It was Tarski who stated the result in its most general form,<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> and so the theorem is often known as <b>Tarski's fixed-point theorem</b>. Some time earlier, Knaster and Tarski established the result for the special case where <i>L</i> is the <a href="/wiki/Lattice_(order)" title="Lattice (order)">lattice</a> of <a href="/wiki/Subset" title="Subset">subsets</a> of a set, the <a href="/wiki/Power_set" title="Power set">power set</a> lattice.<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> </p><p>The theorem has important applications in <a href="/wiki/Formal_semantics_of_programming_languages" class="mw-redirect" title="Formal semantics of programming languages">formal semantics of programming languages</a> and <a href="/wiki/Abstract_interpretation" title="Abstract interpretation">abstract interpretation</a>, as well as in <a href="/wiki/Game_theory" title="Game theory">game theory</a>. </p><p>A kind of converse of this theorem was proved by <a href="/wiki/Anne_C._Morel" title="Anne C. Morel">Anne C. Davis</a>: If every <a href="/wiki/Order-preserving_function" class="mw-redirect" title="Order-preserving function">order-preserving function</a> <i>f</i> : <i>L</i> → <i>L</i> on a lattice <i>L</i> has a fixed point, then <i>L</i> is a complete lattice.<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="Consequences:_least_and_greatest_fixed_points">Consequences: least and greatest fixed points</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Knaster%E2%80%93Tarski_theorem&action=edit&section=1" title="Edit section: Consequences: least and greatest fixed points"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Since complete lattices cannot be <a href="/wiki/Empty_set" title="Empty set">empty</a> (they must contain a <a href="/wiki/Supremum" class="mw-redirect" title="Supremum">supremum</a> and <a href="/wiki/Infimum" class="mw-redirect" title="Infimum">infimum</a> of the empty set), the theorem in particular guarantees the existence of at least one fixed point of <i>f</i>, and even the existence of a <a href="/wiki/Least_fixed_point" title="Least fixed point"><i>least</i> fixed point</a> (or <a href="/wiki/Greatest_fixed_point" class="mw-redirect" title="Greatest fixed point"><i>greatest</i> fixed point</a>). In many practical cases, this is the most important implication of the theorem. </p><p>The <a href="/wiki/Least_fixpoint" class="mw-redirect" title="Least fixpoint">least fixpoint</a> of <i>f</i> is the least element <i>x</i> such that <i>f</i>(<i>x</i>) = <i>x</i>, or, equivalently, such that <i>f</i>(<i>x</i>) ≤ <i>x</i>; the <a href="/wiki/Duality_(order_theory)" title="Duality (order theory)">dual</a> holds for the <a href="/wiki/Greatest_fixpoint" class="mw-redirect" title="Greatest fixpoint">greatest fixpoint</a>, the greatest element <i>x</i> such that <i>f</i>(<i>x</i>) = <i>x</i>. </p><p>If <i>f</i>(lim <i>x</i><sub><i>n</i></sub>) = lim <i>f</i>(<i>x</i><sub><i>n</i></sub>) for all ascending <a href="/wiki/Sequence" title="Sequence">sequences</a> <i>x</i><sub><i>n</i></sub>, then the least fixpoint of <i>f</i> is lim <i>f</i><sup> <i>n</i></sup>(0) where 0 is the <a href="/wiki/Least_element" class="mw-redirect" title="Least element">least element</a> of <i>L</i>, thus giving a more "constructive" version of the theorem. (See: <a href="/wiki/Kleene_fixed-point_theorem" title="Kleene fixed-point theorem">Kleene fixed-point theorem</a>.) More generally, if <i>f</i> is monotonic, then the least fixpoint of <i>f</i> is the stationary limit of <i>f</i><sup> α</sup>(0), taking α over the <a href="/wiki/Ordinal_number" title="Ordinal number">ordinals</a>, where <i>f</i><sup> α</sup> is defined by <a href="/wiki/Transfinite_induction" title="Transfinite induction">transfinite induction</a>: <i>f</i><sup> α+1</sup> = <i>f</i> (<i>f</i><sup> α</sup>) and <i>f</i><sup> γ</sup> for a limit ordinal γ is the <a href="/wiki/Least_upper_bound" class="mw-redirect" title="Least upper bound">least upper bound</a> of the <i>f</i><sup> β</sup> for all β ordinals less than γ.<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> The dual theorem holds for the greatest fixpoint. </p><p>For example, in theoretical <a href="/wiki/Computer_science" title="Computer science">computer science</a>, least fixed points of <a href="/wiki/Monotonic_function#In_order_theory" title="Monotonic function">monotonic functions</a> are used to define <a href="/wiki/Program_semantics" class="mw-redirect" title="Program semantics">program semantics</a>, see <i><a href="/wiki/Least_fixed_point#Denotational_semantics" title="Least fixed point">Least fixed point § Denotational semantics</a></i> for an example. Often a more specialized version of the theorem is used, where <i>L</i> is assumed to be the lattice of all subsets of a certain set ordered by <a href="/wiki/Subset_inclusion" class="mw-redirect" title="Subset inclusion">subset inclusion</a>. This reflects the fact that in many applications only such lattices are considered. One then usually is looking for the smallest set that has the property of being a fixed point of the function <i>f</i>. <a href="/wiki/Abstract_interpretation" title="Abstract interpretation">Abstract interpretation</a> makes ample use of the Knaster–Tarski theorem and the formulas giving the least and greatest fixpoints. </p><p>The Knaster–Tarski theorem can be used to give a simple proof of the <a href="/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Cantor–Bernstein–Schroeder theorem</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Weaker_versions_of_the_theorem">Weaker versions of the theorem</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Knaster%E2%80%93Tarski_theorem&action=edit&section=2" title="Edit section: Weaker versions of the theorem"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Weaker versions of the Knaster–Tarski theorem can be formulated for ordered sets, but involve more complicated assumptions. For example:<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (February 2024)">citation needed</span></a></i>]</sup> </p> <dl><dd><i>Let L be a <a href="/wiki/Partially_ordered_set" title="Partially ordered set">partially ordered set</a> with a <a href="/wiki/Least_element" class="mw-redirect" title="Least element">least element</a> (bottom) and let f</i> : <i>L</i> → <i>L be an <a href="/wiki/Monotonic_function#In_order_theory" title="Monotonic function">monotonic function</a>. Further, suppose there exists u in L such that f</i>(<i>u</i>) ≤ <i>u and that any <a href="/wiki/Total_order#Chains" title="Total order">chain</a> in the subset <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 \{x\in L\mid x\leq f(x),x\leq u\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>x</mi> <mo>∈</mo> <mi>L</mi> <mo>∣</mo> <mi>x</mi> <mo>≤</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>x</mi> <mo>≤</mo> <mi>u</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d8201ccb80f233cdf0c23c6d9b367bff44f6793" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.653ex; height:2.843ex;" alt="{\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}}"></span> has a supremum. Then f admits a <a href="/wiki/Least_fixed_point" title="Least fixed point">least fixed point</a>.</i></dd></dl> <p>This can be applied to obtain various theorems on <a href="/wiki/Invariant_set" class="mw-redirect" title="Invariant set">invariant sets</a>, e.g. the Ok's theorem: </p> <dl><dd><i>For the monotone map F</i> : <i>P</i>(<i>X</i> ) → <i>P</i>(<i>X</i> ) <i>on the <a href="/wiki/Powerset" class="mw-redirect" title="Powerset">family</a> of (closed) nonempty subsets of X, the following are equivalent: (o) F admits A in P</i>(<i>X</i> ) <i>s.t. <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 A\subseteq F(A)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>⊆</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>A</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\subseteq F(A)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f779af0e236b2f0ab40dbc775608897df72e3417" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.135ex; height:2.843ex;" alt="{\displaystyle A\subseteq F(A)}"></span>, (i) F admits invariant set A in P</i>(<i>X</i> ) <i>i.e. <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 A=F(A)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>=</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mi>A</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A=F(A)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/80031c7f9f313fef177e47024f8db4c7658cb542" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.135ex; height:2.843ex;" alt="{\displaystyle A=F(A)}"></span>, (ii) F admits maximal invariant set A, (iii) F admits the greatest invariant set A.</i></dd></dl> <p>In particular, using the Knaster-Tarski principle one can develop the theory of global attractors for noncontractive discontinuous (multivalued) <a href="/wiki/Iterated_function_system" title="Iterated function system">iterated function systems</a>. For weakly contractive iterated function systems the <a href="/wiki/Kantorovich_theorem" title="Kantorovich theorem">Kantorovich theorem</a> (known also as Tarski-Kantorovich fixpoint principle) suffices. </p><p>Other applications of fixed-point principles for ordered sets come from the theory of <a href="/wiki/Differential_equation" title="Differential equation">differential</a>, <a href="/wiki/Integral_equation" title="Integral equation">integral</a> and <a href="/w/index.php?title=Operator_equation&action=edit&redlink=1" class="new" title="Operator equation (page does not exist)">operator</a> equations. </p> <div class="mw-heading mw-heading2"><h2 id="Proof">Proof</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Knaster%E2%80%93Tarski_theorem&action=edit&section=3" title="Edit section: Proof"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Let us restate the theorem. </p><p>For a complete lattice <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 \langle L,\leq \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <mi>L</mi> <mo>,</mo> <mo>≤</mo> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle L,\leq \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f8c51b6f2792719b7a37839ff8a0f71f0764f985" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.234ex; height:2.843ex;" alt="{\displaystyle \langle L,\leq \rangle }"></span> and a monotone function <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 f\colon L\rightarrow L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>:</mo> <mi>L</mi> <mo stretchy="false">→</mo> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\colon L\rightarrow L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cba85b115dfbd76749a925874e993f852cb14519" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.092ex; height:2.509ex;" alt="{\displaystyle f\colon L\rightarrow L}"></span> on <i>L</i>, the set of all fixpoints of <i>f</i> is also a complete lattice <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 \langle P,\leq \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <mi>P</mi> <mo>,</mo> <mo>≤</mo> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle P,\leq \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/135191df5f77b796f8b1e4fcb64b65a2ce5bdabb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.397ex; height:2.843ex;" alt="{\displaystyle \langle P,\leq \rangle }"></span>, with: </p> <ul><li><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 \bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⋁</mo> <mi>P</mi> <mo>=</mo> <mo>⋁</mo> <mo fence="false" stretchy="false">{</mo> <mi>x</mi> <mo>∈</mo> <mi>L</mi> <mo>∣</mo> <mi>x</mi> <mo>≤</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4a05e39347eaaa94e8cef465dc345d9fd01a9c33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:29.255ex; height:3.843ex;" alt="{\displaystyle \bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}}"></span> as the greatest fixpoint of <i>f</i></li> <li><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 \bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⋀</mo> <mi>P</mi> <mo>=</mo> <mo>⋀</mo> <mo fence="false" stretchy="false">{</mo> <mi>x</mi> <mo>∈</mo> <mi>L</mi> <mo>∣</mo> <mi>x</mi> <mo>≥</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9eafd3614a5c75db185a0b32327c6fe43f45055d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:29.255ex; height:3.843ex;" alt="{\displaystyle \bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}}"></span> as the least fixpoint of <i>f</i>.</li></ul> <p><i>Proof.</i> We begin by showing that <i>P</i> has both a least element and a greatest element. Let <span class="texhtml"><i>D</i> = {<i>x</i> | <i>x</i> ≤ <i>f</i>(<i>x</i>)}</span> and <span class="texhtml"><i>x</i> ∈ <i>D</i></span> (we know that at least 0<sub><i>L</i></sub> belongs to <i>D</i>). Then because <i>f</i> is monotone we have <span class="texhtml"><i>f</i>(<i>x</i>) ≤ <i>f</i>(<i>f</i>(<i>x</i>))</span>, that is <span class="texhtml"><i>f</i>(<i>x</i>) ∈ <i>D</i></span>. </p><p>Now let <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 u=\bigvee D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mo>=</mo> <mo>⋁</mo> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u=\bigvee D}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4b45c6aa878d5c23ac9221bce6b45fb0d2b7a59" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.321ex; height:3.843ex;" alt="{\displaystyle u=\bigvee D}"></span> (<i>u</i> exists because <span class="texhtml"><i>D</i> ⊆ <i>L</i></span> and <i>L</i> is a complete lattice). Then for all <span class="texhtml"><i>x</i> ∈ <i>D</i></span> it is true that <span class="texhtml"><i>x</i> ≤ <i>u</i></span> and <span class="texhtml"><i>f</i>(<i>x</i>) ≤ <i>f</i>(<i>u</i>)</span>, so <span class="texhtml"><i>x</i> ≤ <i>f</i>(<i>x</i>) ≤ <i>f</i>(<i>u</i>)</span>. Therefore, <i>f</i>(<i>u</i>) is an upper bound of <i>D</i>, but <i>u</i> is the least upper bound, so <span class="texhtml"><i>u</i> ≤ <i>f</i>(<i>u</i>)</span>, i.e. <span class="texhtml"><i>u</i> ∈ <i>D</i></span>. Then <span class="texhtml"><i>f</i>(<i>u</i>) ∈ <i>D</i></span> (because <span class="texhtml"><i>f</i>(<i>u</i>) ≤ <i>f</i>(<i>f</i>(<i>u</i>)))</span> and so <span class="texhtml"><i>f</i>(<i>u</i>) ≤ <i>u</i></span> from which follows <i>f</i>(<i>u</i>) = <i>u</i>. Because every fixpoint is in <i>D</i> we have that <i>u</i> is the greatest fixpoint of <i>f</i>. </p><p>The function <i>f</i> is monotone on the dual (complete) lattice <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 \langle L^{op},\geq \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <msup> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>o</mi> <mi>p</mi> </mrow> </msup> <mo>,</mo> <mo>≥</mo> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle L^{op},\geq \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/326415b3cd7fb04ee1a1a239cbd60c4e819abfb2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.091ex; height:2.843ex;" alt="{\displaystyle \langle L^{op},\geq \rangle }"></span>. As we have just proved, its greatest fixpoint exists. It is the least fixpoint of <i>L</i>, so <i>P</i> has least and greatest elements, that is more generally, every monotone function on a complete lattice has a least fixpoint and a greatest fixpoint. </p><p>For <i>a</i>, <i>b</i> in <i>L</i> we write [<i>a</i>, <i>b</i>] for the <a href="/wiki/Closed_interval_(order_theory)" class="mw-redirect" title="Closed interval (order theory)">closed interval</a> with bounds <i>a</i> and <span class="texhtml"><i>b</i>: {<i>x</i> ∈ <i>L</i> | <i>a</i> ≤ <i>x</i> ≤ <i>b</i>}</span>. If <i>a</i> ≤ <i>b</i>, then <span class="nowrap">⟨[<i>a</i>, <i>b</i>], ≤⟩</span> is a complete lattice. </p><p>It remains to be proven that <i>P</i> is a complete lattice. Let <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 1_{L}=\bigvee L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>L</mi> </mrow> </msub> <mo>=</mo> <mo>⋁</mo> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1_{L}=\bigvee L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7c08aa3105bdea4b5157d69f9a48c3334d3e83a4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.164ex; height:3.843ex;" alt="{\displaystyle 1_{L}=\bigvee L}"></span>, <span class="texhtml"><i>W</i> ⊆ <i>P</i></span> and <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 w=\bigvee W}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>w</mi> <mo>=</mo> <mo>⋁</mo> <mi>W</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w=\bigvee W}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e0372ba353e1ea550f47bfdd306f04ebe87aed1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.166ex; height:3.843ex;" alt="{\displaystyle w=\bigvee W}"></span>. We show that <span class="texhtml"><i>f</i>([<i>w</i>, 1<sub><i>L</i></sub>]) ⊆ [<i>w</i>, 1<sub><i>L</i></sub>]</span>. Indeed, for every <span class="texhtml"><i>x</i> ∈ <i>W</i></span> we have <i>x</i> = <i>f</i>(<i>x</i>) and since <i>w</i> is the least upper bound of <i>W</i>, <span class="texhtml"><i>x</i> ≤ <i>f</i>(<i>w</i>)</span>. In particular <span class="texhtml"><i>w</i> ≤ <i>f</i>(<i>w</i>)</span>. Then from <span class="texhtml"><i>y</i> ∈ [<i>w</i>, 1<sub><i>L</i></sub>]</span> follows that <span class="texhtml"><i>w</i> ≤ <i>f</i>(<i>w</i>) ≤ <i>f</i>(<i>y</i>)</span>, giving <span class="texhtml"><i>f</i>(<i>y</i>) ∈ [<i>w</i>, 1<sub><i>L</i></sub>]</span> or simply <span class="texhtml"><i>f</i>([<i>w</i>, 1<sub><i>L</i></sub>]) ⊆ [<i>w</i>, 1<sub><i>L</i></sub>]</span>. This allows us to look at <i>f</i> as a function on the complete lattice [<i>w</i>, 1<sub><i>L</i></sub>]. Then it has a least fixpoint there, giving us the least upper bound of <i>W</i>. We've shown that an arbitrary subset of <i>P</i> has a supremum, that is, <i>P</i> is a complete lattice. </p> <div class="mw-heading mw-heading2"><h2 id="Computing_a_Tarski_fixed-point">Computing a Tarski fixed-point</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Knaster%E2%80%93Tarski_theorem&action=edit&section=4" title="Edit section: Computing a Tarski fixed-point"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Chang, Lyuu and Ti<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> present an algorithm for finding a Tarski fixed-point in a <a href="/wiki/Total_order" title="Total order">totally-ordered</a> lattice, when the order-preserving function is given by a <a href="/wiki/Value_oracle" class="mw-redirect" title="Value oracle">value oracle</a>. Their algorithm requires <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 O(\log L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8bb5f8c6138a19b1eded4c6e4809b41e19a90f2f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.524ex; height:2.843ex;" alt="{\displaystyle O(\log L)}"></span> queries, where <i>L</i> is the number of elements in the lattice. In contrast, for a general lattice (given as an oracle), they prove a lower bound 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 \Omega (L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Omega (L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b2cf7556ed8c89c1e332f1f3d1fdc100ffae42e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.07ex; height:2.843ex;" alt="{\displaystyle \Omega (L)}"></span> queries. </p><p>Deng, Qi and Ye<sup id="cite_ref-:0_8-0" class="reference"><a href="#cite_note-:0-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> present several algorithms for finding a Tarski fixed-point. They consider two kinds of lattices: componentwise ordering and <a href="/wiki/Lexicographic_ordering" class="mw-redirect" title="Lexicographic ordering">lexicographic ordering</a>. They consider two kinds of input for the function <i>f</i>: <a href="/wiki/Value_oracle" class="mw-redirect" title="Value oracle">value oracle</a>, or a polynomial function. Their algorithms have the following runtime complexity (where <i>d</i> is the number of dimensions, and <i>N<sub>i</sub></i> is the number of elements in dimension <i>i</i>): </p> <table class="wikitable"> <tbody><tr> <th style="background:#EAECF0;background:linear-gradient(to top right,#EAECF0 49%,#AAA 49.5%,#AAA 50.5%,#EAECF0 51%);line-height:1.2;padding:0.1em 0.4em;"><div style="margin-left:2em;text-align:right">Input </div><div style="margin-right:2em;text-align:left">Lattice</div> </th> <th>Polynomial function </th> <th>Value oracle </th></tr> <tr> <td>Componentwise </td> <td><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 O(\operatorname {poly} (\log L)\cdot \log N_{1}\cdots \log N_{d})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>poly</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> <mo>⋅</mo> <mi>log</mi> <mo>⁡</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋯</mo> <mi>log</mi> <mo>⁡</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\operatorname {poly} (\log L)\cdot \log N_{1}\cdots \log N_{d})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fa291ad05e961c5021c6bbcd720aa3c5b9e4bc08" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.436ex; height:2.843ex;" alt="{\displaystyle O(\operatorname {poly} (\log L)\cdot \log N_{1}\cdots \log N_{d})}"></span> </td> <td><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 O(\log N_{1}\cdots \log N_{d})\approx O(\log ^{d}L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋯</mo> <mi>log</mi> <mo>⁡</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>≈</mo> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msup> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log N_{1}\cdots \log N_{d})\approx O(\log ^{d}L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2834c77f659c57a6653b12ccc67d86935668400" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.391ex; height:3.176ex;" alt="{\displaystyle O(\log N_{1}\cdots \log N_{d})\approx O(\log ^{d}L)}"></span> </td></tr> <tr> <td>Lexicographic </td> <td><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 O(\operatorname {poly} (\log L)\cdot \log L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>poly</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> <mo>⋅</mo> <mi>log</mi> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\operatorname {poly} (\log L)\cdot \log L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f34f5732b657605f9101380dc152230327118ba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.284ex; height:2.843ex;" alt="{\displaystyle O(\operatorname {poly} (\log L)\cdot \log L)}"></span> </td> <td><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 O(\log L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8bb5f8c6138a19b1eded4c6e4809b41e19a90f2f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.524ex; height:2.843ex;" alt="{\displaystyle O(\log L)}"></span> </td></tr></tbody></table> <p>The algorithms are based on <a href="/wiki/Binary_search" title="Binary search">binary search</a>. On the other hand, determining whether a given fixed point is <i>unique</i> is computationally hard: </p> <table class="wikitable"> <tbody><tr> <th style="background:#EAECF0;background:linear-gradient(to top right,#EAECF0 49%,#AAA 49.5%,#AAA 50.5%,#EAECF0 51%);line-height:1.2;padding:0.1em 0.4em;"><div style="margin-left:2em;text-align:right">Input </div><div style="margin-right:2em;text-align:left">Lattice</div> </th> <th>Polynomial function </th> <th>Value oracle </th></tr> <tr> <td>Componentwise </td> <td><a href="/wiki/CoNP-complete" class="mw-redirect" title="CoNP-complete">coNP-complete</a> </td> <td><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 \Theta (N_{1}+\cdots +N_{d})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (N_{1}+\cdots +N_{d})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8ce0c14b7cdab1f277dfd388e80a70e87a74dd7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.9ex; height:2.843ex;" alt="{\displaystyle \Theta (N_{1}+\cdots +N_{d})}"></span> </td></tr> <tr> <td>Lexicographic </td> <td><a href="/wiki/CoNP-complete" class="mw-redirect" title="CoNP-complete">coNP-complete</a> </td> <td><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 \Theta (L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63683ffbe135787a23f34673e8858fd8de9dda78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.2ex; height:2.843ex;" alt="{\displaystyle \Theta (L)}"></span> </td></tr></tbody></table> <p>For <i>d</i>=2, for componentwise lattice and a value-oracle, the complexity 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 O(\log ^{2}L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log ^{2}L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18d85c65ec81d6af0f566d7ac49a86390dd2bdc3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.579ex; height:3.176ex;" alt="{\displaystyle O(\log ^{2}L)}"></span> is optimal.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> But for <i>d</i>>2, there are faster algorithms: </p> <ul><li>Fearnley, Palvolgyi and Savani<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> presented an algorithm using only <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 O(\log ^{2\lceil d/3\rceil }L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo fence="false" stretchy="false">⌈</mo> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> <mo fence="false" stretchy="false">⌉</mo> </mrow> </msup> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log ^{2\lceil d/3\rceil }L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e520b7a96c8a7b463c21295c23eceb6da3d6a4e8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.542ex; height:3.343ex;" alt="{\displaystyle O(\log ^{2\lceil d/3\rceil }L)}"></span> queries. In particular, for <i>d</i>=3, only <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 O(\log ^{2}L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log ^{2}L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18d85c65ec81d6af0f566d7ac49a86390dd2bdc3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.579ex; height:3.176ex;" alt="{\displaystyle O(\log ^{2}L)}"></span> queries are needed.</li> <li>Chen and Li<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> presented an algorithm using only <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 O(\log ^{\lceil (d+1)/2\rceil }L)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo fence="false" stretchy="false">⌈</mo> <mo stretchy="false">(</mo> <mi>d</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌉</mo> </mrow> </msup> <mo>⁡</mo> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log ^{\lceil (d+1)/2\rceil }L)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4b208e4ccfdb1397661cd14e9fee73cac55580a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.1ex; height:3.343ex;" alt="{\displaystyle O(\log ^{\lceil (d+1)/2\rceil }L)}"></span> queries.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Application_in_game_theory">Application in game theory</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Knaster%E2%80%93Tarski_theorem&action=edit&section=5" title="Edit section: Application in game theory"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Tarski's fixed-point theorem has applications to <a href="/wiki/Supermodular_game" class="mw-redirect" title="Supermodular game">supermodular games</a>.<sup id="cite_ref-:0_8-1" class="reference"><a href="#cite_note-:0-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> A <i>supermodular game</i> (also called a <i>game of strategic complements</i><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>) is a <a href="/wiki/Game_theory" title="Game theory">game</a> in which the <a href="/wiki/Utility_function" class="mw-redirect" title="Utility function">utility function</a> of each player has <a href="/wiki/Increasing_differences" class="mw-redirect" title="Increasing differences">increasing differences</a>, so the <a href="/wiki/Best_response" title="Best response">best response</a> of a player is a weakly-increasing function of other players' strategies. For example, consider a game of competition between two firms. Each firm has to decide how much money to spend on research. In general, if one firm spends more on research, the other firm's best response is to spend more on research too. Some common games can be modeled as supermodular games, for example <a href="/wiki/Cournot_competition" title="Cournot competition">Cournot competition</a>, <a href="/wiki/Bertrand_competition" title="Bertrand competition">Bertrand competition</a> and <a href="/wiki/Investment_Game" class="mw-redirect" title="Investment Game">Investment Games</a>. </p><p>Because the best-response functions are monotone, Tarski's fixed-point theorem can be used to prove the existence of a <a href="/wiki/Pure_strategy" class="mw-redirect" title="Pure strategy">pure-strategy</a> <a href="/wiki/Nash_equilibrium" title="Nash equilibrium">Nash equilibrium</a> (PNE) in a supermodular game. Moreover, Topkis<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> showed that the set of PNE of a supermodular game is a complete lattice, so the game has a "smallest" PNE and a "largest" PNE. </p><p>Echenique<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> presents an algorithm for finding all PNE in a supermodular game. His algorithm first uses best-response sequences to find the smallest and largest PNE; then, he removes some strategies and repeats, until all PNE are found. His algorithm is exponential in the worst case, but runs fast in practice. Deng, Qi and Ye<sup id="cite_ref-:0_8-2" class="reference"><a href="#cite_note-:0-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> show that a PNE can be computed efficiently by finding a Tarski fixed-point of an order-preserving mapping associated with the game. </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=Knaster%E2%80%93Tarski_theorem&action=edit&section=6" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Modal_%CE%BC-calculus" title="Modal μ-calculus">Modal μ-calculus</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Knaster%E2%80%93Tarski_theorem&action=edit&section=7" title="Edit section: Notes"><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 mw-references-columns"><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="CITEREFAlfred_Tarski1955" class="citation journal cs1">Alfred Tarski (1955). <a rel="nofollow" class="external text" href="https://www.projecteuclid.org/journals/pacific-journal-of-mathematics/volume-5/issue-2/A-lattice-theoretical-fixpoint-theorem-and-its-applications/pjm/1103044538.full">"A lattice-theoretical fixpoint theorem and its applications"</a>. <i>Pacific Journal of Mathematics</i>. <b>5</b> (2): 285–309. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.2140%2Fpjm.1955.5.285">10.2140/pjm.1955.5.285</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Pacific+Journal+of+Mathematics&rft.atitle=A+lattice-theoretical+fixpoint+theorem+and+its+applications&rft.volume=5&rft.issue=2&rft.pages=285-309&rft.date=1955&rft_id=info%3Adoi%2F10.2140%2Fpjm.1955.5.285&rft.au=Alfred+Tarski&rft_id=https%3A%2F%2Fwww.projecteuclid.org%2Fjournals%2Fpacific-journal-of-mathematics%2Fvolume-5%2Fissue-2%2FA-lattice-theoretical-fixpoint-theorem-and-its-applications%2Fpjm%2F1103044538.full&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></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="CITEREFB._Knaster1928" class="citation journal cs1">B. Knaster (1928). "Un théorème sur les fonctions d'ensembles". <i><a href="/wiki/Ann._Soc._Polon._Math." class="mw-redirect" title="Ann. Soc. Polon. Math.">Ann. Soc. Polon. Math.</a></i> <b>6</b>: 133–134.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Ann.+Soc.+Polon.+Math.&rft.atitle=Un+th%C3%A9or%C3%A8me+sur+les+fonctions+d%27ensembles&rft.volume=6&rft.pages=133-134&rft.date=1928&rft.au=B.+Knaster&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span> With A. Tarski.</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="CITEREFAnne_C._Davis1955" class="citation journal cs1"><a href="/wiki/Anne_C._Morel" title="Anne C. Morel">Anne C. Davis</a> (1955). <a rel="nofollow" class="external text" href="https://www.projecteuclid.org/journals/pacific-journal-of-mathematics/volume-5/issue-2/A-characterization-of-complete-lattices/pjm/1103044539.full">"A characterization of complete lattices"</a>. <i>Pacific Journal of Mathematics</i>. <b>5</b> (2): 311–319. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.2140%2Fpjm.1955.5.311">10.2140/pjm.1955.5.311</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Pacific+Journal+of+Mathematics&rft.atitle=A+characterization+of+complete+lattices&rft.volume=5&rft.issue=2&rft.pages=311-319&rft.date=1955&rft_id=info%3Adoi%2F10.2140%2Fpjm.1955.5.311&rft.au=Anne+C.+Davis&rft_id=https%3A%2F%2Fwww.projecteuclid.org%2Fjournals%2Fpacific-journal-of-mathematics%2Fvolume-5%2Fissue-2%2FA-characterization-of-complete-lattices%2Fpjm%2F1103044539.full&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+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="CITEREFCousotCousot1979" class="citation journal cs1">Cousot, Patrick; Cousot, Radhia (1979). <a rel="nofollow" class="external text" href="https://doi.org/10.2140%2Fpjm.1979.82.43">"Constructive versions of tarski's fixed point theorems"</a>. <i>Pacific Journal of Mathematics</i>. <b>82</b>: 43–57. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.2140%2Fpjm.1979.82.43">10.2140/pjm.1979.82.43</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Pacific+Journal+of+Mathematics&rft.atitle=Constructive+versions+of+tarski%27s+fixed+point+theorems&rft.volume=82&rft.pages=43-57&rft.date=1979&rft_id=info%3Adoi%2F10.2140%2Fpjm.1979.82.43&rft.aulast=Cousot&rft.aufirst=Patrick&rft.au=Cousot%2C+Radhia&rft_id=https%3A%2F%2Fdoi.org%2F10.2140%252Fpjm.1979.82.43&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><span class="citation mathworld" id="Reference-Mathworld-Tarski's_Fixed_Point_Theorem"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1">Uhl, Roland. <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/TarskisFixedPointTheorem.html">"Tarski's Fixed Point Theorem"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Tarski%27s+Fixed+Point+Theorem&rft.au=Uhl%2C+Roland&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FTarskisFixedPointTheorem.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> Example 3.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDaveyPriestley2002" class="citation book cs1">Davey, Brian A.; <a href="/wiki/Hilary_Priestley" title="Hilary Priestley">Priestley, Hilary A.</a> (2002). <a href="/wiki/Introduction_to_Lattices_and_Order" title="Introduction to Lattices and Order"><i>Introduction to Lattices and Order</i></a> (2nd ed.). <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. pp. 63, 4. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521784511" title="Special:BookSources/9780521784511"><bdi>9780521784511</bdi></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+Lattices+and+Order&rft.pages=63%2C+4&rft.edition=2nd&rft.pub=Cambridge+University+Press&rft.date=2002&rft.isbn=9780521784511&rft.aulast=Davey&rft.aufirst=Brian+A.&rft.au=Priestley%2C+Hilary+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChangLyuuTi2008" class="citation journal cs1">Chang, Ching-Lueh; Lyuu, Yuh-Dauh; Ti, Yen-Wu (2008-07-23). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S0304397508003812">"The complexity of Tarski's fixed point theorem"</a>. <i>Theoretical Computer Science</i>. <b>401</b> (1): 228–235. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2008.05.005">10.1016/j.tcs.2008.05.005</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/0304-3975">0304-3975</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=The+complexity+of+Tarski%27s+fixed+point+theorem&rft.volume=401&rft.issue=1&rft.pages=228-235&rft.date=2008-07-23&rft_id=info%3Adoi%2F10.1016%2Fj.tcs.2008.05.005&rft.issn=0304-3975&rft.aulast=Chang&rft.aufirst=Ching-Lueh&rft.au=Lyuu%2C+Yuh-Dauh&rft.au=Ti%2C+Yen-Wu&rft_id=https%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fpii%2FS0304397508003812&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-:0-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_8-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_8-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDangQiYe2020" class="citation report cs1">Dang, Chuangyin; Qi, Qi; Ye, Yinyu (2020-05-01). <a rel="nofollow" class="external text" href="https://econpapers.repec.org/paper/arxpapers/2005.09836.htm">Computations and Complexities of Tarski's Fixed Points and Supermodular Games</a> (Report). arXiv.org.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=Computations+and+Complexities+of+Tarski%27s+Fixed+Points+and+Supermodular+Games&rft.pub=arXiv.org&rft.date=2020-05-01&rft.aulast=Dang&rft.aufirst=Chuangyin&rft.au=Qi%2C+Qi&rft.au=Ye%2C+Yinyu&rft_id=https%3A%2F%2Feconpapers.repec.org%2Fpaper%2Farxpapers%2F2005.09836.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEtessamiPapadimitriouRubinsteinYannakakis2020" class="citation journal cs1">Etessami, Kousha; Papadimitriou, Christos; Rubinstein, Aviad; Yannakakis, Mihalis (2020). Vidick, Thomas (ed.). <a rel="nofollow" class="external text" href="https://drops.dagstuhl.de/opus/volltexte/2020/11703">"Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria"</a>. <i>11th Innovations in Theoretical Computer Science Conference (ITCS 2020)</i>. Leibniz International Proceedings in Informatics (LIPIcs). <b>151</b>. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 18:1–18:19. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.ITCS.2020.18">10.4230/LIPIcs.ITCS.2020.18</a></span>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-95977-134-4" title="Special:BookSources/978-3-95977-134-4"><bdi>978-3-95977-134-4</bdi></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:202538977">202538977</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=11th+Innovations+in+Theoretical+Computer+Science+Conference+%28ITCS+2020%29&rft.atitle=Tarski%27s+Theorem%2C+Supermodular+Games%2C+and+the+Complexity+of+Equilibria&rft.volume=151&rft.pages=18%3A1-18%3A19&rft.date=2020&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A202538977%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.4230%2FLIPIcs.ITCS.2020.18&rft.isbn=978-3-95977-134-4&rft.aulast=Etessami&rft.aufirst=Kousha&rft.au=Papadimitriou%2C+Christos&rft.au=Rubinstein%2C+Aviad&rft.au=Yannakakis%2C+Mihalis&rft_id=https%3A%2F%2Fdrops.dagstuhl.de%2Fopus%2Fvolltexte%2F2020%2F11703&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFearnleyPálvölgyiSavani2022" class="citation journal cs1">Fearnley, John; Pálvölgyi, Dömötör; Savani, Rahul (2022-10-11). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3524044">"A Faster Algorithm for Finding Tarski Fixed Points"</a>. <i>ACM Transactions on Algorithms</i>. <b>18</b> (3): 23:1–23:23. <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/2010.02618">2010.02618</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3524044">10.1145/3524044</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/1549-6325">1549-6325</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:222141645">222141645</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Algorithms&rft.atitle=A+Faster+Algorithm+for+Finding+Tarski+Fixed+Points&rft.volume=18&rft.issue=3&rft.pages=23%3A1-23%3A23&rft.date=2022-10-11&rft_id=info%3Aarxiv%2F2010.02618&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A222141645%23id-name%3DS2CID&rft.issn=1549-6325&rft_id=info%3Adoi%2F10.1145%2F3524044&rft.aulast=Fearnley&rft.aufirst=John&rft.au=P%C3%A1lv%C3%B6lgyi%2C+D%C3%B6m%C3%B6t%C3%B6r&rft.au=Savani%2C+Rahul&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F3524044&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChenLi2022" class="citation book cs1">Chen, Xi; Li, Yuhao (2022-07-13). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/3490486.3538297">"Improved Upper Bounds for Finding Tarski Fixed Points"</a>. <i>Proceedings of the 23rd ACM Conference on Economics and Computation</i>. EC '22. New York, NY, USA: Association for Computing Machinery. pp. 1108–1118. <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/2202.05913">2202.05913</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3490486.3538297">10.1145/3490486.3538297</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-9150-4" title="Special:BookSources/978-1-4503-9150-4"><bdi>978-1-4503-9150-4</bdi></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:246823965">246823965</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Improved+Upper+Bounds+for+Finding+Tarski+Fixed+Points&rft.btitle=Proceedings+of+the+23rd+ACM+Conference+on+Economics+and+Computation&rft.place=New+York%2C+NY%2C+USA&rft.series=EC+%2722&rft.pages=1108-1118&rft.pub=Association+for+Computing+Machinery&rft.date=2022-07-13&rft_id=info%3Aarxiv%2F2202.05913&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A246823965%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F3490486.3538297&rft.isbn=978-1-4503-9150-4&rft.aulast=Chen&rft.aufirst=Xi&rft.au=Li%2C+Yuhao&rft_id=https%3A%2F%2Fdl.acm.org%2Fdoi%2F10.1145%2F3490486.3538297&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFVives1990" class="citation journal cs1">Vives, Xavier (1990-01-01). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1016/0304-4068%2890%2990005-T">"Nash equilibrium with strategic complementarities"</a>. <i>Journal of Mathematical Economics</i>. <b>19</b> (3): 305–321. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-4068%2890%2990005-T">10.1016/0304-4068(90)90005-T</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/0304-4068">0304-4068</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Mathematical+Economics&rft.atitle=Nash+equilibrium+with+strategic+complementarities&rft.volume=19&rft.issue=3&rft.pages=305-321&rft.date=1990-01-01&rft_id=info%3Adoi%2F10.1016%2F0304-4068%2890%2990005-T&rft.issn=0304-4068&rft.aulast=Vives&rft.aufirst=Xavier&rft_id=https%3A%2F%2Fdx.doi.org%2F10.1016%2F0304-4068%252890%252990005-T&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTopkis1979" class="citation journal cs1">Topkis, Donald M. (1979-11-01). <a rel="nofollow" class="external text" href="http://epubs.siam.org/doi/10.1137/0317054">"Equilibrium Points in Nonzero-Sum n -Person Submodular Games"</a>. <i>SIAM Journal on Control and Optimization</i>. <b>17</b> (6): 773–787. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0317054">10.1137/0317054</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/0363-0129">0363-0129</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Control+and+Optimization&rft.atitle=Equilibrium+Points+in+Nonzero-Sum+n+-Person+Submodular+Games&rft.volume=17&rft.issue=6&rft.pages=773-787&rft.date=1979-11-01&rft_id=info%3Adoi%2F10.1137%2F0317054&rft.issn=0363-0129&rft.aulast=Topkis&rft.aufirst=Donald+M.&rft_id=http%3A%2F%2Fepubs.siam.org%2Fdoi%2F10.1137%2F0317054&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEchenique2007" class="citation journal cs1">Echenique, Federico (2007-07-01). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S0022053106001086">"Finding all equilibria in games of strategic complements"</a>. <i>Journal of Economic Theory</i>. <b>135</b> (1): 514–532. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jet.2006.06.001">10.1016/j.jet.2006.06.001</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/0022-0531">0022-0531</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Economic+Theory&rft.atitle=Finding+all+equilibria+in+games+of+strategic+complements&rft.volume=135&rft.issue=1&rft.pages=514-532&rft.date=2007-07-01&rft_id=info%3Adoi%2F10.1016%2Fj.jet.2006.06.001&rft.issn=0022-0531&rft.aulast=Echenique&rft.aufirst=Federico&rft_id=https%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fpii%2FS0022053106001086&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></span> </li> </ol></div></div> <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=Knaster%E2%80%93Tarski_theorem&action=edit&section=8" title="Edit section: References"><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="CITEREFAndrzej_Granas_and_James_Dugundji2003" class="citation book cs1">Andrzej Granas and <a href="/wiki/James_Dugundji" title="James Dugundji">James Dugundji</a> (2003). <i>Fixed Point Theory</i>. <a href="/wiki/Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer-Verlag</a>, New York. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-00173-9" title="Special:BookSources/978-0-387-00173-9"><bdi>978-0-387-00173-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fixed+Point+Theory&rft.pub=Springer-Verlag%2C+New+York&rft.date=2003&rft.isbn=978-0-387-00173-9&rft.au=Andrzej+Granas+and+James+Dugundji&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFForster2003" class="citation book cs1">Forster, T. (2003-07-21). <i>Logic, Induction and Sets</i>. Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-53361-4" title="Special:BookSources/978-0-521-53361-4"><bdi>978-0-521-53361-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Logic%2C+Induction+and+Sets&rft.pub=Cambridge+University+Press&rft.date=2003-07-21&rft.isbn=978-0-521-53361-4&rft.aulast=Forster&rft.aufirst=T.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li></ul> <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=Knaster%E2%80%93Tarski_theorem&action=edit&section=9" 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="CITEREFS._Hayashi1985" class="citation journal cs1">S. Hayashi (1985). <a rel="nofollow" class="external text" href="https://doi.org/10.2977%2Fprims%2F1195178796">"Self-similar sets as Tarski's fixed points"</a>. <i>Publications of the Research Institute for Mathematical Sciences</i>. <b>21</b> (5): 1059–1066. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.2977%2Fprims%2F1195178796">10.2977/prims/1195178796</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Publications+of+the+Research+Institute+for+Mathematical+Sciences&rft.atitle=Self-similar+sets+as+Tarski%27s+fixed+points&rft.volume=21&rft.issue=5&rft.pages=1059-1066&rft.date=1985&rft_id=info%3Adoi%2F10.2977%2Fprims%2F1195178796&rft.au=S.+Hayashi&rft_id=https%3A%2F%2Fdoi.org%2F10.2977%252Fprims%252F1195178796&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJ._JachymskiL._GajekK._Pokarowski2000" class="citation journal cs1">J. Jachymski; L. Gajek; K. Pokarowski (2000). <a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0004972700022243">"The Tarski-Kantorovitch principle and the theory of iterated function systems"</a>. <i>Bull. Austral. Math. Soc</i>. <b>61</b> (2): 247–261. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0004972700022243">10.1017/S0004972700022243</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Bull.+Austral.+Math.+Soc.&rft.atitle=The+Tarski-Kantorovitch+principle+and+the+theory+of+iterated+function+systems&rft.volume=61&rft.issue=2&rft.pages=247-261&rft.date=2000&rft_id=info%3Adoi%2F10.1017%2FS0004972700022243&rft.au=J.+Jachymski&rft.au=L.+Gajek&rft.au=K.+Pokarowski&rft_id=https%3A%2F%2Fdoi.org%2F10.1017%252FS0004972700022243&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFE.A._Ok2004" class="citation journal cs1">E.A. Ok (2004). "Fixed set theory for closed correspondences with applications to self-similarity and games". <i>Nonlinear Anal</i>. <b>56</b> (3): 309–330. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.561.4581">10.1.1.561.4581</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.na.2003.08.001">10.1016/j.na.2003.08.001</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Nonlinear+Anal.&rft.atitle=Fixed+set+theory+for+closed+correspondences+with+applications+to+self-similarity+and+games&rft.volume=56&rft.issue=3&rft.pages=309-330&rft.date=2004&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.561.4581%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1016%2Fj.na.2003.08.001&rft.au=E.A.+Ok&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFB.S.W._Schröder1999" class="citation journal cs1">B.S.W. Schröder (1999). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2898%2900273-4">"Algorithms for the fixed point property"</a>. <i>Theoret. Comput. Sci</i>. <b>217</b> (2): 301–358. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2898%2900273-4">10.1016/S0304-3975(98)00273-4</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoret.+Comput.+Sci.&rft.atitle=Algorithms+for+the+fixed+point+property&rft.volume=217&rft.issue=2&rft.pages=301-358&rft.date=1999&rft_id=info%3Adoi%2F10.1016%2FS0304-3975%2898%2900273-4&rft.au=B.S.W.+Schr%C3%B6der&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252FS0304-3975%252898%252900273-4&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFS._Heikkilä1990" class="citation journal cs1">S. Heikkilä (1990). "On fixed points through a generalized iteration method with applications to differential and integral equations involving discontinuities". <i>Nonlinear Anal</i>. <b>14</b> (5): 413–426. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0362-546X%2890%2990082-R">10.1016/0362-546X(90)90082-R</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Nonlinear+Anal.&rft.atitle=On+fixed+points+through+a+generalized+iteration+method+with+applications+to+differential+and+integral+equations+involving+discontinuities&rft.volume=14&rft.issue=5&rft.pages=413-426&rft.date=1990&rft_id=info%3Adoi%2F10.1016%2F0362-546X%2890%2990082-R&rft.au=S.+Heikkil%C3%A4&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFR._Uhl2003" class="citation journal cs1 cs1-prop-long-vol">R. Uhl (2003). "Smallest and greatest fixed points of quasimonotone increasing mappings". <i><a href="/wiki/Mathematische_Nachrichten" title="Mathematische Nachrichten">Mathematische Nachrichten</a></i>. 248–249: 204–210. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fmana.200310016">10.1002/mana.200310016</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:120679842">120679842</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematische+Nachrichten&rft.atitle=Smallest+and+greatest+fixed+points+of+quasimonotone+increasing+mappings&rft.volume=248%E2%80%93249&rft.pages=204-210&rft.date=2003&rft_id=info%3Adoi%2F10.1002%2Fmana.200310016&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A120679842%23id-name%3DS2CID&rft.au=R.+Uhl&rfr_id=info%3Asid%2Fen.wikipedia.org%3AKnaster%E2%80%93Tarski+theorem" class="Z3988"></span></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=Knaster%E2%80%93Tarski_theorem&action=edit&section=10" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>J. B. Nation, <a rel="nofollow" class="external text" href="http://people.math.sc.edu/mcnulty/alglatvar/lat.pdf"><i>Notes on lattice theory</i></a>.</li> <li><a rel="nofollow" class="external text" href="https://math.stackexchange.com/a/3026040">An application to an elementary combinatorics problem</a>: Given a book with 100 pages and 100 lemmas, prove that there is some lemma written on the same page as its index</li></ul>    </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=Knaster–Tarski_theorem&oldid=1254306963">https://en.wikipedia.org/w/index.php?title=Knaster–Tarski_theorem&oldid=1254306963</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:Order_theory" title="Category:Order theory">Order theory</a></li><li><a href="/wiki/Category:Fixed_points_(mathematics)" title="Category:Fixed points (mathematics)">Fixed points (mathematics)</a></li><li><a href="/wiki/Category:Fixed-point_theorems" title="Category:Fixed-point theorems">Fixed-point theorems</a></li><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></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_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_February_2024" title="Category:Articles with unsourced statements from February 2024">Articles with unsourced statements from February 2024</a></li><li><a href="/wiki/Category:CS1:_long_volume_value" title="Category:CS1: long volume value">CS1: long volume value</a></li><li><a href="/wiki/Category:Articles_containing_proofs" title="Category:Articles containing proofs">Articles containing proofs</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 30 October 2024, at 11:14<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=Knaster%E2%80%93Tarski_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-jvw68","wgBackendResponseTime":131,"wgPageParseReport":{"limitreport":{"cputime":"0.365","walltime":"0.551","ppvisitednodes":{"value":2811,"limit":1000000},"postexpandincludesize":{"value":55212,"limit":2097152},"templateargumentsize":{"value":3627,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":72428,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 407.937 1 -total"," 43.57% 177.733 1 Template:Reflist"," 34.93% 142.502 16 Template:Cite_journal"," 23.89% 97.450 1 Template:Short_description"," 11.19% 45.649 2 Template:Pagetype"," 11.07% 45.145 28 Template:Main_other"," 9.84% 40.140 1 Template:Citation_needed"," 9.68% 39.469 1 Template:SDcat"," 8.60% 35.063 1 Template:Fix"," 7.53% 30.698 24 Template:Math"]},"scribunto":{"limitreport-timeusage":{"value":"0.192","limit":"10.000"},"limitreport-memusage":{"value":6663875,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-26bwr","timestamp":"20241122144140","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Knaster\u2013Tarski theorem","url":"https:\/\/en.wikipedia.org\/wiki\/Knaster%E2%80%93Tarski_theorem","sameAs":"http:\/\/www.wikidata.org\/entity\/Q609612","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q609612","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":"2003-02-10T16:53:09Z","dateModified":"2024-10-30T11:14:16Z","headline":"theorem"}</script> </body> </html>