2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ Commented Dec 8, 2021 at 22:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – markvs
    Commented Dec 8, 2021 at 22:25

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .