If S is an infinite set, then there is a bijection from S onto a proper subset o
ID: 2944762 • Letter: I
Question
If S is an infinite set, then there is a bijection from S onto a proper subset of S.
Use two of the sets (N, Q, R, or Z) , or any of their subsets or supersets, to illustrate this fact. Define the bijection explicitly.
Explanation / Answer
let f: N -> N be defined by f(n)=2n. This is the map to the evens. Claim: f is injective. A function is injective iff f(n)=f(m) implies n=m Suppose f(n)=f(m). Then 2n=2m and thus n=m. Claim: f is surjective* A function is surjective iff for every m in M there is an n in N such that f(n)=m. In this case let M=N then it is obvious that for every m there is n such that 2n=m. The only problem could be f(0). But f(0)=0. So f is bijective because any function that is both injective and surjective is bijective. let g: Q -> Q be defined by g(n)= 2n-1. Claim: g is injective suppose g(m)=g(n). Then 2n-1= 2m-1 ==> cancel the -1's and the 2's. Thus n=m. Claim: g is surjective* For every m in Q there is an n such that 2n-1=m, again is obviously true. Again the only problem could be 0. But g(0)=-1. So g is bijective *NOTE: both surjectivity proofs were pretty trivial because of the closure of each set of numbers under the arithmetic operations used in the functions. In other words, it is a property of the N to say that if n and m are in N, then so is n*m.