# Surjection between two finite sets of different sizes

Suppose I have two sets $$A$$ and $$B$$. $$A = \{1, 2\}$$ and $$B = \{2, 4, 6, 8\}$$. I am trying to prove that there is no surjection from $$A$$ to $$B$$ by finding at least one $$y$$ value from $$B$$ such that for every element $$x\in A$$, $$f(x)\ne y$$. I am not entirely sure how to prove this and kind of stuck.

• That approach won't work since you could always define a function $f$ so that $f(x) = y$. (Namely, the function $f_y$ defined by $f_y(x) = y$ for all $x \in A$. Give me a $y$, I'll give you a function mapping to it.) Commented Dec 8, 2021 at 22:23
• For every function $f:A\to B$, there are two values of $f$ and four elements of $B$ so there are at least $2=4-2$ elements of $B$ which are not values of $f$, so $f$ is not surjective. Commented Dec 8, 2021 at 22:25

Recalling the definition of function, two elements from $$B$$ can't correspond to the same element in $$A$$. (Considering $$f:A\to B$$).
Since you have $$|B|=4>2=|A|$$, the definition of suerjection won't be satisfied.
A fully rigorous argument here can be extremely hard. To give a mostly rigorous argument: Suppose for contradiction that $$f:A\to B$$ is a surjection. Then $$f(A)⊆ B$$ and $$f(A)=\{f(1),f(2)\}$$ so that there are only two elements in $$f(A)$$. Since there are four elements in $$B$$ then there must be some element in $$B\smallsetminus f(A)$$ (the "relative complement"). If we call this element $$y$$ then there is no $$x$$ such that $$f(x)=y$$.