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?

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

]]>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?

]]>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.

]]>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.

]]>|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.

]]>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.

]]>