Is Each Set Countable or Uncountable?

[Goldenwind]

Homework Statement

34) Determine whether each of these sets is countable or uncountable. For those that are countable, exhibit a one-to-one correspondence between the set of natural numbers and that set.
a) integers not divisible by 3

b) integers divisible by 5 but not by 7

c) the real numbers with decimal representations consisting of all 1s

d) the real numbers with decimal representations of all 1s or 9s

Homework Equations

N = {0, 1, 2, 3, ...}

The Attempt at a Solution

Not a clue where to start.
For a), how do I express something as divisible by 3? It is either:
Divisible by 3
A number divisible by 3, + 2, or..
A number divisible by 3, + 1.

b) is the same as a), just worse.

c), this would have something to do with the fraction 1/9.

d), same as c), only includes the 9s too. Unsure what fraction gives 9s (Unless 9/9, as people say that 1 = 0.9999... *Shrug*)

 

[StatusX]

Start by trying to list all the elements of the set. If you can find a systematic way to do this, you'll have shown the set is countable. For example, you might do part a by listing the elements as:

1,2,-1,-2,4,5,-4,-5,...

Note that the first two are both subsets of the integers, which is a countable set, so must be countable (such subsets could also be finite, although (a) they are clearly not in this case and (b) finite sets are usually also referred to as countable).

If you can't list the elements this way, and decide the set is probably uncountable, try either producing a cantor diagonal type proof, or try to construct a bijection between the set and the real numbers (a particularly convenient representation of the real numbers for this purpose will be the set of all base two expansions).

 

[HallsofIvy]

The first two are subsets of the integers so that should be pretty obvious. Set up a "list" (one-to-one correspondence with the natural numbers) for the integers and drop out the integers that are not in the subset.

The third should also be obvious. Are there any "real numbers with decimal representations that consist entirely of 1s" that are not rational numbers?

Yes, 9/9= 1!

 

[Goldenwind]

Is it allowed to give multiple formulae to express it?

For example, I *could* answer a) as f(n) = 3n+1, and f(n) = 3n+2... as the combined answers of each of these will span across all non-divisible-by-three integers.

Or do I need to find one formulae that will work for it?

 

[HallsofIvy]

If you want that to be a "one-to-one" correspondence, you can't use that because you would have f(2)= 6+1= 7 and f(2)= 6+2= 8. But you are on the right track. If n is even then n/2= m is an integer and f(n)= (3n/2) + 1= 3m+ 1 will give you numbers 1 more than a multiple of 3 while if n is odd m= (n-1)/2 is an integer and f(n)= (3(n-1)/2)+ 2= 3m+ 2 gives you numbers 2 more than a multiple of 3.
Try "f(n)= (3n/2)+ 1 if n is even, (3(n-1)/2)+ 2 if n is odd".

 

[Goldenwind]

That works for not divisible by 3, but part b) is a bit more troublesome.

With 3, a number must be:
- Divisible by 3
- 1 above divisible by 3
- 2 above divisible by 3

And out of the "1 above" and the "2 above", we can rely on the fact that one is even, and one is odd, to give our two different formulae.

With part b), it's a bit more complex.

A multiple of 5 will end in 5 or 0. It follows that 70, 140, 210, etc, are divisible by both 5 and 7. Also, as far as numbers ending in 5 are concerned, we have 35, 105, 175, that are divisible by both 5 and 7.

We want a set that has all multiples of 5 in it, however with 35, 105, 175, …, and 70, 140, 210, …, removed from it.

Here, a number divisible by 5 can be expressed as 5k. If k is even, we have a result that ends in 0 (5*2 = 10, 5*4 = 20, etc). If k is odd, we have a result that ends in 5 (5*3 = 15, 5*5 = 25, etc).

So to cover all multiples of 5 (Those that end in 5, and those that end in 0), we have f(k) = 5k for each instance. However, we want to tweak this such that it doesn't include the numbers that are multiples of 7.

We want to take out 0, 70, 140, 210, 280, etc... out of the k-is-even case, and 35, 105, 175, etc... out of the k-is-odd case.

Something tells me we want to have f(k) = 5(k), but with something else in the k bracket... be it 5(k+6) or... I dunno, something.

See, in part a), we said:
"If n is even, then use this function"
"If n is odd, then use this function"

