N10 Left and Right Inverses; a Bijection ℕ × ℕ → ℕ
In progress: these notes stop partway.
Exercise N10.1 (Problem 1). Given , consider such that (a right inverse) or (a left inverse).
(a) Show that permits a right inverse iff is surjective. Show that, in general, a right inverse is not unique.
(b) Show that is injective.
Show solution
(a) Let us prove first the and then the .
Proof of . Let . Then for every , writing , we have , for all .
Proof of . For all there exists with ; choose one such for each and set . Then , but , so for all , so .
In general, the right inverse is not unique: consider with and . Then there exist infinitely many right inverses, since the only can be sent to any .
(b)Proof of . Given , let ; we show that whenever ,. So , but since we get .
Proof of . Given for all . For set (well defined by injectivity), and define arbitrarily on (this needs ). So , but , so for all , so .
To show that in general a left inverse is not unique, consider , and the inclusion . Any left inverse must send and , but it does not matter where it sends , since : both and work.
Exercise N10.2 (Problem 2). Give an explicit bijection .
Show solution
We want and . Idea: .
First tries:
Another try: all ,.
Writing the numbers as sums of powers of 2:
Sorting the even numbers by powers of 2 with remainders : “For each there is a distance of , so # of divisors for any .” “Each has remainders for divisors.”