Skip to main content
MathOverflow

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

Ramsey's Theorem

The theorem has two forms.

Finite form. For all nonzero $n, k, m \in \mathbb{N}$ there is a nonzero $r \in \mathbb{N}$ such that, for each set $R$ of size $r$ and each $k$-coloring of the $n$-element subsets of $R$, there is a homogeneous set of size $m$.

 

Ininite form. For all nonzero $n, k \in \mathbb{N}$, each infinite set $W$, and each $k$-coloring of the $n$-element subsets of $W$, there is an infinite homogeneous set.

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic. For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]

Ramsey's Theorem

The theorem has two forms.

Finite form. For all nonzero $n, k, m \in \mathbb{N}$ there is a nonzero $r \in \mathbb{N}$ such that, for each set $R$ of size $r$ and each $k$-coloring of the $n$-element subsets of $R$, there is a homogeneous set of size $m$.

 

Ininite form. For all nonzero $n, k \in \mathbb{N}$, each infinite set $W$, and each $k$-coloring of the $n$-element subsets of $W$, there is an infinite homogeneous set.

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic. For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]

Ramsey's Theorem

The theorem has two forms.

Finite form. For all nonzero $n, k, m \in \mathbb{N}$ there is a nonzero $r \in \mathbb{N}$ such that, for each set $R$ of size $r$ and each $k$-coloring of the $n$-element subsets of $R$, there is a homogeneous set of size $m$.

Ininite form. For all nonzero $n, k \in \mathbb{N}$, each infinite set $W$, and each $k$-coloring of the $n$-element subsets of $W$, there is an infinite homogeneous set.

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic. For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]

Added theorem statements.
Source Link
Cole Leahy
Cole Leahy
  • 1.1k
  • 9
  • 21

Ramsey's Theorem

The theorem has two forms.

Finite form. For all nonzero $n, k, m \in \mathbb{N}$ there is a nonzero $r \in \mathbb{N}$ such that, for each set $R$ of size $r$ and each $k$-coloring of the $n$-element subsets of $R$, there is a homogeneous set of size $m$.

Ininite form. For all nonzero $n, k \in \mathbb{N}$, each infinite set $W$, and each $k$-coloring of the $n$-element subsets of $W$, there is an infinite homogeneous set.

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic.

  For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]

Ramsey's Theorem

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic.

  For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]

Ramsey's Theorem

The theorem has two forms.

Finite form. For all nonzero $n, k, m \in \mathbb{N}$ there is a nonzero $r \in \mathbb{N}$ such that, for each set $R$ of size $r$ and each $k$-coloring of the $n$-element subsets of $R$, there is a homogeneous set of size $m$.

Ininite form. For all nonzero $n, k \in \mathbb{N}$, each infinite set $W$, and each $k$-coloring of the $n$-element subsets of $W$, there is an infinite homogeneous set.

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic. For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]

Post Made Community Wiki
Source Link
François G. Dorais
François G. Dorais
  • 45.3k
  • 6
  • 152
  • 237

Ramsey's Theorem

Frank Ramsey's original paper was titled On a problem of formal logic, so it should be no surprise that the famous theorem and its generalizations have magical applications in logic.

For example, Ramsey's Theorem, the Erdős-Rado Theorem, and their more esoteric extensions, are often used in model theory to establish the existence of indiscernible elements.

[Please expand this!!!]