Skip to main content
added 2136 characters in body
Source Link
Jing Zhang
  • 3k
  • 1
  • 17
  • 15

We can't find such pair of bad order types, aka there indeed is some Erdös-Rado phenomenon in the polarized partitions with respect to linear orderings. Indeed given $\gamma$ number of colors and $\theta$, $\psi$ we can find large saturated dense linear orders $\alpha, \beta$ such that for any $f: \alpha\times \beta \to \gamma$, there exists $X\subset \alpha, Y\subset \beta$ such that $tp(X)=tp(\alpha), tp(Y)=tp(\beta)$ such that $f''X\times Y$ is constant.

To elaborate: Given $\gamma$ the number of colors and order types $\theta, \psi$, given let $\lambda$ be regular a lot larger than $|\theta|, |\psi|, \gamma$, let $\beta$ be a $\lambda$-saturated dense linear order. Let $\lambda'$ be a lot larger than $2^{|\beta|}, \gamma$ and let $\alpha$ be $\lambda'$-saturated dense linear ordering, we claim that ${\alpha\choose \beta}\to {\theta\choose \psi}^{1,1}_{\gamma}$. Given a coloring $f: \alpha \times \beta\to \gamma$, for each $i\in \alpha$, consider $f_i: \beta\to \gamma$.

There exists a monochromatic under $f_i$ sub order of $\beta$ that is $\lambda$-saturated. Why? Suppose not, then induct on $i\in \gamma$ to build a cut. Stage 0, there exists $\eta_0,\eta_1<\lambda$ and $A_0=\{a_j: j<\eta_0\}<B_0=\{b_j: j<\eta_1\}$ such that there is no $c\in \beta$ that has color 0 such that $A_0<c<B_0$. Note that $(A_0,B_0)=\{c\in \beta: A_0<c<B_0\}$ is still $\lambda$-saturated. Inductively at stage $\alpha$, suppose we have $A_0<A_1<\cdots<A_\beta<\cdots < B_\beta<\cdots <B_0$ (i.e. $\forall \beta<\gamma<\alpha \ A_\beta<A_\gamma<B_\gamma<B_\beta$). Since $\beta$ is $\lambda$-saturated, let $A'_\alpha= \bigcup_{i<\alpha}A_i, B'_\alpha=\bigcup_{i<\alpha}B_i$, we know $(A'_\alpha, B'_\alpha)$ is still $\lambda$-saturated. By hypothesis, we can find $A_\alpha, B_\alpha$ such that $A'_\alpha<A_\alpha<B_\alpha<B'_\alpha$ such that no element in $(A_\alpha, B_\alpha)$ has color $\alpha$. This can proceed in $\gamma$ steps since $\gamma<\lambda$ but absurdity arises since $\beta$ is saturated and every element gets colored.

Denote the monochromatic $\lambda$-saturated suborder of $\beta$ under $f_i$ $\beta_i$, and the color be $\gamma_i$. Now define a coloring $g: \alpha\to 2^{\beta}\times \gamma$ such that $g(i)=(\beta_i,\gamma_i)$. By the similar argument above we can get a suborder of $\alpha$, say $\alpha'$ that is monochromatic and $\lambda'$-saturated. Let $(\beta',\gamma')$ be the color $g''\alpha'$, then $f''\alpha'\times \beta'=\gamma'$, as $\alpha'$ and $\beta'$ are sufficiently saturated we can embed $\theta$ and $\psi$ into them respectively.

We can't find such pair of bad order types. Indeed given $\gamma$ number of colors and $\theta$, $\psi$ we can find large saturated dense linear orders $\alpha, \beta$ such that for any $f: \alpha\times \beta \to \gamma$, there exists $X\subset \alpha, Y\subset \beta$ such that $tp(X)=tp(\alpha), tp(Y)=tp(\beta)$ such that $f''X\times Y$ is constant.

We can't find such pair of bad order types, aka there indeed is some Erdös-Rado phenomenon in the polarized partitions with respect to linear orderings. Indeed given $\gamma$ number of colors and $\theta$, $\psi$ we can find large saturated dense linear orders $\alpha, \beta$ such that for any $f: \alpha\times \beta \to \gamma$, there exists $X\subset \alpha, Y\subset \beta$ such that $tp(X)=tp(\alpha), tp(Y)=tp(\beta)$ such that $f''X\times Y$ is constant.

To elaborate: Given $\gamma$ the number of colors and order types $\theta, \psi$, given let $\lambda$ be regular a lot larger than $|\theta|, |\psi|, \gamma$, let $\beta$ be a $\lambda$-saturated dense linear order. Let $\lambda'$ be a lot larger than $2^{|\beta|}, \gamma$ and let $\alpha$ be $\lambda'$-saturated dense linear ordering, we claim that ${\alpha\choose \beta}\to {\theta\choose \psi}^{1,1}_{\gamma}$. Given a coloring $f: \alpha \times \beta\to \gamma$, for each $i\in \alpha$, consider $f_i: \beta\to \gamma$.

