Proving Bijections: Q and Q x X

[laminatedevildoll]

I am not sure how to start these proofs.

Prove that there is a bijection between Q and Q x X if

a. X = N
B. X = {0,1,...n-1}

We're learning about cardinality, but I was thinking that I have to show that it's one-to-one and onto.

 

[Andrew Mason]

I am not sure how to start these proofs.

Prove that there is a bijection between Q and Q x X if

a. X = N
B. X = {0,1,...n-1}

We're learning about cardinality, but I was thinking that I have to show that it's one-to-one and onto.

One can associate a rational number, a/b, with the point (a,b) on a cartesian plane. One can then proceed to count all of the points on the cartesian graph by starting at the origin and proceeding in a spiral outward. One will eventually reach the point (a,b) for any value of a and b. So there is a bijection between Q and N.

[edit:]To make a bijection between Q and Q x N, associate each rational number (a,b) with (a,b,n) where $n \epsilon N$.

A bijection exists between Q and Q x X = {0,1,...n-1} as X is a subset of N.

AM

 

[matt grime]

It states a bijection from Q to QxN and QxX.

note it doesn't state you have to find a bijection, merely show one exists. How you do that will depend on what you know already.

For instance, do you know there is a bijection between Q and N? if so we can immediately restrict to showing a bijection between N and NxN. Clearly all we need to do is send a pair (a,b) to 2^a3^b, this is a bijection from NxN to an infinite subset of N, this implies they have the same cardinality and hence a bijection exists (note we've not found one).

The casen of a bijection between N and NxX as above is easier, in that it can be done explicitly.

send the element (a,b) to an+b that is a bijection between N and NxX.

 

[laminatedevildoll]

Finding a bijection can be very confusing. I know that I have to map stuff to Q and N to find that its one-to-one and onto.