/sci/ - Science & Math

Suppose we have two finite sets, A and B, with size m and n respectively, then suppose [math]f : A \to B[/math] is a function.

Proof: if f is injective, then [math]m\leq n[/math]

by contrapositive, m > n [math]\implies[/math] f is not injective. by the PHP there exists [math]x_{1},x_{2} \in A [/math] such that, for [math]y\in B[/math], [math]f(x_{1} )= y = f(x_{2})[/math]. So f is not injective.

Proof: if f is surjective, then [math]m \geq n[/math]

by contrapositive, m<n [math]\implies[/math] f is not surjective. by the PHP there exists [math]y\in B[/math] such that [math]y \neq f(x) [/math], so f is not surjective.


how'd I do?

only patricians can post in this thread