Problem is, we don't have a "Divisible by 3, or even, or odd" problem, we have a "Divisible by 7, or 1 above, or 2 above, or 3 above, or 4 above, or 5 above, or 6 above"... and then you have to find out which are multiples of 5... and blah.

'kay, I know you start off with f(k) = 5k, which will cover all multiples of 5. How do I keep this the same, while ruling out multiples of 7?

 

[Goldenwind]

Still need a clue for b). I know how to express the multiples of 5, but unsure how to lock out the multiples of 7.

And for c), I know how to, but just need clarification... when it says "real numbers with decimal representations of all 1s", I know it means stuff like 0.111... and 1.111... would work too, but what about 2.111...? When it says decimal representations, does it mean just the decimals have to be 1s, or everything must be ones, and not in fraction form?

d) I got.

 

[StatusX]

Still need a clue for b). I know how to express the multiples of 5, but unsure how to lock out the multiples of 7.

Numbers divisible by 5 and 7 are exactly those divisible by 35. So just exclude these multiples of 5, ie, skip over every 7th element in the list of multiples of 5.

And for c), I know how to, but just need clarification... when it says "real numbers with decimal representations of all 1s", I know it means stuff like 0.111... and 1.111... would work too, but what about 2.111...? When it says decimal representations, does it mean just the decimals have to be 1s, or everything must be ones, and not in fraction form?

I would guess it means every digit is a 1. But in this case the interpretation you choose won't affect the answer, although the second one would be some more work.

 

[Goldenwind]

That leads me back to the same problem though. While it was helpful that you pointed out I'm taking out multiples of 35, it's now the same thing...

...to express multiples of 5 (5k, where k is some integer), but without multiples of 35. Unsure how to take them out.

HallsOfIvy did it for multiples of 3, taking advantage of the fact that the numbers between two 3-multiples have 1 even and 1 odd... but for this, every 7th 5 will need to be removed. Some of those 5 will be even, some odd... how do I express this in a formula? =/

 

[StatusX]

I don't think an actual formula is really necessary, but if you need one, you can write something like:

a_n = 5 \left( ( n \mbox{ mod } 7 ) + 8\mbox{ floor }(n/7) \right)

where n mod 7 is the remainder of n upon division by 7 and floor(x) is the greatest integer less than or equal to x. Then for 1<=n<=6, the first term in the parantheses is n and the second is zero, so you get a_n=5n. For 7<=n<=13, the first term is n-7 and the second is 8, so you get a_n=5(n+1). It's not hard to see this keeps working, because when n+1 is not a multiple of seven, we have a_n+1-a_n=5, while if n+1 is a multiple of seven, we have a_n+1-a_n=10, so that we skip every multiple of 35. But, again, I see no reason why you can't just list the numbers as:

5,10,15,20,25,30,40,45,...

 

[Goldenwind]

Sadly, the textbook doesn't have any useful examples that deal with "is not a multiple of".

"For those that are countable, exhibit a one-to-one correspondence between the set of natural numbers and that set."
Without giving formulae, such as f(n) = blah, how do I "exhibit" this "correspondence"? That's what I don't like about English... everything is so vague :(

Like, earlier today, I had to write "hiking/dog sledding". To me, this says "(hiking/dog) sledding", even though I realize it's meant to say "hiking/(dog sledding)"... but I can't put extra brackets there for emphasis, as it's "wrong" in the vague English language.

5+3*2 = 16, ZOMG INVISIBLE BRACKETS! D:

/endRant

 

[StatusX]

Here's a one-to-one correspondence:

..., 5, 10, 15, 20, 25, 30, 40, 45, ...

..., 1, 2, 3, 4, 5, 6, 7, 8, ...

It's clear how this will continue, and that to every integer we will associate a unique multiple of 5 that's not a multiple of 7, and conversely for every multiple of 5 that's not a multiple of 7 there will correspond a unique integer. I don't see how a formula like the one I wrote above makes this any more rigorous.

 

[xk25c]

I have a alternative for the second one:

f(n)= 5(n + floor(n/7))

the "floor" is a floor function, the greatest integer not exceeding the real number n/7

the sequence is as follows: 5,10,15,20,25,30,40,45,50,55,60,65,75,80,85,90,95,100,110,115,120,125,130,135,145,150...

By testing each element, I think the function works.