/sci/ - Science & Math » Thread #13788819

116KiB, 2400x338, sketch-1635177319643.png

View Same Google iqdb SauceNAO

Anonymous Mon 25 Oct 16:01:49 2021 No.13788819 View Reply Original Report

Quoted By: >>13788841 >>13789009

How do I prove this? I can't even prove that it is injective nor can I prove that it's surjective. Am I missing some mathematical property of this function, which makes the proof easy? Or am I just supposed to find the inverse function by luck and thereby proof that it is bijective?
Any help is greatly appreciated!

Anonymous

Anonymous Mon 25 Oct 2021 16:07:50 No.13788833 Report

Quoted By: >>13788848

Are you stupid? I'll admit the proof that it's surjective is nontrivial, but proving the function is injective is trivial.

Anonymous

Anonymous Mon 25 Oct 2021 16:09:13 No.13788841 Report

Quoted By:

>>13788819
Not gonna do your homework kiddo.

Anonymous

Anonymous Mon 25 Oct 2021 16:11:29 No.13788847 Report

Quoted By:

Morally if should be clear:

Every number n can be divided by 2 a fixed amount of time. This amount is b.
Now n/2^b can't be divided by 2, so it's an uneven number, i.e. of the form 2*a+1 for some unique a.
Conversely, all a and b give you some number.
You just need to formally prove that for given a and b, there's no x<a and y>b such that you get the same number. (Informally it follows from what I already said, namely that a given number can be divided by 2 a unique number fo times)

PS I think you'll find this function on the Cantor pairing function Wikipedia page, gl

Anonymous

Anonymous Mon 25 Oct 2021 16:12:08 No.13788848 Report

Quoted By:

>>13788833
>the proof that it's surjective is nontrivial
???? You must be joking. It's completely obvious

Anonymous

Anonymous Mon 25 Oct 2021 16:27:46 No.13788895 Report

Quoted By: >>13788913

Every non-zero even number can be expressed as m*(2^n) where m is odd and n>0
That means your expression is obviously a surjection over the even numbers if you let m=2a+1 and n=b.
For the case where n=b=0 then the expression reduces to 2a+1, which implies the function is surjective for all the odd numbers.
Surjection proved.

Anonymous

Anonymous Mon 25 Oct 2021 16:34:09 No.13788913 Report

Quoted By: >>13788919

>>13788895
>Surjection proved
No, here
>Every non-zero even number can be expressed as m*(2^n) where m is odd and n>0
you simply assumed that it is true.

Anonymous

Anonymous Mon 25 Oct 2021 16:36:41 No.13788919 Report

Quoted By: >>13788930

>>13788913
>you simply assumed that it is true.
Yes i did, it's a lemma which OP can easily prove (Hint: use the fundemental theorem of arithmetic)
I'm not going to do his entire homework for him.

Anonymous

Anonymous Mon 25 Oct 2021 16:41:15 No.13788930 Report

Quoted By: >>13789017

>>13788919
>use the fundemental theorem of arithmetic
You also use the Generalized Stokes theorem if an exercise asks you to proof the Fundamental theorem of Calculus?

You can prove this much more elementary with induction.

Anonymous

Anonymous Mon 25 Oct 2021 17:02:52 No.13789009 Report

Quoted By: >>13789042

>>13788819
Hint: f(a,b) = f(a)f(b)

Anonymous

Anonymous Mon 25 Oct 2021 17:04:25 No.13789017 Report

Quoted By: >>13789023

>>13788930
If f(a,b) generates all N, then doesn't that mean it's also a prime number generational function?

Anonymous

Anonymous Mon 25 Oct 2021 17:06:25 No.13789023 Report

Quoted By:

>>13789017
f(n) = n generates all of N too

Anonymous

Anonymous Mon 25 Oct 2021 17:10:30 No.13789042 Report

Quoted By:

>>13789009
I think what you really meant is f(a,b)=f(a,0)f(0,b)

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches