Need help with a simple proof about a bijection.

Question

anonymous · Answer

Here is the problem.

anonymous · Answer

@phi @SithsAndGiggles

anonymous · Answer

@DebbieG

anonymous · Answer

So I actually have a solution for the problem. The main problem is I don't understand the solution.

debbieg · Answer

Welllll........ it's been a long time since I did a proof anything like this. Here's my "intuitive" thoughts behind it.

There is a bijection from 3N to 5N because for each integer k$in$N, there exists a $\large n_k=3k$ in 3N and a $\large n_k=5k$ in 5N such that $\large k|n_k$.

Know what I mean?

anonymous · Answer

I'm a little confused about the notation. I know that N =  the Natural numbers. So what would 3N mean in 3N --> 5N.

debbieg · Answer

They defined 3N and 5N in the problem. (Actually, it's a general definition for mN.)

3N is the set of all natural numbers that are divisible by 3 (or put another way, all the positive integer multiples of 3... 3, 6, 9, 12, etc).

5N is all the natural numbers divisible by 5 (5, 10, 15, etc).

anonymous · Answer

ah, that makes sense.

anonymous · Answer

So, in the solution how did they get that f(n) = 5n/3?

anonymous · Answer

Hmm, just trying to get my head around the problem. Got a test tomorrow that will probably have a problem like this, lol.

So I kind of see why we divide 5n by 3 becasue m | n. But do we know that f is a bijection?

anonymous · Answer

Sorry, I keep going on and off, getting a bad internet connection here.

debbieg · Answer

To prove that f is a bijection, must prove that:

(1) it is an injection (so each element of the domain maps to only one element of the range).

To prove that, show that if f(m)=f(n), then m=n.

and (2) is it a surjection (so each element of the range maps to an element of the domain).

So to prove that, show that if m is in the range (5N) then there is an element of the domain (3N) which, when evaluated, gives that range element as the output.

anonymous · Answer

Oh, I see, so when the solution said that it was a bijection right at the start the didn't actually know that until they had proved it was an injection and a surjection. 

That is starting to make better sense now :)

anonymous · Answer

I am gonna try some more problems and see if I can figure them out. But I think I'm understanding the concept now anyway. Thanks for all the help!