Bijection/Countability (1 Viewer)

[Librah]

Don't know where to start.

 

[InteGrand]

Don't know where to start.

is countable, and are uncountable.

 

[Carrotsticks]

The rationals (Q) are countable. Construct a grid of naturals. Let the origin be (1,1). From there, move right to (2,1) then diagonally to (1,2), then up to (1,3) then down the diagonal to pass through (2,2) and (3,1) and repeat this pattern infinitely. By doing this, you can construct a bijection from the corresponding sequence to the naturals, so positive Q is countable. To show it for all of Q (so including negative), just do the exact same thing as what you did for integers to show that they were countable (0, 1, -1, 2, -2 etc etc).

The reals (R) are not countable. Consider the interval [0,1] and suppose the reals are countable. In other words, there exists a 'list' of all the real numbers from 0 to 1. Suppose this list has terms named N_1, N_2, N_3 etc etc.

Now let's construct a number M by this (I'll describe it in words, perhaps easier for you to understand).

The number M starts with 0.xxxxx (to ensure it's in the interval [0,1]. Take the n'th number in the list and look at it's n'th digit. If that digit is something other than say 1, then M's n'th digit is 1. If that digit is a 1, then M's n'th digit is a 0.

What you'll notice is that M (which is a real number) cannot be on our 'list of real numbers' because it differs in digits to the terms in our 'list' (more specifically, the n'th digit is always different). But since M is real, this means that the cardinality of R is larger than the cardinality of N, so there cannot be a bijection. Hence, the reals are uncountable.

From here it follows that C is uncountable since R is a subset of C. So if R is uncountable, then so must C.

 

[Librah]

The rationals (Q) are countable. Construct a grid of naturals. Let the origin be (1,1). From there, move right to (2,1) then diagonally to (1,2), then up to (1,3) then down the diagonal to pass through (2,2) and (3,1) and repeat this pattern infinitely. By doing this, you can construct a bijection from the corresponding sequence to the naturals, so positive Q is countable. To show it for all of Q (so including negative), just do the exact same thing as what you did for integers to show that they were countable (0, 1, -1, 2, -2 etc etc).

The reals (R) are not countable. Consider the interval [0,1] and suppose the reals are countable. In other words, there exists a 'list' of all the real numbers from 0 to 1. Suppose this list has terms named N_1, N_2, N_3 etc etc.

Now let's construct a number M by this (I'll describe it in words, perhaps easier for you to understand).

The number M starts with 0.xxxxx (to ensure it's in the interval [0,1]. Take the n'th number in the list and look at it's n'th digit. If that digit is something other than say 1, then M's n'th digit is 1. If that digit is a 1, then M's n'th digit is a 0.

What you'll notice is that M (which is a real number) cannot be on our 'list of real numbers' because it differs in digits to the terms in our 'list' (more specifically, the n'th digit is always different). But since M is real, this means that the cardinality of R is larger than the cardinality of N, so there cannot be a bijection. Hence, the reals are uncountable.

From here it follows that C is uncountable since R is a subset of C. So if R is uncountable, then so must C.

So was the first part just putting the some rational x/y into a co-ordinate system (x,y)?
But ugh, i don't think i'll be able to produce a proof like that during an actual exam.

 

[Carrotsticks]

So was the first part just putting the some rational x/y into a co-ordinate system (x,y)?
But ugh, i don't think i'll be able to produce a proof like that during an actual exam.

You won't be required to produce proofs like the above under exam conditions.

What I had above is pretty standard if you've studied countability.