current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

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.

share|cite|improve this question
1  
In your proposition, do you mean to specify that there exist such functions? It is not clearly stated. – forallepsilon Aug 23 '14 at 17:18
    
The statement "For every two sets $A,B$, there exists $f : A \to B$ such that $f$ is injective if and only if there exists $g : B \to A$ such that $g$ is surjective" is equivalent to the axiom of choice. So at some point you will need to use the axiom of choice or an equivalent statement. – Ian Aug 23 '14 at 17:21
    
I mean "there exist". Thanks! – Guilherme Duarte Aug 23 '14 at 17:21
1  
In that proposition, you must rule out $A = \varnothing$. – GEdgar Aug 23 '14 at 17:45
up vote 1 down vote accepted

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.

share|cite|improve this answer
up vote 2 down vote

There are several problems with your proof.

Firstly, in both directions of your proof, your statements "By hypothesis, ..." seem to assume that all proofs are by contradiction, and that you must refute the negation of the statement. What you are assuming is not a hypothesis.

Secondly, your negation of the statement you wish to prove is incorrect. The negation of "there exists a surjective function" is not "there exists a function that is not surjective," but rather: "all functions are not surjective." The same goes for your other direction.

You may want to look at the $\underline{inverse}$ of these funtions, and in one case, extend its domain.

share|cite|improve this answer
up vote 1 down vote

No, this proof is not correct. First of all, you misstate what you set out to prove in each half. “Firstly, we prove...” says you will prove that something implies $g$ is surjective. But at this point, $g$ is not something that has been defined. There is a big difference between “$g$ is surjective” and “There exists a surjective function $g$.” You need to prove the latter.

Next, in each part of your proof, you say “By hypothesis, there exists...” You have no hypothesis that allows you to say this. In the “Firstly” part, for example, your only hypothesis is that there exists an injective function $f$ from $A$ to $B$. This does allow you to say there exists a non-surjective function from $B$ to $A$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.