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

  • $\begingroup$ Looking at Chapter 7 of "How to prove it" by Daniel Vellerman should help you to understand these issues in detail. $\endgroup$ – Ariel Serranoni Jul 11 '18 at 16:30
  • $\begingroup$ In your case it is clear $B\subseteq A $, so unless $A$ contains an element not in $B$, they would be equal as sets, and $A=B$ implies they have the same cardinality (size). $\endgroup$ – hardmath Jul 11 '18 at 16:55
  • $\begingroup$ "Is there an elegant way to prove this obvious fact, that will be understandable even to a non-expert audience?" It's not a matter of proof. It's a matter of definition. A being "larger" than B means that it is not possible to map $B\to A$ so that all elements of B are mapped to. If every element of A was in B we could map to every element of A simply by mapping every element of B to itself. But as every map $B\to A$ will fail, that is not the case. $\endgroup$ – fleablood Jul 11 '18 at 17:00
  • $\begingroup$ @hardmath Not necessarily: $A$ could be the powerset of the language 0* over the alphabet {0,1}, in which case $B$ contains things like {1} that aren't in $A$. In the general case, neither is a subset of the other. $\endgroup$ – Draconis Jul 11 '18 at 17:08
  • $\begingroup$ @Draconis: For your purpose (showing $A$ contains an element not in $B$), it suffices to consider $A\cap B$, which as a subset of $B$ is at most countable, and then work with $A\cap B \subseteq A$. Again, unless $A$ contains an element not in $B$, $A$ and $A\cap B$ would be equal as sets and have the same size (contradicting the assumed uncountable cardinality of $A$). $\endgroup$ – hardmath Jul 16 '18 at 4:58

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.


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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