World's most popular travel blog for travel bloggers.

# Intersection and partial quantity decidability

, ,
Problem Detail:

I'm still insecure in the section decidability (no proof needed, I want to divine it):

X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable?

X is decidable and Y is a partial quantity of X. Is Y decidable, too or not?

Thanks!

###### Answered By : Rick Decker

For your first question, the answer is that \$X\cap Y\$ will not necessarily be decidable. Let \$Y\$ be an undecidable language over an alphabet \$\Sigma\$ and let \$X=\Sigma^*\$. Then obviously \$X\$ will be decidable and \$X\cap Y=Y\$ will be undecidable. On the other hand, the intersection may be decidable, as we could show by letting \$X=\emptyset\$.

For your second question, I assume that by "\$Y\$ is a partial quantity of \$X\$" you mean that \$Y\$ is a subset of \$X\$ (i.e., \$Y\subseteq X\$). Then we can do a similar construction, letting \$X=\Sigma^*\$, and \$Y\$ be undecidable, so again, \$Y\$ may or may not be decidable.

It's worth mentioning that this latter result frequently trips up students. Very few properties of languages are closed under subset/superset: there's no guarantee that a subset of a regular language will be regular, for example.