Difference between revisions of "Partition property"
Zetapology (Talk | contribs) (Created stand in article) |
Zetapology (Talk | contribs) (Added page) |
||
Line 1: | Line 1: | ||
[[Category:Partition property]] | [[Category:Partition property]] | ||
− | + | A partition property is an infinitary combinatorical principle in set theory. Partition properties are best associated with various [[upper attic|large cardinal axioms]] (all of which are below [[measurable]]), but can also be associated with infinite graphs. | |
− | {{ | + | The '''pigeonhole principle''' famously states that if there are $n$ pigeons in $n-m$ holes, then at least one hole contains at least $m$ pigeons. Partition properties are best motivated as generalizations of the pigeonhole principle to infinite cardinals. For example, if there are $\aleph_1$ pigeons and there are $\aleph_0$ many holes, then at least one hole contains $\aleph_1$ pigeons. |
+ | |||
+ | == Definitions == | ||
+ | |||
+ | There are quite a few definitions involved with partition properties. In fact, partition calculus, the study of partition properties, almost completely either comprisse or describes most of infinitary combinatorics itself, so it would make sense that the terminology involved with it is quite unique. | ||
+ | |||
+ | === Square Bracket Notation === | ||
+ | |||
+ | The square bracket notation is somewhat simple and easy to grasp (and used in many other places). Let $X$ be a set of ordinals. $[X]^\beta$ for some ordinal $\beta$ is the set of all subsets $x\subseteq X$ such that $(x,<)$ has order-type $\beta$; that is, there is a bijection $f$ from $x$ to $\beta$ such that $f(a)<f(b)$ iff $a<b$ for each $a$ and $b$ in $x$. Such a bijection is often called an order-isomorphism. | ||
+ | |||
+ | $[X]^{<\beta}$ for some ordinal $\beta$ is simply defined as the union of all $[X]^{\alpha}$ for $\alpha<\beta$, the set of all subsets $x\subseteq X$ with order-type less than $\beta$. In the case of $\omega$, $[X]^{<\omega}$ is the set of all finite subsets of $X$. | ||
+ | |||
+ | === Homogeneous Sets === | ||
+ | |||
+ | Let $f:[\kappa]^\beta\rightarrow\lambda$ be a function (in this study, such functions are often called partitions). A set $H\subseteq\kappa$ is then called '''homogeneous for $f$''' when for any two subsets $h_0,h_1\subseteq H$ of order type $\beta$, $f(h_0)=f(h_1)$. This is equivalent to $f$ being constant on $[H]^\beta$. | ||
+ | |||
+ | In another case, let $f:[\kappa]^{<\omega}\rightarrow\lambda$ be a function. A set $H\subseteq\kappa$ is then called '''homogeneous for $f$''' when for any two finite subsets $h_0,h_1\subseteq H$ of the same size, $f(h_0)=f(h_1)$. | ||
+ | |||
+ | === The Various Partition Properties === | ||
+ | |||
+ | Let $\kappa$ and $\lambda$ be cardinals and let $\alpha$ and $\beta$ be ordinals. Then, the following notations are used for the partition properties: | ||
+ | |||
+ | *$\kappa\rightarrow (\alpha)_\lambda^\beta$ iff for every function $f:[\kappa]^\beta\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$. If $\alpha$ is a cardinal (which it most often is), then the requirement on $H$ can be loosened to $H$ having cardinality $\alpha$ and being homogeneous for $f$ without loss of generality. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *A common abbreviation for $\kappa\rightarrow (\alpha)_2^n$ is $\kappa\rightarrow (\alpha)^n$. | ||
+ | *$\kappa\rightarrow (\alpha)_\lambda^{<\omega}$ iff for every function $f:[\kappa]^{<\omega}\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$. If $\alpha$ is a cardinal (which it most often is), then the requirement on $H$ can be loosened to $H$ having cardinality $\alpha$ and being homogeneous for $f$ without loss of generality. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | |||
+ | Let $\nu$ be a cardinal. The '''square bracket partition properties''' are defined as follows: | ||
+ | |||
+ | *$\kappa\rightarrow [\alpha]_\lambda^\beta$ iff for every function $f:[\kappa]^\beta\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ and an ordinal $\gamma<\lambda$ such that $f(h)\neq\gamma$ for each $h\in [H]^\beta$. | ||
+ | *$\kappa\rightarrow [\alpha]_\lambda^{<\omega}$ iff for every function $f:[\kappa]^{<\omega}\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ and an ordinal $\gamma<\lambda$ such that $f(h)\neq\gamma$ for each finite subset $h$ of $H$. | ||
+ | *$\kappa\rightarrow [\alpha]_{\lambda,<\nu}^\beta$ iff for every function $f:[\kappa]^\beta\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ such that $f$ restricted to $[H]^\beta$ yields less than $\nu$-many distinct outputs. | ||
+ | *$\kappa\rightarrow [\alpha]_{\lambda,<\nu}^{<\omega}$ iff for every function $f:[\kappa]^{<\omega}\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ such that $f$ restricted to $[H]^{<\omega}$ yields less than $\nu$-many distinct outputs. | ||
+ | |||
+ | == Theorems and Large Cardinal Axioms == | ||
+ | |||
+ | There are several theorems in the study of partition calculus. Namely: | ||
+ | |||
+ | *Ramsey's theorem, which states that $\aleph_0\rightarrow (\omega)_m^n$ for each finite $m$ and $n$. <cite>Jech2003:SetTheory</cite> | ||
+ | *$2^\kappa\not\rightarrow (\kappa^+)^2$ <cite>Jech2003:SetTheory</cite> | ||
+ | *The Erdős-Rado theorem, which states that $\beth_n^+\rightarrow (\omega_1)_{\aleph_0}^{n+1}$. <cite>Jech2003:SetTheory</cite> | ||
+ | *$\kappa\not\rightarrow(\omega)_2^\omega$ <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *For any finite nonzero $n$ and ordinals $\alpha$ and $\beta$, there is a $\kappa$ such that $\kappa\rightarrow(\alpha)_\beta^n$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *The Gödel-Erdős-Kakutani theorem, which states that $2^\kappa\not\rightarrow (3)^2_\kappa$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *$\kappa\not\rightarrow [\kappa]_\kappa^\omega$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *$\lambda^+\not\rightarrow[\lambda+1]^2_{\lambda,<\lambda}$ <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *$\lambda\not\rightarrow[\lambda]^1_{\mathrm{cf}(\lambda),<\mathrm{cf}(\lambda)}$ <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *For any regular $\kappa$, $\kappa^+\not\rightarrow[\kappa^+]^2_{\kappa^+}$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | |||
+ | In terms of large cardinal axioms, many can be described using a partition property. Here are those which can be found on this website: | ||
+ | |||
+ | *Although not a large cardinal itself, Chang's conjecture holds iff $\aleph_2\rightarrow[\omega_1]^{<\omega}_{\aleph_1,<\aleph_1}$, iff $\aleph_2\rightarrow[\omega_1]^{n}_{\aleph_1,<\aleph_1}$ for some $n$, iff $\aleph_2\rightarrow[\omega_1]^{n}_{\aleph_1,<\aleph_1}$ for every finite $n$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *A cardinal $\kappa$ is [[Ramsey]] iff $\kappa\rightarrow(\kappa)_\lambda^{<\omega}$ for some $\lambda$, iff $\kappa\rightarrow(\kappa)_\lambda^{<\omega}$ for every $\lambda<\kappa$. <cite>Kanamori2009:HigherInfinite</cite><cite>Jech2003:SetTheory</cite> | ||
+ | *A cardinal $\kappa$ is defined to be [[Rowbottom|$\nu$-Rowbottom]] iff $\kappa\rightarrow[\kappa]_{\lambda,<\nu}^{<\omega}$ for every $\lambda<\kappa$. | ||
+ | *A cardinal $\kappa$ is [[Jonsson|Jónsson]] iff $\kappa\rightarrow[\kappa]_\kappa^{<\omega}$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | *A cardinal $\kappa$ is defined to be [[Erdos|$\alpha$-Erdős]] iff $\kappa\rightarrow(\alpha)^{<\omega}$. | ||
+ | *A cardinal $\kappa$ is [[weakly compact]] iff $\kappa\rightarrow(\kappa)^2_\lambda$ for some $\lambda$, iff $\kappa\rightarrow(\kappa)^2_\lambda$ for every $\lambda<\kappa$. <cite>Jech2003:SetTheory</cite> | ||
+ | |||
+ | {{References}} |
Revision as of 21:57, 14 November 2017
A partition property is an infinitary combinatorical principle in set theory. Partition properties are best associated with various large cardinal axioms (all of which are below measurable), but can also be associated with infinite graphs.
The pigeonhole principle famously states that if there are $n$ pigeons in $n-m$ holes, then at least one hole contains at least $m$ pigeons. Partition properties are best motivated as generalizations of the pigeonhole principle to infinite cardinals. For example, if there are $\aleph_1$ pigeons and there are $\aleph_0$ many holes, then at least one hole contains $\aleph_1$ pigeons.
Contents
Definitions
There are quite a few definitions involved with partition properties. In fact, partition calculus, the study of partition properties, almost completely either comprisse or describes most of infinitary combinatorics itself, so it would make sense that the terminology involved with it is quite unique.
Square Bracket Notation
The square bracket notation is somewhat simple and easy to grasp (and used in many other places). Let $X$ be a set of ordinals. $[X]^\beta$ for some ordinal $\beta$ is the set of all subsets $x\subseteq X$ such that $(x,<)$ has order-type $\beta$; that is, there is a bijection $f$ from $x$ to $\beta$ such that $f(a)<f(b)$ iff $a<b$ for each $a$ and $b$ in $x$. Such a bijection is often called an order-isomorphism.
$[X]^{<\beta}$ for some ordinal $\beta$ is simply defined as the union of all $[X]^{\alpha}$ for $\alpha<\beta$, the set of all subsets $x\subseteq X$ with order-type less than $\beta$. In the case of $\omega$, $[X]^{<\omega}$ is the set of all finite subsets of $X$.
Homogeneous Sets
Let $f:[\kappa]^\beta\rightarrow\lambda$ be a function (in this study, such functions are often called partitions). A set $H\subseteq\kappa$ is then called homogeneous for $f$ when for any two subsets $h_0,h_1\subseteq H$ of order type $\beta$, $f(h_0)=f(h_1)$. This is equivalent to $f$ being constant on $[H]^\beta$.
In another case, let $f:[\kappa]^{<\omega}\rightarrow\lambda$ be a function. A set $H\subseteq\kappa$ is then called homogeneous for $f$ when for any two finite subsets $h_0,h_1\subseteq H$ of the same size, $f(h_0)=f(h_1)$.
The Various Partition Properties
Let $\kappa$ and $\lambda$ be cardinals and let $\alpha$ and $\beta$ be ordinals. Then, the following notations are used for the partition properties:
- $\kappa\rightarrow (\alpha)_\lambda^\beta$ iff for every function $f:[\kappa]^\beta\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$. If $\alpha$ is a cardinal (which it most often is), then the requirement on $H$ can be loosened to $H$ having cardinality $\alpha$ and being homogeneous for $f$ without loss of generality. [1]
- A common abbreviation for $\kappa\rightarrow (\alpha)_2^n$ is $\kappa\rightarrow (\alpha)^n$.
- $\kappa\rightarrow (\alpha)_\lambda^{<\omega}$ iff for every function $f:[\kappa]^{<\omega}\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$. If $\alpha$ is a cardinal (which it most often is), then the requirement on $H$ can be loosened to $H$ having cardinality $\alpha$ and being homogeneous for $f$ without loss of generality. [1]
Let $\nu$ be a cardinal. The square bracket partition properties are defined as follows:
- $\kappa\rightarrow [\alpha]_\lambda^\beta$ iff for every function $f:[\kappa]^\beta\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ and an ordinal $\gamma<\lambda$ such that $f(h)\neq\gamma$ for each $h\in [H]^\beta$.
- $\kappa\rightarrow [\alpha]_\lambda^{<\omega}$ iff for every function $f:[\kappa]^{<\omega}\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ and an ordinal $\gamma<\lambda$ such that $f(h)\neq\gamma$ for each finite subset $h$ of $H$.
- $\kappa\rightarrow [\alpha]_{\lambda,<\nu}^\beta$ iff for every function $f:[\kappa]^\beta\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ such that $f$ restricted to $[H]^\beta$ yields less than $\nu$-many distinct outputs.
- $\kappa\rightarrow [\alpha]_{\lambda,<\nu}^{<\omega}$ iff for every function $f:[\kappa]^{<\omega}\rightarrow\lambda$, there is set $H$ of order-type $\alpha$ which is homogeneous for $f$ such that $f$ restricted to $[H]^{<\omega}$ yields less than $\nu$-many distinct outputs.
Theorems and Large Cardinal Axioms
There are several theorems in the study of partition calculus. Namely:
- Ramsey's theorem, which states that $\aleph_0\rightarrow (\omega)_m^n$ for each finite $m$ and $n$. [2]
- $2^\kappa\not\rightarrow (\kappa^+)^2$ [2]
- The Erdős-Rado theorem, which states that $\beth_n^+\rightarrow (\omega_1)_{\aleph_0}^{n+1}$. [2]
- $\kappa\not\rightarrow(\omega)_2^\omega$ [1]
- For any finite nonzero $n$ and ordinals $\alpha$ and $\beta$, there is a $\kappa$ such that $\kappa\rightarrow(\alpha)_\beta^n$. [1]
- The Gödel-Erdős-Kakutani theorem, which states that $2^\kappa\not\rightarrow (3)^2_\kappa$. [1]
- $\kappa\not\rightarrow [\kappa]_\kappa^\omega$. [1]
- $\lambda^+\not\rightarrow[\lambda+1]^2_{\lambda,<\lambda}$ [1]
- $\lambda\not\rightarrow[\lambda]^1_{\mathrm{cf}(\lambda),<\mathrm{cf}(\lambda)}$ [1]
- For any regular $\kappa$, $\kappa^+\not\rightarrow[\kappa^+]^2_{\kappa^+}$. [1]
In terms of large cardinal axioms, many can be described using a partition property. Here are those which can be found on this website:
- Although not a large cardinal itself, Chang's conjecture holds iff $\aleph_2\rightarrow[\omega_1]^{<\omega}_{\aleph_1,<\aleph_1}$, iff $\aleph_2\rightarrow[\omega_1]^{n}_{\aleph_1,<\aleph_1}$ for some $n$, iff $\aleph_2\rightarrow[\omega_1]^{n}_{\aleph_1,<\aleph_1}$ for every finite $n$. [1]
- A cardinal $\kappa$ is Ramsey iff $\kappa\rightarrow(\kappa)_\lambda^{<\omega}$ for some $\lambda$, iff $\kappa\rightarrow(\kappa)_\lambda^{<\omega}$ for every $\lambda<\kappa$. [1][2]
- A cardinal $\kappa$ is defined to be $\nu$-Rowbottom iff $\kappa\rightarrow[\kappa]_{\lambda,<\nu}^{<\omega}$ for every $\lambda<\kappa$.
- A cardinal $\kappa$ is Jónsson iff $\kappa\rightarrow[\kappa]_\kappa^{<\omega}$. [1]
- A cardinal $\kappa$ is defined to be $\alpha$-Erdős iff $\kappa\rightarrow(\alpha)^{<\omega}$.
- A cardinal $\kappa$ is weakly compact iff $\kappa\rightarrow(\kappa)^2_\lambda$ for some $\lambda$, iff $\kappa\rightarrow(\kappa)^2_\lambda$ for every $\lambda<\kappa$. [2]
References
- Kanamori, Akihiro. The higher infinite. Second, Springer-Verlag, Berlin, 2009. (Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition) www bibtex
- Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www bibtex