Proving $A\subset B\implies |A|\leq |B|$

220 Views Asked by At

I would like to prove the following:

Let $A,B\subset\mathbb{R}$ be non-empty finite sets. Prove that if $A\subset B$, then $|A|\leq |B|$.

We are also given the following theorem:

Theorem $1.31$: Let $n,m\in\mathbb{N}$ with $n<m$. Then there does not exist an injectve function $f:[m]\rightarrow[n]$.

Here we define $[n]=\lbrace 1,2,3,...,n\rbrace$.

Here is my attempt:

Assume that $|A|>|B|$. Then $A$ is in bijective correspondence with $[k_1]$ and $B$ is in bijective correspondence with $[k_2]$, with $k_1>k_2$. By theorem $1.31$ (this was previously given in the text), there exists no injection from $A$ to $B$. By the definition of $\subset$ every $x\in A$ satisfies $x\in B$. Define a function $1:A\rightarrow B$ such that $1(x)=x$. Because all $x\in A$ are in $B$, and each $x\in A$ is distinct by definition of a set, $1(x)$ is an injection into $B$. By definition of $A$ and $B$ there exist bijective functions $f_A:[k_1]\rightarrow A$ and $f_B:B\rightarrow [k_2]$. Thus, the function $g(x)=f_B(1(f_A(x)))$ is an injection $g:[k_1]\rightarrow [k_2]$ which by theorem $1.31$ cannot exist. This is a contradiction, and therefore our assumption $|A|>|B|$ must be false.

I would like to know if this proof works, something feels off.

2

There are 2 best solutions below

0
On BEST ANSWER

Your proof is fine but redundant.

By definition $|A|\leq|B|$ means that there exists a inyection $f:A\rightarrow B$. So, as $A\subseteq B$ then $1:A\rightarrow B$ is a inyection, then you get your conclution.

5
On

This proof is quite simple, and you don't need a contradiction to do it.

Since $A\subset B$, we have that $\forall x\in A, x\in B$, and $\exists x\in B:x\notin A$. $$\therefore |A|<|B|$$ QED