How do I prove this using an injection (if needed)?

Question

I'm trying to prove the following:

Show that if $A$ and $B$ are sets and $A\subset B$, then $|A|\leq |B|$.

This is what I came up with:

Proof: Let $A$ and $B$ be sets where $A\subset B$, therefore $A\ne B$. Then there exists an $a\in B$ such that $a\notin A$. Therefore, $A$ has cardinality less than $B$. Therefore proving that when $A\subset B$, then $|A|\leq |B|$. QED

From what I've been researching, that because $|A|\leq |B|$ is in this proof, that means I would need to use some sort of injection to prove this. Just wondering if anyone can give me any advice on how this would be done.

Answer 1

Unfortunately everything about this is wrong.

If $A \subset B$ then $A$ could be equal to $B$. $A \subset A$. Every set is a subset of itself. (this problem is about all subsets; not just proper subsets.)

You say that showing there is an $a \in B$ so that $a\not \in A$ means $|A| \le |B|$. Well, let $A = \mathbb Q$ and $B = \{\pi\}$. Then $|B| = 1$ and $\pi \not \in \mathbb Q = A$. Do you want to claim that $|\mathbb Q| \le 1$.

I think what you were thinking was if all the $x \in A$ are also in $B$ then $|A| \le |B|$ because $B$ has everything $A$ has and more. But that is exactly what you are trying to prove.

That is the intuition but you have to define the intuition formally.

$|A| = |B|$ means there is a bijection $\phi: A \to B$. $\phi$ is injective and surjective.

$|A| \le |B|$ means there is an injection $\phi: A \to B$ but $\phi$ may or may not be surjective.

$|A| < |B|$ means there is an injective $\phi: A\to B$ but $\phi$ is not surjective an there does not exist and and can not exist a surjective function from $A$ to $B$.

....

So you need to prove $|A| \le |B|$ means there is an injection $\phi: A \to B$ but $\phi$ may or may not be surjective.

....

And this is surprisingly easy:

The intuition is every $x \in A$ is in $B$ and $B$ has everything $A$ does.

So we are looking at each $x\in A$ and saying "Here it is! It's in $B$!". So what function is that?

Well that's just the identity functions.

Let $\phi: A \to B$ via $\phi(x) = x$. That's it!

We must prove:

1) $\phi$ is a well defined function: $A \to B$. That is for every $x \in A$ there is exactly one $\phi(x) = x \in B$. That is true because $A \subset B$ so $x \in A\implies \phi(x) = x \in B$.

2) That $\phi$ is injective. That is: If $\phi(x) = \phi(y)$ then $x = y$. Well that's trivial: If $\phi(x) = \phi(y)$ then $\phi(x) =x$ and $\phi(y) = y$ so $x=\phi(x)=\phi(y)= y$.

And that's it.

By definition $|A| \le |B|$.

....

Now, I can see why this seems abstract or roundabout. Or a weird definition of $|A| \le |B|$. But notice. If you are talking about infinite sets this is the only definition you've got! And this is the only way you can explain cardinality.

That's actually why they call an injective function "injective". Because it maps a set INTO another set. And the must basic way a set can be IN another set is by being a subset.

Answer 2

Consider the inclusion map $\iota:A \to B$ defined by $\iota(x) = x$. This is surely an injection $A \to B$.

Answer 3

You aren't considering the infinite case, e.g. $I=(0,1) \subset \mathbb{R}$.

There still exist $r \in \mathbb{R}$ such that $r \notin I$ but $|I| \nless |\mathbb{R}|$. In fact $|I| = |\mathbb{R}|$

So the argument you gave applies only to the case where B is finite. Now you have to think about the case where B can be infinite as well.

Your argument does apply to a few infinite subsets such as:

$\mathbb{N}= \{1,2,3,...\} \subset \mathbb{R}$ and $|\mathbb{N}| < |\mathbb{R}|$ is true. But as in the above example, this doesn't always hold for every infinite subset.