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

You are not logged in.

• Index
•  » Help Me !
•  » Need help with a injective (one-to-one) proof

|
Options

Kazy
2006-02-23 04:59:52

Thanks! I appreciate it.

Ricky
2006-02-23 04: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?

Kazy
2006-02-23 03:30:52

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

Kazy
2006-02-22 15:04:19

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

Ricky
2006-02-22 13: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.

Kazy
2006-02-22 10: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-22 07: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.

Kazy
2006-02-22 07: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-22 02: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-22 00:58:22

Yes I mean the number of elements in the set

2006-02-21 18: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 16: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.