Tuesday, 5 August 2014

elementary set theory - Is this proof correct? Injective function $ f: A rightarrow B iff $ function $ g: B rightarrow A $ is surjective




I've begun a course in "Real Analysis" recently and I have this trivial exercise. Could someone check if my proof is correct?



Proposition: There exists Injective function $ f: A \rightarrow B \iff $ there exists function $ g: B \rightarrow A $ is surjective



Proof: Firstly, we prove injective function $f: A \rightarrow B \Longrightarrow g: B \rightarrow A$ is surjective Suppose $\exists f: A \rightarrow B, $ such that $ f$ is injective, i. e., $ \forall x_{1}, x_{@} \in A, x_{1} \neq x_{2} \rightarrow f(x_{1}) \neq f(x_{2})$.



By hypothesis, $\exists g: B \rightarrow A$ such that $g$ is not surjective. Then,there is at least one $ x \in A $ such that $ \forall y \in B, g(y) \neq x $. But, that is not possible, because if $f$ is injective, then all $x \in A$ correspond to some $y \in B$. Contradiction!



Now, we prove surjective function $g: B \rightarrow A \Longrightarrow f: A \rightarrow B$ is injective. Suppose $g: B \rightarrow A $ is surjective, i. e., $\forall y \in B, \exists x \in A$, such that $ g(y) = x$. By hypothesis, $\exists f: A \rightarrow B$ such that f is not injective. Then, there are $x_{1}, x_{2} \in A$ such that for $x_{1} \neq x_{2}$, there are $f(x_{1}) = f(x_{2})$. By the definition of function, that only could happen, if there is $ y \in B $ such that $ y \notin Dom(g) $. Contradiction!




So, There exists Injective function $ f: A \rightarrow B \iff $ there exists function $ g: B \rightarrow A $ is surjective. Q.E.D.


Answer



I'm sorry, but your proof seems to have some issues.



First of all, you should clarify, what you mean by




Proposition: Injective function f:A→B⟺ function g:B→A is surjective





Is $g$ supposed to be the inverse function of $f$? If so, the statement itself is not quite true. If you have an injective function $f:A\rightarrow B$, then you cannot define its inverse on the whole of $B$ but merely on the image of $A$ under $f$. This is denoted by $f(A)$ and clearly it holds $f(A) \subset B$. Furthermore you should make it a habit to alway state what $A$ and $B$ actually are. Finite dimensional vector spaces? Metric Spaces? Hilbert Spaces?



Now answering your question: the statement




Then,there is at least one x∈A such that ∀y∈B,g(y)≠x. But, that is not possible, because if f is injective, then all x∈A correspond to some y∈B




is not true. This has nothing to do with $f$ being injective. In fact, $f$ being injective is needed to define the inverse function $g:f(A)\rightarrow A$ because, as you know a function needs to assert a uniquely determined value to each argument. But if you define $g$ like this, then it is already surjective by definition because suppose $\exists x \in A$ s.t. $g(y)\neq x \quad \forall y \in f(A)$ then this means, x has no image under $f$ but because of $x \in A$ and $f :A\rightarrow B$ This is a contradiction.




The second part of your proof looks good though. You definitely had the right thought.



EDIT: I've just seen the question was edited, so i guess my answer doesn't fit in anymore.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...