Let $I$ be the set of all recursively enumerable languages over an alphabet $\Sigma$. Let $$S_\alpha=\{i\in I : \alpha\in i\}$$ for all $\alpha\in\Sigma^*$. Then $$E=\{S_\alpha:\alpha\in K\subseteq\Sigma^*\}$$ can be extended to an ultrafilter $\mathscr{U}$ since $E$ has the finite intersection property: $$\{{\alpha_1},\dots,{\alpha_n}\}\in S_{\alpha_1}\cap\dots\cap S_{\alpha_n}\text { and }\{{\alpha_1},\dots,{\alpha_n}\}\in I \text{ since it's a finite language}$$ We can define $L=\{\alpha:\{i\in I:\alpha\in i\}\in \mathscr{U}\}$.

What is the relationship between $L$ and $K$?

  • 1
    $\begingroup$ Extending $E$ to $U$ means that $E \subseteq U$. Note that $K = \{\alpha \mid S_\alpha \in E\}$ and $L = \{\alpha \mid S_\alpha \in U\}$, so $K \subseteq L$. (This question seems like an exercise – what is your motivation for asking it?) $\endgroup$ Sep 27, 2013 at 19:32


Your Answer

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

Browse other questions tagged or ask your own question.