1966/01/01 by J. D. Halpern, H. Läuchli · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Advanced Graph Theory Research #Mathematics #Partition (number theory) #Combinatorics #Discrete mathematics #Finite set #Axiom of choice #Axiom #Set (abstract data type) #Set theory
paper · pdf · doi:10.1090/s0002-9947-1966-0200172-2
openalex publication_date 1966/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
We prove a partition theorem (in the sense of the theorems of Ramsey [3], Erds-Rado [1], and Rado [2]) which together with a forthcoming paper by Halpern and A. Levy will constitute a proof of the independence of the axiom of choice from the Boolean prime ideal theorem in Zermelo-Fraenkel set theory with the axiom of regularity.Although the theorem arises in logic, it is of a purely combinatorial character and, we believe, interesting in its own right.One application is as follows.Let P be a partition of /t X R (R being the rational numbers) into two parts, i.e.P P0,Pi, P0r\Py = 0, P0 yjPy= R x R. Thus P determines a matrix of O's and 1 'sWhat kind of solid submatrices are there?(a solid submatrix is a subset of R x R of the form Ax B, whose entries are either all O's or all l's).Results of Rado [2] tell us that for any positive integers m, n there are A, BezzR, \A = n, |P| = m and A x B is solid.Our theorem implies that A, B can be found satisfying additional properties of separation or scattering in R. The finite version gives similar results for the case where R is replaced by any large finite set.The theorem is applicable to all finite dimensions (not just d = 2 as in the example).In fact much of the difficulty in the proof was generalizing from dimension 2 to higher dimensions.The proof is novel in the sense that we accomplish it by means of metamathematical techniques.Thus the proof we give is in some sense dissatisfying.We have tried to eliminate the use of metamathematics without success and would welcome a simplification in this direction 1).1. Notation, terminology and results.A tree &~=<fF, ^> is a partially ordered set such that the set of predecessors of x, i.e. y:y < x, for each node x, i= xe T), is totally ordered.The cardinality of this set is called the order of x or the level at which x occurs.Afinitistic tree is a tree with a least element, all of whose nodes have finite orders and such that each level is a finite set.It follows that the set of immediate successors of any node of a finitistic tree is