Timeline for Complexity of a combinatorial constraint
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20, 2020 at 11:44 | comment | added | Jiayi Liu | 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. | |
| Apr 20, 2020 at 10:08 | history | edited | Johannes Schürz | CC BY-SA 4.0 |
added 11 characters in body
|
| Apr 20, 2020 at 10:04 | comment | added | Johannes Schürz | Yes, you are absolutely right!! Thanks! | |
| Apr 20, 2020 at 9:37 | comment | added | Jonathan Schilhan | 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$. | |
| Apr 20, 2020 at 9:31 | comment | added | Jonathan Schilhan | 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)$. | |
| Apr 20, 2020 at 7:40 | vote | accept | Jiayi Liu | ||
| Apr 20, 2020 at 7:33 | vote | accept | Jiayi Liu | ||
| Apr 20, 2020 at 7:40 | |||||
| Apr 19, 2020 at 19:13 | comment | added | Johannes Schürz | Concerning your first comment, I assume you mean taking a witness from a $\Pi_1^1$ ultrafilterbase in L? However, this $Q$ might not work in $V$ as condition (1) need not be absolute?! | |
| Apr 19, 2020 at 18:46 | comment | added | Johannes Schürz | Concerning your second comment, I had the same idea, just wasn't 100% sure that an ultrafilter cannot be $\Pi_1^1$.... How does this relate to your $\Pi_1^1$ P-point base (in L)? Can't I just say $X \in \mathcal{U}$ iff $\forall Y \in \mathcal{B} \colon X \cap Y \neq \emptyset$? | |
| Apr 19, 2020 at 18:38 | comment | added | Jonathan Schilhan | 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. | |
| Apr 19, 2020 at 18:33 | comment | added | Jonathan Schilhan | 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$. | |
| Apr 19, 2020 at 18:33 | history | edited | Johannes Schürz | CC BY-SA 4.0 |
added 11 characters in body
|
| Apr 19, 2020 at 12:45 | history | edited | Johannes Schürz | CC BY-SA 4.0 |
deleted 23 characters in body
|
| Apr 19, 2020 at 12:16 | history | answered | Johannes Schürz | CC BY-SA 4.0 |