Theory of Relations

R. Fraisse

• Publisher: North Holland
• Year: 2000
• Print ISBN: 9780444505422
• eBook ISBN: 9780080519111
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

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.

Chapter 1

Review of axiomatic set theory, ordinal, cardinal, aleph, relation, poset, chain

The purpose of this chapter is to situate precisely ”theory of relations” within the framework of axiomatic set theory, which initially will be that of ZERMELO-FRAENKEL. The axioms of ZF are introduced below in sections 1.1 and 1.2. Our initial notations will be introduced there. In referring to the first and sometimes second chapter, we will indicate throughout the book which statements require only the axioms of ZF and those which require, to our knowledge, the axiom of choice, or rather the weaker ultrafilter axiom (boolean prime ideal axiom), or the axiom of dependent choice, etc. Most of the proofs, as well as classical definitions from the first and second chapter, are left to the reader.

1.1 First group of axioms for ZF; finite set, axiom of choice, König’s theorem

We begin with the axioms of extensionality, pair, union, power set and the scheme of separation, all supposed known to the reader and going back to [252] ZERMELO 1908 (see Bibliography). We denote the empty set by 0, inclusion ⊆, strict inclusion ⊂. We denote the union of the set a by ⊆a (set of all elements of elements of a) and the power set by P(a) (set of all subsets of a). If b ⊆ a, we designate the difference by a − b. Singletons, unordered pairs (simply called pairs) are denoted by {a}, {a, b}, etc. Note that ∪{a} = a, that ∪ {a, b} is usually denoted a ∪ b, etc.

The successor set a∪{a} of a is denoted by a+1. So that 1 = 0+1 = {0} is the successor of the empty set; 2 = 1 + 1 = {0,1} is the successor of 1, etc. This notation coincides with the notation for ordinal addition, introduced in 1.3 below.

1.1.1 Finite set: Tarski’s definition

Following [241] TARSKI 1924, we define a set a to be finite iff every non-empty set b of subsets of a contains an element which is minimal with respect to inclusion, i.e. an element c ∈ b such that no x ∈ b satisfies x ⊂ c. Taking complements, it is equivalent to say that a is finite exactly when every non-empty set of subsets of a contains a maximal element. A non-finite set is said to be infinite.

The empty set, a singleton, a pair are finite sets. Every subset of a finite set is finite. If a is finite, then so is the set composed of a together with an additional element. In particular, the successor a + 1 of a is finite. If a and b are both finite, so is their union.

If a set a and all its elements are finite, then the union ∪a is finite. Indeed there exists at least a subset b of a such that ∪b is finite (singletons for example); take a maximal b and then prove that b = a. This is often expressed in the following form called pigeonhole principle: if we partition an infinite set into finitely many subsets, then at least one of these subsets is infinite.

Scheme of induction for finite sets. If a condition C is true for the empty set, and if for every set a satisfying C and every set u, the set a ∪ {u} satisfies C, then C is true for every finite set.

1.1.2 Couple (= ordered pair), cartesian product, function

Given two sets a, b, the couple or ordered pair (a, b) is the set {{a},{a, b}} formed of the singleton {a} and the (unordered) pair {a, b} This definition goes back to KURATOWSKI 1921 (see also AJDUKIEWICZ). The set a is said to be the first term and b the second term of the couple. Clearly two couples are equal iff they have the same first and the same second terms.

The cartesian product a × b is the set of couples (x, y) where x belongs to a and y belongs to b.

A function or mapping from a onto b is a subset f of a × b such that every element x of a appears as first term in exactly one couple (x, y) belonging to f and every element y of b appears as a second term in at least one couple belonging to f. The set a = Dom f is called the domain, the set b = Rng f is the range of f. For each element x of a, the second term y of the unique couple (x, y) having first term x is denoted y = f(x) or y = fx and is called the value of f on x, or the image of x under f. For every superset c ⊃ Rng f we say that f is a function from a into c.

The transformation

and its inverse. If u ⊆ Dom f, we denote by

the set of elements fx where x ∈ u The function thus denoted

is a function on the set of subsets of Dom f and is called the transformation associated with f. This ...

Table of contents

• Cover image
• Title page
• Table of Contents
• Studies in Logic and the Foundations of Mathematics
• Copyright page
• Introduction
• Chapter 1: Review of axiomatic set theory, ordinal, cardinal, aleph, relation, poset, chain
• Chapter 2: Real, well-founded poset, coherence lemma, cofinality, regular or singular aleph, tree, net or ideal
• Chapter 3: Ramsey theorems, partition theorems, incidence matrix, combinatorial principles, profile
• Chapter 4: Good and bad sequence, well partial ordering, dimension, extraction property, directed well partial ordering
• Chapter 5: Embeddability between relations, posets, chains; Suslin chain and tree, universal class
• Chapter 6: Scattered chain, right or left indecomposable chain, scattered poset, topology on initial intervals
• Chapter 7: Barrier, forerunning, well quasi-ordering of scattered chains, better partial ordering
• Chapter 8: Faithful extension of a relation, bivalent tableau, faithful augmentation, Szpilrajn chain
• Chapter 9: Local isomorphism, free operator, chainable and monomorphic relations, relational or strong interval
• Chapter 10: Age, rich relation, alpha-morphism, finitist and almost chainable relation, back-and-forth notions
• Chapter 11: Relative isomorphism, saturated relation, existence criterion, solid or fragil family, interval-closure
• Chapter 12: Homogeneous relation, orbit, connection with permutation groups
• Chapter 13: Bound of a relation, well relation, compatibility and chainability theorems, indicative group
• Appendix A: Partitions of countable homogeneous systems
• Bibliography
• Index