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>Composition of relations - 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":"f5ec8e3d-ec5f-4f4e-b698-2f6b8e5d7db0","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Composition_of_relations","wgTitle":"Composition of relations","wgCurRevisionId":1251719997,"wgRevisionId":1251719997,"wgArticleId":7472170,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Webarchive template wayback links","Articles with short description","Short description matches Wikidata","Wikipedia articles needing clarification from January 2022","Algebraic logic","Binary operations","Mathematical relations"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Composition_of_relations","wgRelevantArticleId":7472170,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true, "wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q2795123","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","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","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 name="viewport" content="width=1120"> <meta property="og:title" content="Composition of relations - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Composition_of_relations"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Composition_of_relations&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/Composition_of_relations"> <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-Composition_of_relations rootpage-Composition_of_relations 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=Composition+of+relations" 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=Composition+of+relations" 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=Composition+of+relations" 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=Composition+of+relations" 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-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <button aria-controls="toc-Definition-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Definition subsection</span> </button> <ul id="toc-Definition-sublist" class="vector-toc-list"> <li id="toc-Notational_variations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Notational_variations"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Notational variations</span> </div> </a> <ul id="toc-Notational_variations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Mathematical_generalizations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Mathematical_generalizations"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Mathematical generalizations</span> </div> </a> <ul id="toc-Mathematical_generalizations-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Properties</span> </div> </a> <ul id="toc-Properties-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Composition_in_terms_of_matrices" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Composition_in_terms_of_matrices"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Composition in terms of matrices</span> </div> </a> <ul id="toc-Composition_in_terms_of_matrices-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Heterogeneous_relations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Heterogeneous_relations"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Heterogeneous relations</span> </div> </a> <button aria-controls="toc-Heterogeneous_relations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Heterogeneous relations subsection</span> </button> <ul id="toc-Heterogeneous_relations-sublist" class="vector-toc-list"> <li id="toc-Example" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Example</span> </div> </a> <ul id="toc-Example-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Schröder_rules" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Schröder_rules"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Schröder rules</span> </div> </a> <ul id="toc-Schröder_rules-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Quotients" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Quotients"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Quotients</span> </div> </a> <ul id="toc-Quotients-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Join:_another_form_of_composition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Join:_another_form_of_composition"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Join: another form of composition</span> </div> </a> <ul id="toc-Join:_another_form_of_composition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-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">9</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">10</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">Composition of relations</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 6 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-6" 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">6 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Skl%C3%A1d%C3%A1n%C3%AD_zobrazen%C3%AD" title="Skládání zobrazení – Czech" lang="cs" hreflang="cs" data-title="Skládání zobrazení" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A3%CF%8D%CE%BD%CE%B8%CE%B5%CF%83%CE%B7_%CF%83%CF%87%CE%AD%CF%83%CE%B5%CF%89%CE%BD" title="Σύνθεση σχέσεων – Greek" lang="el" hreflang="el" data-title="Σύνθεση σχέσεων" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%B1%DA%A9%DB%8C%D8%A8_%D8%B1%D9%88%D8%A7%D8%A8%D8%B7" title="ترکیب روابط – Persian" lang="fa" hreflang="fa" data-title="ترکیب روابط" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Samengestelde_relatie" title="Samengestelde relatie – Dutch" lang="nl" hreflang="nl" data-title="Samengestelde relatie" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E9%96%A2%E4%BF%82%E3%81%AE%E5%90%88%E6%88%90" title="関係の合成 – Japanese" lang="ja" hreflang="ja" data-title="関係の合成" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCenie_relacji" title="Złożenie relacji – Polish" lang="pl" hreflang="pl" data-title="Złożenie relacji" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</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/Q2795123#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/Composition_of_relations" 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:Composition_of_relations" 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/Composition_of_relations"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Composition_of_relations&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=Composition_of_relations&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/Composition_of_relations"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Composition_of_relations&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=Composition_of_relations&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/Composition_of_relations" 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/Composition_of_relations" 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=Composition_of_relations&oldid=1251719997" 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=Composition_of_relations&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=Composition_of_relations&id=1251719997&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%2FComposition_of_relations"><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%2FComposition_of_relations"><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=Composition_of_relations&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=Composition_of_relations&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/Q2795123" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Mathematical operation</div> <p>In the <a href="/wiki/Mathematics" title="Mathematics">mathematics</a> of <a href="/wiki/Binary_relation" title="Binary relation">binary relations</a>, the <b>composition of relations</b> is the forming of a new binary relation <span class="nowrap"><i>R</i> ; <i>S</i></span> from two given binary relations <i>R</i> and <i>S</i>. In the <a href="/wiki/Calculus_of_relations" class="mw-redirect" title="Calculus of relations">calculus of relations</a>, the composition of relations is called <b>relative multiplication</b>,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and its result is called a <b>relative product</b>.<sup id="cite_ref-GS11_2-0" class="reference"><a href="#cite_note-GS11-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 40">: 40 </span></sup> <a href="/wiki/Function_composition" title="Function composition">Function composition</a> is the special case of composition of relations where all relations involved are <a href="/wiki/Function_(mathematics)" title="Function (mathematics)">functions</a>. </p><p>The word <a href="/wiki/Uncle" title="Uncle">uncle</a> indicates a compound relation: for a person to be an uncle, he must be the brother of a parent. In <a href="/wiki/Algebraic_logic" title="Algebraic logic">algebraic logic</a> it is said that the relation of Uncle (<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 xUz}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mi>U</mi> <mi>z</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle xUz}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/11fbe4a96ffb2effd6f5dd3c38bcb1046ed565b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.2ex; height:2.176ex;" alt="{\displaystyle xUz}"></span>) is the composition of relations "is a brother of" (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xBy}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mi>B</mi> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle xBy}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/356ce90213f8079cc6df93c09668fe343e2628fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.249ex; height:2.509ex;" alt="{\displaystyle xBy}"></span>) and "is a parent of" (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle yPz}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mi>P</mi> <mi>z</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle yPz}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10f073ca990cba0d4b7fa2790b81eac3b5de21ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.989ex; height:2.509ex;" alt="{\displaystyle yPz}"></span>). <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xUz{\text{ if and only if }}\exists y\ xByPz.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo>=</mo> <mi>B</mi> <mi>P</mi> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext> is equivalent to: </mtext> </mrow> <mspace width="1em" /> <mi>x</mi> <mi>U</mi> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> if and only if </mtext> </mrow> <mi mathvariant="normal">∃</mi> <mi>y</mi> <mtext> </mtext> <mi>x</mi> <mi>B</mi> <mi>y</mi> <mi>P</mi> <mi>z</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xUz{\text{ if and only if }}\exists y\ xByPz.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f05ca8e7d504fb0169eef13e46d4e2ab405a5d04" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:58.757ex; height:2.509ex;" alt="{\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xUz{\text{ if and only if }}\exists y\ xByPz.}"></span> </p><p>Beginning with <a href="/wiki/Augustus_De_Morgan" title="Augustus De Morgan">Augustus De Morgan</a>,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> the traditional form of reasoning by <a href="/wiki/Syllogism" title="Syllogism">syllogism</a> has been subsumed by relational logical expressions and their composition.<sup id="cite_ref-DDM_4-0" class="reference"><a href="#cite_note-DDM-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\subseteq X\times Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>⊆</mo> <mi>X</mi> <mo>×</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\subseteq X\times Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6359bb38c371b192e5c531ca4a75485091c4cf15" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.456ex; height:2.343ex;" alt="{\displaystyle R\subseteq X\times 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 S\subseteq Y\times Z}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>⊆</mo> <mi>Y</mi> <mo>×</mo> <mi>Z</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\subseteq Y\times Z}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba44c229d23aa188df8d737b09f777e709ad54" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.892ex; height:2.343ex;" alt="{\displaystyle S\subseteq Y\times Z}"></span> are two binary relations, then their composition <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 R\mathbin {;} S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e3471beea6486bff9bf489168fd3ac792825ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.942ex; height:2.509ex;" alt="{\displaystyle R\mathbin {;} S}"></span> is the relation <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(y,z)\in S\}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>z</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>X</mi> <mo>×</mo> <mi>Z</mi> <mo>:</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext> there exists </mtext> </mrow> <mi>y</mi> <mo>∈</mo> <mi>Y</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> such that </mtext> </mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> and </mtext> </mrow> <mo stretchy="false">(</mo> <mi>y</mi> <mo>,</mo> <mi>z</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>S</mi> <mo fence="false" stretchy="false">}</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(y,z)\in S\}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/61dfc6fb72cb65e6d0f752d1acf50674bae34c3f" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:80.69ex; height:2.843ex;" alt="{\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(y,z)\in S\}.}"></span> </p><p>In other words, <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 R\mathbin {;} S\subseteq X\times Z}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> <mo>⊆</mo> <mi>X</mi> <mo>×</mo> <mi>Z</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} S\subseteq X\times Z}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7cbacb0a70316a1f2bcf690dec47cea4596bb5d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.542ex; height:2.509ex;" alt="{\displaystyle R\mathbin {;} S\subseteq X\times Z}"></span> is defined by the rule that says <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)\in R\mathbin {;} S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>z</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x,z)\in R\mathbin {;} S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ecf770e07b77ab829b16ba8b459e556a2129f0f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.044ex; height:2.843ex;" alt="{\displaystyle (x,z)\in R\mathbin {;} S}"></span> if and only if there is an element <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 y\in Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo>∈</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y\in Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cee1c0ec36a82f33f5e3d7434d5667881b4ec323" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.769ex; height:2.509ex;" alt="{\displaystyle y\in Y}"></span> such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\,R\,y\,S\,z}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mspace width="thinmathspace" /> <mi>R</mi> <mspace width="thinmathspace" /> <mi>y</mi> <mspace width="thinmathspace" /> <mi>S</mi> <mspace width="thinmathspace" /> <mi>z</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\,R\,y\,S\,z}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5af34cb7ca64e5d602d48d3ad8e2978654519f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.385ex; height:2.509ex;" alt="{\displaystyle x\,R\,y\,S\,z}"></span> (that is, <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,y)\in R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x,y)\in R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/564266a1c3efe90b1974df60a445161fdf58f14e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.933ex; height:2.843ex;" alt="{\displaystyle (x,y)\in R}"></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 (y,z)\in S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>y</mi> <mo>,</mo> <mi>z</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (y,z)\in S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19ae8da98cf35d7554db325d41526384d195b984" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.427ex; height:2.843ex;" alt="{\displaystyle (y,z)\in S}"></span>).<sup id="cite_ref-GSTS_5-0" class="reference"><a href="#cite_note-GSTS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 13">: 13 </span></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Notational_variations">Notational variations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=2" title="Edit section: Notational variations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <a href="/wiki/Semicolon" title="Semicolon">semicolon</a> as an <a href="/wiki/Infix_notation" title="Infix notation">infix notation</a> for composition of relations dates back to <a href="/wiki/Ernst_Schroder" class="mw-redirect" title="Ernst Schroder">Ernst Schroder</a>'s textbook of 1895.<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> <a href="/wiki/Gunther_Schmidt" title="Gunther Schmidt">Gunther Schmidt</a> has renewed the use of the semicolon, particularly in <i>Relational Mathematics</i> (2011).<sup id="cite_ref-GS11_2-1" class="reference"><a href="#cite_note-GS11-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 40">: 40 </span></sup><sup id="cite_ref-Taylor1999_7-0" class="reference"><a href="#cite_note-Taylor1999-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> The use of the semicolon <a href="/wiki/Function_composition#Alternative_notations" title="Function composition">coincides</a> with the notation for function composition used (mostly by computer scientists) in <a href="/wiki/Category_theory" title="Category theory">category theory</a>,<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> as well as the notation for dynamic conjunction within linguistic <a href="/wiki/Dynamic_semantics" title="Dynamic semantics">dynamic semantics</a>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p><p>A small circle <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 (R\circ S)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>R</mi> <mo>∘</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (R\circ S)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3a937111f1324ef8340b11e88ed315b402d24a64" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.267ex; height:2.843ex;" alt="{\displaystyle (R\circ S)}"></span> has been used for the infix notation of composition of relations by <a href="/wiki/John_M._Howie" class="mw-redirect" title="John M. Howie">John M. Howie</a> in his books considering <a href="/wiki/Semigroup" title="Semigroup">semigroups</a> of relations.<sup id="cite_ref-How_10-0" class="reference"><a href="#cite_note-How-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> However, the small circle is widely used to represent <a href="/wiki/Composition_of_functions" class="mw-redirect" title="Composition of functions">composition of functions</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 g(f(x))=(g\circ f)(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>g</mi> <mo>∘</mo> <mi>f</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(f(x))=(g\circ f)(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3df5a23b2111fffc1c7e9406305fe224c7eb528d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.979ex; height:2.843ex;" alt="{\displaystyle g(f(x))=(g\circ f)(x)}"></span>, which <i>reverses</i> the text sequence from the operation sequence. The small circle was used in the introductory pages of <i>Graphs and Relations</i><sup id="cite_ref-GSTS_5-1" class="reference"><a href="#cite_note-GSTS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 18">: 18 </span></sup> until it was dropped in favor of juxtaposition (no infix notation). <a href="/wiki/Juxtaposition#Mathematics" title="Juxtaposition">Juxtaposition</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 (RS)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>R</mi> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (RS)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdffda1db2897651d03f8629b3cedcc2c871d884" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.073ex; height:2.843ex;" alt="{\displaystyle (RS)}"></span> is commonly used in algebra to signify multiplication, so too, it can signify relative multiplication. </p><p>Further with the circle notation, subscripts may be used. Some authors<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> prefer to write <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 \circ _{l}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mo>∘</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>l</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \circ _{l}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/756747a209b1b6bb0989cf2abd4424ff1300cac0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.885ex; height:2.009ex;" alt="{\displaystyle \circ _{l}}"></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 \circ _{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mo>∘</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \circ _{r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2654fc19adccef52d8831a666143ffadf43dd1f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.136ex; height:2.009ex;" alt="{\displaystyle \circ _{r}}"></span> explicitly when necessary, depending whether the left or the right relation is the first one applied. A further variation encountered in computer science is the <a href="/wiki/Z_notation" title="Z notation">Z notation</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 \circ }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>∘</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \circ }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/99add39d2b681e2de7ff62422c32704a05c7ec31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.125ex; margin-bottom: -0.297ex; width:1.162ex; height:1.509ex;" alt="{\displaystyle \circ }"></span> is used to denote the traditional (right) composition, while left composition is denoted by a fat semicolon. The unicode symbols are ⨾ and ⨟.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Mathematical_generalizations">Mathematical generalizations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=3" title="Edit section: Mathematical generalizations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Binary relations <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 R\subseteq X\times Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>⊆</mo> <mi>X</mi> <mo>×</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\subseteq X\times Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6359bb38c371b192e5c531ca4a75485091c4cf15" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.456ex; height:2.343ex;" alt="{\displaystyle R\subseteq X\times Y}"></span> are morphisms <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 R:X\to Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>:</mo> <mi>X</mi> <mo stretchy="false">→</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R:X\to Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46ee57c22406f16a29c26fef70496e291f52391d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.069ex; height:2.176ex;" alt="{\displaystyle R:X\to Y}"></span> in the <a href="/wiki/Category_(mathematics)" title="Category (mathematics)">category</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 {\mathsf {Rel}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">R</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">l</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {Rel}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f55f34eddfa4853c62c34afaeff4b6223802a6cd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.09ex; height:2.176ex;" alt="{\displaystyle {\mathsf {Rel}}}"></span>. In <b><a href="/wiki/Category_of_relations" title="Category of relations">Rel</a></b> the objects are <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">sets</a>, the morphisms are binary relations and the composition of morphisms is exactly composition of relations as defined above. The category <b><a href="/wiki/Category_of_sets" title="Category of sets">Set</a></b> of sets and functions is a <a href="/wiki/Subcategory" title="Subcategory">subcategory</a> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {Rel}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">R</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">l</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {Rel}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f55f34eddfa4853c62c34afaeff4b6223802a6cd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.09ex; height:2.176ex;" alt="{\displaystyle {\mathsf {Rel}}}"></span> where the maps <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\to Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo stretchy="false">→</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\to Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/290b16963d52e4a7995aae01ee854b97a6ea10c0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.367ex; height:2.176ex;" alt="{\displaystyle X\to Y}"></span> are functions <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:X\to Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>:</mo> <mi>X</mi> <mo stretchy="false">→</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f:X\to Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/abd1e080abef4bbdab67b43819c6431e7561361c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.583ex; height:2.509ex;" alt="{\displaystyle f:X\to Y}"></span>. </p><p>Given a <a href="/wiki/Regular_category" title="Regular category">regular category</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 \mathbb {X} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">X</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {X} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01c0954f67c8e841542d7ac6a8472c4ea739824b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {X} }"></span>, its category of internal relations <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 {\mathsf {Rel}}(\mathbb {X} )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">R</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">l</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">X</mi> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {Rel}}(\mathbb {X} )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a695bf659ebd3ccfc7d1376026af6156fd28ea75" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.578ex; height:2.843ex;" alt="{\displaystyle {\mathsf {Rel}}(\mathbb {X} )}"></span> has the same objects as <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 {X} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">X</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {X} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01c0954f67c8e841542d7ac6a8472c4ea739824b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {X} }"></span>, but now the morphisms <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\to Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo stretchy="false">→</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\to Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/290b16963d52e4a7995aae01ee854b97a6ea10c0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.367ex; height:2.176ex;" alt="{\displaystyle X\to Y}"></span> are given by subobjects <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 R\subseteq X\times Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>⊆</mo> <mi>X</mi> <mo>×</mo> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\subseteq X\times Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6359bb38c371b192e5c531ca4a75485091c4cf15" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.456ex; height:2.343ex;" alt="{\displaystyle R\subseteq X\times Y}"></span> in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {X} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">X</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {X} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01c0954f67c8e841542d7ac6a8472c4ea739824b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {X} }"></span>.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> Formally, these are <a href="/w/index.php?title=Jointly_monic&action=edit&redlink=1" class="new" title="Jointly monic (page does not exist)">jointly monic</a> <a href="/wiki/Span_(category_theory)" title="Span (category theory)">spans</a> between <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></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 Y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/961d67d6b454b4df2301ac571808a3538b3a6d3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}"></span>. Categories of internal relations are <a href="/wiki/Allegory_(mathematics)" title="Allegory (mathematics)">allegories</a>. In particular <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 {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">R</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">l</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">t</mi> </mrow> </mrow> <mo stretchy="false">)</mo> <mo>≅</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">R</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">l</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b7fa5cb9596903e5ae1016dc92c29b82ce6f567" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.253ex; height:2.843ex;" alt="{\displaystyle {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}"></span>. Given a <a href="/wiki/Field_(mathematics)" title="Field (mathematics)">field</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 k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> (or more generally a <a href="/wiki/Principal_ideal_domain" title="Principal ideal domain">principal ideal domain</a>), the category of relations internal to <a href="/wiki/Matrix_(mathematics)" title="Matrix (mathematics)">matrices</a> over <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 k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span>, <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 {\mathsf {Rel}}({\mathsf {Mat}}(k)),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">R</mi> <mi mathvariant="sans-serif">e</mi> <mi mathvariant="sans-serif">l</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">a</mi> <mi mathvariant="sans-serif">t</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k)),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc9e8c2896eadb765a7719bd7eab3e6c0cf0bba0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.558ex; height:2.843ex;" alt="{\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k)),}"></span> has morphisms <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 n\to m}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo stretchy="false">→</mo> <mi>m</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\to m}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4edd07b8b4d39fdd124a7761a53dfc148557aab2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.049ex; height:1.843ex;" alt="{\displaystyle n\to m}"></span> the <a href="/wiki/Linear_subspace" title="Linear subspace">linear subspaces</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 R\subseteq k^{n}\oplus k^{m}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>⊆</mo> <msup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>⊕</mo> <msup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\subseteq k^{n}\oplus k^{m}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/352783c267250a8a2ef0addbe69d79cc91975cb8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.019ex; height:2.509ex;" alt="{\displaystyle R\subseteq k^{n}\oplus k^{m}}"></span>. The category of linear relations over the <a href="/wiki/Finite_field" title="Finite field">finite field</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 \mathbb {F} _{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">F</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fde97f1e971e76227cd0aac645b7b0901d7b668d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle \mathbb {F} _{2}}"></span> is isomorphic to the phase-free qubit <a href="/wiki/ZX-calculus" title="ZX-calculus">ZX-calculus</a> modulo scalars. </p> <div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=4" title="Edit section: Properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Composition of relations is <a href="/wiki/Associative_property" title="Associative property">associative</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 R\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>T</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>T</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c2087164f742d8f5160e0079186d051fb289bef9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.879ex; height:2.843ex;" alt="{\displaystyle R\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}"></span></li> <li>The <a href="/wiki/Converse_relation" title="Converse relation">converse relation</a> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\mathbin {;} S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e3471beea6486bff9bf489168fd3ac792825ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.942ex; height:2.509ex;" alt="{\displaystyle R\mathbin {;} S}"></span> is <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 (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>=</mo> <msup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49a7a54a249e32fb56bd5db49960fd012b0d7972" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.516ex; height:3.176ex;" alt="{\displaystyle (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}"></span> This property makes the set of all binary relations on a set a <a href="/wiki/Semigroup_with_involution" title="Semigroup with involution">semigroup with involution</a>.</li> <li>The composition of <a href="/wiki/Partial_function" title="Partial function">(partial) functions</a> (that is, functional relations) is again a (partial) function.</li> <li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></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 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> are <a href="/wiki/Injective" class="mw-redirect" title="Injective">injective</a>, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\mathbin {;} S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e3471beea6486bff9bf489168fd3ac792825ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.942ex; height:2.509ex;" alt="{\displaystyle R\mathbin {;} S}"></span> is injective, which conversely implies only the injectivity of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdcae6b33a27f86c7961318cd7ee3d789d3bcdd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.411ex; height:2.176ex;" alt="{\displaystyle R.}"></span></li> <li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></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 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> are <a href="/wiki/Surjective" class="mw-redirect" title="Surjective">surjective</a>, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\mathbin {;} S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\mathbin {;} S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e3471beea6486bff9bf489168fd3ac792825ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.942ex; height:2.509ex;" alt="{\displaystyle R\mathbin {;} S}"></span> is surjective, which conversely implies only the surjectivity of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>.</mo> </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/23bbb1f0f6ebdfa78b4fed06049640f7386bb44b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.146ex; height:2.176ex;" alt="{\displaystyle S.}"></span></li> <li>The set of binary relations on a 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 X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> (that is, relations 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 X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> to <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span>) together with (left or right) relation composition forms a <a href="/wiki/Monoid" title="Monoid">monoid</a> with zero, where the identity map 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 X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> is the <a href="/wiki/Neutral_element" class="mw-redirect" title="Neutral element">neutral element</a>, and the empty set is the <a href="/wiki/Absorbing_element" title="Absorbing element">zero element</a>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Composition_in_terms_of_matrices">Composition in terms of matrices</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=5" title="Edit section: Composition in terms of matrices"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Finite binary relations are represented by <a href="/wiki/Logical_matrix" title="Logical matrix">logical matrices</a>. The entries of these matrices are either zero or one, depending on whether the relation represented is false or true for the row and column corresponding to compared objects. Working with such matrices involves the Boolean arithmetic with <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+1=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1+1=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5120dbef0aa4b1760be59a33516661780dfc7a14" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.426ex; height:2.343ex;" alt="{\displaystyle 1+1=1}"></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 1\times 1=1.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>×</mo> <mn>1</mn> <mo>=</mo> <mn>1.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1\times 1=1.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/16054e88bbde31b761e88231ed88759d60f8b7c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.073ex; height:2.176ex;" alt="{\displaystyle 1\times 1=1.}"></span> An entry in the <a href="/wiki/Matrix_product" class="mw-redirect" title="Matrix product">matrix product</a> of two logical matrices will be 1, then, only if the row and column multiplied have a corresponding 1. Thus the logical matrix of a composition of relations can be found by computing the matrix product of the matrices representing the factors of the composition. "Matrices constitute a method for <i>computing</i> the conclusions traditionally drawn by means of hypothetical syllogisms and <a href="/wiki/Polysyllogism" title="Polysyllogism">sorites</a>."<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Heterogeneous_relations">Heterogeneous relations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=6" title="Edit section: Heterogeneous relations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Consider a heterogeneous relation <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 R\subseteq A\times B;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>⊆</mo> <mi>A</mi> <mo>×</mo> <mi>B</mi> <mo>;</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\subseteq A\times B;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f4a857c730a74820077c6d0d7315af4f53dd66f2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.857ex; height:2.509ex;" alt="{\displaystyle R\subseteq A\times B;}"></span> that is, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></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 B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span> are distinct sets. Then using composition of relation <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> with its <a href="/wiki/Converse_relation" title="Converse relation">converse</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 R^{\textsf {T}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/256a7115a188cc5be9639245f4185afcb2210888" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.762ex; height:3.009ex;" alt="{\displaystyle R^{\textsf {T}},}"></span> there are homogeneous relations <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 RR^{\textsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle RR^{\textsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fd30853fffab7a587651025b62e487378abb8ce9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.88ex; height:2.676ex;" alt="{\displaystyle RR^{\textsf {T}}}"></span> (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 A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></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 R^{\textsf {T}}R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}}R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a361bdfc2aea9d72797dcffe420e2950c8de2e9d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.88ex; height:2.676ex;" alt="{\displaystyle R^{\textsf {T}}R}"></span> (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 B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span>). </p><p>If for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27bcc9b2afb295d4234bc294860cd0c63bcad2ca" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle x\in A}"></span> there exists some <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 y\in B,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo>∈</mo> <mi>B</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y\in B,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d228848d6506f90b6a15c8fd36d092a539ceaa5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.407ex; height:2.509ex;" alt="{\displaystyle y\in B,}"></span> such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xRy}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mi>R</mi> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle xRy}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/324aab4e2674bb19cc073ea887888b98f0fc63d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.249ex; height:2.509ex;" alt="{\displaystyle xRy}"></span> (that is, <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> is a <a href="/wiki/Left-total_relation" class="mw-redirect" title="Left-total relation">(left-)total relation</a>), then for all <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,xRR^{\textsf {T}}x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>,</mo> <mi>x</mi> <mi>R</mi> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x,xRR^{\textsf {T}}x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/21a51c0796a766aa7c6ed39ccc3992dcf9c8d0c6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.902ex; height:3.009ex;" alt="{\displaystyle x,xRR^{\textsf {T}}x}"></span> so that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle RR^{\textsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle RR^{\textsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fd30853fffab7a587651025b62e487378abb8ce9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.88ex; height:2.676ex;" alt="{\displaystyle RR^{\textsf {T}}}"></span> is a <a href="/wiki/Reflexive_relation" title="Reflexive relation">reflexive relation</a> or <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 \mathrm {I} \subseteq RR^{\textsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">I</mi> </mrow> <mo>⊆</mo> <mi>R</mi> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {I} \subseteq RR^{\textsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b2a2885a6fbbce77378b60eef0f7b06ac380111" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.818ex; height:2.843ex;" alt="{\displaystyle \mathrm {I} \subseteq RR^{\textsf {T}}}"></span> where I is the identity relation <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,x):x\in A\}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>:</mo> <mi>x</mi> <mo>∈</mo> <mi>A</mi> <mo fence="false" stretchy="false">}</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{(x,x):x\in A\}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc35df0b4f395b3e119aee5e246959f627be9d24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.325ex; height:2.843ex;" alt="{\displaystyle \{(x,x):x\in A\}.}"></span> Similarly, if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> is a <a href="/wiki/Surjective_relation" class="mw-redirect" title="Surjective relation">surjective relation</a> then <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R^{\textsf {T}}R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> <mo>⊇</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">I</mi> </mrow> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>:</mo> <mi>x</mi> <mo>∈</mo> <mi>B</mi> <mo fence="false" stretchy="false">}</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}}R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4c9202fd006096ce083e571df0e7b41964b5a0f" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.262ex; height:3.176ex;" alt="{\displaystyle R^{\textsf {T}}R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}"></span> In this case <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 R\subseteq RR^{\textsf {T}}R.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo>⊆</mo> <mi>R</mi> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\subseteq RR^{\textsf {T}}R.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a99770e54189cd0f05ef7f70000471e0dfc5d72b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.153ex; height:2.843ex;" alt="{\displaystyle R\subseteq RR^{\textsf {T}}R.}"></span> The opposite inclusion occurs for a <a href="/wiki/Difunctional" class="mw-redirect" title="Difunctional">difunctional</a> relation. </p><p>The composition <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 {\bar {R}}^{\textsf {T}}R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>R</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\bar {R}}^{\textsf {T}}R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9de595c85f97278b093b858dcb588d3a975f308" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.88ex; height:3.009ex;" alt="{\displaystyle {\bar {R}}^{\textsf {T}}R}"></span> is used to distinguish relations of Ferrer's type, which satisfy <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 R{\bar {R}}^{\textsf {T}}R=R.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>R</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> <mo>=</mo> <mi>R</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d8a0365605ace0d43fa131b98d5eb156dd417da8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.153ex; height:3.009ex;" alt="{\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}"></span> </p> <div class="mw-heading mw-heading3"><h3 id="Example">Example</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=7" title="Edit section: Example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>=</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A=}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8af9c8f62b6dd59911491b509a8705bc862c4429" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.196ex; height:2.176ex;" alt="{\displaystyle A=}"></span> { France, Germany, Italy, Switzerland } 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 B=}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo>=</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B=}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3500d05a8f761313103968e3942c4ed235f88135" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.217ex; height:2.176ex;" alt="{\displaystyle B=}"></span> { French, German, Italian } with the relation <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> given by <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 aRb}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mi>R</mi> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle aRb}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c8b0b52168739fd16b254298771ec07b900e5a6e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.991ex; height:2.176ex;" alt="{\displaystyle aRb}"></span> when <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 b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"></span> is a <a href="/wiki/National_language" title="National language">national language</a> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b803da9c45c1186883bde55107e9ccb102c92c6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.877ex; height:1.676ex;" alt="{\displaystyle a.}"></span> Since both <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></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 B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span> is finite, <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> can be represented by a <a href="/wiki/Logical_matrix" title="Logical matrix">logical matrix</a>, assuming rows (top to bottom) and columns (left to right) are ordered alphabetically: <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b257fc9cd03d757c45a85242efc0da1150fccef" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:13.598ex; height:12.509ex;" alt="{\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}"></span> </p><p>The <a href="/wiki/Converse_relation" title="Converse relation">converse relation</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 R^{\textsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34d5ce28bc55f46518e403396cf7451b8d36e483" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.116ex; height:2.676ex;" alt="{\displaystyle R^{\textsf {T}}}"></span> corresponds to the <a href="/wiki/Transposed_matrix" class="mw-redirect" title="Transposed matrix">transposed matrix</a>, and the relation composition <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 R^{\textsf {T}};R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>;</mo> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}};R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b47bacdfb7ee76d859721c192b093a0809d69835" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.913ex; height:3.009ex;" alt="{\displaystyle R^{\textsf {T}};R}"></span> corresponds to the <a href="/wiki/Matrix_product" class="mw-redirect" title="Matrix product">matrix product</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 R^{\textsf {T}}R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}}R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a361bdfc2aea9d72797dcffe420e2950c8de2e9d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.88ex; height:2.676ex;" alt="{\displaystyle R^{\textsf {T}}R}"></span> when summation is implemented by <a href="/wiki/Logical_disjunction" title="Logical disjunction">logical disjunction</a>. It turns out that the <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 3\times 3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>3</mn> <mo>×</mo> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 3\times 3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ddc0d4d6106875f8006be1d898512ca5843bad8e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 3\times 3}"></span> matrix <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 R^{\textsf {T}}R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}}R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a361bdfc2aea9d72797dcffe420e2950c8de2e9d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.88ex; height:2.676ex;" alt="{\displaystyle R^{\textsf {T}}R}"></span> contains a 1 at every position, while the reversed matrix product computes as: <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mn>0</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85cb8a4e1aa1d77ca677b948beaa154e25a22c66" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:25.061ex; height:12.509ex;" alt="{\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}"></span> This matrix is symmetric, and represents a homogeneous relation 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 A.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a71bf21ad35b8fe05555041d54d1e17eeb0f490" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.39ex; height:2.176ex;" alt="{\displaystyle A.}"></span> </p><p>Correspondingly, <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 R^{\textsf {T}}\,;R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mspace width="thinmathspace" /> <mo>;</mo> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R^{\textsf {T}}\,;R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1d61438ee5faffd4df5a9438e59d6a7ebab12ff2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.301ex; height:3.009ex;" alt="{\displaystyle R^{\textsf {T}}\,;R}"></span> is the <a href="/wiki/Universal_relation" class="mw-redirect" title="Universal relation">universal relation</a> 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 B,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/075d661417b8ca5a991a2a7bd4991cc1ab856d9d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.411ex; height:2.509ex;" alt="{\displaystyle B,}"></span> hence any two languages share a nation where they both are spoken (in fact: Switzerland). Vice versa, the question whether two given nations share a language can be answered using <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 R\,;R^{\textsf {T}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mspace width="thinmathspace" /> <mo>;</mo> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R\,;R^{\textsf {T}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b845fc4da633e42e0c34ba62fccc2df6f270f00" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.947ex; height:3.009ex;" alt="{\displaystyle R\,;R^{\textsf {T}}.}"></span> </p> <div class="mw-heading mw-heading2"><h2 id="Schröder_rules"><span id="Schr.C3.B6der_rules"></span>Schröder rules</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=8" title="Edit section: Schröder rules"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For a given 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 V,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ace9595e3ce66fdec7e9d30202626accd676b11e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.434ex; height:2.509ex;" alt="{\displaystyle V,}"></span> the collection of all <a href="/wiki/Binary_relation" title="Binary relation">binary relations</a> 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 V}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}"></span> forms a <a href="/wiki/Boolean_lattice" class="mw-redirect" title="Boolean lattice">Boolean lattice</a> ordered by <a href="/wiki/Inclusion_(set_theory)" class="mw-redirect" title="Inclusion (set theory)">inclusion</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 (\subseteq ).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mo>⊆</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\subseteq ).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d922009a5ebfac7c285f061f7397c0d20b498bd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.264ex; height:2.843ex;" alt="{\displaystyle (\subseteq ).}"></span> Recall that <a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">complementation</a> reverses inclusion: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>⊆</mo> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> implies </mtext> </mrow> <msup> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>∁</mi> </mrow> </msup> <mo>⊆</mo> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>∁</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5dbfb2fe26eeff0baff00af79bea38e24f6e370c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.245ex; height:3.343ex;" alt="{\displaystyle A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.}"></span> In the <a href="/wiki/Calculus_of_relations" class="mw-redirect" title="Calculus of relations">calculus of relations</a><sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> it is common to represent the complement of a set by an overbar: <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 {\bar {A}}=A^{\complement }.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>A</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo>=</mo> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>∁</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\bar {A}}=A^{\complement }.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/095898ce00d7ddd630266bee5903902ef68aff03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.318ex; height:3.009ex;" alt="{\displaystyle {\bar {A}}=A^{\complement }.}"></span> </p><p>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 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> is a binary relation, let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S^{\textsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S^{\textsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9762381246028fdae4ac0c0325258528a784723e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.873ex; height:2.676ex;" alt="{\displaystyle S^{\textsf {T}}}"></span> represent the <a href="/wiki/Converse_relation" title="Converse relation">converse relation</a>, also called the <i>transpose</i>. Then the Schröder rules are <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mi>R</mi> <mo>⊆</mo> <mi>S</mi> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext> is equivalent to </mtext> </mrow> <mspace width="1em" /> <msup> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>S</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>R</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext> is equivalent to </mtext> </mrow> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>S</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>Q</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f8dd6204194ae0b3635e55d8ecd2dac984f7b08a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:70.224ex; height:3.009ex;" alt="{\displaystyle QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}"></span> Verbally, one equivalence can be obtained from another: select the first or second factor and transpose it; then complement the other two relations and permute them.<sup id="cite_ref-GSTS_5-2" class="reference"><a href="#cite_note-GSTS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 15–19">: 15–19 </span></sup> </p><p>Though this transformation of an inclusion of a composition of relations was detailed by <a href="/wiki/Ernst_Schr%C3%B6der_(mathematician)" title="Ernst Schröder (mathematician)">Ernst Schröder</a>, in fact <a href="/wiki/Augustus_De_Morgan" title="Augustus De Morgan">Augustus De Morgan</a> first articulated the transformation as Theorem K in 1860.<sup id="cite_ref-DDM_4-1" class="reference"><a href="#cite_note-DDM-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> He wrote<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mi>M</mi> <mo>⊆</mo> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> implies </mtext> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>N</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>L</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/725d869d597e3978c86174c13750f53adc7cb960" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:28.708ex; height:3.009ex;" alt="{\displaystyle LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}"></span> </p><p>With Schröder rules and complementation one can solve for an unknown relation <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span> in relation inclusions such as <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mi>X</mi> <mo>⊆</mo> <mi>S</mi> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>and</mtext> </mrow> <mspace width="1em" /> <mi>X</mi> <mi>R</mi> <mo>⊆</mo> <mi>S</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/26b6ff4de2cd794afdba77baac34fd154d876516" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:25.723ex; height:2.343ex;" alt="{\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}"></span> For instance, by Schröder rule <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 RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mi>X</mi> <mo>⊆</mo> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> implies </mtext> </mrow> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>S</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>X</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cad20669cf09cd3c1cffb6a5f0789532915c32aa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.034ex; height:3.009ex;" alt="{\displaystyle RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}"></span> and complementation gives <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\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mover> <mrow> <msup> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>S</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> </mrow> <mo accent="false">¯</mo> </mover> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1920f51b019be75ede3a253fc9b9b6d5e0e63f1f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.528ex; height:3.843ex;" alt="{\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}"></span> which is called the <b>left residual of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 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> by <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span></b>. </p> <div class="mw-heading mw-heading2"><h2 id="Quotients">Quotients</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=9" title="Edit section: Quotients"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Just as composition of relations is a type of multiplication resulting in a product, so some <a href="/wiki/Binary_relation#Operations" title="Binary relation">operations</a> compare to division and produce quotients. Three quotients are exhibited here: left residual, right residual, and symmetric quotient. The left residual of two relations is defined presuming that they have the same domain (source), and the right residual presumes the same codomain (range, target). The symmetric quotient presumes two relations share a domain and a codomain. </p><p>Definitions: </p> <ul><li>Left residual: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mi class="MJX-variant" mathvariant="normal">∖</mi> <mi>B</mi> <mrow class="MJX-TeXAtom-REL"> <mo>:=</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mover> <mrow> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>B</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> </mrow> <mo accent="false">¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6108d3611e546056752cf072670adf8313a42846" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.388ex; height:4.009ex;" alt="{\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}"></span></li> <li>Right residual: <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 D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>C</mi> <mrow class="MJX-TeXAtom-REL"> <mo>:=</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mover> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>D</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <msup> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mrow> <mo accent="false">¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/df69c20db149cff6a19523233f66a7acb7fc28c9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.787ex; height:4.009ex;" alt="{\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}"></span></li> <li>Symmetric quotient: <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 \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>syq</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>E</mi> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-REL"> <mo>:=</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mover> <mrow> <msup> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>F</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> </mrow> <mo accent="false">¯</mo> </mover> </mrow> <mo>∩</mo> <mrow class="MJX-TeXAtom-ORD"> <mover> <mrow> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>E</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mi>F</mi> </mrow> <mo accent="false">¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/413c707713dfb2db8f30068d748a11245bba96d8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.267ex; height:4.343ex;" alt="{\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}"></span></li></ul> <p>Using Schröder's rules, <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 AX\subseteq B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mi>X</mi> <mo>⊆</mo> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle AX\subseteq B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c921c4ba485a029f008cf337ed13d7d8153a33db" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.586ex; height:2.343ex;" alt="{\displaystyle AX\subseteq B}"></span> is equivalent to <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\subseteq A\backslash B.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>⊆</mo> <mi>A</mi> <mi class="MJX-variant" mathvariant="normal">∖</mi> <mi>B</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X\subseteq A\backslash B.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b737051a6e7ef7c780d05ddaaf62213c77a20e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.395ex; height:2.843ex;" alt="{\displaystyle X\subseteq A\backslash B.}"></span> Thus the left residual is the greatest relation satisfying <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 AX\subseteq B.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mi>X</mi> <mo>⊆</mo> <mi>B</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle AX\subseteq B.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a5a756d17bd51d8e0b7efb86d2dc8c9ae0664fcd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.232ex; height:2.343ex;" alt="{\displaystyle AX\subseteq B.}"></span> Similarly, the inclusion <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 YC\subseteq D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mi>C</mi> <mo>⊆</mo> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle YC\subseteq D}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92aedfcc88a6fb64d57f9e7fda16ad548dad14b1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.562ex; height:2.343ex;" alt="{\displaystyle YC\subseteq D}"></span> is equivalent to <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 Y\subseteq D/C,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo>⊆</mo> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>C</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y\subseteq D/C,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4d7d214b82b60f59b5556a48f01a02ac708993fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.372ex; height:2.843ex;" alt="{\displaystyle Y\subseteq D/C,}"></span> and the right residual is the greatest relation satisfying <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 YC\subseteq D.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mi>C</mi> <mo>⊆</mo> <mi>D</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle YC\subseteq D.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba1671ca71d94897da367f699bbb2c2872ea9fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.209ex; height:2.343ex;" alt="{\displaystyle YC\subseteq D.}"></span><sup id="cite_ref-GS11_2-2" class="reference"><a href="#cite_note-GS11-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 43–6">: 43–6 </span></sup> </p><p>One can practice the logic of residuals with <a href="/wiki/Sudoku_solving_algorithms#Relations_and_residuals" title="Sudoku solving algorithms">Sudoku</a>.<sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="The text near this tag needs further explanation. (January 2022)">further explanation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading2"><h2 id="Join:_another_form_of_composition">Join: another form of composition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=10" title="Edit section: Join: another form of composition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A fork operator <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 (<)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mo><</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (<)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/268a8484734fef1e0d276b5a54abd49e66083eb2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.617ex; height:2.843ex;" alt="{\displaystyle (<)}"></span> has been introduced to fuse two relations <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 c:H\to A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mo>:</mo> <mi>H</mi> <mo stretchy="false">→</mo> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c:H\to A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/870029aa15966bf16d90f5a00f74456ab98a1ffb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.365ex; height:2.176ex;" alt="{\displaystyle c:H\to A}"></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 d:H\to B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo>:</mo> <mi>H</mi> <mo stretchy="false">→</mo> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d:H\to B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe6d2b5e5749849a366e24a55ccf82f792d0012f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.595ex; height:2.176ex;" alt="{\displaystyle d:H\to B}"></span> into <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 c\,(<)\,d:H\to A\times B.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mspace width="thinmathspace" /> <mo stretchy="false">(</mo> <mo><</mo> <mo stretchy="false">)</mo> <mspace width="thinmathspace" /> <mi>d</mi> <mo>:</mo> <mi>H</mi> <mo stretchy="false">→</mo> <mi>A</mi> <mo>×</mo> <mi>B</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c\,(<)\,d:H\to A\times B.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eef11ddcca67f454e16418c4a8ddaaac7a795bd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.224ex; height:2.843ex;" alt="{\displaystyle c\,(<)\,d:H\to A\times B.}"></span> The construction depends on projections <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a:A\times B\to A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>:</mo> <mi>A</mi> <mo>×</mo> <mi>B</mi> <mo stretchy="false">→</mo> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a:A\times B\to A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb7c04430f82905f7871289a28f5e462141d3499" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.872ex; height:2.176ex;" alt="{\displaystyle a:A\times B\to A}"></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 b:A\times B\to B,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <mo>:</mo> <mi>A</mi> <mo>×</mo> <mi>B</mi> <mo stretchy="false">→</mo> <mi>B</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b:A\times B\to B,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7997efd0a82f57d96801c43b0fe1d349f99cb036" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.307ex; height:2.509ex;" alt="{\displaystyle b:A\times B\to B,}"></span> understood as relations, meaning that there are converse relations <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\textsf {T}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{\textsf {T}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/948597b8dc59ff2ad74936cf7dbd7b1540f467da" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.581ex; height:2.676ex;" alt="{\displaystyle a^{\textsf {T}}}"></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 b^{\textsf {T}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b^{\textsf {T}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/460334ee77fbace8975230ef87daedbf25c4b427" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.996ex; height:2.676ex;" alt="{\displaystyle b^{\textsf {T}}.}"></span> Then the <b><style data-mw-deduplicate="TemplateStyles:r1238216509">.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}</style><span class="vanchor"><span id="fork"></span><span class="vanchor-text">fork</span></span></b> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}"></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 d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> is given by<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,(<)\,d~\mathrel {:=} ~c\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mspace width="thinmathspace" /> <mo stretchy="false">(</mo> <mo><</mo> <mo stretchy="false">)</mo> <mspace width="thinmathspace" /> <mi>d</mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-REL"> <mo>:=</mo> </mrow> <mtext> </mtext> <mi>c</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>∩</mo> <mtext> </mtext> <mi>d</mi> <mrow class="MJX-TeXAtom-BIN"> <mo>;</mo> </mrow> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext mathvariant="sans-serif">T</mtext> </mrow> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c\,(<)\,d~\mathrel {:=} ~c\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8090f2b797ac598cfdc006c06ad7b3706d3f3517" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.842ex; height:3.176ex;" alt="{\displaystyle c\,(<)\,d~\mathrel {:=} ~c\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}"></span> </p><p>Another form of composition of relations, which applies to general <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 n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>-place relations for <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 n\geq 2,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>≥</mo> <mn>2</mn> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\geq 2,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5dc6614bb42ea59d62b121053bd415ee9b6170a7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.302ex; height:2.509ex;" alt="{\displaystyle n\geq 2,}"></span> is the <i><a href="/wiki/Join_(relational_algebra)" class="mw-redirect" title="Join (relational algebra)">join</a></i> operation of <a href="/wiki/Relational_algebra" title="Relational algebra">relational algebra</a>. The usual composition of two binary relations as defined here can be obtained by taking their join, leading to a ternary relation, followed by a projection that removes the middle component. For example, in the <a href="/wiki/Query_language" title="Query language">query language</a> <a href="/wiki/SQL" title="SQL">SQL</a> there is the operation <a href="/wiki/Join_(SQL)" title="Join (SQL)">join (SQL)</a>. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=11" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Demonic_composition" title="Demonic composition">Demonic composition</a></li> <li><a href="/wiki/Friend_of_a_friend" title="Friend of a friend">Friend of a friend</a> – Human contact that exists because of a mutual friend</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=Composition_of_relations&action=edit&section=12" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a href="/wiki/Bjarni_J%C3%B3nsson" title="Bjarni Jónsson">Bjarni Jónsson</a> (1984) "Maximal Algebras of Binary Relations", in <i>Contributions to Group Theory</i>, K.I. Appel editor <a href="/wiki/American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a> <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><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8218-5035-0" title="Special:BookSources/978-0-8218-5035-0">978-0-8218-5035-0</a></span> </li> <li id="cite_note-GS11-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-GS11_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-GS11_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-GS11_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">Gunther Schmidt (2011) <i>Relational Mathematics</i>, Encyclopedia of Mathematics and its Applications, vol. 132, <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-76268-7" title="Special:BookSources/978-0-521-76268-7">978-0-521-76268-7</a></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">A. De Morgan (1860) "On the Syllogism: IV and on the Logic of Relations"</span> </li> <li id="cite_note-DDM-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-DDM_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-DDM_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Daniel D. Merrill (1990) <i>Augustus De Morgan and the Logic of Relations</i>, page 121, <a href="/wiki/Kluwer_Academic" class="mw-redirect" title="Kluwer Academic">Kluwer Academic</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9789400920477" title="Special:BookSources/9789400920477">9789400920477</a></span> </li> <li id="cite_note-GSTS-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-GSTS_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-GSTS_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-GSTS_5-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><a href="/wiki/Gunther_Schmidt" title="Gunther Schmidt">Gunther Schmidt</a> & Thomas Ströhlein (1993) <i>Relations and Graphs</i>, <a href="/wiki/Springer_books" class="mw-redirect" title="Springer books">Springer books</a></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"><a href="/wiki/Ernst_Schroder" class="mw-redirect" title="Ernst Schroder">Ernst Schroder</a> (1895) <a rel="nofollow" class="external text" href="https://gdz.sub.uni-goettingen.de/id/PPN717195317">Algebra und Logik der Relative</a></span> </li> <li id="cite_note-Taylor1999-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-Taylor1999_7-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPaul_Taylor1999" class="citation book cs1">Paul Taylor (1999). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=iSCqyNgzamcC&pg=PA24"><i>Practical Foundations of Mathematics</i></a>. Cambridge University Press. p. 24. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-63107-5" title="Special:BookSources/978-0-521-63107-5"><bdi>978-0-521-63107-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=Practical+Foundations+of+Mathematics&rft.pages=24&rft.pub=Cambridge+University+Press&rft.date=1999&rft.isbn=978-0-521-63107-5&rft.au=Paul+Taylor&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DiSCqyNgzamcC%26pg%3DPA24&rfr_id=info%3Asid%2Fen.wikipedia.org%3AComposition+of+relations" class="Z3988"></span> A free HTML version of the book is available at <a rel="nofollow" class="external free" href="http://www.cs.man.ac.uk/~pt/Practical_Foundations/">http://www.cs.man.ac.uk/~pt/Practical_Foundations/</a></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"><a href="/wiki/Michael_Barr_(mathematician)" title="Michael Barr (mathematician)">Michael Barr</a> & Charles Wells (1998) <a rel="nofollow" class="external text" href="http://www.math.mcgill.ca/triples/Barr-Wells-ctcs.pdf">Category Theory for Computer Scientists</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304031956/http://www.math.mcgill.ca/triples/Barr-Wells-ctcs.pdf">Archived</a> 2016-03-04 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, page 6, from <a href="/wiki/McGill_University" title="McGill University">McGill University</a></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Rick Nouwen and others (2016) <a rel="nofollow" class="external text" href="http://plato.stanford.edu/entries/dynamic-semantics/#EncDynTypLog">Dynamic Semantics</a> §2.2, from <a href="/wiki/Stanford_Encyclopedia_of_Philosophy" title="Stanford Encyclopedia of Philosophy">Stanford Encyclopedia of Philosophy</a></span> </li> <li id="cite_note-How-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-How_10-0">^</a></b></span> <span class="reference-text"><a href="/wiki/John_M._Howie" class="mw-redirect" title="John M. Howie">John M. Howie </a>(1995) <i>Fundamentals of Semigroup Theory</i>, page 16, LMS Monograph #12, <a href="/wiki/Clarendon_Press" class="mw-redirect" title="Clarendon Press">Clarendon Press</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-19-851194-9" title="Special:BookSources/0-19-851194-9">0-19-851194-9</a></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Kilp, Knauer & Mikhalev, p. 7</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">ISO/IEC 13568:2002(E), p. 23</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text">See <a rel="nofollow" class="external text" href="https://www.fileformat.info/info/unicode/char/2a3e/index.htm">U+2A3E</a> and <a rel="nofollow" class="external text" href="https://www.fileformat.info/info/unicode/char/2a1f/index.htm">U+2A1F</a> on FileFormat.info</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://ncatlab.org/nlab/show/internal+relation">"internal relations"</a>. <i>nlab</i><span class="reference-accessdate">. Retrieved <span class="nowrap">26 September</span> 2023</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=nlab&rft.atitle=internal+relations&rft_id=https%3A%2F%2Fncatlab.org%2Fnlab%2Fshow%2Finternal%2Brelation&rfr_id=info%3Asid%2Fen.wikipedia.org%3AComposition+of+relations" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><a href="/wiki/Irving_Copilowish" class="mw-redirect" title="Irving Copilowish">Irving Copilowish</a> (December 1948) "Matrix development of the calculus of relations", <a href="/wiki/Journal_of_Symbolic_Logic" title="Journal of Symbolic Logic">Journal of Symbolic Logic</a> 13(4): 193–203 <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2267134?seq=1#page_scan_tab_contents">Jstor link</a>, quote from page 203</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><a href="/wiki/Vaughn_Pratt" class="mw-redirect" title="Vaughn Pratt">Vaughn Pratt</a> <a rel="nofollow" class="external text" href="http://boole.stanford.edu/pub/ocbr.pdf">The Origins of the Calculus of Relations</a>, from <a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text">De Morgan indicated contraries by lower case, conversion as M<sup>−1</sup>, and inclusion with )), so his notation was <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 nM^{-1}))\ l.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mtext> </mtext> <mi>l</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle nM^{-1}))\ l.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8c8f89924f8063997a88eac07f42dcb876433343" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.956ex; height:3.176ex;" alt="{\displaystyle nM^{-1}))\ l.}"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><a href="/wiki/Gunther_Schmidt" title="Gunther Schmidt">Gunther Schmidt</a> and Michael Winter (2018): <i>Relational Topology</i>, page 26, <a href="/wiki/Lecture_Notes_in_Mathematics" title="Lecture Notes in Mathematics">Lecture Notes in Mathematics</a> vol. 2208, <a href="/wiki/Springer_books" class="mw-redirect" title="Springer books">Springer books</a>, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-319-74451-3" title="Special:BookSources/978-3-319-74451-3">978-3-319-74451-3</a></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Composition_of_relations&action=edit&section=13" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>M. Kilp, U. Knauer, A.V. Mikhalev (2000) <i>Monoids, Acts and Categories with Applications to Wreath Products and Graphs</i>, De Gruyter Expositions in Mathematics vol. 29, <a href="/wiki/Walter_de_Gruyter" class="mw-redirect" title="Walter de Gruyter">Walter de Gruyter</a>,<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-11-015248-7" title="Special:BookSources/3-11-015248-7">3-11-015248-7</a>.</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="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 href="/wiki/Graded_poset" title="Graded poset">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 class="mw-selflink selflink">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=Composition_of_relations&oldid=1251719997">https://en.wikipedia.org/w/index.php?title=Composition_of_relations&oldid=1251719997</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_logic" title="Category:Algebraic logic">Algebraic logic</a></li><li><a href="/wiki/Category:Binary_operations" title="Category:Binary operations">Binary operations</a></li><li><a href="/wiki/Category:Mathematical_relations" title="Category:Mathematical relations">Mathematical relations</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_January_2022" title="Category:Wikipedia articles needing clarification from January 2022">Wikipedia articles needing clarification from January 2022</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 17 October 2024, at 18:02<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=Composition_of_relations&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-dqsxq","wgBackendResponseTime":144,"wgPageParseReport":{"limitreport":{"cputime":"0.650","walltime":"1.023","ppvisitednodes":{"value":4594,"limit":1000000},"postexpandincludesize":{"value":32994,"limit":2097152},"templateargumentsize":{"value":2252,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":44017,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 739.103 1 -total"," 29.14% 215.402 1 Template:Reflist"," 19.52% 144.309 2 Template:Annotated_link"," 15.87% 117.293 6 Template:Rp"," 15.01% 110.943 6 Template:R/superscript"," 12.85% 94.988 1 Template:Cite_book"," 12.32% 91.026 1 Template:Order_theory"," 11.86% 87.657 18 Template:R/where"," 11.72% 86.617 1 Template:Short_description"," 11.63% 85.931 1 Template:Navbox"]},"scribunto":{"limitreport-timeusage":{"value":"0.334","limit":"10.000"},"limitreport-memusage":{"value":19647194,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-57488d5c7d-29gmv","timestamp":"20241128022935","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Composition of relations","url":"https:\/\/en.wikipedia.org\/wiki\/Composition_of_relations","sameAs":"http:\/\/www.wikidata.org\/entity\/Q2795123","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q2795123","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":"2006-10-16T18:22:08Z","dateModified":"2024-10-17T18:02:15Z","headline":"mathematical operation"}</script> </body> </html>