Intereting Posts

Proving the irrationality of $e^n$
Extending a morphism of schemes
Representing negative numbers with an infinite number?
Why isn't an odd improper integral equal to zero
Primality test for Proth numbers using Fibonacci numbers
Calculating the height of a circular segment at all points provided only chord and arc lengths
What's umbral calculus about?
Detail in Conditional expectation on more than one random variable
Proof that the tensor product is the coproduct in the category of R-algebras
How can I choose the best algorithm to integrate ODE's numerically?
What is the purpose of Jordan Canonical Form?
Show that, for any $\epsilon>0$, there exist two rationals such that $q < x < q'$ and $|q-q'|<\epsilon$
Partial sums of $\sin(x)$
Which number its greater $\pi^3$ or $3^\pi$?
Prove that a subgroup which contains half of all elements is a normal subgroup.

Let $X$ and $Y$ be sets with $m$ and $n$ elements respectively and let $f:X\rightarrow Y$ be a function from $X$ to $Y$.

Show that if $f$ is surjective, then $m\geq n$.

I know this should be true since in words a surjective can be seen as:

- How to tackle a recurrence that contains the sum of all previous elements?
- Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number
- $A \oplus B = A \oplus C$ imply $B = C$?
- How to solve $a_n = 2a_{n-1} + 1, a_0 = 0, a_1 = 1$?
- Prove that $h< \frac{(k+l)^{k+l}}{(k^{k}l^{l})}$.
- Prove $\sum_{i=1}^n i! \cdot i = (n+1)! - 1$?

“For every element in the codomain, there is at least one element of the domain mapping onto it”.

I’m having trouble converting this idea into a proof. My guess is I need to show that at least $n$ maps from $Y$ to $X$ are possible for distinct values of $x$. If this is the case, we can assert $m \geq n$.

So far I basically have the definition with quantifiers.

Proof: Show than at least $n$ distinct maps from the codomian, back to the domain are possible.

Since $f$ is surjective, $\forall y \in Y, \exists x \in X : f(x) = y.$

- Rubik's cube and counting
- Evaluate $\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+…+\binom{n}{2k}$
- Matrix linear algebra generators
- Choosing numbers without consecutive numbers.
- What is the history of this theorem about the finite sum of a polynomial?
- Proof that no polynomial with integer coefficients can only produce primes
- Positive integers less than 1000 without repeated digits
- difference between some terminologies in logics
- Show that, if $f:A\to B$ is a function, with $A$ and $B$ being finite sets, and $|A|=|B|$, then $f$ is one to one iff $f$ is onto.
- How can I prove that Game of Life's evolution function is continuous?

Let us prove this by contradiction, so suppose $f$ is surjective and $m < n$. Since $m < n$, we have that $m + k = n$ for some natural number $k > 0$.

Let us denote the set $X = \{x_1, x_2, \ldots x_m\}$ and $Y = \{y_1, \ldots y_m, y_{m+1}, \ldots, y_{m+k}\}$. Consider the first $m$ elements of $Y$, then without loss of generality, we can assume that $f(x_i) = y_i$ for $i \in \{1, \ldots, m\}$ (we may assume this, since we can simply swithch the indices of the elements to make this work). But then we have that there is no element $x \in X$ such that $f(x) = y_{m+1}$ (since a function maps each $x$ to exactly one element $y \in Y$). Hence the map $f$ is not surjective, which is a contradiction. Therefore, our assumption $m < n$ is false and we find that $m \geq n$.

For each $y\in Y$, let $N(y)$ be the number of elements in $X$ that are mapped to $y$.

Then $\sum_{y\in Y} N(y) = |X|$ because every element of $X$ is mapped to some element of $Y$ and the fibers of $f$ partition $X$.

If $f$ is surjective, then $N(y)\ge 1$ for all $y \in Y$. Therefore

$$

|Y|=\sum_{y\in Y} 1 \le \sum_{y\in Y} N(y) = |X|

$$

If $f$ is injective, then $N(y)\le 1$ for all $y \in Y$. Therefore

$$

|Y|=\sum_{y\in Y} 1 \ge \sum_{y\in Y} N(y) = |X|

$$

*Hint:* The inverse of $f$ lets us define an injection between $Y$ and a subset of $X$.

- Prove that Pascals triangle contains only natural numbers, using induction.
- Is there a memorable solution to Kirkman's School Girl Problem?
- Get the direction vector passing through the intersection point of two straight lines
- Fun Linear Algebra Problems
- Proving with diagonal lemma
- In how many different ways can we fully parenthesize the matrix product?
- Question of Clifford theory
- How to prove that complex numbers (C) are linear space over real numbers (R) field?
- Proof of Non-Convexity
- Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle.
- Preconditioning for an LBFGS
- How to find the maximum diagonal length inside a dodecahedron?
- Unique ultrafilter on $\omega$
- Prob. 11, Chap. 4 in Baby Rudin: uniformly continuous extension from a dense subset to the entire space
- Laplace Operator in $3D$