Prove a function from a finite set to the same set is 1-1 iff it is onto

[Newtime]

Homework Statement

for n$$\in$$N and $$\phi$$: {1,...,n} $$\rightarrow$$ {1,...,n}. Prove $$\phi$$ is 1-1 if and only if it is onto.

The second part of this is to prove that if E is a finite set and f:E$$\rightarrow$$E then f is 1-1 iff f is onto.

Homework Equations

There are several (many) theorems which could be usefl, but all of them are standard logical ones which don't really need to be restated, and I will cite all theorems used in my attempt at a solution below.

The Attempt at a Solution

I used induction but I have a strong suspicion I made a logical error so let me start by saying that in truth, I don't really know how to approach this problem because we are given so little. I can't say that {1,...,n} is a finite set so there has to be a 1-1 function from {1,...,n} onto it because I can't say that the set is "finite" simply by looking. Actually, I can say that, and it is finite, but in the proof, I certainly cannot simply say this. Also, proving both parts of thsi has been proving to be a challenge. Proving that 1-1 implies it is onto seems easier than proving the function is onto implies it is 1-1. I'm just sort of lost and frustrated. But here's my attempt in it's entirety:

(it's the attached image, I typed it up on MAPLE)

Also, I have a little scribbled out for proving that if the function is onto then it is 1-1 but I didn't get as far and any help there would be appreciated.

Thanks in advance for the help.

edit: also, for the second part of thsi problem, proving the same thing but for a generalized finite set, I think this would be substantially easier because I could reference the above proofs and also because I could use the definition of finite.

 

[Newtime]

Also, I should say that the only reason my main attempt was using induction was that my professor said it would be a good way to go about it. However, my instinct is to prove both direction of the first problem by contradiction, which I attempted to do for a while with no success...however, I still think I could maybe do it that way.

 

[jbunniii]

Induction seems unnecessary and actually complicates the proof.

Suppose $$\phi$$ is onto. Then $$|image(\phi)| = n = |domain(\phi)|$$. Therefore since $$n < \infty$$, $$\phi$$ must map distinct inputs to distinct outputs (else we would have fewer image points than domain points). By definition this means that $$\phi$$ is 1-1.

The converse is very similar.

 

[Newtime]

Induction seems unnecessary and actually complicates the proof.

Suppose $$\phi$$ is onto. Then $$|image(\phi)| = n = |domain(\phi)|$$. Therefore since $$n < \infty$$, $$\phi$$ must map distinct inputs to distinct outputs (else we would have fewer image points than domain points). By definition this means that $$\phi$$ is 1-1.

The converse is very similar.

This is absolutely correct for a way of reasoning but you used what I am trying to prove in your proof (At least I think you did). Namely where you say

$$\phi$$ must map distinct inputs to distinct outputs (else we would have fewer image points than domain points).

Especially the part you have in parentheses. This is obvious but it still needs to be proven and is the central matter to the proof and I can't seem to express this mathematically...

I'm so tempted to say that because for each elemtn in {1,...,N} there is an element in the domain: {1,...,N} then we simply let (phi) be the identity function which means (phi) is 1-1 but I feel like this is making too many assumptions especially since I was given so little.

 

[Office_Shredder]

Your induction looks pretty good, but you juggle your words a bit wishy washily so it's not clear what you're driving at. Here's the key point:

Call the function f. Then f(1) is an element of the range of f. 1 is the only element of the domain mapping to f(1) since f is 1-1. Then the map f₁ from domain-{1} to codomain-{f(1)} where f₁(x)=f(x) for all x in the new domain is a 1-1 function, so is onto by induction (since the size of the domain and codomain are smaller, and are now one smaller). Hence f is onto since it must map onto the codomain minus f(1), but also maps to f(1).

 

[aPhilosopher]

I don't have any greek letters but given phi, let s(a) be the count of elements that map to a.
by the definition of a function the sum of all s(a) is equal to N. See what you can do with the assumptions of 1-1 and onto one at a time to get it both ways.

 

[Newtime]

Your induction looks pretty good, but you juggle your words a bit wishy washily so it's not clear what you're driving at. Here's the key point:

Call the function f. Then f(1) is an element of the range of f. 1 is the only element of the domain mapping to f(1) since f is 1-1. Then the map f₁ from domain-{1} to codomain-{f(1)} where f₁(x)=f(x) for all x in the new domain is a 1-1 function, so is onto by induction (since the size of the domain and codomain are smaller, and are now one smaller). Hence f is onto since it must map onto the codomain minus f(1), but also maps to f(1).

I'm not following the last sentence...why would this have to be the case?

I don't have any greek letters but given phi, let s(a) be the count of elements that map to a.
by the definition of a function the sum of all s(a) is equal to N. See what you can do with the assumptions of 1-1 and onto one at a time to get it both ways.

This does not have to be the case is the function is not 1-1. But are you saying assume it is 1-1 and try to prove it is onto using the function s(a) you defined?

Thanks for all the replies so far by the way.

 

[aPhilosopher]

This does not have to be the case is the function is not 1-1. But are you saying assume it is 1-1 and try to prove it is onto using the function s(a) you defined?

Thanks for all the replies so far by the way.

Yes it does. One of the cool things about any function is that they let you separate the domain into non-intersecting, covering subsets and give you an association between the subsets and elements of the image. This is because even if a function isn't 1-1, it's still many-1. If it was 1-many or many-many, it wouldn't be a function would it?

 

[jbunniii]

This is absolutely correct for a way of reasoning but you used what I am trying to prove in your proof (At least I think you did). Namely where you say Especially the part you have in parentheses. This is obvious but it still needs to be proven and is the central matter to the proof and I can't seem to express this mathematically...

I'm so tempted to say that because for each elemtn in {1,...,N} there is an element in the domain: {1,...,N} then we simply let (phi) be the identity function which means (phi) is 1-1 but I feel like this is making too many assumptions especially since I was given so little.

I will clarify.

Suppose $$\phi$$ is onto. That means that its image is the entire codomain:

$$image(\phi) = \{1,2,\ldots,n\}$$

Therefore the SIZE of its image is n:

$$|image(\phi)| = n$$

But this is also the size of the domain. Thus we have

$$|image(\phi)| = |domain(\phi)| = n$$

Suppose that $$\phi$$ is NOT one-to-one. Then there must be two distinct input points, call them x and y, such that

$$\phi(x) = \phi(y)$$

Thus we have used up two of the input points and obtained only one output point. There are $$n - 2$$ input points left, and $$n-1$$ output points left. Thus there's no way that we can reach all of the output points. But this is a contradiction. Therefore $$\phi$$ must be one-to-one.

Thus $$\phi$$ onto implies $$\phi$$ one-to-one. It remains to prove the converse. I'll leave that to you. It's quite similar.

By the way, note that I implicitly used the fact that $$n$$ is FINITE in the boldface sentence above. That sentence would not necessarily be true if $$n$$ were infinite.

 

[Newtime]

thanks again for the replies guys, it's a bit late here so I will read over them in the morning and post back.

 

[Office_Shredder]

Thus we have used up two of the input points and obtained only one output point. There are $$n - 2$$ input points left, and $$n-1$$ output points left. Thus there's no way that we can reach all of the output points. But this is a contradiction. Therefore $$\phi$$ must be one-to-one.

Thus $$\phi$$ onto implies $$\phi$$ one-to-one. It remains to prove the converse. I'll leave that to you. It's quite similar.

This is basically the pigeonhole principle that you're using. It may not surprise you that what is to be proven is also called the pigeonhole principle sometimes. Basically, you need to prove some result like this in order to demonstrate the pigeonhole principle is true, so there probably will not be credit given for a proof like this

To go back to

Hence f is onto since it must map onto the codomain minus f(1), but also maps to f(1).

To use more formal notation:

$$f: A \rightarrow B |A|=n, |B|=n$$

Suppose the result holds whenever $|A|, |B| \leq n-1$
If f is 1-1 then f(1) is contained in B. So we define new sets
$$C=A\{1}, D=B\{f(1)}$$

where \ is set subtraction. The f must map C to D, as f(m) is not f(1) when m is not 1. This is where we use that f IS 1-1. If it wasn't, there might be some other element of A that maps to f(1), and our codomain wouldn't shrink in size. So the map
$$g:C \rightarrow D, g(m)=f(m)$$

is 1-1. But |C|=|D| = n-1 so by induction g is onto. Hence f must map to every element in D, since given d in D, there exists c in C (and hence A) so that g(c)=d - but g(c)=f(c).

Also, f(1)=f(1), so for every element b in B, we have that there exists an element a in A so that f(a)=b (if b=f(1) we use the fact that 1 is in A; if b is not 1, we use the g(m) argument above)