Skip to main content
MathOverflow

Return to Answer

added 5 characters in body
Source Link
喻 良
喻 良
  • 4.2k
  • 1
  • 21
  • 30

I have another interesting example applying set theory method to prove a result in recursion theory.

Given an infinite set $E\subseteq \omega$, a question is what's cardinality of the set $A_E=\{x\in 2^{\omega}\mid \exists c\forall n K^x(n)\geq K(n)-c\}$$A_E=\{x\in 2^{\omega}\mid \exists c\forall n\in E K^x(n)\geq K(n)-c\}$, where $K$ is the Kolmogorov complexity and $K^x$ is the Kolmogorov complexity relative to $x$?

A famous result in algorithmic randomness theory is that $A_{\omega}$ is countable. In fact, for any set $E$ having a recursive subset, $A_E$ must be countable. Then a natural question is can $A_E$ be uncountable?

Wolfgang and I (Wolfgang Merkle and Liang Yu, Being low along a sequence and elsewhere, The Journal of Symbolic Logic, Volume 84, Issue 2 June 2019 , pp. 497-516.) constructed some $E$ so that $A_E$ uncountable. The proof is by Mathias forcing together Shoenfield absoluteness.

I have another interesting example applying set theory method to prove a result in recursion theory.

Given an infinite set $E\subseteq \omega$, a question is what's cardinality of the set $A_E=\{x\in 2^{\omega}\mid \exists c\forall n K^x(n)\geq K(n)-c\}$, where $K$ is the Kolmogorov complexity and $K^x$ is the Kolmogorov complexity relative to $x$?

A famous result in algorithmic randomness theory is that $A_{\omega}$ is countable. In fact, for any set $E$ having a recursive subset, $A_E$ must be countable. Then a natural question is can $A_E$ be uncountable?

Wolfgang and I (Wolfgang Merkle and Liang Yu, Being low along a sequence and elsewhere, The Journal of Symbolic Logic, Volume 84, Issue 2 June 2019 , pp. 497-516.) constructed some $E$ so that $A_E$ uncountable. The proof is by Mathias forcing together Shoenfield absoluteness.

I have another interesting example applying set theory method to prove a result in recursion theory.

Given an infinite set $E\subseteq \omega$, a question is what's cardinality of the set $A_E=\{x\in 2^{\omega}\mid \exists c\forall n\in E K^x(n)\geq K(n)-c\}$, where $K$ is the Kolmogorov complexity and $K^x$ is the Kolmogorov complexity relative to $x$?

A famous result in algorithmic randomness theory is that $A_{\omega}$ is countable. In fact, for any set $E$ having a recursive subset, $A_E$ must be countable. Then a natural question is can $A_E$ be uncountable?

Wolfgang and I (Wolfgang Merkle and Liang Yu, Being low along a sequence and elsewhere, The Journal of Symbolic Logic, Volume 84, Issue 2 June 2019 , pp. 497-516.) constructed some $E$ so that $A_E$ uncountable. The proof is by Mathias forcing together Shoenfield absoluteness.

Source Link
喻 良
喻 良
  • 4.2k
  • 1
  • 21
  • 30

I have another interesting example applying set theory method to prove a result in recursion theory.

Given an infinite set $E\subseteq \omega$, a question is what's cardinality of the set $A_E=\{x\in 2^{\omega}\mid \exists c\forall n K^x(n)\geq K(n)-c\}$, where $K$ is the Kolmogorov complexity and $K^x$ is the Kolmogorov complexity relative to $x$?

A famous result in algorithmic randomness theory is that $A_{\omega}$ is countable. In fact, for any set $E$ having a recursive subset, $A_E$ must be countable. Then a natural question is can $A_E$ be uncountable?

Wolfgang and I (Wolfgang Merkle and Liang Yu, Being low along a sequence and elsewhere, The Journal of Symbolic Logic, Volume 84, Issue 2 June 2019 , pp. 497-516.) constructed some $E$ so that $A_E$ uncountable. The proof is by Mathias forcing together Shoenfield absoluteness.