1
$\begingroup$

I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is computable/decidable?

That is, given two recursively enumerable sets $A$, $B$, is $|A \cap B|$ always decidable/computable (provided we know what $|A|$ and $|B|$ are, even if they are infinite)?

My first hunch is that this is equivalent to the halting problem for Turing Machines, but how would I show this?

$\endgroup$
4
  • $\begingroup$ What exactly do you mean by "given" in given two recursively enumerable sets A, B? If you mean that you know the algorithms that enumerate the sets, you can't even say what $|A|$ is. $\endgroup$
    – Dmitry
    Aug 27, 2022 at 22:17
  • $\begingroup$ Are you saying that the cardinality is in general undecidable? "Given" as in for ANY two such sets. $\endgroup$
    – T. Rex
    Aug 27, 2022 at 22:35
  • 2
    $\begingroup$ What are the inputs and outputs for your desired algorithm? You can't say that inputs are sets $A$ and $B$ since they can potentially have infinite sizes. If your inputs are enumerators for $A$ and $B$, then you can't even tell what the cardinalities of these languages are (in case if they are finite). $\endgroup$
    – Dmitry
    Aug 27, 2022 at 23:03
  • $\begingroup$ @Dmitry To clarify (revised my question), if we have an algorithm (or better yet a Turing Machine) which determines if $x \in A \cap B$, I would like to solve the question of "how many" such $x$ will the Turing Machine will halt / algorithm will say "yes". $\endgroup$
    – T. Rex
    Aug 27, 2022 at 23:36

1 Answer 1

1
$\begingroup$

Interesting question.

Claim: A finite recursively-enumerable set is decidable.
Proof: In fact, a finite set is decidable.

Claim: It is computable to find $|A\cap B|$ given two finite sets $A$ and $B$.
Proof: List all elements in $A$. For each one of them, check whether it is in $B$. Return the number of all elements that are found in $B$.

Claim: It is not computable to find $|A\cap B|$ given two recursively-enumerable sets $A$ and $B$ such that $|A|$ is finite and $|B|$ is infinite.
Proof: For the sake of contradiction suppose algorithm $M$ finds $|A\cap B|$ given such $A$ and $B$. Let us solve the halting problem, as you expected.
Let $X$ be an arbitrary Turing machine and $w$ be an arbitrary input.
Let $M_1$ be a Turing machine that halts only when the input is $w$. Let $M_\infty$ be a Turing machine that always halts except when the input is $w$, at which time $X$ behaves the same as $X$ upon input $w$. Note that $|L(M_1)|=1$ is finite and $|L(M_\infty)|$ is infinite.
Apply $M$ to $L(M_1)$ and $L(M_\infty)$. If $|L(M_1)\cap L(M\infty)|=1$, then $X$ halts upon $w$. Otherwise, $|L(M_1)\cap L(M_\infty)|=0$, and $X$ loops forever upon $w$. $\quad\checkmark$

Corollary: It is not computable to find $|A\cap B|$ given two recursively-enumerable sets $A$ and $B$ with known cardinalities.

$\endgroup$
2
  • $\begingroup$ What is $L$ supposed to mean ? $\endgroup$
    – T. Rex
    Aug 28, 2022 at 5:24
  • $\begingroup$ $L(T)$ for a Turing machine $T$ is the language accepted by $T$. $\endgroup$
    – John L.
    Aug 28, 2022 at 6:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.