Relation theory originates with Hausdorff (Mengenlehre 1914) and Sierpinski (Nombres transfinis, 1928) with the study of order types, specially among chains = total orders = linear orders. One of its first important problems was partially solved by Dushnik, Miller 1940 who, starting from the chain of reals, obtained an infinite strictly decreasing sequence of chains (of continuum power) with respect to embeddability. In 1948 I conjectured that every strictly decreasing sequence of denumerable chains is finite. This was affirmatively proved by Laver (1968), in the more general case of denumerable unions of scattered chains (ie: which do not embed the chain Q of rationals), by using the barrier and the better orderin gof Nash-Williams (1965 to 68).
Another important problem is the extension to posets of classical properties of chains. For instance one easily sees that a chain A is scattered if the chain of inclusion of its initial intervals is itself scattered (6.1.4). Let us again define a scattered poset A by the non-embedding of Q in A. We say that A is finitely free if every antichain restriction of A is finite (antichain = set of mutually incomparable elements of the base). In 1969 Bonnet and Pouzet proved that a poset A is finitely free and scattered iff the ordering of inclusion of initial intervals of A is scattered. In 1981 Pouzet proved the equivalence with the a priori stronger condition that A is topologically scattered: (see 6.7.4; a more general result is due to Mislove 1984); ie: every non-empty set of initial intervals contains an isolated elements for the simple convergence topology.
In chapter 9 we begin the general theory of relations, with the notions of local isomorphism, free interpretability and free operator (9.1 to 9.3), which is the relationist version of a free logical formula. This is generalized by the back-and-forth notions in 10.10: the (k,p)-operator is the relationist version of the elementary formula (first order formula with equality).
Chapter 12 connects relation theory with permutations: theorem of the increasing number of orbits (Livingstone, Wagner in 12.4). Also in this chapter homogeneity is introduced, then more deeply studied in the Appendix written by Norbert Saucer.
Chapter 13 connects relation theory with finite permutation groups; the main notions and results are due to Frasnay. Also mention the extension to relations of adjacent elements, by Hodges, Lachlan, Shelah who by this mean give an exact calculus of the reduction threshold.
The book covers almost all present knowledge in Relation Theory, from origins (Hausdorff 1914, Sierpinski 1928) to classical results (Frasnay 1965, Laver 1968, Pouzet 1981) until recent important publications (Abraham, Bonnet 1999).
All results are exposed in axiomatic set theory. This allows us, for each statement, to specify if it is proved only from ZF axioms of choice, the continuum hypothesis or only the ultrafilter axiom or the axiom of dependent choice, for instance.
Introduction 5(8) Review of axiomatic set theory, relation 13(30) First group of axioms for ZF, finite set 13(5) Second group of axioms, ordinal, integer 18(6) Review of ordinal algebra 24(3) Transitive closure, fundamental rank, cardinal 27(3) Cardinality of the continuum 30(1) Binary relation, poset, chain, aleph 31(6) Relation, multirelation, restriction 37(3) Axiom of dependent choice 40(1) Exercises 41(2) Coherence lemma, cofinality, tree, ideal 43(36) Rational, real (chains Q and R) 43(2) Well-founded poset, maximal chain 45(3) Filter, ultrafilter axiom 48(2) Coherence lemma, ordering axiom 50(2) Set of initial intervals 52(1) Ordinal sum and product of chains; Dedekinds statement 53(2) Height, cofinal subset, confinality 55(3) Regular or singular aleph, accessibility 58(5) Augmentation: relation, poset 63(2) Partition in slices (Bonnet, Pouzet) 65(1) Tree 66(3) Confinality of a poset, confinal height 69(3) Net or directed poset, ideal 72(1) Computation of posets (Chaunier, Lygeros) 73(1) Exercises 74(5) Ramsey theorem, partition, incidence matrix 79(30) Ramseys theorem, Ramsey number 79(5) Lexico ordered set: Galvin, Nash-Williams 84(3) Partition theorems: Dushnik, Miller, Erdos, Rado 87(7) Linear independence: Kantor, multicolor: Pouzet 94(3) Combinatorial lemmas, color and inclusion 97(2) Profile increase theorem (Pouzet) 99(1) Ramsey sequence for Galvins theorem (Lopez) 100(3) Exercises 103(6) Good, bad sequence, well partial ordering 109(34) Less than relation, embedding between sequences 109(2) Good, bad, minimal bad sequence 111(5) Well partial ordering 116(1) Initial intervals of a w.p.o. : Higman, Rado 117(2) Extraction theorem, words: Higman 119(3) Well-ordered restrictions 122(2) Ideal and finitely free poset: Bonnet 124(2) Direct product of posets 126(2) Dimension: Dushnik, Miller, Hiraguchi 128(4) Bound 132(1) Maximal augmented chain: De Jongh, Parikh 133(2) Confinality of a finitely free poset 135(2) Cofinal restriction of a directed w.p.o (Pouzet) 137(4) Exercises 141(2) Embeddability between relations and chains 143(24) Embeddability, immediate extension (Hagendorf) 143(2) Embeddability between posets: Dilworth, Gleason 145(2) Dense chain; embeddability conditions 147(2) Well partial ordering of finite trees (Kruskal) 149(1) Decreasing sequences: Dushnik, Miller, Sierpinski 149(3) Immediate extension (chains): Hagendorf 152(1) Dense chain for an infinite cardinal 153(3) Suslin chain and Suslin tree 156(3) Aronszajn tree, Specker chain 159(2) Universal class (Tarski, Vaught) 161(3) Decreasing sequence of posets 164(1) K. Kunen A. Miller Exercises 165(2) Scattered chain, scattered poset 167(28) Scattered chain 167(2) Hausdorff decomposition, neighborhood 169(3) Right or left indecomposable chain 172(3) Covering by indecomposable chains or by doublets 175(3) Scattered poset: Bonnet, Pouzet 178(3) Simple convergence topology 181(4) Topologically scattered poset 185(4) Indivisible relation or chain 189(1) Rigid chain 190(1) Exercises 191(4) Well quasi-ordering of scattered chains 195(28) Barrier partition theorem: Nash-Williams 195(4) Barrier sequence, minimal bad sequence 199(2) Forerunning 201(4) Hereditarily indecomposable chain 205(3) Embeddability theorem (Laver) 208(3) Indecomposable sequence, better partial ordering 211(4) Better partial ordering w. r. to barriers 215(6) Exercises 221(2) Bivalent tableau, Szpilrajn chain 223(18) Faithful extension between relations 223(2) Faithful extension: chains (Hagendorf, Jullien) 225(2) Faithful infinite extension: Malitz, Lopez 227(2) Bivalent tableau (= bipartite graph) 229(2) C. Rauzy Poset of height 2 231(5) Hazim Sharif Szpilrajn chain, Julliens theorem 236(5) Free operator, chainability, strong interval 241(32) Permutation, transposition, local isomorphism 241(3) Free interpretability 244(3) Free operator 247(4) Constant relation 251(2) Chainable relation 253(5) Monomorphic relation 258(2) Tournament and monomorphy (Jean, Pouzet) 260(5) Relational or strong interval 265(2) Hausdorff construction: Abraham, Bonnet 267(4) Exercises 271(2) Age, α-morphism, back-and-forth 273(32) Projection filter, 1-extension, (1,p)-morphism 273(5) Closed under embeddability, age 278(3) Rich relation 281(1) α-morphism, non-embeddability rank 282(4) A relation rich for its age 286(2) Inexhaustible relation, inexhaustible age 288(3) A relation minimal for its age 291(1) Finitist relation 292(2) Almost chainable relation 294(4) Back-and-forth notions 298(4) Exercises 302(3) Relative isomorphism, saturated relation 305(26) Relative restriction, relative isomorphism, rel-age 305(2) Maximal rel-age, maximalist relation 307(3) Saturated subset, saturated relation 310(3) Criterion for a rich relation: Pouzet, Vaught 313(3) Solid or fragil family (Thomasse) 316(2) Solid or fragil morphism (Thomasse) 318(3) Interval-filter and interval-closure 321(3) Non-classical ultraproduct and ultrapower 324(2) Interval-closures: Ille 326(5) Homogeneous relation, orbit 331(20) Homogeneous relation 331(2) Amalgamable set, amalgamable age 333(2) Relational system, orbit, transitive group 335(4) Increasing number of orbits: Livingstone, Wagner 339(1) Extensive subset, pseudo-homogeneous relation 340(2) Pseudo-amalgamable age 342(2) Prehomogeneous relation 344(1) Isolated rel-age 345(3) Criterion for a prehomogeneous relation 348(1) Exercise 349(2) Compatibility and chainability theorems 351(36) Bound of a relation, bound of an age 351(3) Well relation 354(3) Compatibility and chainability theorems: Frasnay 357(3) Dilated group 360(2) Bichain, contracted group 362(2) Indicative group, indicator (Frasnay) 364(2) Q-bichain, Q-indicative group 366(5) Set-transitive group theorem (Cameron) 371(2) Indicative group theorem, reduction theorem 373(2) Reduction, compatibility theresholds 375(3) Adjacent elements: Hodges, Lachlan, Shelah 378(6) Exercises 384(3) A On countable homogeneous systems: Sauer 387 A.1 Some prominent homogeneous relations 387 A.2 Various types of amalgamation 392 A.3 Cutting finite pieces from homogeneous systems 397 A.4 Partitions of homogeneous relational systems 400 A.5 Coloring copies of relational systems 410
Biežāk uzdotie jautājumi par e-grāmatām