In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
to
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
s.
Some of the things studied include
continuous graph
GraphOn GO-Global is a multi-user remote access application for Windows.
Overview
GO-Global allows multiple users to concurrently run Microsoft Windows applications installed on a Windows server or server farm  from network-connected loc ...
s and
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
, extensions of
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
, and
Martin's axiom
In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consist ...
.
Recent developments concern combinatorics of the
continuum
Continuum may refer to:
* Continuum (measurement), theories or models that explain gradual transitions from one condition to another without abrupt changes
Mathematics
* Continuum (set theory), the real line or the corresponding cardinal number ...
and combinatorics on successors of singular cardinals.
[Todd Eisworth, ''Successors of Singular Cardinals'' Chapter 15 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010]
Ramsey theory for infinite sets
Write κ, λ for ordinals, ''m'' for a
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
and ''n'' for a natural number. introduced the notation
:
as a shorthand way of saying that every
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of the set
ºsup>''n'' of ''n''-element
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of
into ''m'' pieces has a
homogeneous set
Homogeneity and heterogeneity are concepts often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, s ...
of order type λ. A homogeneous set is in this case a subset of κ such that every ''n''-element subset is in the same element of the partition. When ''m'' is 2 it is often omitted.
Assuming the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
, there are no ordinals κ with κ→(ω)
ω, so ''n'' is usually taken to be finite. An extension where ''n'' is almost allowed to be infinite is
the notation
:
which is a shorthand way of saying that every
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of the set of finite subsets of κ into ''m'' pieces has a subset of order type λ such that for any finite ''n'', all subsets of size ''n'' are in the same element of the partition. When ''m'' is 2 it is often omitted.
Another variation is the notation
:
which is a shorthand way of saying that every coloring of the set
ºsup>''n'' of ''n''-element subsets of κ with 2 colors has a subset of order type λ such that all elements of
»sup>''n'' have the first color, or a subset of order type μ such that all elements of
¼sup>''n'' have the second color.
Some properties of this include: (in what follows
is a cardinal)
:
for all finite ''n'' and ''k'' (
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
).
:
(
Erdős–Rado theorem
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
Richard Rado FRS (28 ...
.)
:
(Sierpiński theorem)
:
:
(
Erdős–Dushnik–Miller 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 t ...
).
In choiceless universes, partition properties with infinite exponents may hold, and some of them are obtained as consequences of the
axiom of determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...
(AD). For example,
Donald A. Martin
Donald Anthony Martin (born December 24, 1940), also known as Tony Martin, is an American set theorist and philosopher of mathematics at UCLA, where he is an emeritus professor of mathematics and philosophy.
Education and career
Martin rece ...
proved that AD implies
:
Large cardinals
Several
large cardinal
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least Î ...
properties can be defined using this notation. In particular:
*
Weakly compact cardinal In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by ; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the ZFC, standard axioms of set theory. (Tarski original ...
s κ are those that satisfy κ→(κ)
2
*α-
Erdős cardinal In mathematics, an Erdős cardinal, also called a partition cardinal is a certain kind of large cardinal number introduced by .
The Erdős cardinal is defined to be the least cardinal such that for every function there is a set of order type tha ...
s κ are the smallest that satisfy κ→(α)
<ω
*
Ramsey cardinal In mathematics, a Ramsey cardinal is a certain kind of large cardinal number introduced by and named after Frank P. Ramsey, whose theorem establishes that ω enjoys a certain property that Ramsey cardinals generalize to the uncountable case.
L ...
s κ are those that satisfy κ→(κ)
<ω
Notes
References
*
*
*
*
*
*{{Citation , last1=Kunen , first1=Kenneth , author1-link=Kenneth Kunen , title=
Set Theory: An Introduction to Independence Proofs , publisher=North-Holland , location=Amsterdam , isbn=978-0-444-85401-8 , year=1980
Set theory
Combinatorics