330:
1780:
2904:
The total orders are the partial orders that are also total preorders. The number of preorders that are neither a partial order nor a total preorder is, therefore, the number of preorders, minus the number of partial orders, minus the number of total preorders, plus the number of total orders: 0, 0,
464:. For example, the relation over the integers in which each odd number is related to itself is a coreflexive relation. The equality relation is the only example of a both reflexive and coreflexive relation, and any coreflexive relation is a subset of the identity relation.
2466:
2403:
102:
have developed understanding of endorelations. Terminology particular for graph theory is used for description, with an ordinary (undirected) graph presumed to correspond to a
1767:
is a relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and total, since these properties imply reflexivity.
2895:
2241:
1708:
1783:
Implications (blue) and conflicts (red) between properties (yellow) of homogeneous binary relations. For example, every asymmetric relation is irreflexive (
813:. A transitive relation is irreflexive if and only if it is asymmetric. For example, "is ancestor of" is a transitive relation, while "is parent of" is not.
3319:
749:. A relation is asymmetric if and only if it is both antisymmetric and irreflexive. For example, > is an asymmetric relation, but ≥ is not.
3376:
1254:
holds. For example, > is a trichotomous relation on the real numbers, while the relation "divides" over the natural numbers is not.
2490:
3412:
3558:
2009:
3536:
3303:
3276:
3249:
3222:
3197:
3172:
1208:. This property, too, is sometimes called "total", which is distinct from the definitions of "left/right-total" given below.
2881:
753:
Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation
1172:. This property is sometimes called "total", which is distinct from the definitions of "left/right-total" given below.
3502:
3453:
3341:
981:
3443:
2215:
1698:
1069:) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.
2317:
1757:
1398:
87:
17:
2416:
2438:
2375:
1406:
340:
of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as a
2143:
1890:
1443:
353:
2428:
2420:
1212:
917:
540:
3024:
1450:
Moreover, all properties of binary relations in general also may apply to homogeneous relations:
3517:
2994:
2469:
2357:
667:
3361:
3293:
3477:
3266:
3043:
2534:
2192:
1681:
1383:
504:
3384:. Prague: School of Mathematics – Physics Charles University. p. 1. Archived from
3239:
2921:
2292:
2037:
1736:
3385:
2988:
2549:
2539:
2338:
2020:
1763:
578:. A relation is quasi-reflexive if, and only if, it is both left and right quasi-reflexive.
468:
428:
397:
91:
3051:
1969:. This can be seen to be equal to the intersection of all transitive relations containing
8:
3037:
2999:
2514:
2122:
2064:
771:
717:
344:
with 1 indicating contact and 0 no contact. This example expresses a symmetric relation.
83:
3420:
3393:
Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".
3358:
Foundations of Logic and
Mathematics: Applications to Computer Science and Cryptography
3031:
2909:
2524:
2519:
2285:
2069:
2059:
2054:
1951:
1470:
1258:
1176:
1130:
615:
371:
103:
3532:
3498:
3449:
3337:
3299:
3272:
3245:
3218:
3193:
3168:
3093:
2424:
1845:
582:
The previous 6 alternatives are far from being exhaustive; e.g., the binary relation
257:
55:
610:, respectively. The latter two facts also rule out (any kind of) quasi-reflexivity.
3524:
2432:
2102:
598:
is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair
139:
3064:
2509:
1045:
Again, the previous 5 alternatives are not exhaustive. For example, the relation
863:
47:
3528:
3119:
3009:
2948:
2931:
the relation is its own complement. The non-symmetric ones can be grouped into
2891:
The number of irreflexive relations is the same as that of reflexive relations.
2082:
1595:
1483:
is a set. (This makes sense only if relations over proper classes are allowed.)
1074:
817:
341:
337:
115:
107:
1773:
Implications and conflicts between properties of homogeneous binary relations
1752:, is a relation that is irreflexive, antisymmetric, transitive and connected.
1734:, is a relation that is reflexive, antisymmetric, transitive and connected. A
3552:
2160:
1812:
1797:), and no relation on a non-empty set can be both irreflexive and reflexive (
1038:
710:
131:
3318:
Fonseca de
Oliveira, J. N., & Pereira Cunha Rodrigues, C. D. J. (2004).
3482:
3003:
2958:
2952:
910:
99:
95:
3019:
2913:
2898:(irreflexive transitive relations) is the same as that of partial orders.
2544:
2265:
1936:
1718:
1123:
647:. For example, "is a blood relative of" is a symmetric relation, because
31:
2901:
The number of strict weak orders is the same as that of total preorders.
1779:
2185:
1716:, is a relation that is irreflexive, antisymmetric, and transitive. A
3515:
Schmidt, Gunther; Ströhlein, Thomas (1993). "Homogeneous
Relations".
3013:
2966:
2411:
186:
1706:, is a relation that is reflexive, antisymmetric, and transitive. A
3295:
Touch of Class: Learning to
Program Well with Objects and Contracts
2529:
2167:
1998:
1675:
3519:
Relations and Graphs: Discrete
Mathematics for Computer Scientists
329:
3215:
Mathematical
Foundations of Computational Engineering: A Handbook
3067:
in general need not be homogeneous, it is defined to be a subset
2974:
2932:
76:
3265:
Tanaev, V.; Gordon, W.; Shafransky, Yakov M. (6 December 2012).
3241:
Fuzzy
Mathematics: An Introduction for Engineers and Scientists
2980:
2920:
The homogeneous relations can be grouped into pairs (relation,
2234:
709:. For example, ≥ is an antisymmetric relation; so is >, but
3165:
Goguen
Categories: A Categorical Approach to L-fuzzy Relations
1693:, is a relation that is reflexive, transitive, and connected.
766:
is neither symmetric nor antisymmetric, let alone asymmetric.
424:. For example, > is an irreflexive relation, but ≥ is not.
3374:
3332:
Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006),
3212:
2857:
2852:
2847:
2842:
2837:
2832:
2827:
2822:
2817:
2812:
2485:
75:". An example of a homogeneous relation is the relation of
3375:
Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007).
3320:
Transposing
Relations: From Maybe Functions to Hash Tables
1836:
then each of the following is a homogeneous relation over
3238:
Mordeson, John N.; Nair, Premchand S. (8 November 2012).
393:. For example, ≥ is a reflexive relation but > is not.
3298:. Springer Science & Business Media. p. 509.
3264:
3217:. Springer Science & Business Media. p. 496.
358:
Some important properties that a homogeneous relation
3271:. Springer Science & Business Media. p. 41.
2908:
The number of equivalence relations is the number of
2475:
The number of distinct homogeneous relations over an
2472:
where the identity element is the identity relation.
2441:
2378:
3402:
Since neither 5 divides 3, nor 3 divides 5, nor 3=5.
1628:. This property is different from the definition of
1305:. For example, = is a Euclidean relation because if
3331:
3206:
2936:
1761:is a relation that is symmetric and transitive. An
145:
3516:
3322:. In Mathematics of Program Construction (p. 337).
2460:
2397:
1679:is a relation that is reflexive and transitive. A
713:(the condition in the definition is always false).
1961:Defined as the smallest transitive relation over
150:Some particular homogeneous relations over a set
3550:
3514:
106:, and a general endorelation corresponding to a
3475:Gunther Schmidt & Thomas Strohlein (2012)
3162:
3445:Theory of Relations, Volume 145 - 1st Edition
2501:-element binary relations of different types
67:. This is commonly phrased as "a relation on
3523:. Berlin, Heidelberg: Springer. p. 14.
3237:
3187:
3046:, the complement of some dependency relation
1446:is assumed, both conditions are equivalent.
3355:
3336:(6th ed.), Brooks/Cole, p. 160,
3192:. Cambridge University Press. p. 22.
3378:Transitive Closures of Binary Relations I
3181:
3156:
1889:. This can be proven to be equal to the
1881:or the smallest reflexive relation over
1778:
328:
79:, where the relation is between people.
3441:
3268:Scheduling Theory. Single-Stage Systems
1811:). Omitting the red edges results in a
54:and itself, i.e. it is a subset of the
14:
3551:
3448:(1st ed.). Elsevier. p. 46.
3213:Peter J. Pahl; Rudolf Damrath (2001).
3034:, a reflexive and symmetric relation:
2010:Reflexive transitive symmetric closure
1893:of all reflexive relations containing
1033:are also incomparable with respect to
82:Common types of endorelations include
3291:
2372:The set of all homogeneous relations
2041:also apply to homogeneous relations.
1832:is a homogeneous relation over a set
27:Binary relation over a set and itself
3334:A Transition to Advanced Mathematics
2882:Stirling numbers of the second kind
118:of 0s and 1s, where the expression
24:
3057:
2444:
2381:
2047:Homogeneous relations by property
25:
3570:
2461:{\displaystyle {\mathcal {B}}(X)}
2398:{\displaystyle {\mathcal {B}}(X)}
2038:Binary relation § Operations
1013:are incomparable with respect to
3442:Fraisse, R. (15 December 2000).
3413:"Condition for Well-Foundedness"
3292:Meyer, Bertrand (29 June 2009).
2423:of mapping of a relation to its
1409:(that is, no infinite chain ...
873:is transitive. That is, for all
146:Particular homogeneous relations
130:in the graph, and to a 1 in the
3508:
3487:
3469:
3435:
3405:
3396:
3368:
1405:. Well-foundedness implies the
982:Transitivity of incomparability
122:corresponds to an edge between
71:" or "a (binary) relation over
3559:Properties of binary relations
3349:
3325:
3312:
3285:
3258:
3231:
3190:Relational Knowledge Discovery
2455:
2449:
2392:
2386:
2367:
13:
1:
3149:
3040:, a finite tolerance relation
1823:
347:
2318:Partial equivalence relation
1977:Reflexive transitive closure
1758:partial equivalence relation
913:in constructive mathematics.
7:
3529:10.1007/978-3-642-77968-8_2
3360:, Springer-Verlag, p.
3167:. Springer. pp. x–xi.
2942:
2905:0, 3, and 85, respectively.
1017:and if the same is true of
10:
3575:
2312:Strict alphabetical order
2035:All operations defined in
1407:descending chain condition
351:
324:
3356:Nievergelt, Yves (2002),
3025:Equipollent line segments
1642:(also called right-total)
1444:axiom of dependent choice
354:Category:Binary relations
154:(with arbitrary elements
94:. Specialized studies of
3497:, Academic Press, 1982,
2963:Greater than or equal to
2429:composition of relations
2019:Defined as the smallest
1599:(also called left-total)
3163:Michael Winter (2007).
3141:, it is also called an
2939:, inverse complement).
2935:(relation, complement,
659:is a blood relative of
651:is a blood relative of
3493:Joseph G. Rosenstein,
3244:. Physica. p. 2.
2470:monoid with involution
2462:
2399:
1816:
1389:every nonempty subset
333:
142:in graph terminology.
3188:M. E. Müller (2012).
3044:Independency relation
2989:Equivalence relations
2971:Less than or equal to
2896:strict partial orders
2463:
2400:
1782:
869:if the complement of
505:Right quasi-reflexive
332:
302:holds if and only if
3478:Relations and Graphs
2550:Equivalence relation
2439:
2376:
2339:Equivalence relation
2242:Strict partial order
2021:equivalence relation
1764:equivalence relation
1709:strict partial order
1100:, there exists some
469:Left quasi-reflexive
36:homogeneous relation
3423:on 20 February 2019
3125:and arbitrary sets
3081:for arbitrary sets
3038:Dependency relation
2924:), except that for
2502:
2419:augmented with the
2048:
1901:Reflexive reduction
1746:strict simple order
1742:strict linear order
1442:can exist). If the
3032:Tolerance relation
2496:
2458:
2395:
2293:Strict total order
2286:Alphabetical order
2046:
1952:Transitive closure
1817:
1737:strict total order
1655:, there exists an
1177:Strongly connected
1122:. This is used in
1037:. This is used in
909:. This is used in
334:
213:Universal relation
138:. It is called an
110:. An endorelation
104:symmetric relation
3538:978-3-642-77968-8
3305:978-3-540-92145-5
3278:978-94-011-1190-4
3251:978-3-7908-1808-6
3224:978-3-540-67995-0
3199:978-0-521-19021-3
3174:978-1-4020-6164-6
3094:finitary relation
3052:Kinship relations
2863:
2862:
2425:converse relation
2363:
2362:
1935:} or the largest
1846:Reflexive closure
1821:
1820:
1636:by some authors).
1232:, exactly one of
258:Identity function
253:Identity relation
114:corresponds to a
56:Cartesian product
16:(Redirected from
3566:
3543:
3542:
3522:
3512:
3506:
3495:Linear orderings
3491:
3485:
3473:
3467:
3466:
3464:
3462:
3439:
3433:
3432:
3430:
3428:
3419:. Archived from
3409:
3403:
3400:
3394:
3392:
3390:
3383:
3372:
3366:
3364:
3353:
3347:
3346:
3329:
3323:
3316:
3310:
3309:
3289:
3283:
3282:
3262:
3256:
3255:
3235:
3229:
3228:
3210:
3204:
3203:
3185:
3179:
3178:
3160:
3117:
3080:
2930:
2879:
2807:
2794:
2793:
2773:
2756:
2755:
2704:
2699:
2694:
2689:
2503:
2495:
2488:
2482:
2479:-element set is
2467:
2465:
2464:
2459:
2448:
2447:
2433:binary operation
2414:
2404:
2402:
2401:
2396:
2385:
2384:
2103:Undirected graph
2049:
2045:
1996:
1934:
1880:
1808:
1805:
1802:
1794:
1791:
1788:
1770:
1769:
1664:
1654:
1627:
1621:
1611:
1590:
1580:
1574:
1568:
1554:
1536:
1526:
1520:
1514:
1504:
1482:
1476:
1468:
1441:
1404:
1401:with respect to
1396:
1392:
1378:
1372:
1366:
1360:
1334:
1324:
1314:
1304:
1298:
1292:
1286:
1253:
1243:
1237:
1231:
1207:
1201:
1195:
1171:
1165:
1159:
1149:
1121:
1115:
1109:
1099:
1093:
1068:
1057:
1050:
1036:
1032:
1028:
1024:
1020:
1016:
1012:
1008:
1004:
976:
970:
964:
958:
952:
946:
940:
908:
902:
896:
890:
858:
852:
846:
840:
812:
806:
800:
794:
765:
758:
748:
742:
736:
708:
698:
692:
686:
662:
658:
654:
650:
646:
640:
634:
609:
605:
601:
597:
587:
577:
571:
565:
559:
535:
529:
523:
499:
493:
487:
463:
453:
447:
423:
417:
392:
386:
365:
361:
317:
301:
284:
246:
229:
206:
189:
171:
162:
140:adjacency matrix
66:
21:
3574:
3573:
3569:
3568:
3567:
3565:
3564:
3563:
3549:
3548:
3547:
3546:
3539:
3513:
3509:
3492:
3488:
3474:
3470:
3460:
3458:
3456:
3440:
3436:
3426:
3424:
3411:
3410:
3406:
3401:
3397:
3388:
3381:
3373:
3369:
3354:
3350:
3344:
3330:
3326:
3317:
3313:
3306:
3290:
3286:
3279:
3263:
3259:
3252:
3236:
3232:
3225:
3211:
3207:
3200:
3186:
3182:
3175:
3161:
3157:
3152:
3140:
3131:
3116:
3107:
3097:
3068:
3065:binary relation
3060:
3058:Generalizations
2949:Order relations
2945:
2925:
2912:, which is the
2866:
2792:
2786:
2785:
2784:
2782:
2754:
2748:
2747:
2746:
2744:
2702:
2697:
2692:
2687:
2506:Elements
2484:
2480:
2443:
2442:
2440:
2437:
2436:
2417:Boolean algebra
2410:
2380:
2379:
2377:
2374:
2373:
2370:
1997:, the smallest
1987:
1910:
1856:
1826:
1806:
1803:
1800:
1792:
1789:
1786:
1687:linear preorder
1656:
1646:
1623:
1613:
1612:there exists a
1603:
1582:
1576:
1570:
1556:
1546:
1528:
1522:
1516:
1506:
1492:
1478:
1474:
1460:
1440:
1434:
1428:
1418:
1410:
1402:
1399:minimal element
1394:
1390:
1374:
1368:
1362:
1344:
1326:
1316:
1306:
1300:
1294:
1288:
1270:
1259:Right Euclidean
1245:
1239:
1233:
1219:
1203:
1197:
1183:
1167:
1161:
1151:
1137:
1117:
1111:
1101:
1095:
1081:
1059:
1052:
1046:
1034:
1030:
1026:
1022:
1018:
1014:
1010:
1006:
988:
972:
966:
960:
954:
948:
942:
924:
918:Quasitransitive
904:
898:
892:
874:
854:
848:
842:
824:
808:
802:
796:
778:
760:
754:
744:
738:
724:
700:
694:
688:
674:
660:
656:
655:if and only if
652:
648:
642:
636:
622:
607:
603:
599:
589:
583:
573:
567:
561:
547:
541:Quasi-reflexive
531:
525:
511:
495:
489:
475:
455:
449:
435:
419:
409:
388:
378:
363:
359:
356:
350:
338:tectonic plates
327:
316:
309:
303:
300:
294:
288:
286:
264:
245:
239:
233:
231:
217:
205:
199:
193:
191:
181:
170:
164:
161:
155:
148:
58:
48:binary relation
28:
23:
22:
15:
12:
11:
5:
3572:
3562:
3561:
3545:
3544:
3537:
3507:
3486:
3468:
3454:
3434:
3404:
3395:
3391:on 2013-11-02.
3367:
3348:
3342:
3324:
3311:
3304:
3284:
3277:
3257:
3250:
3230:
3223:
3205:
3198:
3180:
3173:
3154:
3153:
3151:
3148:
3147:
3146:
3145:-ary relation.
3136:
3129:
3120:natural number
3112:
3105:
3090:
3059:
3056:
3055:
3054:
3049:
3048:
3047:
3041:
3029:
3028:
3027:
3022:
3017:
3010:Equinumerosity
3007:
2997:
2986:
2985:
2984:
2978:
2972:
2969:
2964:
2961:
2944:
2941:
2918:
2917:
2906:
2902:
2899:
2894:The number of
2892:
2861:
2860:
2855:
2850:
2845:
2840:
2835:
2830:
2825:
2820:
2815:
2809:
2808:
2787:
2780:
2774:
2749:
2742:
2740:
2738:
2735:
2732:
2730:
2727:
2721:
2720:
2717:
2714:
2711:
2708:
2705:
2700:
2695:
2690:
2685:
2681:
2680:
2677:
2674:
2671:
2668:
2665:
2662:
2659:
2656:
2653:
2649:
2648:
2645:
2642:
2639:
2636:
2633:
2630:
2627:
2624:
2621:
2617:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2585:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2553:
2552:
2547:
2542:
2540:Total preorder
2537:
2532:
2527:
2522:
2517:
2512:
2507:
2457:
2454:
2451:
2446:
2427:. Considering
2394:
2391:
2388:
2383:
2369:
2366:
2365:
2364:
2361:
2360:
2355:
2352:
2350:
2347:
2344:
2341:
2335:
2334:
2332:
2330:
2328:
2325:
2322:
2320:
2314:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2289:
2288:
2283:
2280:
2277:
2274:
2273:Antisymmetric
2271:
2268:
2262:
2261:
2260:Strict subset
2258:
2255:
2253:
2250:
2247:
2244:
2238:
2237:
2232:
2229:
2227:
2224:
2223:Antisymmetric
2221:
2218:
2212:
2211:
2209:
2206:
2203:
2200:
2198:
2195:
2193:Total preorder
2189:
2188:
2183:
2180:
2178:
2175:
2173:
2170:
2164:
2163:
2158:
2156:
2154:
2152:
2149:
2146:
2140:
2139:
2137:
2135:
2133:
2131:
2128:
2125:
2119:
2118:
2116:
2114:
2112:
2110:
2107:
2105:
2099:
2098:
2096:
2093:
2091:
2089:
2087:
2085:
2083:Directed graph
2079:
2078:
2075:
2072:
2067:
2062:
2057:
2052:
2033:
2032:
2017:
2012:
2006:
1984:
1978:
1974:
1959:
1954:
1948:
1939:relation over
1907:
1902:
1898:
1853:
1848:
1825:
1822:
1819:
1818:
1775:
1774:
1766:
1760:
1751:
1747:
1743:
1740:, also called
1739:
1733:
1729:
1725:
1722:, also called
1721:
1715:
1712:, also called
1711:
1705:
1702:, also called
1701:
1692:
1688:
1685:, also called
1684:
1682:total preorder
1678:
1671:
1670:
1643:
1641:
1637:
1600:
1598:
1592:
1543:
1542:
1538:
1489:
1488:
1484:
1457:
1456:
1448:
1447:
1438:
1432:
1426:
1414:
1387:
1386:
1380:
1341:
1340:
1339:Left Euclidean
1336:
1267:
1265:
1261:
1255:
1216:
1215:
1209:
1180:
1179:
1173:
1134:
1133:
1127:
1078:
1077:
1043:
1042:
1039:weak orderings
985:
984:
978:
921:
920:
914:
867:
866:
860:
821:
820:
818:Antitransitive
814:
775:
774:
751:
750:
721:
720:
714:
671:
670:
664:
619:
618:
580:
579:
544:
543:
537:
508:
507:
501:
472:
471:
465:
432:
431:
425:
406:
404:
400:
394:
375:
374:
366:may have are:
349:
346:
342:logical matrix
336:Fifteen large
326:
323:
322:
321:
320:
319:
314:
307:
298:
292:
250:
249:
248:
243:
237:
210:
209:
208:
203:
197:
177:Empty relation
168:
159:
147:
144:
116:logical matrix
108:directed graph
26:
9:
6:
4:
3:
2:
3571:
3560:
3557:
3556:
3554:
3540:
3534:
3530:
3526:
3521:
3520:
3511:
3504:
3503:0-12-597680-1
3500:
3496:
3490:
3484:
3480:
3479:
3472:
3457:
3455:9780444505422
3451:
3447:
3446:
3438:
3422:
3418:
3414:
3408:
3399:
3387:
3380:
3379:
3371:
3363:
3359:
3352:
3345:
3343:0-534-39900-2
3339:
3335:
3328:
3321:
3315:
3307:
3301:
3297:
3296:
3288:
3280:
3274:
3270:
3269:
3261:
3253:
3247:
3243:
3242:
3234:
3226:
3220:
3216:
3209:
3201:
3195:
3191:
3184:
3176:
3170:
3166:
3159:
3155:
3144:
3139:
3135:
3128:
3124:
3121:
3115:
3111:
3104:
3100:
3095:
3091:
3088:
3084:
3079:
3075:
3071:
3066:
3062:
3061:
3053:
3050:
3045:
3042:
3039:
3036:
3035:
3033:
3030:
3026:
3023:
3021:
3018:
3015:
3011:
3008:
3005:
3004:affine spaces
3001:
2998:
2996:
2993:
2992:
2990:
2987:
2982:
2979:
2976:
2973:
2970:
2968:
2965:
2962:
2960:
2957:
2956:
2954:
2953:strict orders
2950:
2947:
2946:
2940:
2938:
2934:
2928:
2923:
2915:
2911:
2907:
2903:
2900:
2897:
2893:
2890:
2889:
2888:
2885:
2883:
2877:
2873:
2869:
2859:
2856:
2854:
2851:
2849:
2846:
2844:
2841:
2839:
2836:
2834:
2831:
2829:
2826:
2824:
2821:
2819:
2816:
2814:
2811:
2810:
2805:
2801:
2797:
2790:
2781:
2778:
2775:
2771:
2767:
2763:
2759:
2752:
2743:
2741:
2739:
2736:
2733:
2731:
2728:
2726:
2723:
2722:
2718:
2715:
2712:
2709:
2706:
2701:
2696:
2691:
2686:
2683:
2682:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2651:
2650:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2618:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2586:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2554:
2551:
2548:
2546:
2543:
2541:
2538:
2536:
2535:Partial order
2533:
2531:
2528:
2526:
2523:
2521:
2518:
2516:
2513:
2511:
2508:
2505:
2504:
2500:
2494:
2492:
2487:
2478:
2473:
2471:
2468:, it forms a
2452:
2434:
2430:
2426:
2422:
2418:
2415:, which is a
2413:
2408:
2389:
2359:
2356:
2353:
2351:
2348:
2345:
2342:
2340:
2337:
2336:
2333:
2331:
2329:
2326:
2323:
2321:
2319:
2316:
2315:
2311:
2308:
2305:
2302:
2299:
2296:
2294:
2291:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2267:
2264:
2263:
2259:
2256:
2254:
2251:
2248:
2245:
2243:
2240:
2239:
2236:
2233:
2230:
2228:
2225:
2222:
2219:
2217:
2216:Partial order
2214:
2213:
2210:
2207:
2204:
2201:
2199:
2196:
2194:
2191:
2190:
2187:
2184:
2181:
2179:
2176:
2174:
2171:
2169:
2166:
2165:
2162:
2161:Pecking order
2159:
2157:
2155:
2153:
2150:
2147:
2145:
2142:
2141:
2138:
2136:
2134:
2132:
2129:
2126:
2124:
2121:
2120:
2117:
2115:
2113:
2111:
2108:
2106:
2104:
2101:
2100:
2097:
2094:
2092:
2090:
2088:
2086:
2084:
2081:
2080:
2076:
2073:
2071:
2070:Connectedness
2068:
2066:
2063:
2061:
2058:
2056:
2053:
2051:
2050:
2044:
2043:
2042:
2040:
2039:
2030:
2026:
2022:
2018:
2016:
2011:
2008:
2007:
2004:
2000:
1994:
1990:
1985:
1982:
1976:
1975:
1972:
1968:
1964:
1960:
1958:
1953:
1950:
1949:
1946:
1943:contained in
1942:
1938:
1933:
1929:
1925:
1921:
1917:
1913:
1908:
1906:
1900:
1899:
1896:
1892:
1888:
1884:
1879:
1875:
1871:
1867:
1863:
1859:
1854:
1852:
1847:
1844:
1843:
1842:
1841:
1839:
1835:
1831:
1814:
1813:Hasse diagram
1810:
1796:
1781:
1777:
1776:
1772:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1749:
1745:
1741:
1738:
1735:
1731:
1727:
1723:
1720:
1717:
1713:
1710:
1707:
1703:
1700:
1699:partial order
1697:
1694:
1690:
1686:
1683:
1680:
1677:
1674:
1668:
1663:
1659:
1653:
1649:
1644:
1639:
1638:
1635:
1632:(also called
1631:
1626:
1620:
1616:
1610:
1606:
1601:
1597:
1594:
1593:
1589:
1585:
1579:
1573:
1567:
1563:
1559:
1553:
1549:
1544:
1540:
1539:
1535:
1531:
1525:
1519:
1513:
1509:
1503:
1499:
1495:
1490:
1486:
1485:
1481:
1472:
1467:
1463:
1458:
1454:
1453:
1452:
1451:
1445:
1437:
1431:
1425:
1421:
1417:
1413:
1408:
1400:
1388:
1385:
1382:
1381:
1377:
1371:
1365:
1359:
1355:
1351:
1347:
1342:
1338:
1337:
1333:
1329:
1323:
1319:
1313:
1309:
1303:
1297:
1291:
1285:
1281:
1277:
1273:
1268:
1263:
1260:
1257:
1256:
1252:
1248:
1242:
1236:
1230:
1226:
1222:
1217:
1214:
1211:
1210:
1206:
1200:
1194:
1190:
1186:
1181:
1178:
1175:
1174:
1170:
1164:
1158:
1154:
1148:
1144:
1140:
1135:
1132:
1129:
1128:
1125:
1120:
1114:
1108:
1104:
1098:
1092:
1088:
1084:
1079:
1076:
1073:
1072:
1071:
1070:
1066:
1062:
1055:
1049:
1040:
1003:
999:
995:
991:
986:
983:
980:
979:
975:
969:
963:
957:
951:
945:
939:
935:
931:
927:
922:
919:
916:
915:
912:
911:pseudo-orders
907:
901:
895:
889:
885:
881:
877:
872:
868:
865:
864:Co-transitive
862:
861:
857:
851:
845:
839:
835:
831:
827:
822:
819:
816:
815:
811:
805:
799:
793:
789:
785:
781:
776:
773:
770:
769:
768:
767:
763:
757:
747:
741:
735:
731:
727:
722:
719:
716:
715:
712:
707:
703:
697:
691:
685:
681:
677:
672:
669:
668:Antisymmetric
666:
665:
645:
639:
633:
629:
625:
620:
617:
614:
613:
612:
611:
596:
592:
586:
576:
570:
564:
558:
554:
550:
545:
542:
539:
538:
534:
528:
522:
518:
514:
509:
506:
503:
502:
498:
492:
486:
482:
478:
473:
470:
467:
466:
462:
458:
452:
446:
442:
438:
433:
430:
427:
426:
422:
416:
412:
407:
402:
399:
396:
395:
391:
385:
381:
376:
373:
370:
369:
368:
367:
355:
345:
343:
339:
331:
313:
306:
297:
291:
283:
279:
275:
271:
267:
263:
262:
260:
259:
254:
251:
247:holds always;
242:
236:
228:
224:
220:
216:
215:
214:
211:
202:
196:
188:
184:
180:
179:
178:
175:
174:
173:
167:
158:
153:
143:
141:
137:
133:
132:square matrix
129:
125:
121:
117:
113:
109:
105:
101:
97:
93:
89:
85:
80:
78:
74:
70:
65:
61:
57:
53:
49:
45:
41:
38:(also called
37:
33:
19:
3518:
3510:
3494:
3489:
3483:Google Books
3481:, p. 54, at
3476:
3471:
3459:. Retrieved
3444:
3437:
3425:. Retrieved
3421:the original
3416:
3407:
3398:
3386:the original
3377:
3370:
3357:
3351:
3333:
3327:
3314:
3294:
3287:
3267:
3260:
3240:
3233:
3214:
3208:
3189:
3183:
3164:
3158:
3142:
3137:
3133:
3126:
3122:
3113:
3109:
3102:
3098:
3096:is a subset
3086:
3082:
3077:
3073:
3069:
2959:Greater than
2951:, including
2926:
2919:
2886:
2875:
2871:
2867:
2864:
2803:
2799:
2795:
2788:
2776:
2769:
2765:
2761:
2757:
2750:
2724:
2498:
2476:
2474:
2406:
2371:
2297:Irreflexive
2246:Irreflexive
2148:Irreflexive
2065:Transitivity
2036:
2034:
2028:
2024:
2014:
2002:
1992:
1988:
1980:
1970:
1966:
1962:
1956:
1944:
1940:
1931:
1927:
1923:
1919:
1915:
1911:
1904:
1894:
1891:intersection
1886:
1882:
1877:
1873:
1869:
1865:
1861:
1857:
1850:
1837:
1833:
1829:
1827:
1798:
1784:
1754:
1750:strict chain
1728:simple order
1724:linear order
1714:strict order
1695:
1672:
1666:
1661:
1657:
1651:
1647:
1633:
1629:
1624:
1618:
1614:
1608:
1604:
1587:
1583:
1577:
1571:
1565:
1561:
1557:
1551:
1547:
1533:
1529:
1523:
1517:
1511:
1507:
1501:
1497:
1493:
1479:
1465:
1461:
1449:
1435:
1429:
1423:
1419:
1415:
1411:
1384:Well-founded
1375:
1369:
1363:
1357:
1353:
1349:
1345:
1331:
1327:
1321:
1317:
1311:
1307:
1301:
1295:
1289:
1283:
1279:
1275:
1271:
1250:
1246:
1240:
1234:
1228:
1224:
1220:
1213:Trichotomous
1204:
1198:
1192:
1188:
1184:
1168:
1162:
1156:
1152:
1146:
1142:
1138:
1124:dense orders
1118:
1112:
1106:
1102:
1096:
1090:
1086:
1082:
1064:
1060:
1053:
1047:
1044:
1001:
997:
993:
989:
973:
967:
961:
955:
953:but neither
949:
943:
937:
933:
929:
925:
905:
899:
893:
887:
883:
879:
875:
870:
855:
849:
843:
837:
833:
829:
825:
809:
803:
797:
791:
787:
783:
779:
761:
755:
752:
745:
739:
733:
729:
725:
705:
701:
695:
689:
683:
679:
675:
643:
637:
631:
627:
623:
594:
590:
584:
581:
574:
568:
562:
556:
552:
548:
532:
526:
520:
516:
512:
496:
490:
484:
480:
476:
460:
456:
450:
444:
440:
436:
420:
414:
410:
389:
383:
379:
357:
335:
311:
304:
295:
289:
281:
277:
273:
269:
265:
256:
252:
240:
234:
226:
222:
218:
212:
207:holds never;
200:
194:
182:
176:
165:
156:
151:
149:
135:
127:
123:
119:
111:
100:graph theory
96:order theory
92:equivalences
81:
72:
68:
63:
59:
51:
43:
40:endorelation
39:
35:
29:
18:Endorelation
3505:, p. 4
3461:20 February
3427:20 February
2914:Bell number
2545:Total order
2409:is the set
2405:over a set
2368:Enumeration
2349:Transitive
2327:Transitive
2303:Transitive
2300:Asymmetric
2276:Transitive
2266:Total order
2252:Transitive
2249:Asymmetric
2226:Transitive
2202:Transitive
2177:Transitive
2151:Asymmetric
2055:Reflexivity
2027:containing
2001:containing
1986:Defined as
1965:containing
1937:irreflexive
1909:Defined as
1885:containing
1855:Defined as
1719:total order
1487:Left-unique
1397:contains a
853:then never
759:defined by
588:defined by
429:Coreflexive
398:Irreflexive
362:over a set
42:) on a set
32:mathematics
3150:References
3020:Isomorphic
3012:or "is in
3002:with (for
2933:quadruples
2922:complement
2910:partitions
2880:refers to
2865:Note that
2515:Transitive
2497:Number of
2483:(sequence
2421:involution
2346:Symmetric
2343:Reflexive
2324:Symmetric
2306:Connected
2279:Connected
2270:Reflexive
2220:Reflexive
2205:Connected
2197:Reflexive
2186:Preference
2172:Reflexive
2144:Tournament
2130:Symmetric
2127:Reflexive
2123:Dependency
2109:Symmetric
1824:Operations
1691:weak order
1665:such that
1640:Surjective
1622:such that
1477:such that
1110:such that
1094:such that
772:Transitive
718:Asymmetric
606:, but not
352:See also:
348:Properties
255:(see also
3417:ProofWiki
3118:for some
3014:bijection
2967:Less than
2525:Symmetric
2520:Reflexive
1630:connected
1541:Univalent
1264:Euclidean
1262:(or just
1131:Connected
743:then not
711:vacuously
616:Symmetric
372:Reflexive
287:that is,
232:that is,
192:that is,
3553:Category
3132:, ...,
3108:× ... ×
3000:Parallel
2995:Equality
2977:(evenly)
2943:Examples
2530:Preorder
2358:Equality
2168:Preorder
2077:Example
2060:Symmetry
1999:preorder
1676:preorder
1645:for all
1602:for all
1555:and all
1545:for all
1505:and all
1491:for all
1459:for all
1455:Set-like
1343:for all
1269:for all
1218:for all
1182:for all
1136:for all
1080:for all
987:for all
971:but not
923:for all
823:for all
777:for all
723:for all
673:for all
621:for all
546:for all
510:for all
474:for all
434:for all
408:for all
377:for all
50:between
2975:Divides
2937:inverse
2887:Notes:
2858:A000110
2853:A000142
2848:A000670
2843:A001035
2838:A000798
2833:A006125
2828:A053763
2823:A006905
2818:A002416
2489:in the
2486:A002416
2074:Symbol
1473:of all
1025:, then
965:, then
897:, then
325:Example
172:) are:
77:kinship
3535:
3501:
3452:
3340:
3302:
3275:
3248:
3221:
3196:
3171:
2981:Subset
2688:65,536
2235:Subset
1801:Irrefl
1793:Irrefl
1469:, the
764:> 2
608:(2, 2)
604:(2, 4)
602:, and
600:(0, 0)
418:, not
403:strict
90:, and
88:graphs
84:orders
3389:(PDF)
3382:(PDF)
3016:with"
2703:1,024
2698:4,096
2693:3,994
2431:as a
2354:~, ≡
2309:<
2257:<
2023:over
1991:* = (
1748:, or
1732:chain
1730:, or
1704:order
1634:total
1596:Total
1581:then
1569:, if
1527:then
1515:, if
1471:class
1373:then
1361:, if
1325:then
1299:then
1287:, if
1160:then
1150:, if
1075:Dense
1005:, if
941:, if
891:, if
841:, if
807:then
795:, if
737:, if
699:then
687:, if
641:then
635:, if
566:then
560:, if
530:then
524:, if
494:then
488:, if
454:then
448:, if
46:is a
3533:ISBN
3499:ISBN
3463:2019
3450:ISBN
3429:2019
3338:ISBN
3300:ISBN
3273:ISBN
3246:ISBN
3219:ISBN
3194:ISBN
3169:ISBN
3085:and
2813:OEIS
2491:OEIS
1926:) |
1918:\ {(
1876:} ∪
1868:) |
1860:= {(
1807:Refl
1787:ASym
1575:and
1521:and
1367:and
1315:and
1293:and
1116:and
1051:if (
1029:and
1021:and
1009:and
959:nor
947:and
847:and
801:and
693:and
572:and
401:(or
276:) |
268:= {(
126:and
98:and
34:, a
3525:doi
3362:158
2929:= 0
2719:15
2710:219
2707:355
2658:171
2655:512
2510:Any
2493:):
2435:on
1828:If
1689:or
1667:xRy
1625:xRy
1578:xRz
1572:xRy
1524:zRy
1518:xRy
1480:yRx
1422:...
1393:of
1376:yRz
1370:zRx
1364:yRx
1302:yRz
1296:xRz
1290:xRy
1244:or
1241:yRx
1235:xRy
1205:yRx
1202:or
1199:xRy
1169:yRx
1166:or
1163:xRy
1119:zRy
1113:xRz
1097:xRy
1058:or
1056:= 0
1048:xRy
974:zRx
968:xRz
962:zRy
956:yRx
950:yRz
944:xRy
906:yRz
903:or
900:xRy
894:xRz
856:xRz
850:yRz
844:xRy
810:xRz
804:yRz
798:xRy
756:xRy
746:yRx
740:xRy
696:yRx
690:xRy
644:yRx
638:xRy
585:xRy
575:yRy
569:xRx
563:xRy
533:yRy
527:xRy
497:xRx
491:xRy
451:xRy
421:xRx
390:xRx
134:of
120:xRy
30:In
3555::
3531:.
3415:.
3101:⊆
3092:A
3076:×
3072:⊆
3063:A
2991::
2983:of
2955::
2884:.
2874:,
2802:,
2791:=0
2779:!
2768:,
2753:=0
2737:2
2734:2
2729:2
2716:24
2713:75
2679:5
2673:13
2670:19
2667:29
2664:64
2661:64
2647:2
2626:13
2623:16
2615:1
2583:1
2282:≤
2231:≤
2208:≤
2182:≤
2095:→
2013:,
1979:,
1955:,
1930:∈
1922:,
1914:=
1903:,
1872:∈
1864:,
1849:,
1840::
1755:A
1744:,
1726:,
1696:A
1673:A
1660:∈
1650:∈
1617:∈
1607:∈
1586:=
1564:∈
1560:,
1550:∈
1532:=
1510:∈
1500:∈
1496:,
1464:∈
1436:Rx
1430:Rx
1424:Rx
1356:∈
1352:,
1348:,
1330:=
1320:=
1310:=
1282:∈
1278:,
1274:,
1249:=
1238:,
1227:∈
1223:,
1196:,
1191:∈
1187:,
1155:≠
1145:∈
1141:,
1105:∈
1089:∈
1085:,
1067:+1
1063:=
1000:∈
996:,
992:,
936:∈
932:,
928:,
886:∈
882:,
878:,
836:∈
832:,
828:,
790:∈
786:,
782:,
732:∈
728:,
704:=
682:∈
678:,
630:∈
626:,
593:=
555:∈
551:,
519:∈
515:,
483:∈
479:,
459:=
443:∈
439:,
413:∈
387:,
382:∈
310:=
296:Ix
285:};
280:∈
272:,
261:)
241:Ux
225:×
221:=
201:Ex
185:=
163:,
86:,
62:×
3541:.
3527::
3465:.
3431:.
3365:.
3308:.
3281:.
3254:.
3227:.
3202:.
3177:.
3143:n
3138:n
3134:X
3130:1
3127:X
3123:n
3114:n
3110:X
3106:1
3103:X
3099:R
3089:.
3087:Y
3083:X
3078:Y
3074:X
3070:R
3006:)
2927:n
2916:.
2878:)
2876:k
2872:n
2870:(
2868:S
2806:)
2804:k
2800:n
2798:(
2796:S
2789:k
2783:∑
2777:n
2772:)
2770:k
2766:n
2764:(
2762:S
2760:!
2758:k
2751:k
2745:∑
2725:n
2684:4
2676:6
2652:3
2644:2
2641:3
2638:3
2635:4
2632:8
2629:4
2620:2
2612:1
2609:1
2606:1
2603:1
2600:2
2597:1
2594:2
2591:2
2588:1
2580:1
2577:1
2574:1
2571:1
2568:1
2565:1
2562:1
2559:1
2556:0
2499:n
2481:2
2477:n
2456:)
2453:X
2450:(
2445:B
2412:2
2407:X
2393:)
2390:X
2387:(
2382:B
2031:.
2029:R
2025:X
2015:R
2005:.
2003:R
1995:)
1993:R
1989:R
1983:*
1981:R
1973:.
1971:R
1967:R
1963:X
1957:R
1947:.
1945:R
1941:X
1932:X
1928:x
1924:x
1920:x
1916:R
1912:R
1905:R
1897:.
1895:R
1887:R
1883:X
1878:R
1874:X
1870:x
1866:x
1862:x
1858:R
1851:R
1838:X
1834:X
1830:R
1815:.
1809:"
1804:#
1799:"
1795:"
1790:⇒
1785:"
1669:.
1662:X
1658:x
1652:Y
1648:y
1619:Y
1615:y
1609:X
1605:x
1591:.
1588:z
1584:y
1566:Y
1562:z
1558:y
1552:X
1548:x
1537:.
1534:z
1530:x
1512:Y
1508:y
1502:X
1498:z
1494:x
1475:y
1466:X
1462:x
1439:1
1433:2
1427:3
1420:R
1416:n
1412:x
1403:R
1395:X
1391:S
1379:.
1358:X
1354:z
1350:y
1346:x
1335:.
1332:z
1328:y
1322:z
1318:x
1312:y
1308:x
1284:X
1280:z
1276:y
1272:x
1266:)
1251:y
1247:x
1229:X
1225:y
1221:x
1193:X
1189:y
1185:x
1157:y
1153:x
1147:X
1143:y
1139:x
1126:.
1107:X
1103:z
1091:X
1087:y
1083:x
1065:x
1061:y
1054:y
1041:.
1035:R
1031:z
1027:x
1023:z
1019:y
1015:R
1011:y
1007:x
1002:X
998:z
994:y
990:x
977:.
938:X
934:z
930:y
926:x
888:X
884:z
880:y
876:x
871:R
859:.
838:X
834:z
830:y
826:x
792:X
788:z
784:y
780:x
762:x
734:X
730:y
726:x
706:y
702:x
684:X
680:y
676:x
663:.
661:x
657:y
653:y
649:x
632:X
628:y
624:x
595:x
591:y
557:X
553:y
549:x
536:.
521:X
517:y
513:x
500:.
485:X
481:y
477:x
461:y
457:x
445:X
441:y
437:x
415:X
411:x
405:)
384:X
380:x
364:X
360:R
318:.
315:2
312:x
308:1
305:x
299:2
293:1
290:x
282:X
278:x
274:x
270:x
266:I
244:2
238:1
235:x
230:;
227:X
223:X
219:U
204:2
198:1
195:x
190:;
187:∅
183:E
169:2
166:x
160:1
157:x
152:X
136:R
128:y
124:x
112:R
73:X
69:X
64:X
60:X
52:X
44:X
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
