Recursively enumerable set meets the intersection of subsets

computabilityelementary-set-theorylogicrecursion

Write $\phi_p$ for the function defined by the program $p$, as in these examples on Wikipedia.

Suppose that sets $X_i\subset \mathbb N, i=1,2$ satisfy $$\text{ if the domain } W_p=\{x:\phi_p(x)\downarrow\} \text { of }\phi_p \text{ is infinite, then } W_p\cap X_i\ne \emptyset$$
and also $X_i^c$ is infinite and $X_i=W_{p_i}$ for some $p_i$ (they are 'recursively enumerable').

How to prove that $X_1\cap X_2$ also has these properties?

The second two properties are clear. But the first isn't.

The conditions in the display only guarantee that these is some $x_1\in W_p\cap X_1$ and $x_2\in W_p\cap X_2$ but it may be the case that $x_1\in X_1-X_2$ and $x_2\in X_2-X_1$ so that neither $x_1$ not $x_2$ lies in $X_1\cap X_2$. How to produce a common $x$ which lies in $W_p\cap X_1\cap X_2$?

Best Answer

You're quite right that the implication isn't immediate. But it is there. There are two key facts:

  • The $X_i$s themselves are r.e., so we can combine them with r.e. sets to create new r.e. sets.

  • "Finite modifications" don't affect r.e.-ness.

The second bulletpoint is the more subtle one; it lets us apparently strengthen one of our assumptions in a very useful way. Specifically, consider the following property:

An r.e. set $Y$ is big if for every infinite r.e. set $W$ we have $W\cap Y$ is infinite.

A priori, bigness seems lie a strengthening of the first property on your list. But in fact they are equivalent: if $W$ is infinite and r.e. and $W\cap Y$ is finite, then $W\setminus (W\cap Y)$ is infinite, r.e., and disjoint from $Y$.

  • Note that this didn't use any assumptions on $Y$ at all!

So now suppose $X_1,X_2$ are as above. Let $W$ be infinite and r.e.; we want to show that $W\cap X_1\cap X_2\not=\emptyset$. But $W\cap X_1$ is itself an r.e. set disjoint from $X_2$; do you see how to show that $W\cap X_1$ is also infinite (thus yielding a contradiction)?

Related Question