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
    Apr 18, 2020 at 14:26
  • $\begingroup$ It is "for some $s<r$". Thanks~ $\endgroup$
    – Jiayi Liu
    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
    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
    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
    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
    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
    Apr 20, 2020 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.