Justifying the difference between countable and uncountable

Question

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$.)

Answer 1

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.

Answer 2

Being countable means that there exists a bijection between your set and the set $\mathbb N$ of integers (or at least a surjection from $\mathbb N$ to your set, or an injection from your set to $\mathbb N$, if you include finite sets). Being uncountable means there is no such bijection.

Let's suppose $A\subset B$ (so that $A\setminus B=\emptyset$). Let $\phi$ be a bijection between $\mathbb N$ and $B$. For every $a\in A$, define $\psi(a)=n$ if $a=b_n$ (every $a\in A$ is in $B$, remember ?).

Now $\psi$ is clearly an injection from $A$ to $\mathbb N$, therefore a bijection from $A$ to a subset of $\mathbb N$. Therefore $A$ is countable, which contradicts your hypothesis.

Answer 3

What does "larger" mean?

The "same size" means that we can find a way (via a function $f:B\to A$) that will map every distinct item of $B$ to a distinct item of $A$ and that all items of $A$ are mapped to. This function is "one-to-one" meaning every distinct item of $B$ is mapped to a distinct and different item of $A$. This function is also "onto" meaning every element of $A$ is mapped to. A function that is one-to-one and onto is a bijection. That some bijection can exist between the sets means they have the same "cardinality". Informally that mean they are "the same size" but the makes my teeth hurt.

If this is impossible, if no such function can possibly exist, then the sets are not the same size.

If it is impossible to have a function from $B$ to $A$ that is unto, that is to say if every possible function you can imagine from $B$ to $A$ simply can not cover all of $A$ then $A$ is "larger" than $B$.

Not if we can map all the elements of $B$ to themselves. If $A$ is "larger" than $B$ then this is not onto, it can not cove all of $A$ and $A$ has elements that $B$ does not have.

(Note: It's important that the no function can be onto; not just that some function is not onto.)