6
$\begingroup$

For two $k$-partitions $X,Y\in k^\omega$ of $\omega$ (seen as functions $\omega\rightarrow k$), we say $X,Y$ are almost disjoint iff $X^{-1}(i)\cap Y^{-1}(i)$ is finite for all $i<k$.

Question: Does there exist a set $Q\subseteq 3^\omega\times (2^\omega)^r$ such that:

  1. for every $X\in 3^\omega$, there exists $Y\in (2^\omega)^r$ such that $(X,Y)\in Q$;
  2. for every $(X^0,Y^0),(X^1,Y^1)\in Q$, if $X^0,X^1$ are almost disjoint, then $ Y^0_s,Y^1_s$ are almost disjoint for some $s<r$.

If $r=1$, then obviously $Q$ does not exist since every three $2$-partitions, there are two of them not almost disjoint and there are three $3$-partitions that are mutually almost disjoint. If we replace $3^\omega$ by $2^\omega$ then such $Q$ obviously exist. It seems, by Cohen forcing, $Q$ (if exist) cannot be $\Sigma_1^1$. Could it be $\Pi_1^1$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ In 2, did you mean for some $s < r$, rather than all $s < r$? Because as it is now, making $r$ larger makes it harder for such a $Q$ to exist, and so your argument for $r=1$ settles the question. $\endgroup$
    – Dan Turetsky
    Commented Apr 18, 2020 at 14:26
  • $\begingroup$ It is "for some $s<r$". Thanks~ $\endgroup$
    – Jiayi Liu
    Commented Apr 19, 2020 at 4:54

1 Answer 1

Reset to default
3
$\begingroup$

The answer is yes for $r=3$. Take an ultrafilter $\mathcal{U}$ on $\omega$. Define a function $f \colon 3^\omega \rightarrow 3$ such that $f(X):=i$ iff $X^{-1}(i) \in \mathcal{U}$. Note that if $X_1$ and $X_2$ are almost disjoint, then $f(X_1) \neq f(X_2)$.

Let $Q:=\{(X,Y) \in 3^\omega \times (2^\omega)^3 \colon \,\, f(X)=i \Rightarrow Y_i=(\emptyset,\omega) \land f(X)\neq i \Rightarrow Y_i=(\omega, \emptyset)\}$.

Unfortunately, this $Q$ cannot be $\Pi_1^1$ as Jonathan pointed out.

Improve this answer
$\endgroup$
8
  • $\begingroup$ For $r=4$, it seems that you can get $Q$ to be $\Pi^1_1$. Let $\mathcal{U}$ be a $\Sigma^1_2$ ultrafilter (say in L). Then we take exactly the same $Q$ as you did, but simply add an additional coordinate to the $Y$ part for the witness that $f(X)=i$. $\endgroup$
    – Jonathan Schilhan
    Commented Apr 19, 2020 at 18:33
  • $\begingroup$ The $Q$ that you define will never be $\Pi^1_1$, since $x \in \mathcal{U}$ would become $\Pi^1_1$, but this is impossible for an ultrafilter. $\endgroup$
    – Jonathan Schilhan
    Commented Apr 19, 2020 at 18:38
  • 1
    $\begingroup$ The formula $\forall Y \in \mathcal{B}(X \cap Y \neq \emptyset)$ is $\Pi^1_2$ since you need to say $\forall Y (Y \notin \mathcal{B} \vee X \cap Y \neq \emptyset)$. $\endgroup$
    – Jonathan Schilhan
    Commented Apr 20, 2020 at 9:31
  • 1
    $\begingroup$ My first comment was just a consistency result. In $L$ it is not hard to construct a $\Sigma^1_2$ ultrafilter. A $\Sigma^1_2$ set is the projection of a $\Pi^1_1$ set $A \subseteq 2^\omega \times 2^\omega$, so if $x \in \mathcal{U}$, then there is a witness $y$ so that $(x,y) \in A$. $\endgroup$
    – Jonathan Schilhan
    Commented Apr 20, 2020 at 9:37
  • 2
    $\begingroup$ Thanks for answering~ I didn't expect different $r$ would make a difference. Your construction gives a $Q$ for $r=2$ as following. Put $(X,Y)$ in $Q$ where $Y=(\emptyset,\emptyset), (\emptyset,\omega), (\omega,\emptyset)\in (2^\omega)^2$ depending on $f(X)=0,1,2$ respectively. Where $(\emptyset,\emptyset)$ denotes such $(Y_0,Y_1)\in (2^\omega)^2$ that $Y_0^{-1}(1)=Y_1^{-1}(1)=\emptyset$ (similarly for $(\emptyset,\omega), (\omega,\emptyset)$). So $Q$ could be $\Pi_1^1$ for $r=3$ by Jonathan's comment. $\endgroup$
    – Jiayi Liu
    Commented Apr 20, 2020 at 11:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .