1321:
104:
1433:
each color partition the order into a family of unbounded dense countable linear orderings. Any partition of an unbounded dense countable linear orderings into subsets, with the property that each subset is unbounded (within the whole set, not just in itself) and dense (again, within the whole set) comes from a coloring in this way. Each two colorings with the same number of colors are order-isomorphic, under any permutation of their colors.
1456:, meaning that every subset of the reals that has a finite upper bound has a real least upper bound. They contain the rational numbers, which are dense in the real numbers. By applying the isomorphism theorem, Cantor proved that whenever a linear ordering has the same properties of being Dedekind-complete and containing a countable dense unbounded subset, it must be order-isomorphic to the real
1658:, various formalizations of the concept of an interval of time can be shown to be equivalent to defining an interval by a pair of distinct elements of a dense unbounded linear order. This connection implies that these theories are also countably categorical, and can be uniquely modeled by intervals of rational
1301:. This means that every logical sentence in the language of this theory is either a theorem, that is, provable as a logical consequence of the axioms, or the negation of a theorem. This is closely related to being categorical (a sentence is a theorem if it is true of the unique countable model; see the
1432:
The isomorphism theorem can be extended to colorings of an unbounded dense countable linear ordering, with a finite or countable set of colors, such that each color is dense, in the sense that a point of that color exists between any other two points of the whole ordering. The subsets of points with
1441:
and their complement; these two sets are dense in each other, and their union has an order isomorphism to any other pair of unbounded linear orders that are countable and dense in each other. Unlike Cantor's isomorphism theorem, the proof needs the full back-and-forth argument, and not just the
371:
by adding a new element from one order, the first missing element in its enumeration, and matching it with an order-equivalent element of the other order, proven to exist using the density and lack of endpoints of the order. The two orderings switch roles at each step: the proof finds the first
1305:) but there can exist multiple distinct models that have the same complete theory. In particular, both the ordering on the rational numbers and the ordering on the real numbers are models of the same theory, even though they are different models. Quantifier elimination can also be used in an
95:, a method for using logic to reason about time. In this application, the theorem implies that it is sufficient to use intervals of rational numbers to model intervals of time: using irrational numbers for this purpose will not lead to any increase in logical power.
1193:
908:
76:. The same back-and-forth method also proves that countable dense unbounded orders are highly symmetric, and can be applied to other kinds of structures. However, Cantor's original proof only used the "going forth" half of this method. In terms of
655:. These sentences include both axioms, formulating in logical terms the requirements of a dense linear order, and all other sentences that can be proven as logical consequences from those axioms. The axioms of this system can be expressed
601:
the order-equivalent element that is first in the second order's enumeration. This naturally finds an equivalence between the first ordering and a subset of the second ordering, and Cantor then argues that the entire second ordering is
1271:. For instance, the usual comparison relation on the rational numbers is a countable model of this theory. Cantor's isomorphism theorem can be expressed by saying that the first-order theory of unbounded dense linear orders is
1463:
asks whether orders having certain other properties of the order on the real numbers, including unboundedness, density, and completeness, must be order-isomorphic to the reals; the truth of this statement is independent of
1667:
stating that any two countable metric spaces without isolated points are homeomorphic can be seen as a topological analogue of Cantor's isomorphism theorem, and can be proved using a similar back-and-forth argument.
807:
2076:
but the strict comparison simplifies the expression of the axioms for the properties of being unbounded and dense. Note that it is not necessary to specify that these orders are antisymmetric, that is, that
1481:. Another consequence of Cantor's proof is that every finite or countable linear order can be embedded into the rationals, or into any unbounded dense ordering. Calling this a "well known" result of Cantor,
727:
247:
as the denominator. By Cantor's isomorphism theorem, the dyadic rational numbers are order-isomorphic to the whole set of rational numbers. In this example, an explicit order isomorphism is provided by
1332:, and consist of order-preserving bijections from the whole linear order to itself. By the back-and-forth method, every countable dense linear order has order automorphisms that map any set of
2122:
517:
by going "back and forth" between the enumeration for the first order and the enumeration for the second order, Cantor's original proof only uses the "going forth" half of the back-and-forth
1056:
964:
1419:
sets of points is summarized by saying that the group of symmetries of a countable dense linear order is "highly homogeneous". However, there is no order automorphism that maps an
239:
Within the rational numbers, certain subsets are also countable, unbounded, and dense. The rational numbers in the open unit interval are an example. Another example is the set of
624:
linear orders have a computable comparison predicate, and computable functions representing their density and unboundedness properties, then the isomorphism between them is also
1638:
is defined as the cardinality of the set of all countable ordinals). Baumgartner's axiom is consistent with ZFC and the negation of the continuum hypothesis, and implied by the
1107:
822:
462:
In an investigation of the history of this theorem by logician
Charles L. Silver, the earliest instance of the back-and-forth proof found by Silver was in a 1914 textbook by
1328:
The same back-and-forth method used to prove Cantor's isomorphism theorem also proves that countable dense linear orders are highly symmetric. Their symmetries are called
2495:
2423:
1636:
1609:
1580:
1541:
1514:
2074:
2054:
1611:
other elements. It states that each two such sets are order-isomorphic, providing in this way another higher-cardinality analogue of Cantor's isomorphism theorem (
1415:
1394:
1370:
1350:
1255:
1235:
1215:
1098:
1078:
1006:
986:
599:
579:
559:
539:
515:
495:
450:
430:
410:
390:
369:
349:
329:
309:
3307:
193:
of any two numbers belongs to the same set and lies between them, but the integers are not dense because is no other integer between any two consecutive
1477:
Although uncountable unbounded dense orderings may not be order-isomorphic, it follows from the back-and-forth method that any two such orderings are
2199:
1818:
458:
Although the back-and-forth method has also been attributed to Cantor, Cantor's original publication of this theorem in 1895â1897 used a different
643:
of unbounded dense linear orders consists of sentences in mathematical logic concerning variables that represent the elements of an order, with a
2150:; Worrell uses a different but equivalent axiomatization for strict linear orders, and combines the two unboundedness axioms into a single axiom.
122:
or total order is defined by a set of elements and a comparison operation that gives an ordering to each pair of distinct elements and obeys the
291:, in an ordering given by a countable enumeration of the two orderings. In more detail, the proof maintains two order-isomorphic finite subsets
452:, etc. Every element of each ordering is eventually matched with an order-equivalent element of the other ordering, so the two orderings are
1992:
Kirst, Dominik (2022), "Computational back-and-forth arguments in constructive type theory", in
Andronick, June; de Moura, Leonardo (eds.),
1854:
Bosi, G.; Mehta, G. B. (2002), "Existence of a semicontinuous or continuous utility function: a unified approach and an elementary proof",
1664:
3259:
742:
260:
It is also possible to apply the theorem to other linear orders whose elements are not defined as numbers. For instance, the binary
256:, the real roots of polynomials with integer coefficients. In this case, they are a superset of the rational numbers, but are again
3242:
2772:
676:
2608:
233:
With these definitions in hand, Cantor's isomorphism theorem states that every two unbounded countable dense linear orders are
204:
1778:
249:
147:
Unboundedness means that the ordering does not contain a minimum or maximum element. This is different from the concept of a
107:
46:
3089:
2080:
3225:
3084:
2263:
2030:
1856:
1725:
159:(0,1) is unbounded as an ordered set, even though it is bounded as a subset of the real numbers, because neither its
1324:
The graph of a piecewise linear order automorphism of rational numbers taking the four points {1,4,5,8} to {3,4,6,7}
1015:
923:
3079:
1465:
1263:
A model of this theory is any system of elements and a comparison relation that obeys all of the axioms; it is a
2797:
1797:
3116:
3036:
2501:
2250:, Springer Monographs in Mathematics (3rd millennium ed.), Berlin: Springer-Verlag, Theorem 4.3, p. 38,
49:
produces an isomorphism (a one-to-one order-preserving correspondence) between the numerical ordering of the
2901:
2830:
2710:
1188:{\displaystyle \forall a\,\forall b\,{\bigl (}a<b\Rightarrow \exists c\,(a<c\wedge c<b){\bigr )}}
903:{\displaystyle \forall a\,\forall b\,\forall c\,{\bigl (}(a<b\wedge b<c)\Rightarrow a<c{\bigr )}}
469:
2804:
2792:
2755:
2730:
2705:
2659:
2628:
1994:
13th
International Conference on Interactive Theorem Proving, ITP 2022, August 7â10, 2022, Haifa, Israel
1584:
sets of real numbers, unbounded sets with the property that every two elements are separated by exactly
3101:
2735:
2725:
2601:
2163:; Danhof, Kenneth J. (1973), "Variations on a theme of Cantor in the theory of relational structures",
617:
3074:
2740:
1373:
621:
609:
261:
3006:
2633:
1759:
Dasgupta, Abhijit (2014), "Chapters 7 & 8: Orders and order types; Dense and complete orders",
1302:
1272:
85:
2577:
Proceedings of the 6th
National Conference on Artificial Intelligence. Seattle, WA, USA, July 1987
3254:
3237:
2473:
2429:
2401:
2358:
2356:(1932), "Généralisation d'un théorÚme de Cantor concernant les ensembles ordonnés dénombrables",
1996:, LIPIcs, vol. 237, Schloss Dagstuhl â Leibniz-Zentrum fĂŒr Informatik, pp. 22:1â22:12,
1614:
1587:
1558:
1519:
1492:
1478:
2160:
3166:
2782:
2394:
2353:
1551:
1547:
1482:
1294:
2022:
1372:
points. This can also be proven directly for the ordering on the rationals, by constructing a
3302:
3297:
3292:
3144:
2979:
2970:
2839:
2720:
2674:
2638:
2594:
1297:
in the first-order theory of unbounded dense linear orders can be used to prove that it is a
284:
69:
64:, who first published it in 1895, using it to characterize the (uncountable) ordering on the
1712:, Texts and Readings in Mathematics, vol. 12, Berlin: Springer-Verlag, pp. 77â86,
3232:
3191:
3181:
3171:
2916:
2879:
2869:
2849:
2834:
2558:
2522:
2452:
2340:
2298:
2273:
2230:
2184:
2059:
1979:
1924:
1877:
1841:
1802:
1735:
1640:
1486:
2381:
2138:
2039:
252:. Another example of a countable unbounded dense linear order is given by the set of real
8:
3159:
3070:
3016:
2975:
2965:
2854:
2787:
2750:
1460:
913:
648:
265:
243:
numbers, the numbers that can be expressed as a fraction with an integer numerator and a
124:
2572:
3271:
3198:
3051:
2960:
2950:
2891:
2809:
2745:
2328:
2293:, Lecture Notes in Mathematics, vol. 405, Berlin & New York: Springer-Verlag,
2218:
1900:
1891:
Lohrey, Markus; Mathissen, Christian (2013), "Isomorphism of regular trees and words",
1425:
1400:
1379:
1355:
1335:
1329:
1280:
1240:
1220:
1200:
1083:
1063:
991:
971:
812:
732:
640:
584:
564:
544:
524:
500:
480:
435:
415:
395:
375:
354:
334:
314:
294:
81:
3111:
1869:
3208:
3186:
3046:
3031:
3011:
2814:
2259:
2026:
1774:
1721:
1647:
1453:
211:
42:
3021:
2874:
2544:
2510:
2438:
2377:
2367:
2320:
2251:
2208:
2172:
1997:
1910:
1865:
1827:
1764:
1713:
1705:
288:
253:
1963:
1816:
Girgensohn, Roland (1996), "Constructing singular functions via Farey fractions",
3203:
2986:
2864:
2859:
2844:
2760:
2669:
2654:
2554:
2518:
2448:
2336:
2294:
2269:
2226:
2180:
1975:
1920:
1873:
1837:
1731:
1469:
1438:
1298:
644:
464:
240:
190:
134:
73:
72:
that is also sometimes attributed to Cantor but was actually published later, by
54:
50:
1717:
279:
One proof of Cantor's isomorphism theorem, in some sources called "the standard
3121:
3106:
3096:
2955:
2933:
2911:
2549:
2466:
2002:
1655:
613:
331:
of the two given orders, initially empty. It repeatedly increases the sizes of
92:
1769:
1287:, there are multiple inequivalent dense unbounded linear orders with the same
3286:
3220:
3176:
3154:
3026:
2896:
2884:
2689:
2176:
1915:
1268:
652:
200:
156:
2443:
2372:
1320:
287:. This proof builds up an isomorphism between any two given orders, using a
3041:
2923:
2906:
2824:
2664:
2617:
2286:
1832:
1420:
647:
used as the comparison operation of the ordering. Here, a sentence means a
636:
244:
152:
119:
88:, meaning that it has only one countable model, up to logical equivalence.
77:
61:
26:
22:
2255:
2036:. The axioms can be formulated logically using either a strict comparison
581:
the first missing element of the first order's enumeration, and adding to
412:; then it finds the first missing element of the second order, adds it to
103:
3247:
2940:
2819:
2684:
2243:
1449:
1284:
223:
174:
148:
138:
65:
38:
34:
1944:(Doctoral dissertation), University of North Texas, p. 1, 305292986
1452:, an uncountable set. Unlike the rational numbers, the real numbers are
1448:
Cantor used the isomorphism theorem to characterize the ordering of the
635:
One way of describing Cantor's isomorphism theorem uses the language of
620:. This formalization process led to a strengthened result that when two
3215:
3149:
2990:
2514:
2332:
2222:
189:
The rational numbers and real numbers are dense in this sense, as the
167:
1 belong to the interval. The integers, rationals, and reals are also
3266:
3139:
2945:
1306:
226:
are order-isomorphic, under a bijection that multiplies each integer
215:
182:
114:
Cantor's isomorphism theorem is stated using the following concepts:
2324:
2213:
1703:
1434:
203:, but the real numbers do not, by a different result of Cantor, his
3061:
2928:
2679:
1704:
Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.;
164:
1905:
1437:
give as an example the partition of the rational numbers into the
110:
provides a concrete isomorphism from rationals to dyadic rationals
2165:
Zeitschrift fĂŒr
Mathematische Logik und Grundlagen der Mathematik
802:{\displaystyle \forall a\,\forall b\,(a=b\vee a<b\vee b<a)}
392:, matches it with an element of the second order, and adds it to
160:
130:
1485:
proved an analogous result for higher cardinality: assuming the
432:, matches it with an element of the first order, and adds it to
2586:
1942:
A computation of partial isomorphism rank on ordinal structures
2311:
Langford, C. H. (1926â1927), "Some theorems on deducibility",
815:
or total, meaning every two distinct elements are comparable.
80:, the isomorphism theorem can be expressed by saying that the
1423:
of points to its reverse, so these symmetries do not form a
722:{\displaystyle \forall a\,{\bigl (}\lnot (a<a){\bigr )}}
2124:; this is a consequence of irreflexivity and transitivity.
2019:
Propositional and
Predicate Calculus: A Model of Argument
91:
One application of Cantor's isomorphism theorem involves
177:
when every pair of elements has another element between
2469:(1981), "Martin's axiom does not imply that every two
2015:
For this axiomatization of strict linear orders, see:
2476:
2404:
2083:
2062:
2042:
1617:
1590:
1561:
1522:
1516:
into which all other linear orderings of cardinality
1495:
1403:
1382:
1358:
1338:
1243:
1223:
1203:
1110:
1086:
1066:
1018:
994:
974:
926:
825:
745:
679:
587:
567:
547:
527:
503:
483:
438:
418:
398:
378:
357:
337:
317:
297:
1554:
in 1973 to study the continuum hypothesis, concerns
2575:, in Forbus, Kenneth D.; Shrobe, Howard E. (eds.),
2535:van Benthem, Johan (1984), "Tense logic and time",
916:: each triple of elements is consistently ordered.
2489:
2417:
2116:
2068:
2048:
1630:
1603:
1574:
1535:
1508:
1409:
1388:
1364:
1344:
1249:
1229:
1209:
1187:
1092:
1072:
1050:
1000:
980:
958:
902:
801:
721:
608:The back-and-forth proof has been formalized as a
593:
573:
553:
533:
509:
489:
444:
424:
404:
384:
363:
343:
323:
303:
2285:
2200:Transactions of the American Mathematical Society
2197:Morley, Michael (1965), "Categoricity in power",
1819:Journal of Mathematical Analysis and Applications
1275:: it has only one countable model, up to logical
3284:
2117:{\displaystyle a<b\Rightarrow \lnot (b<a)}
1964:"Who invented Cantor's back-and-forth argument?"
1489:, there exists a linear ordering of cardinality
477:Instead of building up order-isomorphic subsets
1890:
372:missing element of the first order, adds it to
1051:{\displaystyle \forall a\,\exists b\,(a<b)}
959:{\displaystyle \forall a\,\exists b\,(b<a)}
2602:
2464:
2310:
1180:
1127:
895:
849:
714:
689:
181:This is different from being a topologically
199:The integers and rational numbers both form
2534:
2393:
2387:
2159:
1791:
1789:
1376:order automorphism with breakpoints at the
1309:for deciding whether a given sentence is a
521:It repeatedly augments the two finite sets
205:proof that the real numbers are uncountable
18:Uniqueness of countable dense linear orders
3308:Theorems in the foundations of mathematics
3260:Positive cone of a partially ordered group
2609:
2595:
2352:
2346:
2132:
2130:
1815:
1754:
1752:
1750:
1748:
1746:
1744:
2548:
2442:
2371:
2212:
2001:
1914:
1904:
1853:
1831:
1809:
1795:
1768:
1150:
1124:
1117:
1032:
1025:
940:
933:
846:
839:
832:
759:
752:
686:
98:
3243:Positive cone of an ordered vector space
2304:
1957:
1955:
1953:
1951:
1935:
1933:
1786:
1758:
1319:
102:
2136:
2127:
2016:
2009:
1763:, Springer New York, pp. 131â174,
1741:
1197:The order is dense: every two elements
1060:There is no upper bound; every element
968:There is no lower bound; every element
3285:
2570:
2564:
2528:
2196:
2190:
1961:
1939:
1798:"Curiosities of linearly ordered sets"
1796:Chekmasov, Andrei (October 23, 2019),
1699:
1697:
1695:
1693:
1691:
1689:
1687:
1685:
1683:
1681:
1396:given points. This equivalence of all
129:The familiar numeric orderings on the
2590:
2573:"Models of axioms for time intervals"
2148:(Lecture notes), University of Oxford
1991:
1948:
1930:
1884:
1847:
2242:
2236:
1985:
1710:Notes on infinite permutation groups
1281:categorical for higher cardinalities
1267:when the system of elements forms a
84:of unbounded dense linear orders is
2579:, Morgan Kaufmann, pp. 234â239
1678:
222:For instance, the integers and the
13:
2770:Properties & Types (
2537:Notre Dame Journal of Formal Logic
2478:
2458:
2427:sets of reals can be isomorphic",
2406:
2279:
2153:
2096:
1619:
1592:
1563:
1524:
1497:
1315:
1144:
1118:
1111:
1026:
1019:
934:
927:
840:
833:
826:
753:
746:
735:: no element is less than itself.
694:
680:
250:Minkowski's question-mark function
218:between them that preserves their
108:Minkowski's question-mark function
53:and the numerical ordering of the
47:Minkowski's question-mark function
14:
3319:
3226:Positive cone of an ordered field
1857:Journal of Mathematical Economics
3080:Ordered topological vector space
2616:
33:states that every two countable
2499:sets of reals are isomorphic",
630:
2289:; JohnsbrÄten, HÄvard (1974),
2111:
2099:
2093:
1175:
1151:
1141:
1045:
1033:
953:
941:
881:
878:
854:
796:
760:
709:
697:
1:
3037:Series-parallel partial order
2502:Israel Journal of Mathematics
1870:10.1016/S0304-4068(02)00058-7
1671:
2716:Cantor's isomorphism theorem
1708:(1997), "Rational numbers",
31:Cantor's isomorphism theorem
7:
2756:Szpilrajn extension theorem
2731:Hausdorff maximal principle
2706:Boolean prime ideal theorem
2490:{\displaystyle \aleph _{1}}
2418:{\displaystyle \aleph _{1}}
2056:or a non-strict comparison
1962:Silver, Charles L. (1994),
1893:Information and Computation
1718:10.1007/978-93-80250-91-5_9
1631:{\displaystyle \aleph _{1}}
1604:{\displaystyle \aleph _{1}}
1575:{\displaystyle \aleph _{1}}
1536:{\displaystyle \aleph _{1}}
1509:{\displaystyle \aleph _{1}}
1466:ZermeloâFraenkel set theory
1435:Bhattacharjee et al. (1997)
1352:points to any other set of
141:are all examples of linear
60:The theorem is named after
29:, branches of mathematics,
10:
3324:
3102:Topological vector lattice
2003:10.4230/LIPIcs.ITP.2022.22
618:interactive theorem prover
268:, form another isomorphic
264:that end in a 1, in their
3132:
3060:
2999:
2769:
2698:
2647:
2624:
2571:Ladkin, Peter B. (1987),
1770:10.1007/978-1-4614-8854-5
470:GrundzĂŒge der Mengenlehre
274:
216:one-to-one correspondence
2711:CantorâBernstein theorem
2550:10.1305/ndjfl/1093870515
2177:10.1002/malq.19730192604
1916:10.1016/j.ic.2013.01.002
68:. It can be proved by a
3255:Partially ordered group
3075:Specialization preorder
2444:10.4064/fm-79-2-101-106
2430:Fundamenta Mathematicae
2373:10.4064/fm-18-1-280-284
2359:Fundamenta Mathematicae
2137:Worrell, James (2016),
2017:Goldrei, Derek (2005),
1479:elementarily equivalent
610:computer-verified proof
2741:Kruskal's tree theorem
2736:KnasterâTarski theorem
2726:DushnikâMiller theorem
2491:
2419:
2118:
2070:
2050:
1881:; see Remark 3, p. 323
1833:10.1006/jmaa.1996.0370
1632:
1605:
1576:
1552:James Earl Baumgartner
1537:
1510:
1411:
1390:
1366:
1346:
1325:
1295:quantifier elimination
1251:
1231:
1211:
1189:
1094:
1074:
1052:
1002:
988:has a smaller element
982:
960:
904:
803:
723:
595:
575:
555:
535:
511:
491:
446:
426:
406:
386:
365:
345:
325:
305:
210:Two linear orders are
111:
99:Statement and examples
2492:
2420:
2395:Baumgartner, James E.
2313:Annals of Mathematics
2256:10.1007/3-540-44761-X
2119:
2071:
2069:{\displaystyle \leq }
2051:
1940:Bryant, Ross (2006),
1633:
1606:
1577:
1538:
1511:
1412:
1391:
1367:
1347:
1323:
1273:countably categorical
1252:
1232:
1212:
1190:
1095:
1080:has a larger element
1075:
1053:
1003:
983:
961:
905:
804:
724:
622:computably enumerable
596:
576:
556:
536:
512:
492:
447:
427:
407:
387:
366:
346:
326:
306:
285:back-and-forth method
106:
86:countably categorical
70:back-and-forth method
3233:Ordered vector space
2474:
2402:
2139:"Decidable theories"
2081:
2060:
2049:{\displaystyle <}
2040:
2021:, Springer, p.
1665:SierpiĆski's theorem
1641:proper forcing axiom
1615:
1588:
1559:
1520:
1493:
1487:continuum hypothesis
1401:
1380:
1356:
1336:
1241:
1221:
1201:
1108:
1084:
1064:
1016:
992:
972:
924:
823:
743:
677:
585:
565:
545:
525:
501:
481:
436:
416:
396:
376:
355:
335:
315:
295:
214:when there exists a
155:. For instance, the
3071:Alexandrov topology
3017:Lexicographic order
2976:Well-quasi-ordering
2291:The Souslin problem
1645:but independent of
1548:Baumgartner's axiom
1330:order automorphisms
1279:However, it is not
662:
649:well-formed formula
266:lexicographic order
3052:Transitive closure
3012:Converse/Transpose
2721:Dilworth's theorem
2515:10.1007/BF02761858
2487:
2415:
2354:SierpiĆski, WacĆaw
2171:(26â29): 411â426,
2114:
2066:
2046:
1628:
1601:
1572:
1533:
1506:
1426:2-transitive group
1407:
1386:
1362:
1342:
1326:
1247:
1227:
1207:
1185:
1090:
1070:
1048:
998:
978:
956:
900:
799:
719:
661:
641:first-order theory
591:
571:
551:
531:
507:
487:
442:
422:
402:
382:
361:
341:
321:
301:
112:
82:first-order theory
3280:
3279:
3238:Partially ordered
3047:Symmetric closure
3032:Reflexive closure
2775:
2315:, Second Series,
2161:BĂŒchi, J. Richard
1780:978-1-4614-8853-8
1706:Neumann, Peter M.
1483:WacĆaw SierpiĆski
1454:Dedekind-complete
1410:{\displaystyle k}
1389:{\displaystyle k}
1365:{\displaystyle k}
1345:{\displaystyle k}
1283:: for any higher
1261:
1260:
1250:{\displaystyle c}
1230:{\displaystyle b}
1210:{\displaystyle a}
1093:{\displaystyle b}
1073:{\displaystyle a}
1001:{\displaystyle b}
981:{\displaystyle a}
594:{\displaystyle B}
574:{\displaystyle A}
554:{\displaystyle B}
534:{\displaystyle A}
510:{\displaystyle B}
490:{\displaystyle A}
445:{\displaystyle A}
425:{\displaystyle B}
405:{\displaystyle B}
385:{\displaystyle A}
364:{\displaystyle B}
344:{\displaystyle A}
324:{\displaystyle B}
304:{\displaystyle A}
258:order-isomorphic.
254:algebraic numbers
235:order-isomorphic.
3315:
3022:Linear extension
2771:
2751:Mirsky's theorem
2611:
2604:
2597:
2588:
2587:
2581:
2580:
2568:
2562:
2561:
2552:
2532:
2526:
2525:
2509:(1â2): 161â176,
2498:
2496:
2494:
2493:
2488:
2486:
2485:
2462:
2456:
2455:
2446:
2426:
2424:
2422:
2421:
2416:
2414:
2413:
2391:
2385:
2384:
2375:
2350:
2344:
2343:
2308:
2302:
2301:
2287:Devlin, Keith J.
2283:
2277:
2276:
2240:
2234:
2233:
2216:
2194:
2188:
2187:
2157:
2151:
2149:
2143:
2134:
2125:
2123:
2121:
2120:
2115:
2075:
2073:
2072:
2067:
2055:
2053:
2052:
2047:
2035:
2013:
2007:
2006:
2005:
1989:
1983:
1982:
1959:
1946:
1945:
1937:
1928:
1927:
1918:
1908:
1888:
1882:
1880:
1851:
1845:
1844:
1835:
1813:
1807:
1806:
1793:
1784:
1783:
1772:
1756:
1739:
1738:
1701:
1661:
1651:
1644:
1637:
1635:
1634:
1629:
1627:
1626:
1610:
1608:
1607:
1602:
1600:
1599:
1583:
1581:
1579:
1578:
1573:
1571:
1570:
1550:, formulated by
1546:
1542:
1540:
1539:
1534:
1532:
1531:
1515:
1513:
1512:
1507:
1505:
1504:
1474:
1461:Suslin's problem
1459:
1445:
1439:dyadic rationals
1429:
1418:
1416:
1414:
1413:
1408:
1395:
1393:
1392:
1387:
1374:piecewise linear
1371:
1369:
1368:
1363:
1351:
1349:
1348:
1343:
1312:
1290:
1278:
1256:
1254:
1253:
1248:
1237:have an element
1236:
1234:
1233:
1228:
1216:
1214:
1213:
1208:
1194:
1192:
1191:
1186:
1184:
1183:
1131:
1130:
1099:
1097:
1096:
1091:
1079:
1077:
1076:
1071:
1057:
1055:
1054:
1049:
1007:
1005:
1004:
999:
987:
985:
984:
979:
965:
963:
962:
957:
909:
907:
906:
901:
899:
898:
853:
852:
808:
806:
805:
800:
728:
726:
725:
720:
718:
717:
693:
692:
663:
660:
658:
627:
605:
600:
598:
597:
592:
580:
578:
577:
572:
560:
558:
557:
552:
540:
538:
537:
532:
520:
516:
514:
513:
508:
496:
494:
493:
488:
474:
461:
455:
451:
449:
448:
443:
431:
429:
428:
423:
411:
409:
408:
403:
391:
389:
388:
383:
370:
368:
367:
362:
350:
348:
347:
342:
330:
328:
327:
322:
310:
308:
307:
302:
289:greedy algorithm
282:
271:
259:
236:
229:
221:
212:order-isomorphic
196:
188:
185:within the real
180:
170:
144:
135:rational numbers
128:
55:dyadic rationals
51:rational numbers
45:. For instance,
43:order-isomorphic
3323:
3322:
3318:
3317:
3316:
3314:
3313:
3312:
3283:
3282:
3281:
3276:
3272:Young's lattice
3128:
3056:
2995:
2845:Heyting algebra
2793:Boolean algebra
2765:
2746:Laver's theorem
2694:
2660:Boolean algebra
2655:Binary relation
2643:
2620:
2615:
2585:
2584:
2569:
2565:
2533:
2529:
2481:
2477:
2475:
2472:
2471:
2470:
2467:Shelah, Saharon
2463:
2459:
2409:
2405:
2403:
2400:
2399:
2398:
2392:
2388:
2351:
2347:
2325:10.2307/1968352
2309:
2305:
2284:
2280:
2266:
2241:
2237:
2214:10.2307/1994188
2195:
2191:
2158:
2154:
2146:Logic and Proof
2141:
2135:
2128:
2082:
2079:
2078:
2061:
2058:
2057:
2041:
2038:
2037:
2033:
2014:
2010:
1990:
1986:
1960:
1949:
1938:
1931:
1889:
1885:
1852:
1848:
1814:
1810:
1794:
1787:
1781:
1757:
1742:
1728:
1702:
1679:
1674:
1659:
1646:
1639:
1622:
1618:
1616:
1613:
1612:
1595:
1591:
1589:
1586:
1585:
1566:
1562:
1560:
1557:
1556:
1555:
1544:
1527:
1523:
1521:
1518:
1517:
1500:
1496:
1494:
1491:
1490:
1472:
1470:axiom of choice
1457:
1443:
1424:
1402:
1399:
1398:
1397:
1381:
1378:
1377:
1357:
1354:
1353:
1337:
1334:
1333:
1318:
1316:Related results
1310:
1303:ĆoĆâVaught test
1299:complete theory
1288:
1276:
1265:countable model
1242:
1239:
1238:
1222:
1219:
1218:
1202:
1199:
1198:
1179:
1178:
1126:
1125:
1109:
1106:
1105:
1085:
1082:
1081:
1065:
1062:
1061:
1017:
1014:
1013:
993:
990:
989:
973:
970:
969:
925:
922:
921:
894:
893:
848:
847:
824:
821:
820:
744:
741:
740:
713:
712:
688:
687:
678:
675:
674:
656:
645:binary relation
633:
625:
603:
586:
583:
582:
566:
563:
562:
546:
543:
542:
526:
523:
522:
518:
502:
499:
498:
482:
479:
478:
465:Felix Hausdorff
463:
459:
453:
437:
434:
433:
417:
414:
413:
397:
394:
393:
377:
374:
373:
356:
353:
352:
336:
333:
332:
316:
313:
312:
296:
293:
292:
280:
277:
269:
257:
241:dyadic rational
234:
227:
219:
194:
191:arithmetic mean
186:
178:
173:An ordering is
168:
142:
123:
101:
74:Felix Hausdorff
19:
12:
11:
5:
3321:
3311:
3310:
3305:
3300:
3295:
3278:
3277:
3275:
3274:
3269:
3264:
3263:
3262:
3252:
3251:
3250:
3245:
3240:
3230:
3229:
3228:
3218:
3213:
3212:
3211:
3206:
3199:Order morphism
3196:
3195:
3194:
3184:
3179:
3174:
3169:
3164:
3163:
3162:
3152:
3147:
3142:
3136:
3134:
3130:
3129:
3127:
3126:
3125:
3124:
3119:
3117:Locally convex
3114:
3109:
3099:
3097:Order topology
3094:
3093:
3092:
3090:Order topology
3087:
3077:
3067:
3065:
3058:
3057:
3055:
3054:
3049:
3044:
3039:
3034:
3029:
3024:
3019:
3014:
3009:
3003:
3001:
2997:
2996:
2994:
2993:
2983:
2973:
2968:
2963:
2958:
2953:
2948:
2943:
2938:
2937:
2936:
2926:
2921:
2920:
2919:
2914:
2909:
2904:
2902:Chain-complete
2894:
2889:
2888:
2887:
2882:
2877:
2872:
2867:
2857:
2852:
2847:
2842:
2837:
2827:
2822:
2817:
2812:
2807:
2802:
2801:
2800:
2790:
2785:
2779:
2777:
2767:
2766:
2764:
2763:
2758:
2753:
2748:
2743:
2738:
2733:
2728:
2723:
2718:
2713:
2708:
2702:
2700:
2696:
2695:
2693:
2692:
2687:
2682:
2677:
2672:
2667:
2662:
2657:
2651:
2649:
2645:
2644:
2642:
2641:
2636:
2631:
2625:
2622:
2621:
2614:
2613:
2606:
2599:
2591:
2583:
2582:
2563:
2527:
2484:
2480:
2465:Avraham, Uri;
2457:
2437:(2): 101â106,
2412:
2408:
2386:
2345:
2319:(1â4): 16â40,
2303:
2278:
2264:
2235:
2207:(2): 514â538,
2189:
2152:
2126:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2065:
2045:
2031:
2008:
1984:
1947:
1929:
1883:
1864:(3): 311â328,
1846:
1826:(1): 127â141,
1808:
1785:
1779:
1740:
1726:
1676:
1675:
1673:
1670:
1656:temporal logic
1648:Martin's axiom
1625:
1621:
1598:
1594:
1569:
1565:
1530:
1526:
1503:
1499:
1442:"going forth"
1406:
1385:
1361:
1341:
1317:
1314:
1259:
1258:
1257:between them.
1246:
1226:
1206:
1195:
1182:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1149:
1146:
1143:
1140:
1137:
1134:
1129:
1123:
1120:
1116:
1113:
1102:
1101:
1089:
1069:
1058:
1047:
1044:
1041:
1038:
1035:
1031:
1028:
1024:
1021:
1010:
1009:
997:
977:
966:
955:
952:
949:
946:
943:
939:
936:
932:
929:
918:
917:
912:Comparison is
910:
897:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
851:
845:
842:
838:
835:
831:
828:
817:
816:
811:Comparison is
809:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
758:
755:
751:
748:
737:
736:
731:Comparison is
729:
716:
711:
708:
705:
702:
699:
696:
691:
685:
682:
671:
670:
667:
653:free variables
632:
629:
590:
570:
550:
530:
506:
486:
441:
421:
401:
381:
360:
340:
320:
300:
276:
273:
231:
230:
208:
201:countable sets
197:
171:
145:
125:transitive law
100:
97:
93:temporal logic
17:
9:
6:
4:
3:
2:
3320:
3309:
3306:
3304:
3301:
3299:
3296:
3294:
3291:
3290:
3288:
3273:
3270:
3268:
3265:
3261:
3258:
3257:
3256:
3253:
3249:
3246:
3244:
3241:
3239:
3236:
3235:
3234:
3231:
3227:
3224:
3223:
3222:
3221:Ordered field
3219:
3217:
3214:
3210:
3207:
3205:
3202:
3201:
3200:
3197:
3193:
3190:
3189:
3188:
3185:
3183:
3180:
3178:
3177:Hasse diagram
3175:
3173:
3170:
3168:
3165:
3161:
3158:
3157:
3156:
3155:Comparability
3153:
3151:
3148:
3146:
3143:
3141:
3138:
3137:
3135:
3131:
3123:
3120:
3118:
3115:
3113:
3110:
3108:
3105:
3104:
3103:
3100:
3098:
3095:
3091:
3088:
3086:
3083:
3082:
3081:
3078:
3076:
3072:
3069:
3068:
3066:
3063:
3059:
3053:
3050:
3048:
3045:
3043:
3040:
3038:
3035:
3033:
3030:
3028:
3027:Product order
3025:
3023:
3020:
3018:
3015:
3013:
3010:
3008:
3005:
3004:
3002:
3000:Constructions
2998:
2992:
2988:
2984:
2981:
2977:
2974:
2972:
2969:
2967:
2964:
2962:
2959:
2957:
2954:
2952:
2949:
2947:
2944:
2942:
2939:
2935:
2932:
2931:
2930:
2927:
2925:
2922:
2918:
2915:
2913:
2910:
2908:
2905:
2903:
2900:
2899:
2898:
2897:Partial order
2895:
2893:
2890:
2886:
2885:Join and meet
2883:
2881:
2878:
2876:
2873:
2871:
2868:
2866:
2863:
2862:
2861:
2858:
2856:
2853:
2851:
2848:
2846:
2843:
2841:
2838:
2836:
2832:
2828:
2826:
2823:
2821:
2818:
2816:
2813:
2811:
2808:
2806:
2803:
2799:
2796:
2795:
2794:
2791:
2789:
2786:
2784:
2783:Antisymmetric
2781:
2780:
2778:
2774:
2768:
2762:
2759:
2757:
2754:
2752:
2749:
2747:
2744:
2742:
2739:
2737:
2734:
2732:
2729:
2727:
2724:
2722:
2719:
2717:
2714:
2712:
2709:
2707:
2704:
2703:
2701:
2697:
2691:
2690:Weak ordering
2688:
2686:
2683:
2681:
2678:
2676:
2675:Partial order
2673:
2671:
2668:
2666:
2663:
2661:
2658:
2656:
2653:
2652:
2650:
2646:
2640:
2637:
2635:
2632:
2630:
2627:
2626:
2623:
2619:
2612:
2607:
2605:
2600:
2598:
2593:
2592:
2589:
2578:
2574:
2567:
2560:
2556:
2551:
2546:
2542:
2538:
2531:
2524:
2520:
2516:
2512:
2508:
2504:
2503:
2482:
2468:
2461:
2454:
2450:
2445:
2440:
2436:
2432:
2431:
2410:
2397:(1973), "All
2396:
2390:
2383:
2379:
2374:
2369:
2365:
2362:(in French),
2361:
2360:
2355:
2349:
2342:
2338:
2334:
2330:
2326:
2322:
2318:
2314:
2307:
2300:
2296:
2292:
2288:
2282:
2275:
2271:
2267:
2265:3-540-44085-2
2261:
2257:
2253:
2249:
2245:
2239:
2232:
2228:
2224:
2220:
2215:
2210:
2206:
2202:
2201:
2193:
2186:
2182:
2178:
2174:
2170:
2166:
2162:
2156:
2147:
2140:
2133:
2131:
2108:
2105:
2102:
2090:
2087:
2084:
2063:
2043:
2034:
2032:9781846282294
2028:
2024:
2020:
2012:
2004:
1999:
1995:
1988:
1981:
1977:
1973:
1969:
1965:
1958:
1956:
1954:
1952:
1943:
1936:
1934:
1926:
1922:
1917:
1912:
1907:
1902:
1898:
1894:
1887:
1879:
1875:
1871:
1867:
1863:
1859:
1858:
1850:
1843:
1839:
1834:
1829:
1825:
1821:
1820:
1812:
1805:
1804:
1799:
1792:
1790:
1782:
1776:
1771:
1766:
1762:
1755:
1753:
1751:
1749:
1747:
1745:
1737:
1733:
1729:
1727:81-85931-13-5
1723:
1719:
1715:
1711:
1707:
1700:
1698:
1696:
1694:
1692:
1690:
1688:
1686:
1684:
1682:
1677:
1669:
1666:
1662:
1657:
1652:
1649:
1642:
1623:
1596:
1567:
1553:
1549:
1528:
1501:
1488:
1484:
1480:
1475:
1471:
1467:
1462:
1455:
1451:
1446:
1440:
1436:
1430:
1427:
1422:
1404:
1383:
1375:
1359:
1339:
1331:
1322:
1313:
1308:
1304:
1300:
1296:
1291:
1286:
1282:
1274:
1270:
1269:countable set
1266:
1244:
1224:
1204:
1196:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1147:
1138:
1135:
1132:
1121:
1114:
1104:
1103:
1087:
1067:
1059:
1042:
1039:
1036:
1029:
1022:
1012:
1011:
995:
975:
967:
950:
947:
944:
937:
930:
920:
919:
915:
911:
890:
887:
884:
875:
872:
869:
866:
863:
860:
857:
843:
836:
829:
819:
818:
814:
810:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
756:
749:
739:
738:
734:
730:
706:
703:
700:
683:
673:
672:
668:
665:
664:
659:
654:
650:
646:
642:
638:
628:
623:
619:
615:
611:
606:
588:
568:
561:by adding to
548:
528:
504:
484:
475:
472:
471:
466:
456:
439:
419:
399:
379:
358:
338:
318:
298:
290:
286:
272:
267:
263:
255:
251:
246:
242:
237:
225:
217:
213:
209:
206:
202:
198:
192:
184:
176:
172:
166:
162:
158:
157:open interval
154:
150:
146:
140:
136:
132:
126:
121:
117:
116:
115:
109:
105:
96:
94:
89:
87:
83:
79:
75:
71:
67:
63:
58:
56:
52:
48:
44:
40:
39:linear orders
36:
32:
28:
24:
16:
3303:Georg Cantor
3298:Order theory
3293:Model theory
3064:& Orders
3042:Star product
2971:Well-founded
2924:Prefix order
2880:Distributive
2870:Complemented
2840:Foundational
2805:Completeness
2761:Zorn's lemma
2715:
2665:Cyclic order
2648:Key concepts
2618:Order theory
2576:
2566:
2540:
2536:
2530:
2506:
2500:
2460:
2434:
2428:
2389:
2363:
2357:
2348:
2316:
2312:
2306:
2290:
2281:
2247:
2244:Jech, Thomas
2238:
2204:
2198:
2192:
2168:
2164:
2155:
2145:
2018:
2011:
1993:
1987:
1974:(1): 74â78,
1971:
1968:Modern Logic
1967:
1941:
1896:
1892:
1886:
1861:
1855:
1849:
1823:
1817:
1811:
1801:
1760:
1709:
1663:
1653:
1476:
1450:real numbers
1447:
1431:
1421:ordered pair
1327:
1293:A method of
1292:
1289:cardinality.
1277:equivalence.
1264:
1262:
669:Explanation
651:that has no
637:model theory
634:
631:Model theory
607:
476:
468:
457:
278:
245:power of two
238:
232:
224:even numbers
153:metric space
139:real numbers
120:linear order
113:
90:
78:model theory
66:real numbers
62:Georg Cantor
59:
30:
27:model theory
23:order theory
20:
15:
3248:Riesz space
3209:Isomorphism
3085:Normal cone
3007:Composition
2941:Semilattice
2850:Homogeneous
2835:Equivalence
2685:Total order
2543:(1): 1â16,
2366:: 280â284,
1285:cardinality
733:irreflexive
626:computable.
454:isomorphic.
149:bounded set
3287:Categories
3216:Order type
3150:Cofinality
2991:Well-order
2966:Transitive
2855:Idempotent
2788:Asymmetric
2382:0004.20502
2248:Set theory
1899:: 71â105,
1761:Set Theory
1672:References
914:transitive
169:unbounded.
163:0 nor its
37:unbounded
3267:Upper set
3204:Embedding
3140:Antichain
2961:Tolerance
2951:Symmetric
2946:Semiorder
2892:Reflexive
2810:Connected
2479:ℵ
2407:ℵ
2097:¬
2094:⇒
2064:≤
1906:1102.2782
1803:Chalkdust
1620:ℵ
1593:ℵ
1564:ℵ
1545:embedded.
1525:ℵ
1498:ℵ
1468:with the
1444:argument.
1307:algorithm
1164:∧
1145:∃
1142:⇒
1119:∀
1112:∀
1027:∃
1020:∀
935:∃
928:∀
882:⇒
867:∧
841:∀
834:∀
827:∀
813:connected
785:∨
773:∨
754:∀
747:∀
695:¬
681:∀
604:included.
283:uses the
270:ordering.
220:ordering.
195:integers.
183:dense set
3062:Topology
2929:Preorder
2912:Eulerian
2875:Complete
2825:Directed
2815:Covering
2680:Preorder
2639:Category
2634:Glossary
2246:(2003),
1660:numbers.
1458:numbers.
1417:-element
1311:theorem.
187:numbers.
165:supremum
131:integers
3167:Duality
3145:Cofinal
3133:Related
3112:Fréchet
2989:)
2865:Bounded
2860:Lattice
2833:)
2831:Partial
2699:Results
2670:Lattice
2559:0723616
2523:0599485
2453:0317934
2341:1502760
2333:1968352
2299:0384542
2274:1940513
2231:0175782
2223:1994188
2185:0337567
1980:1253680
1925:3016459
1878:1940365
1842:1412484
1736:1632579
1543:can be
519:method.
281:proof",
262:strings
228:by two.
161:infimum
143:orders.
3192:Subnet
3172:Filter
3122:Normed
3107:Banach
3073:&
2980:Better
2917:Strict
2907:Graded
2798:topics
2629:Topics
2557:
2521:
2497:-dense
2451:
2425:-dense
2380:
2339:
2331:
2297:
2272:
2262:
2229:
2221:
2183:
2029:
1978:
1923:
1876:
1840:
1777:
1734:
1724:
1582:-dense
1473:(ZFC).
666:Axiom
639:. The
612:using
467:, his
460:proof.
275:Proofs
137:, and
3182:Ideal
3160:Graph
2956:Total
2934:Total
2820:Dense
2329:JSTOR
2219:JSTOR
2142:(PDF)
1901:arXiv
616:, an
179:them.
175:dense
151:in a
35:dense
2773:list
2260:ISBN
2106:<
2088:<
2044:<
2027:ISBN
1775:ISBN
1722:ISBN
1217:and
1170:<
1158:<
1136:<
1040:<
948:<
888:<
873:<
861:<
791:<
779:<
704:<
541:and
497:and
351:and
311:and
41:are
25:and
3187:Net
2987:Pre
2545:doi
2511:doi
2439:doi
2378:Zbl
2368:doi
2321:doi
2252:doi
2209:doi
2205:114
2173:doi
2023:193
1998:doi
1911:doi
1897:224
1866:doi
1828:doi
1824:203
1765:doi
1714:doi
1654:In
657:as:
614:Coq
21:In
3289::
2555:MR
2553:,
2541:25
2539:,
2519:MR
2517:,
2507:38
2505:,
2449:MR
2447:,
2435:79
2433:,
2376:,
2364:18
2337:MR
2335:,
2327:,
2317:28
2295:MR
2270:MR
2268:,
2258:,
2227:MR
2225:,
2217:,
2203:,
2181:MR
2179:,
2169:19
2167:,
2144:,
2129:^
2025:,
1976:MR
1970:,
1966:,
1950:^
1932:^
1921:MR
1919:,
1909:,
1895:,
1874:MR
1872:,
1862:38
1860:,
1838:MR
1836:,
1822:,
1800:,
1788:^
1773:,
1743:^
1732:MR
1730:,
1720:,
1680:^
1100:.
1008:.
133:,
118:A
57:.
2985:(
2982:)
2978:(
2829:(
2776:)
2610:e
2603:t
2596:v
2547::
2513::
2483:1
2441::
2411:1
2370::
2323::
2254::
2211::
2175::
2112:)
2109:a
2103:b
2100:(
2091:b
2085:a
2000::
1972:4
1913::
1903::
1868::
1830::
1767::
1716::
1650:.
1643:,
1624:1
1597:1
1568:1
1529:1
1502:1
1428:.
1405:k
1384:k
1360:k
1340:k
1245:c
1225:b
1205:a
1181:)
1176:)
1173:b
1167:c
1161:c
1155:a
1152:(
1148:c
1139:b
1133:a
1128:(
1122:b
1115:a
1088:b
1068:a
1046:)
1043:b
1037:a
1034:(
1030:b
1023:a
996:b
976:a
954:)
951:a
945:b
942:(
938:b
931:a
896:)
891:c
885:a
879:)
876:c
870:b
864:b
858:a
855:(
850:(
844:c
837:b
830:a
797:)
794:a
788:b
782:b
776:a
770:b
767:=
764:a
761:(
757:b
750:a
715:)
710:)
707:a
701:a
698:(
690:(
684:a
589:B
569:A
549:B
529:A
505:B
485:A
473:.
440:A
420:B
400:B
380:A
359:B
339:A
319:B
299:A
207:.
127:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.