Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2006-02-20 17:19:11

Kazy
Member
Registered: 2006-01-24
Posts: 37

Need help with a injective (one-to-one) proof

I need to prove the following and I'm completely lost.. Any help with be much appreciated.

Let A and B be finite sets and let f: A -> B be a function.
A) Prove that if f is injective, then |Im f| = |A|.
b) Is the converse of part (a) true? Prove or disprove.
c) Prove that if f is injective, then |A| ≤ |B|


Im f is the Image of f which i'm pretty sure just means the range.. This is the first time I've ever seen that used instead of the range of f. I think when you prove equality you need to show that whatever is on the left and right of the = needs to be shown as subsets of each other but I have no idea how to go about that.

Offline

#2 2006-02-20 19:27:03

darthradius
Member
Registered: 2005-11-28
Posts: 97

Re: Need help with a injective (one-to-one) proof

Kazy wrote:

|Im f| = |A|.
|A| ≤ |B|

When you use the absolute value symbols, you mean the order of those sets (number of elements in the set), right?

If so, then I'm not sure that you need to prove that they are subsets both ways, because actually each of those terms would just represent a number.


The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
                                                             -Bertrand Russell

Offline

#3 2006-02-21 01:58:22

Kazy
Member
Registered: 2006-01-24
Posts: 37

Re: Need help with a injective (one-to-one) proof

Yes I mean the number of elements in the set

Offline

#4 2006-02-21 03:08:15

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need help with a injective (one-to-one) proof

This isn't a formal proof, but more like what you need to be thinking during your proof:

A) If f is injective, then for every element in Im f (the range), there must be one and only one path to get back to f.  All the elements that don't have path (since you don't know that f is onto) you ignore, otherwise the Im f wouldn't even be a function.

B) Yes, for pretty much the same reasons.  Remember, two elements in Im f can't go to the same element in A, because then f wouldn't even be a function, as it wouldn't be well defined.

C) You know that every element in A corresponds to a unique element in B, so at the very least, |A| = |B|.  But there could be some elements in B which don't have an inverse (it's not guarunteed to be onto), so there may be more elements in B.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#5 2006-02-21 08:07:56

Kazy
Member
Registered: 2006-01-24
Posts: 37

Re: Need help with a injective (one-to-one) proof

I understand the ideas of why its true, I'm just lost on how to contruct a formal proof for it. Any ideas?

Offline

#6 2006-02-21 08:58:08

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need help with a injective (one-to-one) proof

A)

Proof:

Since f is a function, for every element a∈A, there exists a b∈B, such that f(a) = b.  Since f is injective, this b is unique.

Thus, |A| ≤ |B|.  Now let's consider the image, f-¹.

Since f is not onto, for every b, there may or may not exist an a∈A such that f-¹(b) = a.  Consider the two cases:

Case 1: a exists.  If a was not unique, then f(a0) = b and f(a1) = b where a0 ≠ a1.  If this were true, f would not be 1-1.  But f is 1-1.  Thus, contradiction, a is unique.  So for every element b in B, if there exists an a, then there exists one and only one a.

Case 2: a does not exist.  Then b can not be in the domain of f-¹, because if it was, f-¹ wouldn't be a function.

So for every a∈A, f maps a to a unique b, and for every b∈Im f, Im f maps b to a unique a.

∴ |A| = |Im f|.  QED.

The other two are quite similar.  Try to post something up here, even if it's sketch work, and I'll help you out.

Last edited by Ricky (2006-02-21 14:22:51)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#7 2006-02-21 11:03:19

Kazy
Member
Registered: 2006-01-24
Posts: 37

Re: Need help with a injective (one-to-one) proof

Since f is a function, for every element a∈A, there exists a b∈B, such that f(a) = b.  Since f is injective, this b is unique.

Thus, |A| ≤ |B|.

Is that all I need to say for C to prove that part? Can I just say its true because the function is injective?

Offline

#8 2006-02-21 14:22:11

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need help with a injective (one-to-one) proof

For every element in A, you know there has to be one element in B.  Thus, it has to be |A| ≤ |B|.  If it was |A| > |B|, then there would be at least one element in A for which there was no element in B.

Edit: Heh, I don't quite know why this was in the proof for A.  It doesn't belong there.

Last edited by Ricky (2006-02-21 14:23:37)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#9 2006-02-21 16:04:19

Kazy
Member
Registered: 2006-01-24
Posts: 37

Re: Need help with a injective (one-to-one) proof

Are you referring f as the Image (Im f), or the inverse of f?

Offline

#10 2006-02-22 04:30:52

Kazy
Member
Registered: 2006-01-24
Posts: 37

Re: Need help with a injective (one-to-one) proof

or did you mean f-¹ as the inverse image?

Offline

#11 2006-02-22 05:39:50

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Need help with a injective (one-to-one) proof

Ah, sorry, I got mixed up with terms.

The image of f is a subset of B, such that b∈Im f iff there exists an a∈A such that f(a) = b.

Assume |A| < |Im f|.  Then either there exists an a0 and a1∈A, such that a0=a1 and f(a0) ≠ f(a1) or there exists a b∈Im f such that there does not exist an a∈A such that f(a) = b.  These are the only two ways there can be more elements in Im f.  In either case, they lead to contradictions, and so |A| ≥ |Im f|.

Now assume |A| > |Im f|.  Then there must exist a0 and a1∈A such that a0 ≠ a1 and f(a0) = f(a1).  But f must be injective.  Contradiction, so |A| = |Im f|.

Did that make more sense?

Last edited by Ricky (2006-02-22 05:40:45)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#12 2006-02-22 05:59:52

Kazy
Member
Registered: 2006-01-24
Posts: 37

Re: Need help with a injective (one-to-one) proof

Thanks! I appreciate it.

Offline

Board footer

Powered by FluxBB