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

Kazy · 2006-02-20 17:19:11

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.

darthradius · 2006-02-20 19:27:03

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.

Kazy · 2006-02-21 01:58:22

Yes I mean the number of elements in the set

Ricky · 2006-02-21 03:08:15

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.

Kazy · 2006-02-21 08:07:56

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

Ricky · 2006-02-21 08:58:08

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)

Kazy · 2006-02-21 11:03:19

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?

Ricky · 2006-02-21 14:22:11

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)

Kazy · 2006-02-21 16:04:19

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

Kazy · 2006-02-22 04:30:52

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

Ricky · 2006-02-22 05:39:50

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)

Kazy · 2006-02-22 05:59:52

Thanks! I appreciate it.

Math Is Fun Forum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Board footer