Recently, I had sets $A$ and $B$, and needed to prove that there existed some element of $A$ that was not in $B$. I did this by showing that $A$ was uncountably infinite and $B$ was countably infinite, so $A$ was larger. This proof is intended for an audience without significant mathematical knowledge.
But then I got stuck. It seems obvious that if $A$ is larger than $B$, then there must exist some element of $A$ that's not in $B$. But obvious isn't a proof. And while I know how to prove this for finite sets (subtract $B$ from $A$ and the difference will be non-empty), I'm wary about subtracting one infinite set from another. Cantor diagonalization is nicely elegant and understandable, but the elements of my sets are themselves infinite sets, and I don't know how I would diagonalize them.
Is there an elegant way to prove this obvious fact, that will be understandable even to a non-expert audience?
(If it helps, $A$ is the powerset of an arbitrary infinite regular language over an alphabet $\Sigma$, and $B$ is the set of regular languages over $\Sigma$.)
Best Answer
If $B$ is countable, then it can be mapped to the integers. Assume $A$ is a subset of $B$. With the same mapping, $A$ can be mapped to a subset of the integers. But, this contradicts the fact that $A$ is uncountable, so $A$ is not a subset of $B$. Thus $A$ contains an element that $B$ does not have.