Onto functions?

An onto function is a function where every value in the domain has a value in the codomain (i.e., every x in f(x) has a y).

Put more simply, an 'onto' function is one where for every valid x value, there is a defined y.

How do you prove that F(m,n) = 2^(m-1) * (2n - 1) is onto?

The domain of F(m,n) is NxN, meaning the values for m and n can be an of the Natural numbers. (How does your instructor define the set N, does it include zero?)

Let's check...

F(0,0) = 2^(0-1) * (2(0) - 1) = 2^(-1) * (-1) = -1/2, so zero doesn't work because we said F: NxN -> N, and -1/2 is not a member of N. So I'm guessing the definition of N is {1,2,3, ...}

F(1,1) = 2^(1-1) * (2(1) - 1) = 2^0 * (2-1) = 1*1 = 1

So the first values work OK in this function, and we have the first step in our inductive proof.

An inductive proof works like this.

F(1) = a value I'm allowed. (that is you use the first value in the domain to show that it ends up in the codomain, in this case the domain and codomain are both N).

Then you say, if F(x) is a value in the codomain, then F(x+1) is a value in the codomain.

So you've proved (by math) that F(1) is true, and that when any given F(x) is true, F(x+1) is true, so you've proved that all the values in N are true. Bingo!

We've already done step 1.

So you need to show that if:

F(m,n) is a member of N, then F(m+1,n) and F(m,n+1) and F(m+1,n+1) are all members of N. We need to do this because there are two inputs from the domain that might need to be incremented.

You need to do a bunch of algebra to write all this out. I'll do the first one:

F(m+1,n) = 2^((m+1)-1) * (2n-1)

= 2^m * (2n-1)

which is really saying that F(m+1,n) = 2*F(m,n) and 2 times any member of N is in N, so that checks out.

The second inductive element:

F(m,n+1) = 2^(m-1) * (2(n+1) - 1)

= 2^(m-1) * (2n + 2 - 1)

= 2^(m-1) * ((2n - 1) + 2)

so we see that the term 2n -1 was the odd number lower than 2n and thus 2n+1 is the odd number above 2n. So now the second term is 2 higher and if x * y -> N then x * (y+2) -> N. (You can do a little inductive proof on that if you need to. ;-)

Hope that sets you on a path to finish!