As in the title: let $\mathfrak{F}$ be a filter on $\mathbb{N}$ such that, for every computable set $A\subseteq \mathbb{N}$, either $A\in\mathfrak{F}$ or $\mathbb{N}\setminus A\in\mathfrak{F}$; is $\mathfrak{F}$ necessarily an ultrafilter? Or can there be a non-computable set $B$ such that neither $B\in\mathfrak{F}$ nor $\mathbb{N}\setminus B\in\mathfrak{F}$? I suppose we could start from the filter of co-finite sets, enumerate all computable sets, and by transfinite induction add them all or their complements to our filter, but I'm not 100% sure the resulting object indeed has the aforementioned properties. I think immune sets may play a role here, if that helps.
6
- 1$\begingroup$ I believe computable subsets form a proper sub-boolean-algebra of the powerset boolean algebra, so you can take an ultrafilter on it. This should work. Edit: well, a lot won't work, but at least one should. Topologically I'm thinking about choosing a non-singleton equivalence class from the induced quotient on $\beta \mathbb{N}$. $\endgroup$Keith J. Bauer– Keith J. Bauer2025-07-01 21:27:47 +00:00Commented Jul 1 at 21:27
- $\begingroup$ @Keith That is true about the sub-Boolean-algebra, but which ultrafilters (if any) will work? $\endgroup$GVT– GVT2025-07-01 21:35:26 +00:00Commented Jul 1 at 21:35
- $\begingroup$ I would have to think more to find a constructive example. A non-example would be a principal ultrafilter, because it has precisely one extension to the entire $\mathcal{P}(\mathbb{N})$. $\endgroup$Keith J. Bauer– Keith J. Bauer2025-07-01 21:38:17 +00:00Commented Jul 1 at 21:38
- 1$\begingroup$ The question contains a construction of a filter that decides all computable sets, and the construction shows that this filter has a countable base. If you already know that no nonprincipal ultrafilter on $\mathbb N$ has a countable base, you're done. If you don't know it, you can prove it by building a set $A\subseteq\mathbb N$ such that each set in the countable base has at least one element in $A$ and one element outside $A$. $\endgroup$Andreas Blass– Andreas Blass2025-07-01 22:49:27 +00:00Commented Jul 1 at 22:49
- 2$\begingroup$ Would you be willing to change your question so that the answer to the title and the first body question are the same? (In light of the current wording of @NoahSchweber's answer, it's probably best to change the body question.) The current wording has them opposite. $\endgroup$LSpice– LSpice2025-07-02 00:30:05 +00:00Commented Jul 2 at 0:30
| Show 1 more comment
2 Answers
$\begingroup$ $\endgroup$
1 The answer (to the title question) is positive. There are several ways to prove this; the most brute-force, which I still think has some pedagogical value, is to $(i)$ show that there are $2^{2^{\aleph_0}}$-many ultrafilters on $\mathbb{N}$ but $(ii)$ observe that there are only $2^{\aleph_0}$-many different "behaviors-on-the-computable-sets" that an ultrafilter can have, and so there must be many ultrafilters which behave identically on the computable sets. The intersection of two distinct ultrafilters which behave identically on the computable sets is then a filter with your properties which is not an ultrafilter.
- $\begingroup$ Oh, so simple! That's perfect, thank you very much. $\endgroup$GVT– GVT2025-07-01 22:14:03 +00:00Commented Jul 1 at 22:14
$\begingroup$ $\endgroup$
Let $B$ be a subset of $\Bbb N$ which intersects any infinite computable set but does not fully contain any of them. Such a set is easy to construct by diagonalization, and immune sets you mention in your question provide an example.
Now, consider any filter $\mathcal F$ on the algebra of computable sets, and take the filter $\mathfrak F$ on $\mathbb N$ generated by it. Explicitly, its elements are subsets of $\Bbb N$ which contain some element of $\mathcal F$ as a subset. Now, if one of those intersections is finite, then $\mathfrak F$ is a principal ultrafilter. But otherwise, by our choice of $B$, neither $B$ nor $\mathbb N\setminus B$ contains an element of $\mathcal F$, so $\mathfrak F$ is not an ultrafilter.
Thus we get "explicit" examples by taking the cofinite filter on the algebra of computable sets, extending it to an ultrafilter on that algebra, and then using it to generate a filter on $\mathbb N$. Just like Noah's answer, the same argument shows that we can replace computable sets with any countable class of subsets of $\mathbb N$.
