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$ – András Salamon Sep 27 '13 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.