Infinitary combinatorics

Last updated

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum [1] and combinatorics on successors of singular cardinals. [2]

Contents

Ramsey theory for infinite sets

Write for ordinals, for a cardinal number (finite or infinite) and for a natural number. Erdős & Rado (1956) introduced the notation

as a shorthand way of saying that every partition of the set of -element subsets of into pieces has a homogeneous set of order type . A homogeneous set is in this case a subset of such that every -element subset is in the same element of the partition. When is 2 it is often omitted. Such statements are known as partition relations.

Assuming the axiom of choice, there are no ordinals with , so is usually taken to be finite. An extension where is almost allowed to be infinite is the notation

which is a shorthand way of saying that every partition of the set of finite subsets of into pieces has a subset of order type such that for any finite , all subsets of size are in the same element of the partition. When is 2 it is often omitted.

Another variation is the notation

which is a shorthand way of saying that every coloring of the set of -element subsets of with 2 colors has a subset of order type such that all elements of have the first color, or a subset of order type such that all elements of have the second color.

Some properties of this include: (in what follows is a cardinal)

for all finite and (Ramsey's theorem).
(the Erdős–Rado theorem.)
(the Sierpiński theorem)
(the Erdős–Dushnik–Miller theorem)

In choiceless universes, partition properties with infinite exponents may hold, and some of them are obtained as consequences of the axiom of determinacy (AD). For example, Donald A. Martin proved that AD implies

Strong colorings

Wacław Sierpiński showed that the Ramsey theorem does not extend to sets of size by showing that . That is, Sierpiński constructed a coloring of pairs of real numbers into two colors such that for every uncountable subset of real numbers , takes both colors. Taking any set of real numbers of size and applying the coloring of Sierpiński to it, we get that . Colorings such as this are known as strong colorings [3] and studied in set theory. Erdős, Hajnal & Rado (1965) introduced a similar notation as above for this.

Write for ordinals, for a cardinal number (finite or infinite) and for a natural number. Then

is a shorthand way of saying that there exists a coloring of the set of -element subsets of into pieces such that every set of order type is a rainbow set. A rainbow set is in this case a subset of such that takes all colors. When is 2 it is often omitted. Such statements are known as negative square bracket partition relations.

Another variation is the notation

which is a shorthand way of saying that there exists a coloring of the set of 2-element subsets of with colors such that for every subset of order type and every subset of order type , the set takes all colors.

Some properties of this include: (in what follows is a cardinal)

(Sierpiński)
(Sierpiński)
(Laver, Blass)
( Galvin and Shelah)
(Todorčević)
(Moore)
( Galvin and Shelah)

Large cardinals

Several large cardinal properties can be defined using this notation. In particular:

Notes

  1. Andreas Blass, Combinatorial Cardinal Characteristics of the Continuum, Chapter 6 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010
  2. Todd Eisworth, Successors of Singular Cardinals Chapter 15 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010
  3. Rinot, Assaf, Tutorial on strong colorings and their applications, 6th European Set Theory Conference , retrieved 2023-12-10

Related Research Articles

In mathematics, specifically set theory, 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."

<span class="mw-page-title-main">Cardinal number</span> Size of a possibly infinite set

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter (aleph) marked with subscript indicating their rank among the infinite cardinals.

In mathematics, especially in order theory, the cofinality cf(A) of a partially ordered set A is the least of the cardinalities of the cofinal subsets of A.

In set theory, König's theorem states that if the axiom of choice holds, I is a set, and are cardinal numbers for every i in I, and for every i in I, then

In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal κ is strongly inaccessible if it satisfies the following three conditions: it is uncountable, it is not a sum of fewer than κ cardinals smaller than κ, and implies .

In set theory, a Woodin cardinal is a cardinal number such that for all functions , there exists a cardinal with and an elementary embedding from the Von Neumann universe into a transitive inner model with critical point and .

In mathematics, limit cardinals are certain cardinal numbers. A cardinal number λ is a weak limit cardinal if λ is neither a successor cardinal nor zero. This means that one cannot "reach" λ from another cardinal by repeated successor operations. These cardinals are sometimes called simply "limit cardinals" when the context is clear.

In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. More explicitly, this means that is a regular cardinal if and only if every unbounded subset has cardinality . Infinite well-ordered cardinals that are not regular are called singular cardinals. Finite cardinal numbers are typically not called regular or singular.

In set theory, one can define a successor operation on cardinal numbers in a similar way to the successor operation on the ordinal numbers. The cardinal successor coincides with the ordinal successor for finite cardinals, but in the infinite case they diverge because every infinite ordinal and its successor have the same cardinality. Using the von Neumann cardinal assignment and the axiom of choice (AC), this successor operation is easy to define: for a cardinal number κ we have

In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers, conventionally written , where is the Hebrew letter beth. The beth numbers are related to the aleph numbers, but unless the generalized continuum hypothesis is true, there are numbers indexed by that are not indexed by .

In mathematics, specifically set theory and model theory, a stationary set is a set that is not too small in the sense that it intersects all club sets and is analogous to a set of non-zero measure in measure theory. There are at least three closely related notions of stationary set, depending on whether one is looking at subsets of an ordinal, or subsets of something of given cardinality, or a powerset.

In set theory, a Rowbottom cardinal, introduced by Rowbottom, is a certain kind of large cardinal number.

In set theory, Easton's theorem is a result on the possible cardinal numbers of powersets. Easton (1970) showed via forcing that the only constraints on permissible values for 2κ when κ is a regular cardinal are

In the mathematical field of set theory, the proper forcing axiom (PFA) is a significant strengthening of Martin's axiom, where forcings with the countable chain condition (ccc) are replaced by proper forcings.

Kuratowski's free set theorem, named after Kazimierz Kuratowski, is a result of set theory, an area of mathematics. It is a result which has been largely forgotten for almost 50 years, but has been applied recently in solving several lattice theory problems, such as the congruence lattice problem.

András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.

In partition calculus, part of combinatorial set theory, a branch of mathematics, the Erdős–Rado theorem is a basic result extending Ramsey's theorem to uncountable sets. It is named after Paul Erdős and Richard Rado. It is sometimes also attributed to Đuro Kurepa who proved it under the additional assumption of the generalised continuum hypothesis, and hence the result is sometimes also referred to as the Erdős–Rado–Kurepa theorem.

In the mathematical theory of infinite graphs, the Erdős–Dushnik–Miller theorem is a form of Ramsey's theorem stating that every infinite graph contains either a countably infinite independent set, or a clique with the same cardinality as the whole graph.

References