There exists a monochromatic under $f_i$ sub order of $\beta$ that is $\lambda$-saturated. Why? Suppose not, then induct on $i\in \gamma$ to build a cut. Stage 0, there exists $\eta_0,\eta_1<\lambda$ and $A_0=\{a_j: j<\eta_0\}<B_0=\{b_j: j<\eta_1\}$ such that there is no $c\in \beta$ that has color 0 such that $A_0<c<B_0$. Note that $(A_0,B_0)=\{c\in \beta: A_0<c<B_0\}$ is still $\lambda$-saturated. Inductively at stage $\alpha$, suppose we have $A_0<A_1<\cdots<A_\beta<\cdots < B_\beta<\cdots <B_0$ (i.e. $\forall \beta<\gamma<\alpha \ A_\beta<A_\gamma<B_\gamma<B_\beta$). Since $\beta$ is $\lambda$-saturated, let $A'_\alpha= \bigcup_{i<\alpha}A_i, B'_\alpha=\bigcup_{i<\alpha}B_i$, we know $(A'_\alpha, B'_\alpha)$ is still $\lambda$-saturated. By hypothesis, we can find $A_\alpha, B_\alpha$ such that $A'_\alpha<A_\alpha<B_\alpha<B'_\alpha$ such that no element in $(A_\alpha, B_\alpha)$ has color $\alpha$. This can proceed in $\gamma$ steps since $\gamma<\lambda$ but absurdity arises since $\beta$ is saturated and every element gets colored.

Denote the monochromatic $\lambda$-saturated suborder of $\beta$ under $f_i$ $\beta_i$, and the color be $\gamma_i$. Now define a coloring $g: \alpha\to 2^{\beta}\times \gamma$ such that $g(i)=(\beta_i,\gamma_i)$. By the similar argument above we can get a suborder of $\alpha$, say $\alpha'$ that is monochromatic and $\lambda'$-saturated. Let $(\beta',\gamma')$ be the color $g''\alpha'$, then $f''\alpha'\times \beta'=\gamma'$, as $\alpha'$ and $\beta'$ are sufficiently saturated we can embed $\theta$ and $\psi$ into them respectively.

deleted 1382 characters in body
Source Link
Jing Zhang
  • 3k
  • 1
  • 17
  • 15

