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>Graded poset - 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":"b33094bd-0c9f-4e15-aef6-84b0ca329e00","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Graded_poset","wgTitle":"Graded poset","wgCurRevisionId":1255978421,"wgRevisionId":1255978421,"wgArticleId":2514970,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Algebraic combinatorics","Order theory"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Graded_poset","wgRelevantArticleId":2514970,"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":10000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q5591878","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user": "ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns", "ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/1200px-Hasse_diagram_of_powerset_of_3.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="909"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/800px-Hasse_diagram_of_powerset_of_3.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="606"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/640px-Hasse_diagram_of_powerset_of_3.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="485"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Graded poset - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Graded_poset"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Graded_poset&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/Graded_poset"> <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-Graded_poset rootpage-Graded_poset 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=Graded+poset" 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=Graded+poset" 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=Graded+poset" 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=Graded+poset" 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-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Alternative_characterizations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Alternative_characterizations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Alternative characterizations</span> </div> </a> <ul id="toc-Alternative_characterizations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_usual_case" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#The_usual_case"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>The usual case</span> </div> </a> <ul id="toc-The_usual_case-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">4</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">5</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">6</span> <span>References</span> </div> </a> <ul id="toc-References-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">Graded poset</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 1 language" > <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-1" 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">1 language</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D1%83%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%B5_%D1%87%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%BD%D0%BE_%D1%83%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%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> </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/Q5591878#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/Graded_poset" 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:Graded_poset" 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/Graded_poset"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Graded_poset&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=Graded_poset&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/Graded_poset"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Graded_poset&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=Graded_poset&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/Graded_poset" 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/Graded_poset" 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=Graded_poset&oldid=1255978421" 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=Graded_poset&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=Graded_poset&id=1255978421&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%2FGraded_poset"><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%2FGraded_poset"><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=Graded_poset&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=Graded_poset&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/Q5591878" 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"><figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Hasse_diagram_of_powerset_of_3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/300px-Hasse_diagram_of_powerset_of_3.svg.png" decoding="async" width="300" height="227" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/450px-Hasse_diagram_of_powerset_of_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/600px-Hasse_diagram_of_powerset_of_3.svg.png 2x" data-file-width="429" data-file-height="325" /></a><figcaption>A <a href="/wiki/Power_set" title="Power set">power set</a>, partially ordered by <a href="/wiki/Inclusion_(set_theory)" class="mw-redirect" title="Inclusion (set theory)">inclusion</a>, with rank defined as number of elements, forms a graded poset.</figcaption></figure> <p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, in the branch of <a href="/wiki/Combinatorics" title="Combinatorics">combinatorics</a>, a <b>graded poset</b> is a <a href="/wiki/Partially-ordered_set" class="mw-redirect" title="Partially-ordered set">partially-ordered set</a> (poset) <i>P</i> equipped with a <b>rank function</b> <i>ρ</i> from <i>P</i> to the set <b>N</b> of all <a href="/wiki/Natural_number" title="Natural number">natural numbers</a>. <i>ρ</i> must satisfy the following two properties: </p> <ul><li>The rank function is compatible with the ordering, meaning that for all <i>x</i> and <i>y</i> in the order, if <i>x</i> < <i>y</i> then <i>ρ</i>(<i>x</i>) < <i>ρ</i>(<i>y</i>), and</li> <li>The rank is consistent with the <a href="/wiki/Covering_relation" title="Covering relation">covering relation</a> of the ordering, meaning that for all <i>x</i> and <i>y</i>, if <i>y</i> covers <i>x</i> then <i>ρ</i>(<i>y</i>) = <i>ρ</i>(<i>x</i>) + 1.</li></ul> <p>The value of the rank function for an element of the poset is called its <b>rank</b>. Sometimes a graded poset is called a <b>ranked poset</b> but that phrase has other meanings; see <a href="/wiki/Ranked_poset" title="Ranked poset">Ranked poset</a>. A <b>rank</b> or <b>rank level</b> of a graded poset is the <a href="/wiki/Subset" title="Subset">subset</a> of all the elements of the poset that have a given rank value.<sup id="cite_ref-stanley_1-0" class="reference"><a href="#cite_note-stanley-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><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>Graded posets play an important role in <a href="/wiki/Combinatorics" title="Combinatorics">combinatorics</a> and can be visualized by means of a <a href="/wiki/Hasse_diagram" title="Hasse diagram">Hasse diagram</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Graded_poset&action=edit&section=1" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Some examples of graded posets (with the rank function in parentheses) are: </p> <ul><li>Natural numbers <b>N</b> with their usual order (rank: the number itself), or some <a href="/wiki/Partially_ordered_set#Intervals" title="Partially ordered set">interval</a> [0, <i>N</i>] of this poset</li> <li><b>N</b><sup><i>n</i></sup> with the <a href="/wiki/Product_order" title="Product order">product order</a> (sum of the components), or a subposet of it that is a product of intervals</li> <li>Positive <a href="/wiki/Integer" title="Integer">integers</a> ordered by divisibility (number of <a href="/wiki/Prime_number" title="Prime number">prime</a> factors, counted with multiplicity), or a subposet of it formed by the <a href="/wiki/Divisor" title="Divisor">divisors</a> of a fixed <i>N</i></li> <li>The <a href="/wiki/Boolean_lattice" class="mw-redirect" title="Boolean lattice">Boolean lattice</a> of finite subsets of a set ordered by inclusion (number of elements of the subset)</li> <li>Any <a href="/wiki/Distributive_lattice" title="Distributive lattice">distributive lattice</a> of finite <a href="/wiki/Lower_set" class="mw-redirect" title="Lower set">lower sets</a> of another poset (number of elements) <ul><li>In particular any <a href="/wiki/Birkhoff%27s_representation_theorem" title="Birkhoff's representation theorem">finite distributive lattice</a></li></ul></li> <li>Poset of all unlabeled posets on <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,...,n\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>n</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{1,...,n\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b58586317e220f0d1f11815600f8d9063dc41863" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.052ex; height:2.843ex;" alt="{\displaystyle \{1,...,n\}}"></span> (number of elements)<sup id="cite_ref-culberson_3-0" class="reference"><a href="#cite_note-culberson-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/Young%27s_lattice" title="Young's lattice">Young's lattice</a> (number of boxes in the Young diagram)</li> <li>Any <a href="/wiki/Geometric_lattice" title="Geometric lattice">geometric lattice</a>, such as the lattice of <a href="/wiki/Linear_subspace" title="Linear subspace">subspaces</a> of a <a href="/wiki/Vector_space" title="Vector space">vector space</a> (<a href="/wiki/Dimension_(vector_space)" title="Dimension (vector space)">dimension</a> of the subspace)</li> <li>Lattice of <a href="/wiki/Set_partition" class="mw-redirect" title="Set partition">partitions</a> of a set into finitely many parts, ordered by reverse refinement (number of parts)</li> <li>Lattice of <a href="/wiki/Set_partition" class="mw-redirect" title="Set partition">partitions</a> of a finite set <i>X</i>, ordered by refinement (number of elements of <i>X</i> minus number of parts)</li> <li><a href="/wiki/Face_lattice" class="mw-redirect" title="Face lattice">Face lattice</a> of <a href="/wiki/Convex_polytope" title="Convex polytope">convex polytopes</a> (dimension of the face, plus one)</li> <li><a href="/wiki/Abstract_polytope" title="Abstract polytope">Abstract polytope</a> ("distance" from the least face, minus one)</li> <li><a href="/wiki/Abstract_simplicial_complex" title="Abstract simplicial complex">Abstract simplicial complex</a> (number of elements of the simplex)</li> <li>A <a href="/wiki/Group_(mathematics)" title="Group (mathematics)">group</a> with a <a href="/wiki/Generating_set_of_a_group" title="Generating set of a group">generating set</a>, or equivalently its <a href="/wiki/Cayley_graph" title="Cayley graph">Cayley graph</a>, ordered by the weak or strong <a href="/wiki/Bruhat_order" title="Bruhat order">Bruhat order</a>, and ranked by <a href="/wiki/Word_metric" title="Word metric">word length</a> (length of shortest reduced word) <ul><li>In particular a <a href="/wiki/Coxeter_group" title="Coxeter group">Coxeter group</a>, for example <a href="/wiki/Permutation" title="Permutation">permutations</a> of a totally ordered <i>n</i>-element set, with either the weak or strong <a href="/wiki/Bruhat_order" title="Bruhat order">Bruhat order</a> (number of adjacent inversions)</li></ul></li></ul> <div class="mw-heading mw-heading2"><h2 id="Alternative_characterizations">Alternative characterizations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Graded_poset&action=edit&section=2" title="Edit section: Alternative characterizations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Smallest_nonmodular_lattice_1.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Smallest_nonmodular_lattice_1.svg/100px-Smallest_nonmodular_lattice_1.svg.png" decoding="async" width="100" height="129" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Smallest_nonmodular_lattice_1.svg/150px-Smallest_nonmodular_lattice_1.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Smallest_nonmodular_lattice_1.svg/200px-Smallest_nonmodular_lattice_1.svg.png 2x" data-file-width="140" data-file-height="180" /></a><figcaption>The lattice <i>N</i><sub>5</sub> can't be graded.</figcaption></figure> <p>A <a href="/wiki/Bounded_poset" class="mw-redirect" title="Bounded poset">bounded poset</a><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> admits a grading <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> all <a href="/wiki/Maximal_chain" class="mw-redirect" title="Maximal chain">maximal chains</a> in <i>P</i> have the same length:<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> setting the rank of the least element to 0 then determines the rank function completely. This covers many finite cases of interest; see picture for a negative example. However, unbounded posets can be more complicated. </p><p>A candidate rank function, compatible with the ordering, makes a poset into graded poset if and only if, whenever one has <i>x</i> < <i>z</i> with <i>z</i> of rank <i>n</i> + 1, an element <i>y</i> of rank <i>n</i> can be found with <i>x</i> ≤ <i>y</i> < <i>z</i>. This condition is sufficient because if <i>z</i> is taken to be a cover of <i>x</i>, the only possible choice is <i>y</i> = <i>x</i> showing that the ranks of <i>x</i> and <i>z</i> differ by 1, and it is necessary because in a graded poset one can take for <i>y</i> any element of maximal rank with <i>x</i> ≤ <i>y</i> < <i>z</i>, which always exists and is covered by <i>z</i>. </p><p>Often a poset comes with a natural candidate for a rank function; for instance if its elements are finite subsets of some base set <i>B</i>, one can take the number of elements of those subsets. Then the criterion just given can be more practical than the definition because it avoids mention of covers. For instance if <i>B</i> is itself a poset, and <i>P</i> consists of its finite <a href="/wiki/Lower_set" class="mw-redirect" title="Lower set">lower sets</a> (subsets for which with every one of its elements, all smaller elements are also in the subset), then the criterion is automatically satisfied, since for lower sets <i>x</i> ⊊ <i>z</i> there is always a <a href="/wiki/Maximal_element" class="mw-redirect" title="Maximal element">maximal element</a> of <i>z</i> that is absent from <i>x</i>, and it can be removed from <i>z</i> to form <i>y</i>. </p><p>In some common posets such as the <a href="/wiki/Face_lattice" class="mw-redirect" title="Face lattice">face lattice</a> of a <a href="/wiki/Convex_polytope" title="Convex polytope">convex polytope</a> there is a natural grading by <a href="/wiki/Dimension" title="Dimension">dimension</a>, which if used as rank function would give the minimal element, the empty face, rank −1. In such cases it might be convenient to bend the definition stated above by adjoining the value −1 to the set of values allowed for the rank function. Allowing arbitrary integers as rank would however give a fundamentally different notion; for instance the existence of a minimal element would no longer be assured. </p><p>A graded poset (with positive integer ranks) cannot have any elements <i>x</i> for which arbitrarily long <a href="/wiki/Chain_(order_theory)" class="mw-redirect" title="Chain (order theory)">chains</a> with greatest element <i>x</i> exist, as otherwise it would have to have elements of arbitrarily small (and eventually negative) rank. For instance, the integers (with the usual order) cannot be a graded poset, nor can any interval (with more than one element) of <a href="/wiki/Rational_number" title="Rational number">rational</a> or <a href="/wiki/Real_number" title="Real number">real numbers</a>. (In particular, graded posets are <a href="/wiki/Well-founded" class="mw-redirect" title="Well-founded">well-founded</a>, meaning that they satisfy the <a href="/wiki/Descending_chain_condition" class="mw-redirect" title="Descending chain condition">descending chain condition</a> (DCC): they do not contain any <a href="/wiki/Infinite_descending_chain" class="mw-redirect" title="Infinite descending chain">infinite descending chains</a>.<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>) Henceforth we shall therefore only consider posets in which this does not happen. This implies that whenever <i>x</i> < <i>y</i> we can get from <i>x</i> to <i>y</i> by repeatedly choosing a cover, finitely many times. It also means that (for positive integer rank functions) compatibility of <i>ρ</i> with the ordering follows from the requirement about covers. As a variant of the definition of a graded poset, Birkhoff<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> allows rank functions to have arbitrary (rather than only nonnegative) integer values. In this variant, the integers can be graded (by the identity function) in his setting, and the compatibility of ranks with the ordering is not redundant. As a third variant, Brightwell and West<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> define a rank function to be integer-valued, but don't require its compatibility with the ordering; hence this variant can grade even e.g. the real numbers by any function, as the requirement about covers is <a href="/wiki/Vacuous_truth" title="Vacuous truth">vacuous</a> for this example. </p><p>Note that graded posets need not satisfy the <a href="/wiki/Ascending_chain_condition" title="Ascending chain condition">ascending chain condition</a> (ACC): for instance, the natural numbers contain the infinite ascending chain <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 0<1<2<\dots }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo><</mo> <mn>1</mn> <mo><</mo> <mn>2</mn> <mo><</mo> <mo>…</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0<1<2<\dots }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/358551482e36e5e8de642b750d3c9f9f53f8fe72" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.506ex; height:2.176ex;" alt="{\displaystyle 0<1<2<\dots }"></span>. </p><p>A poset is graded if and only if every connected component of its <a href="/wiki/Comparability_graph" title="Comparability graph">comparability graph</a> is graded, so further characterizations will suppose this comparability graph to be connected. On each connected component the rank function is only unique up to a uniform shift (so the rank function can always be chosen so that the elements of minimal rank in their connected component have rank 0). </p><p>If <i>P</i> has a <a href="/wiki/Least_element" class="mw-redirect" title="Least element">least element</a> Ô then being graded is equivalent to the condition that for any element <i>x</i> all <a href="/wiki/Glossary_of_order_theory#M" title="Glossary of order theory">maximal chains</a> in the <a href="/wiki/Partially_ordered_set#Intervals" title="Partially ordered set">interval</a> [Ô, <i>x</i>] have the same length. This condition is necessary since every step in a maximal chain is a covering relation, which should change the rank by 1. The condition is also sufficient, since when it holds, one can use the mentioned length to define the rank of <i>x</i> (the length of a finite chain is its number of "steps", so one less than its number of elements), and whenever <i>x</i> covers <i>y</i>, adjoining <i>x</i> to a maximal chain in [Ô, <i>y</i>] gives a maximal chain in [Ô, <i>x</i>]. </p><p>If <i>P</i> also has a <a href="/wiki/Greatest_element" class="mw-redirect" title="Greatest element">greatest element</a> Î (so that it is a <a href="/wiki/Bounded_poset" class="mw-redirect" title="Bounded poset">bounded poset</a>), then the previous condition can be simplified to the requirement that all maximal chains in <i>P</i> have the same (finite) length. This suffices, since any pair of maximal chains in [Ô, <i>x</i>] can be extended by a maximal chain in [<i>x</i>, Î] to give a pair of maximal chains in <i>P</i>. </p> <dl><dd><i>Note</i> <a href="/wiki/Richard_P._Stanley" title="Richard P. Stanley">Stanley</a> defines a poset to be <b>graded of length</b> <i>n</i> if all its maximal chains have length <i>n</i> (Stanley 1997, p.99). This definition is given in a context where interest is mostly in finite posets, and although the book subsequently often drops the part "of length <i>n</i>", it does not seem appropriate to use this as definition of "graded" for general posets, because (1) it says nothing about posets whose maximal chains are infinite, in particular (2) it excludes important posets like <a href="/wiki/Young%27s_lattice" title="Young's lattice">Young's lattice</a>. Also it is not clear why in a graded poset all minimal elements, as well as all maximal elements, should be required to have the same length, even if Stanley gives examples making clear that he does mean to require that (ibid, pp.216 and 219).</dd></dl> <div class="mw-heading mw-heading2"><h2 id="The_usual_case">The usual case</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Graded_poset&action=edit&section=3" title="Edit section: The usual case"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Many authors in <a href="/wiki/Combinatorics" title="Combinatorics">combinatorics</a> define graded posets in such a way that all <a href="/wiki/Minimal_element" class="mw-redirect" title="Minimal element">minimal elements</a> of <i>P</i> must have rank 0, and moreover that there is a maximal rank <i>r</i> that is the rank of any maximal element. Then being graded means that all maximal chains have length <i>r</i>, as is indicated above. In this case one says that <i>P</i> has rank <i>r</i>. </p><p>Furthermore, in this case, to the <b>rank levels</b> are associated the <b>rank numbers</b> or <b>Whitney numbers</b> <b><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_{0},W_{1},W_{2},...}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{0},W_{1},W_{2},...}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b1ed077c0b922954eedf66792abfba211bda18c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.56ex; height:2.509ex;" alt="{\displaystyle W_{0},W_{1},W_{2},...}"></span></b>. These numbers are defined by <b><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_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7301a4cfd04d4f5db4549fdf23746a0d2ce9f387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}"></span> = number of elements of <i>P</i> having rank <i>i</i> </b>. </p><p>The <b>Whitney numbers</b> are connected with a lot of important combinatorial <a href="/wiki/Theorem" title="Theorem">theorems</a>. The classic example is <a href="/wiki/Sperner%27s_theorem" title="Sperner's theorem">Sperner's theorem</a>, which can be formulated as follows: </p> <style data-mw-deduplicate="TemplateStyles:r1244412712">.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}</style><blockquote class="templatequote"><p>For the <a href="/wiki/Power_set" title="Power set">power set</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}(S)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}(S)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3b51bfe21fd15a7b5531fd9635a87a3863be6025" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle {\mathcal {P}}(S)}"></span> of every <a href="/wiki/Finite_set" title="Finite set">finite set</a> <b><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span></b> the maximum <a href="/wiki/Cardinality" title="Cardinality">cardinality</a> of a <a href="/wiki/Sperner_family" title="Sperner family">Sperner family</a> equals the <a href="/wiki/Maximum" class="mw-redirect" title="Maximum">maximum</a> <b>Whitney number</b>.</p></blockquote> <p>This means: </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1244412712"><blockquote class="templatequote"><p>Every finite power set has the <a href="/wiki/Sperner_property_of_a_partially_ordered_set" title="Sperner property of a partially ordered set">Sperner property</a></p></blockquote> <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=Graded_poset&action=edit&section=4" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Graded_(mathematics)" class="mw-redirect" title="Graded (mathematics)">Graded (mathematics)</a></li> <li><a href="/wiki/Prewellordering" title="Prewellordering">Prewellordering</a> – a prewellordering with a norm is analogous to a graded poset, replacing a map to the integers with a map to the ordinals</li> <li><a href="/wiki/Star_product" title="Star product">Star product</a>, a method for combining two graded posets</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=Graded_poset&action=edit&section=5" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-stanley-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-stanley_1-0">^</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="CITEREFStanley1984" class="citation cs2"><a href="/wiki/Richard_P._Stanley" title="Richard P. Stanley">Stanley, Richard</a> (1984), "Quotients of Peck posets", <i><a href="/wiki/Order_(journal)" title="Order (journal)">Order</a></i>, <b>1</b> (1): 29–34, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00396271">10.1007/BF00396271</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0745587">0745587</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:14857863">14857863</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Order&rft.atitle=Quotients+of+Peck+posets&rft.volume=1&rft.issue=1&rft.pages=29-34&rft.date=1984&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0745587%23id-name%3DMR&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A14857863%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2FBF00396271&rft.aulast=Stanley&rft.aufirst=Richard&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" 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="CITEREFButler1994" class="citation cs2"><a href="/wiki/Lynne_Butler" title="Lynne Butler">Butler, Lynne M.</a> (1994), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=IrK3c3ypPFgC&pg=PA151"><i>Subgroup Lattices and Symmetric Functions</i></a>, Memoirs of the American Mathematical Society, vol. 539, American Mathematical Society, p. 151, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780821826003" title="Special:BookSources/9780821826003"><bdi>9780821826003</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Subgroup+Lattices+and+Symmetric+Functions&rft.series=Memoirs+of+the+American+Mathematical+Society&rft.pages=151&rft.pub=American+Mathematical+Society&rft.date=1994&rft.isbn=9780821826003&rft.aulast=Butler&rft.aufirst=Lynne+M.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DIrK3c3ypPFgC%26pg%3DPA151&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" class="Z3988"></span>.</span> </li> <li id="cite_note-culberson-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-culberson_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCulbersonRawlins1990" class="citation cs2">Culberson, Joseph C.; Rawlins, Gregory J. E. (1990), <a rel="nofollow" class="external text" href="https://link.springer.com/article/10.1007/BF00383201">"New results from an algorithm for counting posets"</a>, <i>Order</i>, <b>7</b> (4): 361–374, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00383201">10.1007/BF00383201</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:120473635">120473635</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Order&rft.atitle=New+results+from+an+algorithm+for+counting+posets&rft.volume=7&rft.issue=4&rft.pages=361-374&rft.date=1990&rft_id=info%3Adoi%2F10.1007%2FBF00383201&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A120473635%23id-name%3DS2CID&rft.aulast=Culberson&rft.aufirst=Joseph+C.&rft.au=Rawlins%2C+Gregory+J.+E.&rft_id=https%3A%2F%2Flink.springer.com%2Farticle%2F10.1007%2FBF00383201&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" 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">Meaning it has a <a href="/wiki/Least_element" class="mw-redirect" title="Least element">least element</a> and <a href="/wiki/Greatest_element" class="mw-redirect" title="Greatest element">greatest element</a>.</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">I.e., one does not have a situation like <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<z_{1}<y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo><</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo><</mo> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x<z_{1}<y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7694ae463308a8c1707e547d378116502c0d5d1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.818ex; height:2.176ex;" alt="{\displaystyle x<z_{1}<y}"></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 x<w_{1}<w_{2}<y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo><</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo><</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo><</mo> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x<w_{1}<w_{2}<y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc2c2ba4d853997958cbedbe2de968adf57a8510" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.217ex; height:2.176ex;" alt="{\displaystyle x<w_{1}<w_{2}<y}"></span> both being maximal chains.</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">Not containing arbitrarily long descending chains starting at a fixed element of course excludes any infinite descending chains. The former condition is strictly stronger though; the set <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 \mathbb {N} \cup \{\infty \}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> <mo>∪</mo> <mo fence="false" stretchy="false">{</mo> <mi mathvariant="normal">∞</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {N} \cup \{\infty \}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/993fe4a59e08e3c356fef9576ab29e0a499173be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.909ex; height:2.843ex;" alt="{\displaystyle \mathbb {N} \cup \{\infty \}}"></span> has arbitrarily long chains descending from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \infty }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">∞</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \infty }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c26c105004f30c27aa7c2a9c601550a4183b1f21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }"></span>, but has no infinite descending chains.</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">'Lattice Theory', Am. Math. Soc., Colloquium Publications, Vol.25, 1967, p.5</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">See reference [2], p.722.</span> </li> </ol></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=Graded_poset&action=edit&section=6" 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="CITEREFStanley1997" class="citation book cs1"><a href="/wiki/Richard_P._Stanley" title="Richard P. Stanley">Stanley, Richard</a> (1997). <i>Enumerative Combinatorics (vol.1, Cambridge Studies in Advanced Mathematics 49)</i>. <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-66351-2" title="Special:BookSources/0-521-66351-2"><bdi>0-521-66351-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Enumerative+Combinatorics+%28vol.1%2C+Cambridge+Studies+in+Advanced+Mathematics+49%29&rft.pub=Cambridge+University+Press&rft.date=1997&rft.isbn=0-521-66351-2&rft.aulast=Stanley&rft.aufirst=Richard&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAnderson1987" class="citation book cs1">Anderson, Ian (1987). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/combinatoricsoff0000ande"><i>Combinatorics of Finite Sets</i></a></span>. Oxford, UK: <a href="/wiki/Clarendon_Press" class="mw-redirect" title="Clarendon Press">Clarendon Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-19-853367-5" title="Special:BookSources/0-19-853367-5"><bdi>0-19-853367-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Combinatorics+of+Finite+Sets&rft.place=Oxford%2C+UK&rft.pub=Clarendon+Press&rft.date=1987&rft.isbn=0-19-853367-5&rft.aulast=Anderson&rft.aufirst=Ian&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcombinatoricsoff0000ande&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEngel1997" class="citation book cs1">Engel, Konrad (1997). <i>Sperner Theory</i>. Cambridge, UK (et al.): Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-45206-6" title="Special:BookSources/0-521-45206-6"><bdi>0-521-45206-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Sperner+Theory&rft.place=Cambridge%2C+UK+%28et+al.%29&rft.pub=Cambridge+University+Press&rft.date=1997&rft.isbn=0-521-45206-6&rft.aulast=Engel&rft.aufirst=Konrad&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKungRotaYan2009" class="citation book cs1">Kung, Joseph P. S.; <a href="/wiki/Gian-Carlo_Rota" title="Gian-Carlo Rota">Rota, Gian-Carlo</a>; <a href="/wiki/Catherine_Yan" title="Catherine Yan">Yan, Catherine H.</a> (2009). <a href="/wiki/Combinatorics:_The_Rota_Way" title="Combinatorics: The Rota Way"><i>Combinatorics: The Rota Way</i></a>. Cambridge, UK (et al.): Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-73794-4" title="Special:BookSources/978-0-521-73794-4"><bdi>978-0-521-73794-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=Combinatorics%3A+The+Rota+Way&rft.place=Cambridge%2C+UK+%28et+al.%29&rft.pub=Cambridge+University+Press&rft.date=2009&rft.isbn=978-0-521-73794-4&rft.aulast=Kung&rft.aufirst=Joseph+P.+S.&rft.au=Rota%2C+Gian-Carlo&rft.au=Yan%2C+Catherine+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGraded+poset" class="Z3988"></span></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Order_theory" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Order_theory" title="Template:Order theory"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Order_theory" title="Template talk:Order theory"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Order_theory" title="Special:EditPage/Template:Order theory"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Order_theory" style="font-size:114%;margin:0 4em"><a href="/wiki/Order_theory" title="Order theory">Order theory</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_order_theory_topics" title="List of order theory topics">Topics</a></li> <li><a href="/wiki/Glossary_of_order_theory" title="Glossary of order theory">Glossary</a></li> <li><a href="/wiki/Category:Order_theory" title="Category:Order theory">Category</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_relation" title="Binary relation">Binary relation</a></li> <li><a href="/wiki/Boolean_algebra_(structure)" title="Boolean algebra (structure)">Boolean algebra</a></li> <li><a href="/wiki/Cyclic_order" title="Cyclic order">Cyclic order</a></li> <li><a href="/wiki/Lattice_(order)" title="Lattice (order)">Lattice</a></li> <li><a href="/wiki/Partially_ordered_set" title="Partially ordered set">Partial order</a></li> <li><a href="/wiki/Preorder" title="Preorder">Preorder</a></li> <li><a href="/wiki/Total_order" title="Total order">Total order</a></li> <li><a href="/wiki/Weak_ordering" title="Weak ordering">Weak ordering</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Results</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Boolean_prime_ideal_theorem" title="Boolean prime ideal theorem">Boolean prime ideal theorem</a></li> <li><a href="/wiki/Cantor%E2%80%93Bernstein_theorem" title="Cantor–Bernstein theorem">Cantor–Bernstein theorem</a></li> <li><a href="/wiki/Cantor%27s_isomorphism_theorem" title="Cantor's isomorphism theorem">Cantor's isomorphism theorem</a></li> <li><a href="/wiki/Dilworth%27s_theorem" title="Dilworth's theorem">Dilworth's theorem</a></li> <li><a href="/wiki/Dushnik%E2%80%93Miller_theorem" title="Dushnik–Miller theorem">Dushnik–Miller theorem</a></li> <li><a href="/wiki/Hausdorff_maximal_principle" title="Hausdorff maximal principle">Hausdorff maximal principle</a></li> <li><a href="/wiki/Knaster%E2%80%93Tarski_theorem" title="Knaster–Tarski theorem">Knaster–Tarski theorem</a></li> <li><a href="/wiki/Kruskal%27s_tree_theorem" title="Kruskal's tree theorem">Kruskal's tree theorem</a></li> <li><a href="/wiki/Laver%27s_theorem" title="Laver's theorem">Laver's theorem</a></li> <li><a href="/wiki/Mirsky%27s_theorem" title="Mirsky's theorem">Mirsky's theorem</a></li> <li><a href="/wiki/Szpilrajn_extension_theorem" title="Szpilrajn extension theorem">Szpilrajn extension theorem</a></li> <li><a href="/wiki/Zorn%27s_lemma" title="Zorn's lemma">Zorn's lemma</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Properties & Types (<small><a href="/wiki/List_of_order_structures_in_mathematics" title="List of order structures in mathematics">list</a></small>)</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Antisymmetric_relation" title="Antisymmetric relation">Antisymmetric</a></li> <li><a href="/wiki/Asymmetric_relation" title="Asymmetric relation">Asymmetric</a></li> <li><a href="/wiki/Boolean_algebra_(structure)" title="Boolean algebra (structure)">Boolean algebra</a> <ul><li><a href="/wiki/List_of_Boolean_algebra_topics" title="List of Boolean algebra topics">topics</a></li></ul></li> <li><a href="/wiki/Completeness_(order_theory)" title="Completeness (order theory)">Completeness</a></li> <li><a href="/wiki/Connected_relation" title="Connected relation">Connected</a></li> <li><a href="/wiki/Covering_relation" title="Covering relation">Covering</a></li> <li><a href="/wiki/Dense_order" title="Dense order">Dense</a></li> <li><a href="/wiki/Directed_set" title="Directed set">Directed</a></li> <li>(<a href="/wiki/Partial_equivalence_relation" title="Partial equivalence relation">Partial</a>) <a href="/wiki/Equivalence_relation" title="Equivalence relation">Equivalence</a></li> <li><a href="/wiki/Foundational_relation" class="mw-redirect" title="Foundational relation">Foundational</a></li> <li><a href="/wiki/Heyting_algebra" title="Heyting algebra">Heyting algebra</a></li> <li><a href="/wiki/Homogeneous_relation" title="Homogeneous relation">Homogeneous</a></li> <li><a href="/wiki/Idempotent_relation" title="Idempotent relation">Idempotent</a></li> <li><a href="/wiki/Lattice_(order)" title="Lattice (order)">Lattice</a> <ul><li><a href="/wiki/Bounded_lattice" class="mw-redirect" title="Bounded lattice">Bounded</a></li> <li><a href="/wiki/Complemented_lattice" title="Complemented lattice">Complemented</a></li> <li><a href="/wiki/Complete_lattice" title="Complete lattice">Complete</a></li> <li><a href="/wiki/Distributive_lattice" title="Distributive lattice">Distributive</a></li> <li><a href="/wiki/Join_and_meet" title="Join and meet">Join and meet</a></li></ul></li> <li><a href="/wiki/Reflexive_relation" title="Reflexive relation">Reflexive</a></li> <li><a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">Partial order</a> <ul><li><a href="/wiki/Chain-complete_partial_order" class="mw-redirect" title="Chain-complete partial order">Chain-complete</a></li> <li><a class="mw-selflink selflink">Graded</a></li> <li><a href="/wiki/Eulerian_poset" title="Eulerian poset">Eulerian</a></li> <li><a href="/wiki/Strict_partial_order" class="mw-redirect" title="Strict partial order">Strict</a></li></ul></li> <li><a href="/wiki/Prefix_order" title="Prefix order">Prefix order</a></li> <li><a href="/wiki/Preorder" title="Preorder">Preorder</a> <ul><li><a href="/wiki/Total_preorder" class="mw-redirect" title="Total preorder">Total</a></li></ul></li> <li><a href="/wiki/Semilattice" title="Semilattice">Semilattice</a></li> <li><a href="/wiki/Semiorder" title="Semiorder">Semiorder</a></li> <li><a href="/wiki/Symmetric_relation" title="Symmetric relation">Symmetric</a></li> <li><a href="/wiki/Total_relation" title="Total relation">Total</a></li> <li><a href="/wiki/Tolerance_relation" title="Tolerance relation">Tolerance</a></li> <li><a href="/wiki/Transitive_relation" title="Transitive relation">Transitive</a></li> <li><a href="/wiki/Well-founded_relation" title="Well-founded relation">Well-founded</a></li> <li><a href="/wiki/Well-quasi-ordering" title="Well-quasi-ordering">Well-quasi-ordering</a> (<a href="/wiki/Better-quasi-ordering" title="Better-quasi-ordering">Better</a>)</li> <li>(<a href="/wiki/Prewellordering" title="Prewellordering">Pre</a>) <a href="/wiki/Well-order" title="Well-order">Well-order</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Constructions</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Composition_of_relations" title="Composition of relations">Composition</a></li> <li><a href="/wiki/Converse_relation" title="Converse relation">Converse/Transpose</a></li> <li><a href="/wiki/Lexicographic_order" title="Lexicographic order">Lexicographic order</a></li> <li><a href="/wiki/Linear_extension" title="Linear extension">Linear extension</a></li> <li><a href="/wiki/Product_order" title="Product order">Product order</a></li> <li><a href="/wiki/Reflexive_closure" title="Reflexive closure">Reflexive closure</a></li> <li><a href="/wiki/Series-parallel_partial_order" title="Series-parallel partial order">Series-parallel partial order</a></li> <li><a href="/wiki/Star_product" title="Star product">Star product</a></li> <li><a href="/wiki/Symmetric_closure" title="Symmetric closure">Symmetric closure</a></li> <li><a href="/wiki/Transitive_closure" title="Transitive closure">Transitive closure</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Topology" title="Topology">Topology</a> & Orders</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alexandrov_topology" title="Alexandrov topology">Alexandrov topology</a> & <a href="/wiki/Specialization_(pre)order" title="Specialization (pre)order">Specialization preorder</a></li> <li><a href="/wiki/Ordered_topological_vector_space" title="Ordered topological vector space">Ordered topological vector space</a> <ul><li><a href="/wiki/Normal_cone_(functional_analysis)" title="Normal cone (functional analysis)">Normal cone</a></li> <li><a href="/wiki/Order_topology_(functional_analysis)" title="Order topology (functional analysis)">Order topology</a></li></ul></li> <li><a href="/wiki/Order_topology" title="Order topology">Order topology</a></li> <li><a href="/wiki/Topological_vector_lattice" title="Topological vector lattice">Topological vector lattice</a> <ul><li><a href="/wiki/Banach_lattice" title="Banach lattice">Banach</a></li> <li><a href="/wiki/Fr%C3%A9chet_lattice" title="Fréchet lattice">Fréchet</a></li> <li><a href="/wiki/Locally_convex_vector_lattice" title="Locally convex vector lattice">Locally convex</a></li> <li><a href="/wiki/Normed_lattice" class="mw-redirect" title="Normed lattice">Normed</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Antichain" title="Antichain">Antichain</a></li> <li><a href="/wiki/Cofinal_(mathematics)" title="Cofinal (mathematics)">Cofinal</a></li> <li><a href="/wiki/Cofinality" title="Cofinality">Cofinality</a></li> <li><a href="/wiki/Comparability" title="Comparability">Comparability</a> <ul><li><a href="/wiki/Comparability_graph" title="Comparability graph">Graph</a></li></ul></li> <li><a href="/wiki/Duality_(order_theory)" title="Duality (order theory)">Duality</a></li> <li><a href="/wiki/Filter_(mathematics)" title="Filter (mathematics)">Filter</a></li> <li><a href="/wiki/Hasse_diagram" title="Hasse diagram">Hasse diagram</a></li> <li><a href="/wiki/Ideal_(order_theory)" title="Ideal (order theory)">Ideal</a></li> <li><a href="/wiki/Net_(mathematics)" title="Net (mathematics)">Net</a> <ul><li><a href="/wiki/Subnet_(mathematics)" title="Subnet (mathematics)">Subnet</a></li></ul></li> <li><a href="/wiki/Monotonic_function" title="Monotonic function">Order morphism</a> <ul><li><a href="/wiki/Order_embedding" title="Order embedding">Embedding</a></li> <li><a href="/wiki/Order_isomorphism" title="Order isomorphism">Isomorphism</a></li></ul></li> <li><a href="/wiki/Order_type" title="Order type">Order type</a></li> <li><a href="/wiki/Ordered_field" title="Ordered field">Ordered field</a> <ul><li><a href="/wiki/Positive_cone_of_an_ordered_field" class="mw-redirect" title="Positive cone of an ordered field">Positive cone of an ordered field</a></li></ul></li> <li><a href="/wiki/Ordered_vector_space" title="Ordered vector space">Ordered vector space</a> <ul><li><a href="/wiki/Partially_ordered_space" title="Partially ordered space">Partially ordered</a></li> <li><a href="/wiki/Positive_cone_of_an_ordered_vector_space" class="mw-redirect" title="Positive cone of an ordered vector space">Positive cone of an ordered vector space</a></li> <li><a href="/wiki/Riesz_space" title="Riesz space">Riesz space</a></li></ul></li> <li><a href="/wiki/Partially_ordered_group" title="Partially ordered group">Partially ordered group</a> <ul><li><a href="/wiki/Positive_cone_of_a_partially_ordered_group" class="mw-redirect" title="Positive cone of a partially ordered group">Positive cone of a partially ordered group</a></li></ul></li> <li><a href="/wiki/Upper_set" title="Upper set">Upper set</a></li> <li><a href="/wiki/Young%27s_lattice" title="Young's lattice">Young's lattice</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Graded_poset&oldid=1255978421">https://en.wikipedia.org/w/index.php?title=Graded_poset&oldid=1255978421</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:Algebraic_combinatorics" title="Category:Algebraic combinatorics">Algebraic combinatorics</a></li><li><a href="/wiki/Category:Order_theory" title="Category:Order theory">Order theory</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 7 November 2024, at 16:00<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=Graded_poset&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-57488d5c7d-9znl9","wgBackendResponseTime":146,"wgPageParseReport":{"limitreport":{"cputime":"0.301","walltime":"0.458","ppvisitednodes":{"value":712,"limit":1000000},"postexpandincludesize":{"value":30689,"limit":2097152},"templateargumentsize":{"value":486,"limit":2097152},"expansiondepth":{"value":8,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":31324,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 269.059 1 -total"," 39.95% 107.499 1 Template:Order_theory"," 37.42% 100.677 3 Template:Citation"," 37.20% 100.096 1 Template:Navbox"," 12.54% 33.735 2 Template:Quote"," 7.51% 20.219 4 Template:Cite_book"," 1.04% 2.799 2 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.181","limit":"10.000"},"limitreport-memusage":{"value":3672649,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-7587f976f-tqtnt","timestamp":"20241107160019","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Graded poset","url":"https:\/\/en.wikipedia.org\/wiki\/Graded_poset","sameAs":"http:\/\/www.wikidata.org\/entity\/Q5591878","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q5591878","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":"2005-08-22T20:56:28Z","dateModified":"2024-11-07T16:00:16Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/e\/ea\/Hasse_diagram_of_powerset_of_3.svg","headline":"partially ordered set equipped with a rank function"}</script> </body> </html>