Sunflower (Mathematics)

Sunflower (mathematics) From Wikipedia, the free encyclopedia Contents 1 Combinatorics 1 1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Approaches and subfields of combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Enumerative combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 Analytic combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.3 Partition theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.4 Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.5 Design theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.6 Finite geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.7 Order theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.8 Matroid theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.9 Extremal combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.10 Probabilistic combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.11 Algebraic combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.12 Combinatorics on words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.13 Geometric combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.14 Topological combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.15 Arithmetic combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.16 Infinitary combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Related fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Combinatorial optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.2 Coding theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.3 Discrete and computational geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.4 Combinatorics and dynamical systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.5 Combinatorics and physics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Continuum hypothesis 17 2.1 Cardinality of infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Independence from ZFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 i ii CONTENTS 2.3 Arguments for and against CH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 The generalized continuum hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Implications of GCH for cardinal exponentiation . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Forcing (mathematics) 22 3.1 Intuitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Forcing posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 P-names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.2 Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Countable transitive models and generic filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.6 Cohen forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.7 The countable chain condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.8 Easton forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.9 Random reals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.10 Boolean-valued models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.11 Meta-mathematical explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.12 Logical explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.13 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.14 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.15 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 Partially ordered set 30 4.1 Formal definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Extrema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4 Orders on the Cartesian product of partially ordered sets . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 Sums of partially ordered sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.6 Strict and non-strict partial orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.7 Inverse and order dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.8 Mappings between partially ordered sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.9 Number of partial orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.10 Linear extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.11 In category theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.12 Partial orders in topological spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.13 Interval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.14 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 CONTENTS iii 4.15 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.16 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.17 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5 Sunflower (mathematics) 37 5.1 Δ lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Δ lemma for !2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Sunflower lemma and conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.4 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6 Upper and lower bounds 39 6.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.3 Bounds of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.4 Tight bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 7 Zermelo–Fraenkel set theory 41 7.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 7.2 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.2.1 1. Axiom of extensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.2.2 2. Axiom of regularity (also called the Axiom of foundation) . . . . . . . . . . . . . . . . 42 7.2.3 3. Axiom schema of specification (also called the axiom schema of separation or of restricted comprehension) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.2.4 4. Axiom of pairing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.2.5 5. Axiom of union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.2.6 6. Axiom schema of replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7.2.7 7. Axiom of infinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 7.2.8 8. Axiom of power set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 7.2.9 9. Well-ordering theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 7.3 Motivation via the cumulative hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7.4 Metamathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7.4.1 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7.5 Criticisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7.6 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.8 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.9 Text and image sources, contributors, and licenses . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.9.1 Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.9.2 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.9.3 Content license . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Chapter 1 Combinatorics Not to be confused with combinatoriality. Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding “largest”, “smallest”, or “optimal” objects (extremal combinatorics and combinatorial optimization), and studying combinatorial structures arising in an algebraic context, or applying algebraic techniques to combinatorial problems (algebraic combinatorics). Combinatorial problems arise inmany areas of puremathematics, notably in algebra, probability theory, topology, and geometry,[1] and combinatorics also has many applications in mathematical optimization, computer science, ergodic theory and statistical physics. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory, which also has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms. A mathematician who studies combinatorics is called a combinatorialist or a combinatorist. 1.1 History Main article: History of combinatorics Basic combinatorial concepts and enumerative results appeared throughout the ancient world. In 6th century BCE, ancient Indian physician Sushruta asserts in Sushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 26 − 1 possibilities. Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to Schröder numbers.[2][3] In theOstomachion, Archimedes (3rd century BCE) considers a tiling puzzle. In the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. The Indian mathematician Mahāvīra (c. 850) provided formulae for the number of permutations and combinations,[4][5] and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE.[6] The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) established the symmetry of binomial coefficients, while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321.[7] The arithmetical triangle— a graphical diagram showing relationships among the binomial coefficients— was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal’s triangle. Later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations.[8] During the Renaissance, together with the rest of mathematics and the sciences, combinatorics enjoyed a rebirth. 1 2 CHAPTER 1. COMBINATORICS Works of Pascal, Newton, Jacob Bernoulli and Euler became foundational in the emerging field. In modern times, the works of J. J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) laid the foundation for enumerative and algebraic combinatorics. Graph theory also enjoyed an explosion of interest at the same time, especially in connection with the four color problem. In the second half of 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject.[9] In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory, etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field. 1.2 Approaches and subfields of combinatorics 1.2.1 Enumerative combinatorics Main article: Enumerative combinatorics Enumerative combinatorics is the most classical area of combinatorics, and concentrates on counting the number of certain combinatorial objects. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. Fibonacci numbers is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a unified framework for counting permutations, combinations and partitions. 1.2.2 Analytic combinatorics Main article: Analytic combinatorics Analytic combinatorics concerns the enumeration of combinatorial structures using tools from complex analysis and probability theory. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae. 1.2.3 Partition theory Main article: Partition theory Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series, special functions and orthogonal polynomials. Originally a part of number theory and analysis, it is now considered a part of combinatorics or an independent field. It incorporates the bijective approach and various tools in analysis, analytic number theory, and has connections with statistical mechanics. 1.2.4 Graph theory Main article: Graph theory Graphs are basic objects in combinatorics. The questions range from counting (e.g., the number of graphs on n vertices with k edges) to structural (e.g., which graphs contain Hamiltonian cycles) to algebraic questions (e.g., given a graph G and two numbers x and y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?). It should be noted that while there are very strong connections between graph theory and combinatorics, these two are sometimes thought of as separate subjects.[10] 1.2. APPROACHES AND SUBFIELDS OF COMBINATORICS 3 1.2.5 Design theory Main article: Combinatorial design Design theory is a study of combinatorial designs, which are collections of subsets with certain intersection properties. Block designs are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in Kirkman’s schoolgirl problem proposed in 1850. The solution of the problem is a special case of a Steiner system, which systems play an important role in the classification of finite simple groups. The area has further connections to coding theory and geometric combinatorics. 1.2.6 Finite geometry Main article: Finite geometry Finite geometry is the study of geometric systems having only a finite number of points. Structures analogous to those found in continuous geometries (Euclidean plane, real projective space, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for design theory. It should not be confused with discrete geometry (combinatorial geometry). 1.2.7 Order theory Main article: Order theory Order theory is the study of partially ordered sets, both finite and infinite. Various examples of partial orders appear in algebra, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and Boolean algebras. 1.2.8 Matroid theory Main article: Matroid theory Matroid theory abstracts part of geometry. It studies the properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a linear dependence relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced by Hassler Whitney and studied as a part of the order theory. It is now an independent field of study with a number of connections with other parts of combinatorics. 1.2.9 Extremal combinatorics Main article: Extremal combinatorics Extremal combinatorics studies extremal questions on set systems. The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest triangle-free graph on 2n vertices is a complete bipartite graph Kn,n. Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate. Ramsey theory is another part of extremal combinatorics. It states that any sufficiently large configuration will contain some sort of order. It is an advanced generalization of the pigeonhole principle. 1.2.10 Probabilistic combinatorics Main article: Probabilistic method 4 CHAPTER 1. COMBINATORICS In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph? For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as the probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time. Often associated with Paul Erdős, who did the pioneer work on the subject, probabilistic combinatorics was tradi- tionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analysis of algorithms in computer science, as well as classical probability, additive and probabilistic number theory, the area recently grew to become an independent field of combinatorics. 1.2.11 Algebraic combinatorics Main article: Algebraic combinatorics Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. Algebraic combinatorics is continuously expanding its scope, in both topics and techniques, and can be seen as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. 1.2.12 Combinatorics on words Main article: Combinatorics on words Combinatorics on words deals with formal languages. It arose independently within several branches of mathematics, including number theory, group theory and probability. It has applications to enumerative combinatorics, fractal analysis, theoretical computer science, automata theory and linguistics. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best known result in the field. 1.2.13 Geometric combinatorics Main article: Geometric combinatorics Geometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, how many faces of each dimension can a convex polytope have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. We should note that combinatorial geometry is an old fashioned name for discrete geometry. 1.2.14 Topological combinatorics Main article: Topological combinatorics Combinatorial analogs of concepts and methods in topology are used to study graph coloring, fair division, partitions, partially ordered sets, decision trees, necklace problems and discrete Morse theory. It should not be confused with combinatorial topology which is an older name for algebraic topology. 1.3. RELATED FIELDS 5 1.2.15 Arithmetic combinatorics Main article: Arithmetic combinatorics Arithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive combinatorics refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the ergodic theory of dynamical systems. 1.2.16 Infinitary combinatorics Main article: Infinitary combinatorics Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of set theory, an area of mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics. Gian-Carlo Rota used the name continuous combinatorics[11] to describe probability and measure theory, since there are many analogies between counting and measure. 1.3 Related fields 1.3.1 Combinatorial optimization Combinatorial optimization is the study of optimization on discrete and combinatorial objects. It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. 1.3.2 Coding theory Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes. The main idea of the subject is to design efficient and reliable methods of data transmission. It is now a large field of study, part of information theory. 1.3.3 Discrete and computational geometry Discrete geometry (also called combinatorial geometry) also began a part of combinatorics, with early results on convex polytopes and kissing numbers. With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study. There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry. 1.3.4 Combinatorics and dynamical systems Combinatorial aspects of dynamical systems is another emerging field. Here dynamical systems can be defined on combinatorial objects. See for example graph dynamical system. 1.3.5 Combinatorics and physics There are increasing interactions between combinatorics and physics, particularly statistical physics. Examples include an exact solution of the Ising model, and a connection between the Potts model on one hand, and the chromatic and Tutte polynomials on the other hand. 6 CHAPTER 1. COMBINATORICS 1.4 See also � Combinatorial biology � Combinatorial chemistry � Combinatorial data analysis � Combinatorial game theory � Combinatorial group theory � List of combinatorics topics � Phylogenetics 1.5 Notes [1] Björner and Stanley, p. 2 [2] Stanley, Richard P.; “Hipparchus, Plutarch, Schröder, and Hough”, American Mathematical Monthly 104 (1997), no. 4, 344–350. [3] Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; “On the Second Number of Plutarch”, American Mathematical Monthly 105 (1998), no. 5, 446. [4] O'Connor, John J.; Robertson, Edmund F., “Combinatorics”, MacTutor History of Mathematics archive, University of St Andrews. [5] Puttaswamy, Tumkur K. (2000), “The Mathematical Accomplishments of Ancient Indian Mathematicians”, in Selin, Helaine, Mathematics Across Cultures: The History of Non-Western Mathematics, Netherlands: Kluwer Academic Pub- lishers, p. 417, ISBN 978-1-4020-0260-1 [6] Biggs, Norman L. (1979). “The Roots of Combinatorics”. Historia Mathematica 6: 109–136. [7] Maistrov, L. E. (1974), Probability Theory: A Historical Sketch, Academic Press, p. 35, ISBN 9781483218632. (Transla- tion from 1967 Russian ed.) [8] White, Arthur T.; “Ringing the Cosets”, American Mathematical Monthly, 94 (1987), no. 8, 721–746; White, Arthur T.; “Fabian Stedman: The First Group Theorist?", American Mathematical Monthly, 103 (1996), no. 9, 771–778. [9] See Journals in Combinatorics and Graph Theory [10] Sanders, Daniel P.; 2-Digit MSC Comparison [11] Continuous and profinite combinatorics 1.6 References � Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany � Bóna, Miklós; (2011); A Walk Through Combinatorics (3rd Edition). ISBN 978-981-4335-23-2, ISBN 978- 981-4460-00-2(pbk) � Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); Handbook of Combinatorics, Vol- umes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. ISBN 0-262- 07169-X � Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press; 1st. edition (Oc- tober 31, 1997). ISBN 0-8493-3986-3. � Riordan, John (1958); An Introduction to Combinatorial Analysis, New York, NY: Wiley & Sons (republished) � Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1 � van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd Edition, Cambridge University Press. ISBN 0-521-80340-3 1.7. EXTERNAL LINKS 7 1.7 External links � Hazewinkel, Michiel, ed. (2001), “Combinatorial analysis”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 � Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition � Combinatorics, a MathWorld article with many references. � Combinatorics, from a MathPages.com portal. � The Hyperbook of Combinatorics, a collection of math articles links. � The Two Cultures of Mathematics by W. T. Gowers, article on problem solving vs theory building. 8 CHAPTER 1. COMBINATORICS An example of change ringing (with six bells), one of the earliest nontrivial results in Graph Theory. 1.7. EXTERNAL LINKS 9 Five binary trees on three vertices, an example of Catalan numbers. A plane partition. 10 CHAPTER 1. COMBINATORICS Petersen graph. 1.7. EXTERNAL LINKS 11 {x,y,z} {y,z}{x,z}{x,y} {y} {z}{x} Ø Hasse diagram of the powerset of {x,y,z} ordered by inclusion. 12 CHAPTER 1. COMBINATORICS Self-avoiding walk in a square grid graph. 1.7. EXTERNAL LINKS 13 Young diagram of a partition (5,4,1). Construction of a Thue–Morse infinite word. 14 CHAPTER 1. COMBINATORICS An icosahedron. 1.7. EXTERNAL LINKS 15 Splitting a necklace with two cuts. 16 CHAPTER 1. COMBINATORICS Kissing spheres are connected to both coding theory and discrete geometry. Chapter 2 Continuum hypothesis This article is about the hypothesis in set theory. For the assumption in fluid mechanics, see Fluid mechanics. In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. It states: There is no set whose cardinality is strictly between that of the integers and the real numbers. The continuum hypothesis was advanced by Georg Cantor in 1878, and establishing its truth or falsehood is the first of Hilbert’s 23 problems presented in the year 1900. Τhe answer to this problem is independent of ZFC set theory, so that either the continuum hypothesis or its negation can be added as an axiom to ZFC set theory, with the resulting theory being consistent if and only if ZFC is consistent. This independence was proved in 1963 by Paul Cohen, complementing earlier work by Kurt Gödel in 1940. The name of the hypothesis comes from the term the continuum for the real numbers. It is abbreviated CH. 2.1 Cardinality of infinite sets Main article: Cardinal number Two sets are said to have the same cardinality or cardinal number if there exists a bijection (a one-to-one correspon- dence) between them. Intuitively, for two sets S and T to have the same cardinality means that it is possible to “pair off” elements of S with elements of T in such a fashion that every element of S is paired off with exactly one element of T and vice versa. Hence, the set fbanana; apple; pearg has the same cardinality as fyellow; red; greeng . With infinite sets such as the set of integers or rational numbers, this becomes more complicated to demonstrate. The rational numbers seemingly form a counterexample to the continuum hypothesis: the integers form a proper subset of the rationals, which themselves form a proper subset of the reals, so intuitively, there are more rational numbers than integers, and more real numbers than rational numbers. However, this intuitive analysis does not take account of the fact that all three sets are infinite. It turns out the rational numbers can actually be placed in one-to-one correspondence with the integers, and therefore the set of rational numbers is the same size (cardinality) as the set of integers: they are both countable sets. Cantor gave two proofs that the cardinality of the set of integers is strictly smaller than that of the set of real numbers (see Cantor’s first uncountability proof and Cantor’s diagonal argument). His proofs, however, give no indication of the extent to which the cardinality of the integers is less than that of the real numbers. Cantor proposed the continuum hypothesis as a possible solution to this question. The hypothesis states that the set of real numbers has minimal possible cardinality which is greater than the cardinality of the set of integers. Equivalently, as the cardinality of the integers is @0 ("aleph-naught") and the cardinality of the real numbers is 2@0 (i.e. it equals the cardinality of the power set of the integers), the continuum hypothesis says that there is no set S for which @0 < jSj < 2@0 : 17 18 CHAPTER 2. CONTINUUM HYPOTHESIS Assuming the axiom of choice, there is a smallest cardinal number @1 greater than @0 , and the continuum hypothesis is in turn equivalent to the equality 2@0 = @1: A consequence of the continuum hypothesis is that every infinite subset of the real numbers either has the same cardinality as the integers or the same cardinality as the entire set of the reals. There is also a generalization of the continuum hypothesis called the generalized continuum hypothesis (GCH) which says that for all ordinals � 2@� = @�+1: That is, GCH asserts that the cardinality of the power set of any infinite set is the smallest cardinality greater than that of the set. 2.2 Independence from ZFC Cantor believed the continuum hypothesis to be true and tried for many years to prove it, in vain (Dauben 1990). It became the first on David Hilbert’s list of important open questions that was presented at the International Congress of Mathematicians in the year 1900 in Paris. Axiomatic set theory was at that point not yet formulated. Kurt Gödel showed in 1940 that the continuum hypothesis (CH for short) cannot be disproved from the standard Zermelo–Fraenkel set theory (ZF), even if the axiom of choice is adopted (ZFC) (Gödel (1940)). Paul Cohen showed in 1963 that CH cannot be proven from those same axioms either (Cohen (1963) & Cohen (1964)). Hence, CH is independent of ZFC. Both of these results assume that the Zermelo–Fraenkel axioms are consistent; this assumption is widely believed to be true. Cohen was awarded the Fields Medal in 1966 for his proof. The continuum hypothesis is closely related to many statements in analysis, point set topology and measure theory. As a result of its independence, many substantial conjectures in those fields have subsequently been shown to be independent as well. So far, CH appears to be independent of all known large cardinal axioms in the context of ZFC. The independence from ZFC means that proving or disproving the CH within ZFC is impossible. Gödel and Cohen’s negative results are not universally accepted as disposing of the hypothesis. Hilbert’s problem remains an active topic of research; see Woodin (2001) and Koellner (2011a) for an overview of the current research status. The continuum hypothesis was not the first statement shown to be independent of ZFC. An immediate consequence of Gödel’s incompleteness theorem, which was published in 1931, is that there is a formal statement (one for each appropriate Gödel numbering scheme) expressing the consistency of ZFC that is independent of ZFC, assuming that ZFC is consistent. The continuum hypothesis and the axiom of choice were among the first mathematical statements shown to be independent of ZF set theory. These proofs of independence were not completed until Paul Cohen developed forcing in the 1960s. They all rely on the assumption that ZF is consistent. These proofs are called proofs of relative consistency (see Forcing (mathematics)). 2.3 Arguments for and against CH Gödel believed that CH is false and that his proof that CH is consistent with ZFC only shows that the Zermelo– Fraenkel axioms do not adequately characterize the universe of sets. Gödel was a platonist and therefore had no problems with asserting the truth and falsehood of statements independent of their provability. Cohen, though a formalist (Goodman 1979), also tended towards rejecting CH. Historically, mathematicians who favored a “rich” and “large” universe of sets were against CH, while those favoring a “neat” and “controllable” universe favored CH. Parallel arguments were made for and against the axiom of con- structibility, which implies CH. More recently, Matthew Foreman has pointed out that ontological maximalism can actually be used to argue in favor of CH, because among models that have the same reals, models with “more” sets of reals have a better chance of satisfying CH (Maddy 1988, p. 500). 2.4. THE GENERALIZED CONTINUUM HYPOTHESIS 19 Another viewpoint is that the conception of set is not specific enough to determine whether CH is true or false. This viewpoint was advanced as early as 1923 by Skolem, even beforeGödel’s first incompleteness theorem. Skolem argued on the basis of what is now known as Skolem’s paradox, and it was later supported by the independence of CH from the axioms of ZFC, since these axioms are enough to establish the elementary properties of sets and cardinalities. In order to argue against this viewpoint, it would be sufficient to demonstrate new axioms that are supported by intuition and resolve CH in one direction or another. Although the axiom of constructibility does resolve CH, it is not generally considered to be intuitively true any more than CH is generally considered to be false (Kunen 1980, p. 171). At least two other axioms have been proposed that have implications for the continuum hypothesis, although these axioms have not currently found wide acceptance in the mathematical community. In 1986, Chris Freiling presented an argument against CH by showing that the negation of CH is equivalent to Freiling’s axiom of symmetry, a statement about probabilities. Freiling believes this axiom is “intuitively true” but others have disagreed. A difficult argument against CH developed by W. Hugh Woodin has attracted considerable attention since the year 2000 (Woodin 2001a, 2001b). Foreman (2003) does not reject Woodin’s argument outright but urges caution. Solomon Feferman (2011) has made a complex philosophical argument that CH is not a definite mathematical prob- lem. He proposes a theory of “definiteness” using a semi-intuitionistic subsystem of ZF that accepts classical logic for bounded quantifiers but uses intuitionistic logic for unbounded ones, and suggests that a proposition � is mathemati- cally “definite” if the semi-intuitionistic theory can prove (�_:�) . He conjectures that CH is not definite according to this notion, and proposes that CH should therefore be considered not to have a truth value. Peter Koellner (2011b) wrote a critical commentary on Feferman’s article. Joel David Hamkins proposes a multiverse approach to set theory and argues that “the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.” (Hamkins 2012). In a related vein, Saharon Shelah wrote that he does “not agree with the pure Platonic view that the interesting problems in set theory can be decided, that we just have to discover the additional axiom. My mental picture is that we have many possible set theories, all conforming to ZFC.” (Shelah 2003). 2.4 The generalized continuum hypothesis The generalized continuum hypothesis (GCH) states that if an infinite set’s cardinality lies between that of an infinite set S and that of the power set of S, then it either has the same cardinality as the set S or the same cardinality as the power set of S. That is, for any infinite cardinal � there is no cardinal � such that � < � < 2�: GCH is equivalent to: @�+1 = 2@� for every ordinal �: (occasionally called Cantor’s aleph hypothesis) The beth numbers provide an alternate notation for this condition: @� = i� for every ordinal �: This is a generalization of the continuum hypothesis since the continuum has the same cardinality as the power set of the integers. It was first suggested by Jourdain (1905). Like CH, GCH is also independent of ZFC, but Sierpiński proved that ZF + GCH implies the axiom of choice (AC), so choice and GCH are not independent in ZF; there are no models of ZF in which GCH holds and AC fails. To prove this, Sierpiński showed GCH implies that every cardinality n is smaller than some Aleph number, and thus can be ordered. This is done by showing that n is smaller than 2@0+n which is smaller than its own Hartogs number — this uses the equality 2@0+n = 2 � 2@0+n ; for the full proof, see Gillman (2002). Kurt Gödel showed that GCH is a consequence of ZF + V=L (the axiom that every set is constructible relative to the ordinals), and is therefore consistent with ZFC. As GCH implies CH, Cohen’s model in which CH fails is a model in which GCH fails, and thus GCH is not provable from ZFC. W. B. Easton used the method of forcing developed by Cohen to prove Easton’s theorem, which shows it is consistent with ZFC for arbitrarily large cardinals @� to fail to satisfy 2@� = @�+1: Much later, Foreman and Woodin proved that (assuming the consistency of very large cardinals) it is consistent that 2� > �+ holds for every infinite cardinal �: Later Woodin extended this by showing the consistency of 2� = �++ for every � . A recent result of Carmi Merimovich shows that, for each n≥1, it is consistent with ZFC that for each κ, 2κ is the nth successor of κ. On the other hand, László Patai (1930) proved, that if γ is an ordinal and for each infinite cardinal κ, 2κ is the γth successor of κ, then γ is finite. For any infinite sets A and B, if there is an injection from A to B then there is an injection from subsets of A to subsets of B. Thus for any infinite cardinals A and B, 20 CHAPTER 2. CONTINUUM HYPOTHESIS A < B ! 2A � 2B: If A and B are finite, the stronger inequality A < B ! 2A < 2B holds. GCH implies that this strict, stronger inequality holds for infinite cardinals as well as finite cardinals. 2.4.1 Implications of GCH for cardinal exponentiation Although the generalized continuum hypothesis refers directly only to cardinal exponentiation with 2 as the base, one can deduce from it the values of cardinal exponentiation in all cases. It implies that @@�� is (see: Hayden & Kennison (1968), page 147, exercise 76): @�+1 when α ≤ β+1; @� when β+1 < α and @� < cf(@�) where cf is the cofinality operation; and @�+1 when β+1 < α and @� � cf(@�) . 2.5 See also � Aleph number � Beth number � Cardinality � Ω-logic � Wetzel’s problem 2.6 References � Cohen, Paul Joseph (2008) [1966]. Set theory and the continuum hypothesis. Mineola, New York: Dover Publications. ISBN 978-0-486-46921-8. � Cohen, Paul J. (December 15, 1963). “The Independence of the Continuum Hypothesis”. Proceedings of the National Academy of Sciences of the United States of America 50 (6): 1143–1148. doi:10.1073/pnas.50.6.1143. JSTOR 71858. PMC 221287. PMID 16578557. � Cohen, Paul J. (January 15, 1964). “The Independence of the Continuum Hypothesis, II”. Proceedings of the National Academy of Sciences of the United States of America 51 (1): 105–110. doi:10.1073/pnas.51.1.105. JSTOR 72252. PMC 300611. PMID 16591132. � Dales, H. G.; Woodin, W. H. (1987). An Introduction to Independence for Analysts. Cambridge. � Dauben, Joseph Warren (1990). Georg Cantor: His Mathematics and Philosophy of the Infinite. Princeton University Press. pp. 134–137. ISBN 9780691024479. � Enderton, Herbert (1977). Elements of Set Theory. Academic Press. � Feferman, Solomon (2011). “Is the ContinuumHypothesis a definitemathematical problem?" (PDF).Exploring the Frontiers of Independence (Harvard lecture series). � Foreman, Matt (2003). “Has the Continuum Hypothesis been Settled?" (PDF). Retrieved February 25, 2006. 2.7. EXTERNAL LINKS 21 � Freiling, Chris (1986). “Axioms of Symmetry: Throwing Darts at the Real Number Line”. Journal of Symbolic Logic (Association for Symbolic Logic) 51 (1): 190–200. doi:10.2307/2273955. JSTOR 2273955. � Gödel, K. (1940). The Consistency of the Continuum-Hypothesis. Princeton University Press. � Gillman, Leonard (2002). “Two Classical Surprises Concerning the Axiom of Choice and the Continuum Hypothesis” (PDF). American Mathematical Monthly 109. � Gödel, K.: What is Cantor’s Continuum Problem?, reprinted in Benacerraf and Putnam’s collection Philosophy of Mathematics, 2nd ed., Cambridge University Press, 1983. An outline of Gödel’s arguments against CH. � Goodman, Nicolas D. (1979). “Mathematics as an objective science”. The American Mathematical Monthly 86 (7): 540–551. doi:10.2307/2320581. MR 542765. This view is often called formalism. Positions more or less like this may be found in Haskell Curry [5], Abraham Robinson [17], and Paul Cohen [4]. � Joel David Hamkins. The set-theoretic multiverse. Rev. Symb. Log. 5 (2012), no. 3, 416–449. � Seymour Hayden and John F. Kennison: Zermelo–Fraenkel Set Theory (1968), Charles E. Merrill Publishing Company, Columbus, Ohio. � Jourdain, Philip E. B. (1905). “On transfinite cardinal numbers of the exponential form”. Philosophical Mag- azine, Series 6 9: 42–56. doi:10.1080/14786440509463254. � Koellner, Peter (2011a). “The Continuum Hypothesis” (PDF). Exploring the Frontiers of Independence (Har- vard lecture series). � Koellner, Peter (2011b). “Feferman On the Indefiniteness of CH” (PDF). � Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. Amsterdam: North-Holland. ISBN 978-0-444-85401-8. � Maddy, Penelope (June 1988). “Believing the Axioms, I”. Journal of Symbolic Logic (Association for Symbolic Logic) 53 (2): 481–511. doi:10.2307/2274520. JSTOR 2274520. � Martin, D. (1976). “Hilbert’s first problem: the continuum hypothesis,” inMathematical Developments Arising fromHilbert’s Problems, Proceedings of Symposia in PureMathematics XXVIII, F. Browder, editor. American Mathematical Society, 1976, pp. 81–92. ISBN 0-8218-1428-1 � McGough, Nancy. “The Continuum Hypothesis”. � Merimovich, Carmi (2007). “A power function with a fixed finite gap everywhere”. Journal of Symbolic Logic 72 (2): 361–417. doi:10.2178/jsl/1185803615. � Moore, Gregory H. (2011). “Early history of the generalized continuum hypothesis: 1878–1938”. Bull. Sym- bolic Logic 17 (4): 489–532. doi:10.2178/bsl/1318855631. MR 2896574. � Shelah, Saharon (2003). “Logical dreams”. Bull. Amer. Math. Soc. (N.S.) 40 (2): 203–228. doi:10.1090/s0273- 0979-03-00981-9. � Woodin, W. Hugh (2001a). “The Continuum Hypothesis, Part I” (PDF). Notices of the AMS 48 (6): 567–576. � Woodin, W. Hugh (2001b). “The ContinuumHypothesis, Part II” (PDF).Notices of the AMS 48 (7): 681–690. German literature � Cantor, Georg (1878). “Ein Beitrag zur Mannigfaltigkeitslehre”. Journal für die Reine und Angewandte Math- ematik 84: 242–258. doi:10.1515/crll.1878.84.242. � Patai, L. (1930). “Untersuchungen über die א-reihe”. Mathematische und naturwissenschaftliche Berichte aus Ungarn 37: 127–142. 2.7 External links � Szudzik, Matthew and Weisstein, Eric W., “Continuum Hypothesis”, MathWorld. This article incorporates material from Generalized continuum hypothesis on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. Chapter 3 Forcing (mathematics) For the use of forcing in recursion theory, see Forcing (recursion theory). In the mathematical discipline of set theory, forcing is a technique discovered by Paul Cohen for proving consistency and independence results. It was first used, in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory. Forcing was considerably reworked and simplified in the following years, and has since served as a powerful technique both in set theory and in areas of mathematical logic such as recursion theory. Descriptive set theory uses the notion of forcing from both recursion theory and set theory. Forcing has also been used in model theory but it is common in model theory to define genericity directly without mention of forcing. 3.1 Intuitions Forcing is equivalent to the method of Boolean-valued models, which some feel is conceptually more natural and intuitive, but usually much more difficult to apply. Intuitively, forcing consists of expanding the set theoretical universeV to a larger universeV*. In this bigger universe, for example, one might have lots of new subsets ofω = {0,1,2,…} that were not there in the old universe, and thereby violate the continuum hypothesis. While impossible on the face of it, this is just another version of Cantor’s paradox about infinity. In principle, one could consider V � = V � f0; 1g; identify x 2 V with (x; 0) , and then introduce an expanded membership relation involving the “new” sets of the form (x; 1) . Forcing is a more elaborate version of this idea, reducing the expansion to the existence of one new set, and allowing for fine control over the properties of the expanded universe. Cohen’s original technique, now called ramified forcing, is slightly different from the unramified forcing expounded here. 3.2 Forcing posets A forcing poset is an ordered triple, (P, ≤, 1), where ≤ is a preorder on P that satisfies following splitting condition: � For all p ∈ P, there are q, r ∈ P such that q, r ≤ p with no s ∈ P such that s ≤ q, r The largest element of P is 1, that is, p ≤ 1 for all p ∈ P.Members of P are called forcing conditions or just conditions. One reads p ≤ q as p is stronger than q. Intuitively, the “smaller” condition provides “more” information, just as the smaller interval [3.1415926,3.1415927] provides more information about the number π than the interval [3.1,3.2] does. 22 3.2. FORCING POSETS 23 There are various conventions in use. Some authors require ≤ to also be antisymmetric, so that the relation is a partial order. Some use the term partial order anyway, conflicting with standard terminology, while some use the term preorder. The largest element can be dispensed with. The reverse ordering is also used, most notably by Saharon Shelah and his co-authors. 3.2.1 P-names Associated with a forcing poset P is the class V(P) of P-names. P-names are sets of the form � {(u, p) : u is a P-name and p ∈ P and (some criterion involving u and p)} Using transfinite recursion, one defines � Name(0) = {} , � Name(α + 1) = the power set of (Name(α) × P), � Name(λ) = ∪{Name(α) : α < λ for λ a limit ordinal} , and then the class of P-names is defined by V(P) = ∪{Name(α) : α is an ordinal} . The P-names are, in fact, an expansion of the universe. Given x ∈ V, one defines xˇ to be the P-name xˇ = {(yˇ, 1) : y ∈ x} . Again, this is really a definition by transfinite recursion. 3.2.2 Interpretation Given any subset G of P, one next defines the interpretation or valuation map from P-names by val(u, G) = {val(v, G) : ∃ p ∈ G , (v, p) ∈ u} . (Again a definition by transfinite recursion.) Note that if 1 is in G, then val(xˇ, G) = x. One defines G = {(pˇ, p) : p ∈ G} , so that val(G,G) = G. 3.2.3 Example A good example of a forcing poset is (Bor(I) , ⊆ , I ) where I = [0,1] and Bor(I) are the Borel subsets of I having non-zero Lebesgue measure. In this case, one can talk about the conditions as being probabilities, and a Bor(I)-name assigns membership in a probabilistic sense. Because of the ready intuition this example can provide, probabilistic language is sometimes used with other forcing posets. 24 CHAPTER 3. FORCING (MATHEMATICS) 3.3 Countable transitive models and generic filters The key step in forcing is, given a ZFC universe V, to find appropriate G not in V. The resulting class of all interpre- tations of P-names will turn out to be a model of ZFC, properly extending the original V (since G∉V). Instead of working with V, one considers a countable transitive model M with (P,≤,1) ∈M. By model, we mean a model of set theory, either of all of ZFC, or a model of a large but finite subset of the ZFC axioms, or some variant thereof. Transitivity means that if x ∈ y ∈M, then x ∈M. TheMostowski collapsing theorem says this can be assumed if the membership relation is well-founded. The effect of transitivity is that membership and other elementary notions can be handled intuitively. Countability of the model relies on the Löwenheim–Skolem theorem. Since M is a set, there are sets not in M – this follows from Russell’s paradox. The appropriate set G to pick, and adjoin toM, is a generic filter on P. The filter condition means that G⊆P and � 1 ∈ G ; � if p ≥ q ∈ G, then p ∈ G ; � if p,q ∈ G, then ∃r ∈ G, r ≤ p and r ≤ q ; For G to be generic means � if D ∈M is a dense subset of P (that is, p ∈ P implies ∃q ∈ D, q ≤ p) then G∩D ≠ 0 . The existence of a generic filter G follows from the Rasiowa–Sikorski lemma. In fact, slightly more is true: given a condition p ∈ P, one can find a generic filter G such that p ∈ G. Due to the splitting condition, if G is filter, then P\G is dense. If G is inM then P\G is inM becauseM is model of set theory. By this reason, a generic filter is never in M. 3.4 Forcing Given a generic filterG⊆P, one proceeds as follows. The subclass ofP-names inM is denotedM(P). LetM[G]={val(u,G):u∈M(P)}. To reduce the study of the set theory ofM[G] to that ofM, one works with the forcing language, which is built up like ordinary first-order logic, with membership as binary relation and all the names as constants. Define p M;P φ(u1,…,un) (read "p forces φ in model M with poset P”) where p is a condition, φ is a formula in the forcing language, and the ui are names, to mean that if G is a generic filter containing p, then M[G] ⊨ φ(val(u1,G),…,val(un,G)). The special case 1 M;P φ is often written P M;P φ or M;P φ. Such statements are true inM[G] no matter what G is. What is important is that this “external” definition of the forcing relation p M;P φ is equivalent to an “internal” definition, defined by transfinite induction over the names on instances of u ∈ v and u = v, and then by ordinary induction over the complexity of formulas. This has the effect that all the properties ofM[G] are really properties of M, and the verification of ZFC inM[G] becomes straightforward. This is usually summarized as three key properties: � Truth: M[G] ⊨ φ(val(u1,G),…,val(un,G)) if and only if it is forced by G, that is, for some condition p ∈ G, p M;P φ(u1,…,un). � Definability: The statement "p M;P φ(u1,…,un)" is definable inM. � Coherence: If p M;P φ(u1,…,un) and q ≤ p, then q M;P φ(u1,…,un). We define the forcing relation in V by induction on complexity, in which we simultaneously define forcing of atomic formulas by ∈-induction and then we define it by induction on formula complexity. 1. p P a 2 b if (8q � p)(9r � q)(9s; c)((s; c) 2 b ^ r � s ^ r P a = c) . 2. p P a = b if (8q � p)(8c 2 V P )(q P c 2 a , q P c 2 b) . 3. p P :f if :(9q � p)q P f . 4. p P (f ^ g) if (p P f ^ p P g) . 3.5. CONSISTENCY 25 5. p P (8x)f if (8x 2 V P )p P f . In 1–5 p is an arbitrary condition. In 1 and 2 a and a are arbitrary names and in 3–5 f and g are arbitrary formulas where all free occurrences of variables referring names. This definition is syntax transform of formulas. This means that for any given formula f(x1; : : : ; xn) the formula p �P f(x1; : : : ; xn)with free variables p; P; x1; : : : ; xn is well defined. In fact this syntax transform has following properties: any equivalence given by 1-5 is theorem (single theo- rem per formula) and for any formula f(x1; : : : ; xn) following formula (8p; P; x1; : : : ; xn)(p P f(x1; : : : ; xn)) (po(P ) ^ p 2 dom(P ) ^ x1; : : : ; xn 2 V P ) is theorem where po(P ) means that P is partial order with splitting condition. The bit of definition is existence of syntax transform with these properties. This definition provides the possibility of working in V without any countable transitive model M . The following statement gives announced definability: (8M;P; x1; : : : ; xn)(ctm(M)^po(P )^P 2M^p 2 dom(P )^x1; : : : ; xn 2MP ) (p M;P f(x1; : : : ; xn) , M j= p P f(x1; : : : ; xn))) where ctm(M) means thatM is countable transitive model satisfying some finite part of ZF axioms depending on formula f . (Where no confusion is possible we simply write .) 3.5 Consistency The above can be summarized by saying the fundamental consistency result is that given a forcing poset P, we may assume that there exists a generic filter G, not in the universe V, such that V[G] is again a set theoretic universe, modelling ZFC. Furthermore, all truths in V[G] can be reduced to truths in V regarding the forcing relation. Both styles, adjoining G to a countable transitive model M or to the whole universe V, are commonly used. Less commonly seen is the approach using the “internal” definition of forcing, and no mention of set or class models is made. This was Cohen’s original method, and in one elaboration, it becomes the method of Boolean-valued analysis. 3.6 Cohen forcing The simplest nontrivial forcing poset is ( Fin(ω,2), ⊇, 0 ), the finite partial functions from ω to 2={0,1} under reverse inclusion. That is, a condition p is essentially two disjoint finite subsets p−1[1] and p−1[0] of ω, to be thought of as the “yes” and “no” parts of p, with no information provided on values outside the domain of p. q is stronger than p means that q ⊇ p, in other words, the “yes” and “no” parts of q are supersets of the “yes” and “no” parts of p, and in that sense, provide more information. Let G be a generic filter for this poset. If p and q are both in G, then p∪q is a condition, because G is a filter. This means that g=⋃G is a well-defined partial function from ω to 2, because any two conditions in G agree on their common domain. g is in fact a total function. Given n ∈ ω, let Dn={ p : p(n) is defined }, then Dn is dense. (Given any p, if n is not in p’s domain, adjoin a value for n, the result is in Dn.) A condition p ∈ G∩Dn has n in its domain, and since p ⊆ g, g(n) is defined. Let X=g−1[1], the set of all “yes” members of the generic conditions. It is possible to give a name for X directly. Let X = { ( nˇ, p ) : p(n)=1 }, then val( X, G ) = X. Now suppose A⊆ω in V. We claim that X≠A. Let DA = { p : ∃n, n∈dom(p) and p(n)=1 if and only if n∉A }. DA is dense. (Given any p, if n is not in p’s domain, adjoin a value for n contrary to the status of "n∈A".) Then any p∈G∩DA witnesses X≠A. To summarize, X is a new subset of ω, necessarily infinite. Replacing ω with ω×ω2, that is, consider instead finite partial functions whose inputs are of the form (n,α), with n 26 CHAPTER 3. FORCING (MATHEMATICS) The last step in showing the independence of the continuum hypothesis, then, is to show that Cohen forcing does not collapse cardinals. For this, a sufficient combinatorial property is that all of the antichains of this poset are countable. 3.7 The countable chain condition Main article: Countable chain condition An antichain A of P is a subset such that if p and q are in A, then p and q are incompatible (written p ⊥ q), meaning there is no r in P such that r ≤ p and r ≤ q. In the Borel sets example, incompatibility means p∩q has measure zero. In the finite partial functions example, incompatibility means that p∪q is not a function, in other words, p and q assign different values to some domain input. P satisfies the countable chain condition (c.c.c.) if every antichain in P is countable. (The name, which is obviously inappropriate, is a holdover from older terminology. Some mathematicians write “c.a.c.” for “countable antichain condition”.) It is easy to see that Bor(I) satisfies the c.c.c., because the measures add up to at most 1. Fin(E,2) is also c.c.c., but the proof is more difficult. Given an uncountable subfamilyW ⊆ Fin(E,2), shrinkW to an uncountable subfamilyW0 of sets of size n, for some n 3.9. RANDOM REALS 27 At one time, it was thought that more sophisticated forcing would also allow arbitrary variation in the powers of singular cardinals. But this has turned out to be a difficult, subtle and even surprising problem, with several more restrictions provable in ZFC, and with the forcing models depending on the consistency of various large cardinal properties. Many open problems remain. 3.9 Random reals Main article: random algebra In the Borel sets ( Bor(I), ⊆, I ) example, the generic filter converges to a real number r, called a random real. A name for the decimal expansion of r (in the sense of the canonical set of decimal intervals that converge to r) can be given by letting r = { ( Eˇ, E ) : E = [ k⋅10−n, (k + 1)⋅10−n ], 0 ≤ k < 10n }. This is, in some sense, just a subname of G. To recover G from r, one takes those Borel subsets of I that “contain” r. Since the forcing poset is in V, but r is not in V, this containment is actually impossible. But there is a natural sense in which the interval [0.5, 0.6] in V “contains” a random real whose decimal expansion begins 0.5. This is formalized by the notion of “Borel code”. Every Borel set can, nonuniquely, be built up, starting from intervals with rational endpoints and applying the opera- tions of complement and countable unions, a countable number of times. The record of such a construction is called a Borel code. Given a Borel set B in V, one recovers a Borel code, and then applies the same construction sequence in V[G], getting a Borel set B*. One can prove that one gets the same set independent of the construction of B, and that basic properties are preserved. For example, if B⊆C, then B*⊆C*. If B has measure zero, then B* has measure zero. So given r, a random real, one can show thatG = { B (inV) : r∈B* (inV[G]) }. Because of the mutual interdefinability between r and G, one generally writes V[r] for V[G]. A different interpretation of reals in V[G] was provided by Dana Scott. Rational numbers in V[G] have names that correspond to countably many distinct rational values assigned to a maximal antichain of Borel sets, in other words, a certain rational-valued function on I = [0,1]. Real numbers in V[G] then correspond to Dedekind cuts of such functions, that is, measurable functions. 3.10 Boolean-valued models Main article: Boolean-valued model Perhaps more clearly, the method can be explained in terms of Boolean-valued models. In these, any statement is assigned a truth value from some complete atomless Boolean algebra, rather than just a true/false value. Then an ultrafilter is picked in this Boolean algebra, which assigns values true/false to statements of our theory. The point is that the resulting theory has a model which contains this ultrafilter, which can be understood as a new model obtained by extending the old one with this ultrafilter. By picking a Boolean-valued model in an appropriate way, we can get a model that has the desired property. In it, only statements which must be true (are “forced” to be true) will be true, in a sense (since it has this extension/minimality property). 3.11 Meta-mathematical explanation In forcing we usually seek to show some sentence is consistent with ZFC (or optionally some extension of ZFC). One way to interpret the argument is that we assume ZFC is consistent and use it to prove ZFC combined with our new sentence is also consistent. Each “condition” is a finite piece of information – the idea is that only finite pieces are relevant for consistency, since by the compactness theorem a theory is satisfiable if and only if every finite subset of its axioms is satisfiable. Then, we can pick an infinite set of consistent conditions to extend our model. Thus, assuming consistency of set theory, we prove consistency of the theory extended with this infinite set. 28 CHAPTER 3. FORCING (MATHEMATICS) 3.12 Logical explanation By Gödel’s incompleteness theorem one cannot prove the consistency of any sufficiently strong formal theory, such as ZFC, using only the axioms of the theory itself, unless the theory itself is inconsistent. Consequently mathematicians do not attempt to prove the consistency of ZFC using only the axioms of ZFC, or to prove ZFC+H is consistent for any hypothesis H using only ZFC+H. For this reason the aim of a consistency proof is to prove the consistency of ZFC + H relative to consistency of ZFC. Such problems are known as problems of relative consistency. In fact one proves (*) ZFC ` Con(ZFC)! Con(ZFC +H): We will give the general schema of relative consistency proofs. Because any proof is finite it uses finite number of axioms. ZFC + :Con(ZFC +H) ` 9T (Fin(T ) ^ T � ZFC ^ (T ` :H)): For any given proof ZFC can verify validity of this proof. This is provable by induction by the length of the proof. ZFC ` 8T ((T ` :H)! (ZFC ` (T ` :H))): Now we obtain ZFC + :Con(ZFC +H) ` 9T (Fin(T ) ^ T � ZFC ^ (ZFC ` (T ` :H))): If we prove the following (**) ZFC ` 8T (Fin(T ) ^ T � ZFC ! (ZFC ` Con(T +H))) we can conclude that ZFC + :Con(ZFC +H) ` 9T (Fin(T ) ^ T � ZFC ^ (ZFC ` (T ` :H)) ^ (ZFC ` Con(T +H))) which is equivalent to ZFC + :Con(ZFC +H) ` :Con(ZFC) which gives (*). The core of the relative consistency proof is proving (**). One has to construct a ZFC proof of Con(T + H) for any given finite set T of ZFC axioms (by ZFC instruments of course). (No universal proof of Con(T + H) of course.) In ZFC it is provable that for any condition p the set of formulas (evaluated by names) forced by p is deductively closed. Also, for any ZFC axiom, ZFC proves that this axiom is forced by 1. Then it suffices to prove that there is at least one condition which forces H. In the case of Boolean valued forcing, the procedure is similar – one has to prove that the Boolean value of H is not 0. Another approach uses the reflection theorem. For any given finite set of ZFC axioms there is ZFC proof that this set of axioms has a countable transitive model. For any given finite set T of ZFC axioms there is finite set T' of ZFC axioms such that ZFC proves that if a countable transitive model M satisfies T' then M[G] satisfies T. One has to prove that there is finite set T” of ZFC axioms such that if a countable transitive model M satisfies T” then M[G] satisfies the hypothesis H. Then, for any given finite set T of ZFC axioms, ZFC proves Con(T + H). Sometimes in (**) some stronger theory S than ZFC is used for proving Con(T + H). Then we have proof of consis- tency of ZFC + H relative to the consistency of S. Note that ZFC ` Con(ZFC)$ Con(ZFL) , where ZFL is ZF + V = L (axiom of constructibility). 3.13. SEE ALSO 29 3.13 See also � List of forcing notions � Nice name 3.14 References � Bell, J. L. (1985) Boolean-ValuedModels and Independence Proofs in Set Theory, Oxford. ISBN 0-19-853241- 5 � Cohen, P. J. (1966). Set theory and the continuum hypothesis. Addison–Wesley. ISBN 0-8053-2327-9. � Grishin, V.N. (2001), “Forcing method”, in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 � Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444- 85401-0. 3.15 External links � Nik Weaver’s book Forcing for Mathematicians was written for mathematicians who want to learn the basic machinery of forcing. No background in logic is assumed, beyond the facility with formal syntax which should be second nature to any well-trained mathematician. � Tim Chow’s article A Beginner’s Guide to Forcing is a good introduction to the concepts of forcing that avoids a lot of technical detail. This paper grew out of Chow’s newsgroup article Forcing for dummies. In addition to improved exposition, the Beginner’s Guide includes a section on Boolean Valued Models. � See also Kenny Easwaran’s article A Cheerful Introduction to Forcing and the Continuum Hypothesis, which is also aimed at the beginner but includes more technical details than Chow’s article. � The Independence of the Continuum Hypothesis Paul J. Cohen, Proceedings of the National Academy of Sciences of the United States of America, Vol. 50, No. 6. (Dec. 15, 1963), pp. 1143–1148. � The Independence of the Continuum Hypothesis, II Paul J. Cohen Proceedings of the National Academy of Sciences of the United States of America, Vol. 51, No. 1. (Jan. 15, 1964), pp. 105–110. � Paul Cohen gave a historical lecture The Discovery of Forcing (Rocky Mountain J. Math. Volume 32, Number 4 (2002), 1071–1100) about how he developed his independence proof. The linked page has a download link for an open access PDF but your browser must send a referer header from the linked page to retrieve it. � Weisstein, Eric W., “Forcing”, MathWorld. Chapter 4 Partially ordered set {x,y,z} {y,z}{x,z}{x,y} {y} {z}{x} Ø The Hasse diagram of the set of all subsets of a three-element set {x, y, z}, ordered by inclusion. Sets on the same horizontal level don't share a precedence relationship. Other pairs, such as {x} and {y,z}, do not either. In mathematics, especially order theory, a partially ordered set (or poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other. Such a relation is called a partial order to reflect the fact that not every pair of elements need be related: for some pairs, it may be that neither element precedes the other in the poset. Thus, partial orders generalize the more familiar total orders, in which every pair is related. A finite poset can be visualized through its Hasse diagram, which depicts the ordering relation.[1] A familiar real-life example of a partially ordered set is a collection of people ordered by genealogical descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs bear no such relationship. 30 4.1. FORMAL DEFINITION 31 4.1 Formal definition A (non-strict) partial order[2] is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., which satisfies for all a, b, and c in P: � a ≤ a (reflexivity); � if a ≤ b and b ≤ a then a = b (antisymmetry); � if a ≤ b and b ≤ c then a ≤ c (transitivity). In other words, a partial order is an antisymmetric preorder. A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used, as long as it is clear from the context that no other kind of order is meant. In particular, totally ordered sets can also be referred to as “ordered sets”, especially in areas where these structures are more common than posets. For a, b, elements of a partially ordered set P, if a ≤ b or b ≤ a, then a and b are comparable. Otherwise they are incomparable. In the figure on top-right, e.g. {x} and {x,y,z} are comparable, while {x} and {y} are not. A partial order under which every pair of elements is comparable is called a total order or linear order; a totally ordered set is also called a chain (e.g., the natural numbers with their standard order). A subset of a poset in which no two distinct elements are comparable is called an antichain (e.g. the set of singletons {{x}, {y}, {z}} in the top-right figure). An element a is said to be covered by another element b, written a c < d ... 4.3 Extrema There are several notions of “greatest” and “least” element in a poset P, notably: 32 CHAPTER 4. PARTIALLY ORDERED SET � Greatest element and least element: An element g in P is a greatest element if for every element a in P, a ≤ g. An element m in P is a least element if for every element a in P, a ≥ m. A poset can only have one greatest or least element. � Maximal elements and minimal elements: An element g in P is a maximal element if there is no element a in P such that a > g. Similarly, an element m in P is a minimal element if there is no element a in P such that a < m. If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements. � Upper and lower bounds: For a subset A of P, an element x in P is an upper bound of A if a ≤ x, for each element a in A. In particular, x need not be in A to be an upper bound of A. Similarly, an element x in P is a lower bound of A if a ≥ x, for each element a in A. A greatest element of P is an upper bound of P itself, and a least element is a lower bound of P. For example, consider the positive integers, ordered by divisibility: 1 is a least element, as it divides all other elements; on the other hand this poset does not have a greatest element (although if one would include 0 in the poset, which is a multiple of any integer, that would be a greatest element; see figure). This partially ordered set does not even have any maximal elements, since any g divides for instance 2g, which is distinct from it, so g is not maximal. If the number 1 is excluded, while keeping divisibility as ordering on the elements greater than 1, then the resulting poset does not have a least element, but any prime number is a minimal element for it. In this poset, 60 is an upper bound (though not a least upper bound) of the subset {2,3,5,10}, which does not have any lower bound (since 1 is not in the poset); on the other hand 2 is a lower bound of the subset of powers of 2, which does not have any upper bound. 4.4 Orders on the Cartesian product of partially ordered sets In order of increasing strength, i.e., decreasing sets of pairs, three of the possible partial orders on the Cartesian product of two partially ordered sets are (see figures): � the lexicographical order: (a,b) ≤ (c,d) if a < c or (a = c and b ≤ d); � the product order: (a,b) ≤ (c,d) if a ≤ c and b ≤ d; � the reflexive closure of the direct product of the corresponding strict orders: (a,b) ≤ (c,d) if (a < c and b < d) or (a = c and b = d). All three can similarly be defined for the Cartesian product of more than two sets. Applied to ordered vector spaces over the same field, the result is in each case also an ordered vector space. See also orders on the Cartesian product of totally ordered sets. 4.5 Sums of partially ordered sets Another way to combine two posets is the ordinal sum[3] (or linear sum[4]), Z = X ⊕ Y, defined on the union of the underlying sets X and Y by the order a ≤Z b if and only if: � a, b ∈ X with a ≤X b, or � a, b ∈ Y with a ≤Y b, or � a ∈ X and b ∈ Y. If two posets are well-ordered, then so is their ordinal sum.[5] 4.6. STRICT AND NON-STRICT PARTIAL ORDERS 33 4.6 Strict and non-strict partial orders In some contexts, the partial order defined above is called a non-strict (or reflexive, orweak) partial order. In these contexts a strict (or irreflexive) partial order " 34 CHAPTER 4. PARTIALLY ORDERED SET partial orders (S,≤) and (T,≤) are said to be isomorphic. Isomorphic orders have structurally similar Hasse diagrams (cf. right picture). It can be shown that if order-preserving maps f: S → T and g: T → S exist such that g∘f and f∘g yields the identity function on S and T, respectively, then S and T are order-isomorphic. [7] For example, a mapping f: ℕ → ℙ(ℕ) from the set of natural numbers (ordered by divisibility) to the power set of natural numbers (ordered by set inclusion) can be defined by taking each number to the set of its prime divisors. It is order-preserving: if x divides y, then each prime divisor of x is also a prime divisor of y. However, it is neither injective (since it maps both 12 and 6 to {2,3}) nor order-reflecting (since besides 12 doesn't divide 6). Taking instead each number to the set of its prime power divisors defines a map g: ℕ → ℙ(ℕ) that is order-preserving, order- reflecting, and hence an order-embedding. It is not an order-isomorphism (since it e.g. doesn't map any number to the set {4}), but it can be made one by restricting its codomain to g(ℕ). The right picture shows a subset of ℕ and its isomorphic image under g. The construction of such an order-isomorphism into a power set can be generalized to a wide class of partial orders, called distributive lattices, see "Birkhoff’s representation theorem". 4.9 Number of partial orders Partially ordered set of set of all subsets of a six-element set {a, b, c, d, e, f}, ordered by the subset relation. Sequence A001035 in OEIS gives the number of partial orders on a set of n labeled elements: The number of strict partial orders is the same as that of partial orders. If we count only up to isomorphism, we get 1, 1, 2, 5, 16, 63, 318, … (sequence A000112 in OEIS). 4.10 Linear extension A partial order �� on a set X is an extension of another partial order � on X provided that for all elements x and y of X, whenever x � y , it is also the case that x �� y . A linear extension is an extension that is also a linear (i.e., total) order. Every partial order can be extended to a total order (order-extension principle).[8] In computer science, algorithms for finding linear extensions of partial orders (represented as the reachability orders of directed acyclic graphs) are called topological sorting. 4.11. IN CATEGORY THEORY 35 4.11 In category theory Every poset (and every preorder) may be considered as a category in which every hom-set has at most one element. More explicitly, let hom(x, y) = {(x, y)} if x ≤ y (and otherwise the empty set) and (y, z)∘(x, y) = (x, z). Posets are equivalent to one another if and only if they are isomorphic. In a poset, the smallest element, if it exists, is an initial object, and the largest element, if it exists, is a terminal object. Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is isomorphism-closed. 4.12 Partial orders in topological spaces Main article: Partially ordered space If P is a partially ordered set that has also been given the structure of a topological space, then it is customary to assume that {(a, b) : a ≤ b} is a closed subset of the topological product space P �P . Under this assumption partial order relations are well behaved at limits in the sense that if ai ! a , bi ! b and ai ≤ bi for all i, then a ≤ b.[9] 4.13 Interval For a ≤ b, the closed interval [a,b] is the set of elements x satisfying a ≤ x ≤ b (i.e. a ≤ x and x ≤ b). It contains at least the elements a and b. Using the corresponding strict relation " 36 CHAPTER 4. PARTIALLY ORDERED SET � semiorder � series-parallel partial order � stochastic dominance � strict weak ordering - strict partial order " Chapter 5 Sunflower (mathematics) A mathematical sunflower can be pictured as a flower. The kernel of the sunflower is the brown part in the middle, and each set of the sunflower is the union of a petal and the kernel. In mathematics, a sunflower or Δ system is a collection of sets whose pairwise intersection is constant, and called the kernel. 37 38 CHAPTER 5. SUNFLOWER (MATHEMATICS) The Δ-lemma, sunflower lemma, and sunflower conjecture give various conditions that imply the existence of a large sunflower in a given collection of sets. The original term for this concept was "Δ-system”. More recently the term “sunflower”, possibly introduced by Deza & Frankl (1981), has been gradually replacing it. 5.1 Δ lemma TheΔ-lemma is a combinatorial set-theoretic tool used in proofs to impose an upper bound on the size of a collection of pairwise incompatible elements in a forcing poset. It may for example be used as one of the ingredients in a proof showing that it is consistent with ZFC that the continuum hypothesis does not hold. It was introduced by Shanin (1946). A Δ-systemW is a collection of sets whose pairwise intersection is constant. That is, there exists a fixed S called the kernel (possibly empty) such that for all A, B ∈W, if A ≠ B then A ∩ B = S. The Δ-lemma states that every uncountable collection of finite sets contains an uncountable Δ-system. 5.2 Δ lemma for !2 IfW is an !2 -sized collection of countable subsets of !2 , and if CH holds, then there is an !2 -sized Δ-subsystem. Let hA� : � < !2i enumerateW . For cf(�) = !1 , let f(�) = sup(A� \ �) . By Fodor’s lemma, fix S stationary in !2 such that f is constantly equal to � on S . Build S0 � S of cardinality !2 such that whenever i < j are in S0 then Ai � j . Using CH, there are only !1 -many countable subsets of � , so by further thinning we may stabilize the kernel. 5.3 Sunflower lemma and conjecture Erdős &Rado (1960, p. 86) proved the sunflower lemma, stating that if a and b are positive integers then a collection of b!ab+1 sets of cardinality at most b contains a sunflower with more than a sets. The sunflower conjecture is one of several variations of the conjecture of (Erdős & Rado 1960, p. 86) that the factor of b! can be replaced by Cb for some constant C. 5.4 References � Deza,M.; Frankl, P. (1981), “Every large set of equidistant (0,+1,–1)-vectors forms a sunflower”, Combinatorica 1 (3): 225–231, doi:10.1007/BF02579328, ISSN 0209-9683, MR 637827 � Erdős, Paul; Rado, R. (1960), “Intersection theorems for systems of sets”, Journal of the London Mathematical Society, Second Series 35 (1): 85–90, doi:10.1112/jlms/s1-35.1.85, ISSN 0024-6107, MR 0111692 � Jech, Thomas (2003). Set Theory. Springer. � Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444- 85401-0. � Shanin, N. A. (1946), “A theorem from the general theory of sets”, C. R. (Doklady) Acad. Sci. URSS (N.S.) 53: 399–400 Chapter 6 Upper and lower bounds This article is about precise bounds. For asymptotic bounds, see Big O notation. In mathematics, especially in order theory, a upper bound of a subset S of some partially ordered set (K, ≤) is an element of K which is greater than or equal to every element of S.[1] The term lower bound is defined dually as an element of K which is less than or equal to every element of S. A set with a upper bound is said to be bounded from above by that bound, a set with a lower bound is said to be bounded from below by that bound. The terms bounded above (bounded below) are also used in the mathematical literature for sets that have upper (respectively lower) bounds. 6.1 Properties A subset S of a partially ordered set P may fail to have any bounds or may have many different upper and lower bounds. By transitivity, any element greater than or equal to a upper bound of S is again a upper bound of S, and any element less than or equal to any lower bound of S is again a lower bound of S. This leads to the consideration of least upper bounds (or suprema) and greatest lower bounds (or infima). The bounds of a subset S of a partially ordered set K may or may not be elements of S itself. If S contains a upper bound then that upper bound is unique and is called the greatest element of S. The greatest element of S (if it exists) is also the least upper bound of S. A special situation does occur when a subset is equal to the set of lower bounds of its own set of upper bounds. This observation leads to the definition of Dedekind cuts. The empty subset ∅ of a partially ordered set K is conventionally considered to be both bounded from above and bounded from below with every element of P being both a upper and lower bound of ∅. 6.2 Examples 5 is a lower bound for the set { 5, 10, 34, 13934 }, but 8 is not. 42 is both a upper and a lower bound for the set { 42 }; all other numbers are either a upper bound or a lower bound for that set. Every subset of the natural numbers has a lower bound, since the natural numbers have a least element (0, or 1 depending on the exact definition of natural numbers). An infinite subset of the natural numbers cannot be bounded from above. An infinite subset of the integers may be bounded from below or bounded from above, but not both. An infinite subset of the rational numbers may or may not be bounded from below and may or may not be bounded from above. Every finite subset of a non-empty totally ordered set has both upper and lower bounds. 6.3 Bounds of functions The definitions can be generalized to functions and even sets of functions. 39 40 CHAPTER 6. UPPER AND LOWER BOUNDS Given a function f with domain D and a partially ordered set (K, ≤) as codomain, an element y of K is a upper bound of f if y ≥ f(x) for each x in D. The upper bound is called sharp if equality holds for at least one value of x. Function g defined on domain D and having the same codomain (K, ≤) is a upper bound of f if g(x) ≥ f(x) for each x in D. Function g is further said to be a upper bound of a set of functions if it is an upper bound of each function in that set. The notion of lower bound for (sets of) functions is defined analogously, with ≤ replacing ≥. 6.4 Tight bounds A upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum if no greater value is a lower bound. 6.5 References [1] Mac Lane, Saunders; Birkhoff, Garrett (1991). Algebra. Providence, RI: American Mathematical Society. p. 145. ISBN 0-8218-1646-2. Chapter 7 Zermelo–Fraenkel set theory “ZFC” redirects here. For other uses, see ZFC (disambiguation). In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zer- melo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets free of paradoxes such as Russell’s paradox. Today ZFC is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. ZFC is intended to formalize a single primitive notion, that of a hereditary well-founded set, so that all entities in the universe of discourse are such sets. Thus the axioms of ZFC refer only to sets, not to urelements (elements of sets that are not themselves sets) or classes (collections of mathematical objects defined by a property shared by their members). The axioms of ZFC prevent its models from containing urelements, and proper classes can only be treated indirectly. Formally, ZFC is a one-sorted theory in first-order logic. The signature has equality and a single primitive binary relation, set membership, which is usually denoted ∈. The formula a ∈ b means that the set a is a member of the set b (which is also read, "a is an element of b" or "a is in b"). There are many equivalent formulations of the ZFC axioms. Most of the ZFC axioms state the existence of particular sets defined from other sets. For example, the axiom of pairing says that given any two sets a and b there is a new set {a, b} containing exactly a and b. Other axioms describe properties of set membership. A goal of the ZFC axioms is that each axiom should be true if interpreted as a statement about the collection of all sets in the von Neumann universe (also known as the cumulative hierarchy). The metamathematics of ZFC has been extensively studied. Landmark results in this area established the indepen- dence of the continuum hypothesis from ZFC, and of the axiom of choice from the remaining ZFC axioms. The consistency of a theory such as ZFC cannot be proved within the theory itself. 7.1 History In 1908, Ernst Zermelo proposed the first axiomatic set theory, Zermelo set theory. However, as first pointed out by Abraham Fraenkel in a 1921 letter to Zermelo, this theory was incapable of proving the existence of certain sets and cardinal numbers whose existence was taken for granted bymost set theorists of the time, notably, the cardinal number ℵω and, where Z0 is any infinite set and ℘ is the power set operation, the set {Z0, ℘(Z0), ℘(℘(Z0)),...} (Ebbinghaus 2007, p. 136). Moreover, one of Zermelo’s axioms invoked a concept, that of a “definite” property, whose operational meaning was not clear. In 1922, Fraenkel and Thoralf Skolem independently proposed operationalizing a “definite” property as one that could be formulated as a first order theory whose atomic formulas were limited to set membership and identity. They also independently proposed replacing the axiom schema of specification with the axiom schema of replacement. Appending this schema, as well as the axiom of regularity (first proposed by Dimitry Mirimanoff in 1917), to Zermelo set theory yields the theory denoted by ZF. Adding to ZF either the axiom of choice (AC) or a statement that is equivalent to it yields ZFC. 41 42 CHAPTER 7. ZERMELO–FRAENKEL SET THEORY 7.2 Axioms There are many equivalent formulations of the ZFC axioms; for a rich but somewhat dated discussion of this fact, see Fraenkel et al. (1973). The following particular axiom set is from Kunen (1980). The axioms per se are expressed in the symbolism of first order logic. The associated English prose is only intended to aid the intuition. All formulations of ZFC imply that at least one set exists. Kunen includes an axiom that directly asserts the existence of a set, in addition to the axioms given below (although he notes that he does so only “for emphasis” (ibid., p. 10)). Its omission here can be justified in two ways. First, in the standard semantics of first-order logic in which ZFC is typically formalized, the domain of discourse must be nonempty. Hence, it is a logical theorem of first-order logic that something exists — usually expressed as the assertion that something is identical to itself, ∃x(x=x). Consequently, it is a theorem of every first-order theory that something exists. However, as noted above, because in the intended semantics of ZFC there are only sets, the interpretation of this logical theorem in the context of ZFC is that some set exists. Hence, there is no need for a separate axiom asserting that a set exists. Second, however, even if ZFC is formulated in so-called free logic, in which it is not provable from logic alone that something exists, the axiom of infinity (below) asserts that an infinite set exists. This implies that a set exists and so, once again, it is superfluous to include an axiom asserting as much. 7.2.1 1. Axiom of extensionality Main article: Axiom of extensionality Two sets are equal (are the same set) if they have the same elements. 8x8y[8z(z 2 x, z 2 y)) x = y]: The converse of this axiom follows from the substitution property of equality. If the background logic does not include equality "=", x=ymay be defined as an abbreviation for the following formula (Hatcher 1982, p. 138, def. 1): 8z[z 2 x, z 2 y] ^ 8w[x 2 w , y 2 w]: In this case, the axiom of extensionality can be reformulated as 8x8y[8z(z 2 x, z 2 y)) 8w(x 2 w , y 2 w)]; which says that if x and y have the same elements, then they belong to the same sets. (Fraenkel et al. 1973) 7.2.2 2. Axiom of regularity (also called the Axiom of foundation) Main article: Axiom of regularity Every non-empty set x contains a member y such that x and y are disjoint sets. 8x[9a(a 2 x)) 9y(y 2 x ^ :9z(z 2 y ^ z 2 x))]: This implies, for example, that no set is an element of itself and that every set has an ordinal rank. 7.2.3 3. Axiom schema of specification (also called the axiom schema of separation or of restricted comprehension) Main article: Axiom schema of specification 7.2. AXIOMS 43 Subsets are commonly constructed using set builder notation. For example, the even integers can be constructed as the subset of the integers Z satisfying the predicate x � 0 (mod 2) : fx 2 Z : x � 0 (mod 2)g: In general, the subset of a set z obeying a formula � (x) with one free variable x may be written as: fx 2 z : �(x)g: The axiom schema of specification states that this subset always exists (it is an axiom schema because there is one ax- iom for each � ). Formally, let �be any formula in the language of ZFC with all free variables among x; z; w1; : : : ; wn (y is not free in �). Then: 8z8w18w2 : : :8wn9y8x[x 2 y , (x 2 z ^ �)]: Note that the axiom schema of specification can only construct subsets, and does not allow the construction of sets of the more general form: fx : �(x)g: This restriction is necessary to avoid Russell’s paradox and its variants that accompany naive set theorywith unrestricted comprehension. In some other axiomatizations of ZF, this axiom is redundant in that it follows from the axiom schema of replacement. The axiom of specification can be used to prove the existence of the empty set, denoted ? , once at least one set is known to exist (see above). One way to do this is to use a property �which no set has. For example, if w is any existing set, the empty set can be constructed as ? = fu 2 w j (u 2 u) ^ :(u 2 u)g Thus the axiom of the empty set is implied by the nine axioms presented here. The axiom of extensionality implies the empty set is unique (does not depend on w). It is common to make a definitional extension that adds the symbol ? to the language of ZFC. 7.2.4 4. Axiom of pairing Main article: Axiom of pairing If x and y are sets, then there exists a set which contains x and y as elements. 8x8y9z(x 2 z ^ y 2 z): The axiom schema of specification must be used to reduce this to a set with exactly these two elements. This axiom is part of Z, but is redundant in ZF because it follows from the axiom schema of replacement, if we are given a set with at least two elements. The existence of a set with at least two elements is assured by either the axiom of infinity, or by the axiom schema of specification and the axiom of the power set applied twice to any set. 7.2.5 5. Axiom of union Main article: Axiom of union 44 CHAPTER 7. ZERMELO–FRAENKEL SET THEORY The union over the elements of a set exists. For example, the union over the elements of the set ff1; 2g; f2; 3gg is f1; 2; 3g . Formally, for any set F there is a set A containing every element that is a member of some member of F : 8F 9A8Y 8x[(x 2 Y ^ Y 2 F)) x 2 A]: A B f(x) f : A → B x Axiom schema of replacement: the image of the domain set A under the definable function f (i.e. the range of f) falls inside a set B. 7.2.6 6. Axiom schema of replacement Main article: Axiom schema of replacement The axiom schema of replacement asserts that the image of a set under any definable function will also fall inside a set. Formally, let �be any formula in the language of ZFC whose free variables are among x; y;A;w1; : : : ; wn , so that in particular B is not free in � . Then: 8A8w18w2 : : :8wn �8x(x 2 A) 9!y �)) 9B 8x�x 2 A) 9y(y 2 B ^ �)��: In other words, if the relation �represents a definable function f, A represents its domain, and f(x) is a set for every x in that domain, then the range of f is a subset of some set B . The form stated here, in which B may be larger than strictly necessary, is sometimes called the axiom schema of collection. 7.2. AXIOMS 45 7.2.7 7. Axiom of infinity Main article: Axiom of infinity Let S(w)abbreviate w [ fwg , where w is some set (We can see that fwg is a valid set by applying the Axiom of Pairing with x = y = wso that the set z is fwg). Then there exists a set X such that the empty set ? is a member of X and, whenever a set y is a member of X, then S(y)is also a member of X. 9X [? 2 X ^ 8y(y 2 X ) S(y) 2 X)] : More colloquially, there exists a set X having infinitely many members. The minimal set X satisfying the axiom of infinity is the von Neumann ordinal ω, which can also be thought of as the set of natural numbers N . 7.2.8 8. Axiom of power set Main article: Axiom of power set By definition a set z is a subset of a set x if and only if every element of z is also an element of x: (z � x), (8q(q 2 z ) q 2 x)): The Axiom of Power Set states that for any set x, there is a set y that contains every subset of x: 8x9y8z[z � x) z 2 y]: The axiom schema of specification is then used to define the power set P(x) as the subset of such a y containing the subsets of x exactly: P (x) = fz 2 y : z � xg Axioms 1–8 define ZF. Alternative forms of these axioms are often encountered, some of which are listed in Jech (2003). Some ZF axiomatizations include an axiom asserting that the empty set exists. The axioms of pairing, union, replacement, and power set are often stated so that the members of the set x whose existence is being asserted are just those sets which the axiom asserts x must contain. The following axiom is added to turn ZF into ZFC: 7.2.9 9. Well-ordering theorem Main article: Well-ordering theorem For any set X, there is a binary relation R which well-orders X. This means R is a linear order on X such that every nonempty subset of X has a member which is minimal under R. 8X9R(R well-orders X): Given axioms 1–8, there are many statements provably equivalent to axiom 9, the best known of which is the axiom of choice (AC), which goes as follows. Let X be a set whose members are all non-empty. Then there exists a function f from X to the union of the members of X, called a "choice function", such that for all Y ∈ X one has f(Y) ∈ Y. Since the existence of a choice function when X is a finite set is easily proved from axioms 1–8, AC only matters for certain infinite sets. AC is characterized as nonconstructive because it asserts the existence of a choice set but says nothing about how the choice set is to be “constructed.” Much research has sought to characterize the definability (or lack thereof) of certain sets whose existence AC asserts. 46 CHAPTER 7. ZERMELO–FRAENKEL SET THEORY 7.3 Motivation via the cumulative hierarchy One motivation for the ZFC axioms is the cumulative hierarchy of sets introduced by John von Neumann (Shoenfield 1977, sec. 2). In this viewpoint, the universe of set theory is built up in stages, with one stage for each ordinal number. At stage 0 there are no sets yet. At each following stage, a set is added to the universe if all of its elements have been added at previous stages. Thus the empty set is added at stage 1, and the set containing the empty set is added at stage 2; see Hinman (2005, p. 467). The collection of all sets that are obtained in this way, over all the stages, is known as V. The sets in V can be arranged into a hierarchy by assigning to each set the first stage at which that set was added to V. It is provable that a set is in V if and only if the set is pure and well-founded; and provable that V satisfies all the axioms of ZFC, if the class of ordinals has appropriate reflection properties. For example, suppose that a set x is added at stage α, which means that every element of x was added at a stage earlier than α. Then every subset of x is also added at stage α, because all elements of any subset of x were also added before stage α. This means that any subset of x which the axiom of separation can construct is added at stage α, and that the powerset of x will be added at the next stage after α. For a complete argument that V satisfies ZFC see Shoenfield (1977). The picture of the universe of sets stratified into the cumulative hierarchy is characteristic of ZFC and related ax- iomatic set theories such as Von Neumann–Bernays–Gödel set theory (often called NBG) and Morse–Kelley set theory. The cumulative hierarchy is not compatible with other set theories such as New Foundations. It is possible to change the definition of V so that at each stage, instead of adding all the subsets of the union of the previous stages, subsets are only added if they are definable in a certain sense. This results in a more “narrow” hierarchy which gives the constructible universe L, which also satisfies all the axioms of ZFC, including the axiom of choice. It is independent from the ZFC axioms whether V = L. Although the structure of L is more regular and well behaved than that of V, few mathematicians argue that V = L should be added to ZFC as an additional axiom. 7.4 Metamathematics The axiom schemata of replacement and separation each contain infinitely many instances. Montague (1961) included a result first proved in his 1957 Ph.D. thesis: if ZFC is consistent, it is impossible to axiomatize ZFC using only finitely many axioms. On the other hand, Von Neumann–Bernays–Gödel set theory (NBG) can be finitely axiomatized. The ontology of NBG includes proper classes as well as sets; a set is any class that can be a member of another class. NBG and ZFC are equivalent set theories in the sense that any theorem not mentioning classes and provable in one theory can be proved in the other. Gödel’s second incompleteness theorem says that a recursively axiomatizable system that can interpret Robinson arithmetic can prove its own consistency only if it is inconsistent. Moreover, Robinson arithmetic can be interpreted in general set theory, a small fragment of ZFC. Hence the consistency of ZFC cannot be proved within ZFC itself (unless it is actually inconsistent). Thus, to the extent that ZFC is identifiedwith ordinarymathematics, the consistency of ZFC cannot be demonstrated in ordinary mathematics. The consistency of ZFC does follow from the existence of a weakly inaccessible cardinal, which is unprovable in ZFC if ZFC is consistent. Nevertheless, it is deemed unlikely that ZFC harbors an unsuspected contradiction; it is widely believed that if ZFC were inconsistent, that fact would have been uncovered by now. This much is certain — ZFC is immune to the classic paradoxes of naive set theory: Russell’s paradox, the Burali-Forti paradox, and Cantor’s paradox. Abian and LaMacchia (1978) studied a subtheory of ZFC consisting of the axioms of extensionality, union, powerset, replacement, and choice. Using models, they proved this subtheory consistent, and proved that each of the axioms of extensionality, replacement, and power set is independent of the four remaining axioms of this subtheory. If this subtheory is augmented with the axiom of infinity, each of the axioms of union, choice, and infinity is independent of the five remaining axioms. Because there are non-well-founded models that satisfy each axiom of ZFC except the axiom of regularity, that axiom is independent of the other ZFC axioms. If consistent, ZFC cannot prove the existence of the inaccessible cardinals that category theory requires. Huge sets of this nature are possible if ZF is augmented with Tarski’s axiom (Tarski 1939). Assuming that axiom turns the axioms of infinity, power set, and choice (7 − 9 above) into theorems. 7.5. CRITICISMS 47 7.4.1 Independence Many important statements are independent of ZFC (see list of statements undecidable in ZFC). The independence is usually proved by forcing, whereby it is shown that every countable transitive model of ZFC (sometimes augmented with large cardinal axioms) can be expanded to satisfy the statement in question. A different expansion is then shown to satisfy the negation of the statement. An independence proof by forcing automatically proves independence from arithmetical statements, other concrete statements, and large cardinal axioms. Some statements independent of ZFC can be proven to hold in particular inner models, such as in the constructible universe. However, some statements that are true about constructible sets are not consistent with hypothesized large cardinal axioms. Forcing proves that the following statements are independent of ZFC: � Continuum hypothesis � Diamond principle � Suslin hypothesis � Martin’s axiom (which is not a ZFC axiom) � Axiom of Constructibility (V=L) (which is also not a ZFC axiom). Remarks: � The consistency of V=L is provable by inner models but not forcing: every model of ZF can be trimmed to become a model of ZFC + V=L. � The Diamond Principle implies the Continuum Hypothesis and the negation of the Suslin Hypothesis. � Martin’s axiom plus the negation of the Continuum Hypothesis implies the Suslin Hypothesis. � The constructible universe satisfies the Generalized Continuum Hypothesis, the Diamond Principle, Martin’s Axiom and the Kurepa Hypothesis. � The failure of the Kurepa hypothesis is equiconsistent with the existence of a strongly inaccessible cardinal. A variation on the method of forcing can also be used to demonstrate the consistency and unprovability of the axiom of choice, i.e., that the axiom of choice is independent of ZF. The consistency of choice can be (relatively) easily verified by proving that the inner model L satisfies choice. (Thus every model of ZF contains a submodel of ZFC, so that Con(ZF) implies Con(ZFC).) Since forcing preserves choice, we cannot directly produce a model contradicting choice from a model satisfying choice. However, we can use forcing to create a model which contains a suitable submodel, namely one satisfying ZF but not C. Another method of proving independence results, one owing nothing to forcing, is based on Gödel’s second in- completeness theorem. This approach employs the statement whose independence is being examined, to prove the existence of a set model of ZFC, in which case Con(ZFC) is true. Since ZFC satisfies the conditions of Gödel’s second theorem, the consistency of ZFC is unprovable in ZFC (provided that ZFC is, in fact, consistent). Hence no statement allowing such a proof can be proved in ZFC. This method can prove that the existence of large cardinals is not provable in ZFC, but cannot prove that assuming such cardinals, given ZFC, is free of contradiction. 7.5 Criticisms For criticism of set theory in general, see Objections to set theory ZFC has been criticized both for being excessively strong and for being excessively weak, as well as for its failure to capture objects such as proper classes and the universal set. Many mathematical theorems can be proven in much weaker systems than ZFC, such as Peano arithmetic and second order arithmetic (as explored by the program of reverse mathematics). Saunders Mac Lane and Solomon Feferman have both made this point. Some of “mainstream mathematics” (mathematics not directly connected with axiomatic 48 CHAPTER 7. ZERMELO–FRAENKEL SET THEORY set theory) is beyond Peano arithmetic and second order arithmetic, but still, all such mathematics can be carried out in ZC (Zermelo set theory with choice), another theory weaker than ZFC. Much of the power of ZFC, including the axiom of regularity and the axiom schema of replacement, is included primarily to facilitate the study of the set theory itself. On the other hand, among axiomatic set theories, ZFC is comparatively weak. Unlike New Foundations, ZFC does not admit the existence of a universal set. Hence the universe of sets under ZFC is not closed under the elementary operations of the algebra of sets. Unlike von Neumann–Bernays–Gödel set theory and Morse–Kelley set theory (MK), ZFC does not admit the existence of proper classes. These ontological restrictions are required for ZFC to avoid Russell’s paradox, but critics argue these restrictions make the ZFC axioms fail to capture the informal concept of set. A further comparative weakness of ZFC is that the axiom of choice included in ZFC is weaker than the axiom of global choice included in MK. There are numerous mathematical statements undecidable in ZFC. These include the continuum hypothesis, the Whitehead problem, and the Normal Moore space conjecture. Some of these conjectures are provable with the addition of axioms such as Martin’s axiom, large cardinal axioms to ZFC. Some others are decided in ZF+AD where AD is the axiom of determinacy, a strong supposition incompatible with choice. One attraction of large cardinal axioms is that they enable many results from ZF+AD to be established in ZFC adjoined by some large cardinal axiom (see projective determinacy). The Mizar system and Metamath have adopted Tarski–Grothendieck set theory, an extension of ZFC, so that proofs involving Grothendieck universes (encountered in category theory and algebraic geometry) can be formalized. 7.6 See also � Foundation of mathematics � Inner model � Large cardinal axiom Related axiomatic set theories: � Morse–Kelley set theory � Von Neumann–Bernays–Gödel set theory � Tarski–Grothendieck set theory � Constructive set theory � Internal set theory 7.7 References � Abian, Alexander (1965). The Theory of Sets and Transfinite Arithmetic. W B Saunders. � ———; LaMacchia, Samuel (1978). “On the Consistency and Independence of Some Set-Theoretical Ax- ioms”. Notre Dame Journal of Formal Logic 19: 155–58. doi:10.1305/ndjfl/1093888220. � Devlin, Keith (1996) [1984]. The Joy of Sets. Springer. � Heinz-Dieter Ebbinghaus, 2007. Ernst Zermelo: An Approach to His Life and Work. Springer. ISBN 978-3- 540-49551-2. � Abraham Fraenkel, Yehoshua Bar-Hillel, and Azriel Levy, 1973 (1958). Foundations of Set Theory. North- Holland. Fraenkel’s final word on ZF and ZFC. � Hatcher, William, 1982 (1968). The Logical Foundations of Mathematics. Pergamon Press. � Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. ISBN 978-1-56881-262-5 7.8. EXTERNAL LINKS 49 � Thomas Jech, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2. � Kenneth Kunen, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9. � Richard Montague, 1961, “Semantic closure and non-finite axiomatizability” in Infinistic Methods. London: Pergamon Press: 45–69. � Patrick Suppes, 1972 (1960). Axiomatic Set Theory. Dover reprint. Perhaps the best exposition of ZFC before the independence of AC and the Continuum hypothesis, and the emergence of large cardinals. Includes many theorems. � Gaisi Takeuti and Zaring, W M, 1971. Introduction to Axiomatic Set Theory. Springer-Verlag. � Alfred Tarski, 1939, “On well-ordered subsets of any set,”, Fundamenta Mathematicae 32: 176-83. � Tiles, Mary, 2004 (1989). The Philosophy of Set Theory. Dover reprint. Weak on metatheory; the author is not a mathematician. � Tourlakis, George, 2003. Lectures in Logic and Set Theory, Vol. 2. Cambridge University Press. � Jean van Heijenoort, 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press. Includes annotated English translations of the classic articles by Zermelo, Fraenkel, and Skolem bearing on ZFC. � Zermelo, Ernst (1908). “Untersuchungen über die Grundlagen der Mengenlehre I”. Mathematische Annalen 65: 261–281. doi:10.1007/BF01449999. English translation in Heijenoort, Jean van (1967). “Investigations in the foundations of set theory”. From Frege to Gödel: A Source Book inMathematical Logic, 1879–1931. Source Books in the History of the Sciences. Harvard University Press. pp. 199–215. ISBN 978-0-674-32449-7. � Zermelo, Ernst (1930). "Über Grenzzahlen und Mengenbereiche”. Fundamenta Mathematicae 16: 29–47. ISSN 0016-2736. 7.8 External links � Hazewinkel, Michiel, ed. (2001), “ZFC”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 � Stanford Encyclopedia of Philosophy articles by Thomas Jech: � Set Theory; � Axioms of Zermelo–Fraenkel Set Theory. � Metamath version of the ZFC axioms — A concise and nonredundant axiomatization. The background first order logic is defined especially to facilitate machine verification of proofs. � Aderivation inMetamath of a version of the separation schema from a version of the replacement schema. � Zermelo-Fraenkel Axioms at PlanetMath.org. � Weisstein, Eric W., “Zermelo-Fraenkel Set Theory”, MathWorld. 50 CHAPTER 7. ZERMELO–FRAENKEL SET THEORY 7.9 Text and image sources, contributors, and licenses 7.9.1 Text � Combinatorics Source: https://en.wikipedia.org/wiki/Combinatorics?oldid=669550774 Contributors: AxelBoldt, Zundark, Stevertigo, Chas zzz brown, Michael Hardy, Kku, Mcarling, Pcb21, Goatasaur, Ejrh, Mxn, Rodney Topor, RodC, Charles Matthews, Viz, Dysprosia, Peregrine981, Zudu29, Furrykef, Hyacinth, McKay, Traroth, Tjdw, Robbot, Naddy, Lowellian, Ianb, MathMartin, Lesonyrra, AceMyth, Aniu~enwiki, JesseW, Marc Venot, Centrx, Giftlite, Dbenbenn, DocWatson42, Paul Richter, Eran, Lethe, Tom harrison, Dratman, Cy- borgTosser, Bobblewik, Zarvok, Alberto da Calvairate~enwiki, Antandrus, Gunnar Larsson, APH, Almit39, Chadernook, Urhixidur, Camipco, Robin klein, ELApro, Shahab, Mormegil, Wfaulk, Ralph Corderoy, Guanabot, Sam Derbyshire, Paul August, Zaslav, Spoon!, Causa sui, Bobo192, R. S. Shaw, Haham hanuka, Jumbuck, Msh210, Stack, Cowsandmilk, Kusma, Igorpak, Ultramarine, Oleg Alexan- drov, Japanese Searobin, Alkarex, Dryguy, Woohookitty, Rocastelo, Will Orrick, Oliphaunt, Mondhir~enwiki, Chochopk, Btyner, Palica, Graham87, Magister Mathematicae, FreplySpang, Kitarak, Rjwilmsi, Nneonneo, Nandesuka, DrBozzball, FlaBot, SchuminWeb, Math- bot, Malhonen, Masnevets, Chobot, Jersey Devil, DVdm, Nehalem, Gwernol, YurikBot, Wavelength, Hairy Dude, Deeptrivia, Michael Slone, KSmrq, Dkostic, Dbmag9, Hakkinen, Nathan11g, LarryLACa, Oakwood, TomJF, Arcades, Anclation~enwiki, Kaicarver, Mem- odude, GrEp, Infinity0, CrniBombarder!!!, Finell, Capitalist, Sardanaphalus, SmackBot, Peterven, Ttzz, Sticky Parkin, Davidhand, In- verseHypercube, Jagged 85, Mcld, Brianv, PrimeHunter, AndrewBuck, Taxipom, Sisodia, RyanEberhart, Mhym, Nonforma, DRLB, -Ozone-, G716, Kensor, Doug Bell, Teutanic, 16@r, Macarion, Dicklyon, Kvng, GoCooL, EZio, Mulder416sBot, CRGreathouse, Wa- fulz, JRavn, Vyznev Xnebara, ShelfSkewed, WeggeBot, Some P. Erson, Myasuda, Ntsimp, Mblumber, Zahlentheorie, Red Director, Aa- jaja, Thijs!bot, King Bee, Gryspnik, Tocharianne, Urdutext, Fedayee, Hermel, JAnDbot, MER-C, VoABot II, Ling.Nut, David Eppstein, DirkOliverTheis, FANSTARbot, Koko90, Lantonov, CombAuc, Indeed123, Aresch~enwiki, Nwbeeson, Policron, Ultra two, Furnald- Hall, Carter, JohnBlackburne, LokiClock, Ptrillian, TXiKiBoT, Malsaqer, Anonymous Dissident, PaulTanenbaum, Peter Alan McAllis- ter~enwiki, Mickster810, Kmhkmh, Bbukh, Arcfrk, Symane, EuPhyte, Gatinha, Gerakibot, Matthew Yeager, Tiptoety, Thehotelambush, Mike2vil, Anchor Link Bot, S2000magician, Athenean, Wantnot, ClueBot, Rks22, Bob1960evens, Thegeneralguy, PixelBot, Bracton, Thingg, Heyzeuss, Erodium, RMFan1, Vadimvadim, XLinkBot, Marc van Leeuwen, SilvonenBot, Willking1979, Betterusername, Ron B. Thomson, Tomthecool, NjardarBot, MrOllie, Delaszk, Nassrat, Zorrobot, Jarble, Noumenon, Legobot, Luckas-bot, Yobot, Kilom691, KamikazeBot, AnomieBOT, Ciphers, ��, Citation bot, Timir2, Thore Husfeldt, GrouchoBot, Arid Zkwelty, Charvest, BoomerAB, Alex- isastupidnoob, Tobby72, HRoestBot, RedBot, Fparnon, TjBot, EmausBot, Jmencisom, Bethnim, Phoenixthebird, Sourabh Katagade, Ahughes6, Devanshuhpandey, OnePt618, Agatecat2700, ClueBot NG, Wcherowi, CocuBot, Joel B. Lewis, Widr, Helpful Pixie Bot, Leonxlin, Ijgt, Piguy101, Rajathsbhat, Will Gladstone, Brad7777, Dtotoo, JYBot, RichardMarioFratini, Mark viking, Purnendu Kar- makar, SakeUPenn, Dough34, Jorgelin10, Theodora.ser, Fts46 and Anonymous: 231 � Continuumhypothesis Source: https://en.wikipedia.org/wiki/Continuum_hypothesis?oldid=663811724Contributors: AxelBoldt, Archibald Fitzchesterfield, Bryan Derksen, Zundark, The Anome, Andre Engels, Hari, Miguel~enwiki, Roadrunner, Shii, Stevertigo, Spiff~enwiki, Michael Hardy, Nixdorf, MartinHarper, Gabbe, Wapcaplet, Karada, Eric119, Snoyes, Marco Krohn, Tim Retout, Schneelocke, Ideyal, Charles Matthews, Timwi, Vanu, Reddi, Paul Stansifer, Doradus, .mau., Phil Boswell, Aleph4, Donarreiskoffer, Fredrik, Bethenco, Timrollpickering, Tobias Bergemann, Giftlite, Dbenbenn, Graeme Bartlett, Ævar Arnfjörð Bjarmason, Lethe, Fropuff, Dratman, Ee- quor, Fuzzy Logic, Icairns, Frenchwhale, Rich Farmbrough, TedPavlic, Guanabot, Luqui, Paul August, EmilJ, Robotje, Reinyday, Obradovic Goran, Haham hanuka, Crust, Jumbuck, Keenan Pepper, Sligocki, Adrian.benko, Oleg Alexandrov, Joriki, StradivariusTV, Ruud Koot, Isnow, Marudubshinki, Graham87, Jobnikon, Yurik, Porcher, Rjwilmsi, NatusRoma, Salix alba, R.e.b., Penumbra2000, FlaBot, Laubrau~enwiki, YurikBot, Open4D, Ksnortum, Gaius Cornelius, Abarry, Stassats, B-Con, CarlHewitt, SEWilcoBot, Trova- tore, Eltwarg, Arthur Rubin, AssistantX, GrinBot~enwiki, SmackBot, Nihonjoe, InverseHypercube, SaxTeacher, TimBentley, DHN- bot~enwiki, Tekhnofiend, Cybercobra, DRLB, Byelf2007, Loadmaster, Mets501, MedeaMelana, Quaeler, Dan Gluck, Zero sharp, JR- Spriggs, CBM, Discordant~enwiki, Gregbard, Cydebot, Peterdjones, Michael C Price, Thijs!bot, King Bee, Drpixie, Dugwiki, Eleuther, AntiVandalBot, M cuffa, Ling.Nut, Sullivan.t.j, David Eppstein, Kope, R'n'B, Alexcalamaro, Leocat, Ttwo, SpeedOfDarkness, VolkovBot, Red Act, Nxavar, Layman1, YohanN7, Dogah, SieBot, Ivan Štambuk, Alexis Humphreys, Likebox, Jojalozzo, Anchor Link Bot, CBM2, Cngoulimis, JustinBlank, JuPitEer, Hans Adler, Candhrim~enwiki, Jsondow, Thehelpfulone, MelonBot, Avoided, DOI bot, Unzerleg- barkeit, Lightbot, Know-edu, Legobot, Luckas-bot, Yobot, AnomieBOT, Materialscientist, Citation bot, ArthurBot, Xqbot, RJGray, VladimirReshetnikov, CES1596, Sémaphore, Citation bot 1, Tkuvho, Elockid, RedBot, Belovedeagle, 777sms, Pierpao, ClueBot NG, Deadwooddrz, Shivsagardharam,WhatisFGH, Trichometetrahydron, ChrisGualtieri, Ardegloo, Dexbot, Andyhowlett, Qualois, Adam.conkey, Monkbot, Wchargin, MathPhilFan, SoSivr and Anonymous: 113 � Forcing (mathematics) Source: https://en.wikipedia.org/wiki/Forcing_(mathematics)?oldid=669357287Contributors: AxelBoldt, Michael Hardy, Ottawakungfu, Bogdangiusca, Poor Yorick, Charles Matthews, Dysprosia, Quux, Aleph4, Tobias Bergemann, Giftlite, Sam Hoce- var, Splatty, Luqui, Gauge, Peter M Gerdes, Oleg Alexandrov, Ryan Reich, Eyu100, Mikedelsol, R.e.b., Billjefferys, Hornplease, KSmrq, Gaius Cornelius, Trovatore, Baarslag, That Guy, From That Show!, AndrewWTaylor, SmackBot, SaxTeacher, Slaniel, Mhss, Silly rab- bit, Nbarth, Radagast83, Luke Gustafson, Nat2, Beetstra, Mets501, Stotr~enwiki, Jason22~enwiki, JRSpriggs, CRGreathouse, Myasuda, Gregbard, Cydebot, Yrodro, Thijs!bot, Eleuther, Alphachimpbot, S vatev, Ttwo, VolkovBot, Nxavar, YohanN7, Mathwizard44, Paul Clapham, ClueBot, Arakunem, MystBot, Good Olfactory, Addbot, יש דוד, Citation bot, RJGray, VladimirReshetnikov, Ash870284, D'ohBot, MarcelB612, ToematoeAdmn, EmausBot, Set theorist, Fairflow, ChuispastonBot, ClueBot NG, Frietjes, Harsimaja, Ansatz, Nedeljko Stefanovic, ChrisGualtieri, Dtotoo and Anonymous: 47 � Partially ordered set Source: https://en.wikipedia.org/wiki/Partially_ordered_set?oldid=670239477 Contributors: Bryan Derksen, Zun- dark, Tomo, Patrick, Bcrowell, Chinju, TakuyaMurata, GTBacchus, AugPi, Charles Matthews, Timwi, Dcoetzee, Dysprosia, Doradus, Maximus Rex, Fibonacci, Tobias Bergemann, Giftlite, Markus Krötzsch, Fropuff, Peruvianllama, Jason Quinn, Neilc, Gubbubu, De- fLog~enwiki, MarkSweep, Urhixidur, TheJames, Paul August, Zaslav, Spoon!, Porton, Haham hanuka, DougOrleans, Msh210, Oleg Alexandrov, Daira Hopwood, MFH, Salix alba, FlaBot, Vonkje, Chobot, Laurentius, Dmharvey, Vecter, Sanguinity, Modify, RDBury, Incnis Mrsi, Brick Thrower, Cesine, Zanetu, Jcarroll, Nbarth, Jdthood, Javalenok, Kjetil1001, Dreadstar, Esoth~enwiki, Mike Fikes, A. Pichler, Vaughan Pratt, CRGreathouse, L'œuf, CBM, Werratal, Rlupsa, CZeke, Ill logic, JAnDbot, MER-C, BrotherE, Tbleher, A3nm, David Eppstein, SlamDiego, Bissinger, Haseldon, Daniel5Ko, GaborLajos, NewEnglandYankee, Orphic, RobertDanielEmerson, TXiK- iBoT, Digby Tantrum, PaulTanenbaum, Arcfrk, SieBot, Mochan Shrestha, TheGhostOfAdrianMineha, Thehotelambush, Megaloxantha, Peiresc~enwiki, Cheesefondue, Jludwig, ClueBot, Morinus, Justin W Smith, Methossant, Pi zero, Jonathanrcoxhead, Watchduck, Com- puterGeezer, He7d3r, Hans Adler, Jtle515, Palnot, Marc van Leeuwen, Ankan babee, Addbot, Download, Luckyz, Legobot, Kilom691, AnomieBOT, Erel Segal, Citation bot, SteveWoolf, Undsoweiter, FrescoBot, Nicolas Perrault III, Confluente, Ricardo Ferreira de Oliveira, Throw it in the Fire, Gnathan87, Setitup, EmausBot, John of Reading, Febuiles, Thecheesykid, ZéroBot, Chharvey, The man who was 7.9. TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES 51 Friday, SporkBot, Zfeinst, Rathgemz, CocuBot, Vdamanafshan, Mesoderm, MerlIwBot, Wbm1058, Jakshap, Paolo Lipparini, ElphiBot, Larion Garaczi, Aabhis, Jochen Burghardt, Mark viking, Eamonford, Sgbmyr, K401sTL3, Tudor987, Victor Lesyk, Some1Redirects4You and Anonymous: 78 � Sunflower (mathematics) Source: https://en.wikipedia.org/wiki/Sunflower_(mathematics)?oldid=627085018Contributors: Michael Hardy, Charles Matthews, David Haslam, R.e.b., Jason22~enwiki, Cydebot, David Eppstein, VolkovBot, Rei-bot, Hans Adler, Addbot, Luckas- bot, Yobot, Citation bot, Trappist the monk, EmausBot, Set theorist, ZéroBot and Anonymous: 3 � Upper and lower bounds Source: https://en.wikipedia.org/wiki/Upper_and_lower_bounds?oldid=668513297 Contributors: Toby Bar- tels, Miguel~enwiki, Patrick, Michael Hardy, Emperorbma, Dysprosia, Thue, Shizhao, Tobias Bergemann, Markus Krötzsch, Guillau- mito, Discospinster, Sligocki, RJFJR, Gortu, Oleg Alexandrov, Esben~enwiki, Isnow, Therefore, YurikBot, Voidxor, Bota47, Arthur Rubin, Vicarious, SmackBot, PizzaMargherita, Mhss, Carbonrodney, Nbarth, Lambiam, Dicklyon, CBM, Lightblade, Widefox, Kerotan, Wku2m5rr, MartinBot, L06ChBea, Vipul S. Chawathe, PaulTanenbaum, Insanity Incarnate, Steven Zhang, DEMcAdams, Martarius, Pal- lida Mors, AmirOnWiki, Addbot, OlEnglish, Gail, Yobot, TaBOT-zerem, Zagothal, Capricorn42, J36miles, ClueBot NG, Gaara2link, Pluma, MerlIwBot, Ricordisamoa, Onedirectionsbabe, Jianhui67, Loraof and Anonymous: 52 � Zermelo–Fraenkel set theory Source: https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory?oldid=667302194Con- tributors: AxelBoldt, Matthew Woodcraft, Zundark, Tarquin, Toby Bartels, Dwheeler, Patrick, Michael Hardy, MartinHarper, Bcrow- ell, Chinju, Haakon, Habj, Tim Retout, Schneelocke, Charles Matthews, Dcoetzee, Dysprosia, Greenrd, Hyacinth, VeryVerily, Fi- bonacci, JohnH~enwiki, Aleph4, Rursus, Tobias Bergemann, Giftlite, Smjg, Dratman, CyborgTosser, Mellum, Jorend, Ajgorhoe, Taran- toga~enwiki, David Sneek, Vsmith, Bender235, Elwikipedista~enwiki, Peter M Gerdes, Nortexoid, Obradovic Goran, Msh210, Su- ruena, TXlogic, Gible, Oleg Alexandrov, Joriki, OwenX, Drostie, Ma Baker, Hdante, Esben~enwiki, Dionyziz, MarSch, Salix alba, R.e.b., STarry, Chobot, Karch, YurikBot, Hairy Dude, Michael Slone, Piet Delport, Ksnortum, Ogai, Trovatore, Twin Bird, Expen- sivehat, Insipid, Jpbowen, Crasshopper, Wknight94, Arthur Rubin, Josh3580, Banus, Otto ter Haar, Schizobullet, A bit iffy, SmackBot, Fulldecent, Mhss, Darth Panda, Foxjwill, Tsca.bot, Miguel1626, TKD, Allan McInnes, Grover cleveland, Acepectif, Jon Awbrey, Meni Rosenfeld, Stefano85, Vina-iwbot~enwiki, Noegenesis, Rainwarrior, Dicklyon, Tophtucker, JRSpriggs, CRGreathouse, CBM, Myasuda, Gregbard, Awmorp, Thijs!bot, Whooooooknows, Odoncaoa, Jirka6, VictorAnyakin, JAnDbot, Quentar~enwiki, Giler, Mathfreq, Omi- cron18, JustinRosenstein, Diroth, The Real Marauder, Numbo3, Ttwo, Trumpet marietta 45750, Policron, JavierMC, The enemies of god, Crisperdue, Pasixxxx, Magmi, Bistromathic, Henry Delforn (old), Jjepfl, C xong, JP.Martin-Flatin, Alexbot, Iohannes Animosus, Palnot, Marc van Leeuwen, Addbot, Matěj Grabovský, Yobot, AnomieBOT, Materialscientist, La comadreja, Control.valve, Vladimir- Reshetnikov, Nicolas Perrault III, Andrewjameskirk, NSH002, Tkuvho, Zdorovo, ClueBot NG, Chetrasho, Snotbot, Helpful Pixie Bot, Brad7777, Daysrr, Khazar2, Jochen Burghardt, Mark viking and Anonymous: 119 7.9.2 Images � File:Birkhoff120.svg Source: https://upload.wikimedia.org/wikipedia/commons/7/7c/Birkhoff120.svg License: Public domain Contrib- utors: Own work Original artist: David Eppstein � File:Catalan_4_leaves_binary_tree_example.svg Source: https://upload.wikimedia.org/wikipedia/commons/b/b4/Catalan_4_leaves_ binary_tree_example.svg License: Public domain Contributors: Transferred from es.wikipedia to Commons. Original artist: The original uploader was Jasampler at Spanish Wikipedia � File:Codomain2_A_B.SVG Source: https://upload.wikimedia.org/wikipedia/commons/d/d1/Codomain2_A_B.SVG License: Public domain Contributors: Own work (Original text: I created this work entirely by myself.) Original artist: Damien Karras (talk) � File:Collier-de-perles-rouge-vert.svg Source: https://upload.wikimedia.org/wikipedia/commons/4/47/Collier-de-perles-rouge-vert.svg License: CC BY-SA 4.0 Contributors: Own work Original artist: Kilom691 � File:Commons-logo.svg Source: https://upload.wikimedia.org/wikipedia/en/4/4a/Commons-logo.svg License: ? Contributors: ? Origi- nal artist: ? � File:Folder_Hexagonal_Icon.svg Source: https://upload.wikimedia.org/wikipedia/en/4/48/Folder_Hexagonal_Icon.svg License: Cc- by-sa-3.0 Contributors: ? Original artist: ? � File:Hasse_diagram_of_powerset_of_3.svg Source: https://upload.wikimedia.org/wikipedia/commons/e/ea/Hasse_diagram_of_powerset_ of_3.svg License: CC-BY-SA-3.0 Contributors: self-made using graphviz's dot. Original artist: KSmrq � File:Hasse_diagram_of_powerset_of_3_no_greatest_or_least.svg Source: https://upload.wikimedia.org/wikipedia/commons/9/9e/ Hasse_diagram_of_powerset_of_3_no_greatest_or_least.svg License: CC-BY-SA-3.0 Contributors: Based on File:Hasse diagram of powerset of 3.svg Original artist: User:Fibonacci, User:KSmrq � File:Icosahedron.svg Source: https://upload.wikimedia.org/wikipedia/commons/b/b7/Icosahedron.svg License: CC-BY-SA-3.0 Con- tributors: Vectorisation of Image:Icosahedron.jpg Original artist: User:DTR � File:Infinite_lattice_of_divisors.svg Source: https://upload.wikimedia.org/wikipedia/commons/e/e6/Infinite_lattice_of_divisors.svg License: Public domain Contributors: w:de:Datei:Verband TeilerN.png Original artist: Watchduck (a.k.a. Tilman Piesk) � File:Internet_map_1024.jpg Source: https://upload.wikimedia.org/wikipedia/commons/d/d2/Internet_map_1024.jpg License: CC BY 2.5 Contributors: Originally from the English Wikipedia; description page is/was here. Original artist: The Opte Project � File:Kissing-3d.png Source: https://upload.wikimedia.org/wikipedia/commons/8/8f/Kissing-3d.png License: CC BY-SA 3.0 Contrib- utors: Transferred from en.wikipedia; transfer was stated to be made by User:Yelm. Original artist: Original uploader was Robertwb at en.wikipedia � File:Lexicographic_order_on_pairs_of_natural_numbers.svg Source: https://upload.wikimedia.org/wikipedia/commons/8/8a/Lexicographic_ order_on_pairs_of_natural_numbers.svg License: CC BY-SA 3.0 Contributors: Own work Original artist: Jochen Burghardt � File:Monotonic_but_nonhomomorphic_map_between_lattices.gif Source: https://upload.wikimedia.org/wikipedia/commons/8/8c/ Monotonic_but_nonhomomorphic_map_between_lattices.gif License: CC BY-SA 3.0 Contributors: Own work Original artist: Jochen Burghardt � File:Morse-Thue_sequence.gif Source: https://upload.wikimedia.org/wikipedia/commons/f/f1/Morse-Thue_sequence.gifLicense: Pub- lic domain Contributors: Own work Original artist: Axa2 52 CHAPTER 7. ZERMELO–FRAENKEL SET THEORY � File:N-Quadrat,_gedreht.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/13/N-Quadrat%2C_gedreht.svgLicense: CC0 Contributors: Own work Original artist: Mini-floh � File:Partition3D.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/14/Partition3D.svg License: CC BY-SA 3.0 Contrib- utors: Own work Original artist: Kilom691 � File:People_icon.svg Source: https://upload.wikimedia.org/wikipedia/commons/3/37/People_icon.svgLicense: CC0Contributors: Open- Clipart Original artist: OpenClipart � File:Petersen1_tiny.svg Source: https://upload.wikimedia.org/wikipedia/commons/9/91/Petersen1_tiny.svg License: CC BY-SA 3.0 Contributors: Own work by uploader based on http://en.wikipedia.org/wiki/File:Heawood_Graph.svg Original artist: Leshabirukov � File:Plain-bob-minor_2.png Source: https://upload.wikimedia.org/wikipedia/commons/0/0b/Plain-bob-minor_2.png License: Public domain Contributors: ? Original artist: ? � File:Portal-puzzle.svg Source: https://upload.wikimedia.org/wikipedia/en/f/fd/Portal-puzzle.svg License: Public domain Contributors: ? Original artist: ? � File:Poset6.jpg Source: https://upload.wikimedia.org/wikipedia/en/1/12/Poset6.jpg License: PD Contributors: ? Original artist: ? � File:Self_avoiding_walk.svg Source: https://upload.wikimedia.org/wikipedia/commons/5/5b/Self_avoiding_walk.svg License: GFDL Contributors: Own work Original artist: User:Rocchini, simplification by User:Life of Riley � File:Sonnenblume_02_KMJ.jpg Source: https://upload.wikimedia.org/wikipedia/commons/e/ec/Sonnenblume_02_KMJ.jpg License: CC-BY-SA-3.0 Contributors: Transfered from de.wikipedia Original artist: Original uploader was KMJ at de.wikipedia � File:Strict_product_order_on_pairs_of_natural_numbers.svg Source: https://upload.wikimedia.org/wikipedia/commons/8/88/Strict_ product_order_on_pairs_of_natural_numbers.svg License: CC BY-SA 3.0 Contributors: Own work Original artist: Jochen Burghardt � File:Text_document_with_red_question_mark.svg Source: https://upload.wikimedia.org/wikipedia/commons/a/a4/Text_document_ with_red_question_mark.svg License: Public domain Contributors: Created by bdesham with Inkscape; based upon Text-x-generic.svg from the Tango project. Original artist: Benjamin D. Esham (bdesham) � File:Venn_A_intersect_B.svg Source: https://upload.wikimedia.org/wikipedia/commons/6/6d/Venn_A_intersect_B.svg License: Pub- lic domain Contributors: Own work Original artist: Cepheus � File:Wiki_letter_w_cropped.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/1c/Wiki_letter_w_cropped.svg License: CC-BY-SA-3.0 Contributors: � Wiki_letter_w.svg Original artist: Wiki_letter_w.svg: Jarkko Piiroinen � File:Wiktionary-logo-en.svg Source: https://upload.wikimedia.org/wikipedia/commons/f/f8/Wiktionary-logo-en.svg License: Public domain Contributors: Vector version of Image:Wiktionary-logo-en.png. Original artist: Vectorized by Fvasconcellos (talk · contribs), based on original logo tossed together by Brion Vibber � File:Young_diagram_for_541_partition.svg Source: https://upload.wikimedia.org/wikipedia/commons/f/f2/Young_diagram_for_541_ partition.svg License: CC-BY-SA-3.0 Contributors: ? Original artist: ? 7.9.3 Content license � Creative Commons Attribution-Share Alike 3.0 Combinatorics History Approaches and subfields of combinatorics Enumerative combinatorics Analytic combinatorics Partition theory Graph theory Design theory Finite geometry Order theory Matroid theory Extremal combinatorics Probabilistic combinatorics Algebraic combinatorics Combinatorics on words Geometric combinatorics Topological combinatorics Arithmetic combinatorics Infinitary combinatorics Related fields Combinatorial optimization Coding theory Discrete and computational geometry Combinatorics and dynamical systems Combinatorics and physics See also Notes References External links Continuum hypothesis Cardinality of infinite sets Independence from ZFC Arguments for and against CH The generalized continuum hypothesis Implications of GCH for cardinal exponentiation See also References External links Forcing (mathematics) Intuitions Forcing posets P-names Interpretation Example Countable transitive models and generic filters Forcing Consistency Cohen forcing The countable chain condition Easton forcing Random reals Boolean-valued models Meta-mathematical explanation Logical explanation See also References External links Partially ordered set Formal definition Examples Extrema Orders on the Cartesian product of partially ordered sets Sums of partially ordered sets Strict and non-strict partial orders Inverse and order dual Mappings between partially ordered sets Number of partial orders Linear extension In category theory Partial orders in topological spaces Interval See also Notes References External links Sunflower (mathematics) Δ lemma Δ lemma for 2 Sunflower lemma and conjecture References Upper and lower bounds Properties Examples Bounds of functions Tight bounds References Zermelo–Fraenkel set theory History Axioms 1. Axiom of extensionality 2. Axiom of regularity (also called the Axiom of foundation) 3. Axiom schema of specification (also called the axiom schema of separation or of restricted comprehension) 4. Axiom of pairing 5. Axiom of union 6. Axiom schema of replacement 7. Axiom of infinity 8. Axiom of power set 9. Well-ordering theorem Motivation via the cumulative hierarchy Metamathematics Independence Criticisms See also References External links Text and image sources, contributors, and licenses Text Images Content license