OK consistently there is indeed some Erdös-Rado type phenomenon in partition relations for linear orderings (so theWe can't find such pair of bad order type as requested cannot be obtained by set forcing).

Assume there is a proper class of measurable cardinalstypes.

Let $\kappa<\lambda$ be measurable cardinals, then ${\eta_\lambda \choose \eta_\kappa}\to {\eta_\lambda \choose \eta_\kappa}^{1,1}_\delta$ for any $\delta<\kappa$. We identify $(\eta_\lambda,<)$ with $(2^{<\lambda}, <_{lex})$, similarly for $2^{<\kappa}$. These are typical saturated linear orders.

Given $f: 2^{<\lambda}\times 2^{<\kappa}\to \delta$, for each $\sigma\in 2^{<\lambda}$, consider $f_\sigma: 2^{<\kappa}\to \delta$, by 1-dimensional Halpern-Läuchli theorem on $\kappa$ with Indeed given $\delta$ many$\gamma$ number of colors (denoted asand $HL(1,\delta,\kappa)$, which is always true for measurable cardinals$\theta$, see for example https://arxiv.org/abs/1608.00592),$\psi$ we know there exists a perfect strongly embedded subtree ofcan find large saturated dense linear orders $2^{<\kappa}$$\alpha, \beta$ such that for any $f_{\sigma}$ is monochromatic$f: \alpha\times \beta \to \gamma$, say of color $\delta_\sigma$. As there are only $2^\kappa$ many strong subtrees of $2^{<\kappa}$, we can define a coloring $2^{<\lambda}\to 2^\kappa \times \delta$. By $HL(1,2^\kappa\times \delta,\lambda)$ we get a strong monochromatic subtree of $2^{<\lambda}$. Hence we have $T_0\subset 2^{<\lambda}$ strong subtree andexists $T_1\subset 2^{<\kappa}$ strong subtree$X\subset \alpha, Y\subset \beta$ such that there is some $\gamma\in \delta$$tp(X)=tp(\alpha), tp(Y)=tp(\beta)$ such that for each $\sigma\in T_0,\tau\in T_1$, $f(\sigma, \tau)=f_\sigma(\tau)=\delta_\sigma=\gamma$.

For any given order types $\theta, \psi$, we just need to find $\kappa, \lambda$ measurable as above large enough then it$f''X\times Y$ is always possible to embed $\theta, \psi$ into $\eta_\lambda, \eta_\kappa$ by saturationconstant.

OK consistently there is indeed some Erdös-Rado type phenomenon in partition relations for linear orderings (so the bad order type as requested cannot be obtained by set forcing).

Assume there is a proper class of measurable cardinals.

Let $\kappa<\lambda$ be measurable cardinals, then ${\eta_\lambda \choose \eta_\kappa}\to {\eta_\lambda \choose \eta_\kappa}^{1,1}_\delta$ for any $\delta<\kappa$. We identify $(\eta_\lambda,<)$ with $(2^{<\lambda}, <_{lex})$, similarly for $2^{<\kappa}$. These are typical saturated linear orders.

Given $f: 2^{<\lambda}\times 2^{<\kappa}\to \delta$, for each $\sigma\in 2^{<\lambda}$, consider $f_\sigma: 2^{<\kappa}\to \delta$, by 1-dimensional Halpern-Läuchli theorem on $\kappa$ with $\delta$ many colors (denoted as $HL(1,\delta,\kappa)$, which is always true for measurable cardinals, see for example https://arxiv.org/abs/1608.00592), we know there exists a perfect strongly embedded subtree of $2^{<\kappa}$ such that $f_{\sigma}$ is monochromatic, say of color $\delta_\sigma$. As there are only $2^\kappa$ many strong subtrees of $2^{<\kappa}$, we can define a coloring $2^{<\lambda}\to 2^\kappa \times \delta$. By $HL(1,2^\kappa\times \delta,\lambda)$ we get a strong monochromatic subtree of $2^{<\lambda}$. Hence we have $T_0\subset 2^{<\lambda}$ strong subtree and $T_1\subset 2^{<\kappa}$ strong subtree such that there is some $\gamma\in \delta$ such that for each $\sigma\in T_0,\tau\in T_1$, $f(\sigma, \tau)=f_\sigma(\tau)=\delta_\sigma=\gamma$.

For any given order types $\theta, \psi$, we just need to find $\kappa, \lambda$ measurable as above large enough then it is always possible to embed $\theta, \psi$ into $\eta_\lambda, \eta_\kappa$ by saturation.

We can't find such pair of bad order types. Indeed given $\gamma$ number of colors and $\theta$, $\psi$ we can find large saturated dense linear orders $\alpha, \beta$ such that for any $f: \alpha\times \beta \to \gamma$, there exists $X\subset \alpha, Y\subset \beta$ such that $tp(X)=tp(\alpha), tp(Y)=tp(\beta)$ such that $f''X\times Y$ is constant.

Source Link
Jing Zhang
  • 3k
  • 1
  • 17
  • 15

OK consistently there is indeed some Erdös-Rado type phenomenon in partition relations for linear orderings (so the bad order type as requested cannot be obtained by set forcing).

Assume there is a proper class of measurable cardinals.

Let $\kappa<\lambda$ be measurable cardinals, then ${\eta_\lambda \choose \eta_\kappa}\to {\eta_\lambda \choose \eta_\kappa}^{1,1}_\delta$ for any $\delta<\kappa$. We identify $(\eta_\lambda,<)$ with $(2^{<\lambda}, <_{lex})$, similarly for $2^{<\kappa}$. These are typical saturated linear orders.

Given $f: 2^{<\lambda}\times 2^{<\kappa}\to \delta$, for each $\sigma\in 2^{<\lambda}$, consider $f_\sigma: 2^{<\kappa}\to \delta$, by 1-dimensional Halpern-Läuchli theorem on $\kappa$ with $\delta$ many colors (denoted as $HL(1,\delta,\kappa)$, which is always true for measurable cardinals, see for example https://arxiv.org/abs/1608.00592), we know there exists a perfect strongly embedded subtree of $2^{<\kappa}$ such that $f_{\sigma}$ is monochromatic, say of color $\delta_\sigma$. As there are only $2^\kappa$ many strong subtrees of $2^{<\kappa}$, we can define a coloring $2^{<\lambda}\to 2^\kappa \times \delta$. By $HL(1,2^\kappa\times \delta,\lambda)$ we get a strong monochromatic subtree of $2^{<\lambda}$. Hence we have $T_0\subset 2^{<\lambda}$ strong subtree and $T_1\subset 2^{<\kappa}$ strong subtree such that there is some $\gamma\in \delta$ such that for each $\sigma\in T_0,\tau\in T_1$, $f(\sigma, \tau)=f_\sigma(\tau)=\delta_\sigma=\gamma$.

For any given order types $\theta, \psi$, we just need to find $\kappa, \lambda$ measurable as above large enough then it is always possible to embed $\theta, \psi$ into $\eta_\lambda, \eta_\kappa$ by saturation.