Thread: Two Enumeration Questions

1. Find an enumeration of the set of all odd integers
I know x/2 when x is even and -(x+1)/2 when x is odd represent natural numbers I just cannot turn this into odd numbers only.

when x is even the numbers I need are {2,6,10,14...}
when x is odd the numbers are {1,5,9,13...}

each are separated by 4 but when put together {1,2,5,6,9,10,13,14,...} I cannot find something that works like this.

2. Find an enumeration of the set of all rational numbers that have a terminating decimal representation.
(E.g. 17=10 = 1:7 and 17=8 = 2:125 are in this set, but 17=9 = 1:88888 : : : is
not.)
I'm not sure how to do this one

Originally Posted by gutnedawg

1. Find an enumeration of the set of all odd integers
I know x/2 when x is even and -(x+1)/2 when x is odd represent natural numbers I just cannot turn this into odd numbers only.

when x is even the numbers I need are {2,6,10,14...}
when x is odd the numbers are {1,5,9,13...}

each are separated by 4 but when put together {1,2,5,6,9,10,13,14,...} I cannot find something that works like this.

Do you know an enumeration for all integers?
Do you know a bijection from integers to odd integers?

Compose these two and you have an enumeration for odd integers.

2. Find an enumeration of the set of all rational numbers that have a terminating decimal representation.
(E.g. 17=10 = 1:7 and 17=8 = 2:125 are in this set, but 17=9 = 1:88888 : : : is
not.)
I'm not sure how to do this one

Do you know the enumeration for pairs of natural numbers ?
Find the bijection between paris of natural numbers and terminating decimals.
Again, compose

1. Find an enumeration of the set of all odd integers

Does this mean to find a surjection from to ? Does have to be an injection?

I know x/2 when x is even and -(x+1)/2 when x is odd represent natural numbers

I am not sure why you have - before (x+1)/2. The number -(x+1)/2 is not always natural when x is an odd integer, and it is never natural when x is an odd natural number.

when x is even the numbers I need are {2,6,10,14...}
when x is odd the numbers are {1,5,9,13...}

each are separated by 4 but when put together {1,2,5,6,9,10,13,14,...}

What does {1,2,5,6,9,10,13,14,...} have to do with odd integers, for which you need to find an enumeration? Why do you "need" {2,6,10,14...} and {1,5,9,13...}?

2. Find an enumeration of the set of all rational numbers that have a terminating decimal representation.
(E.g. 17=10 = 1:7 and 17=8 = 2:125 are in this set

It's pretty hard to understand this. 17 is not equal to 10 and neither is 10 to 1:7. Also, 1/7 gives a nonterminating decimal representation 0.142857142...

Hint from Wikipedia: "Terminating decimals represent rational numbers of the form ."

Originally Posted by snowtea

Do you know an enumeration for all integers?
Do you know a bijection from integers to odd integers?

Compose these two and you have an enumeration for odd integers.

I'm not sure how to enumerate the negative numbers. An enumeration for odd positive numbers would be 2x+1 correct?

Originally Posted by gutnedawg

I'm not sure how to enumerate the negative numbers. An enumeration for odd positive numbers would be 2x+1 correct?

That's correct. Composing as snowtea said will give the following enumeration:

1,-1,3,-3,5,-5,...

so how do I 'compose' the enumeration and bijection? The enumeration is x/2 if x is even and -(x+1)/2 if x is odd and the bijection is 2x+1... I just don't get how to describe the nth term of the enumeration

When you substitute x/2 into 2x+1, you get 2(x/2)+1=x+1. When you substitute -(x+1)/2 into 2x+1 you get 2[-(x+1)/2+1=-x-1+1=-x

ah ok this makes sense... so my nth term would be x+1 if x is even and -x if x is odd and this is the correct final answer yes?
Thanks

I do no know the enumeration for pairs of natural numbers so I'm somewhat stuck here.... I guess I need some further explanation

Yes - that's correct.


I think the idea behind the way to do the second one being suggested is the following:

You can think of any positive rational number that terminates as a.b where a and b are natural numbers. Now use snowpea's idea, together with the usual trick (as we've been discussing) to get the negatives as well.

(I don't remember off the top of my head an explicit bijection between natural numbers and pairs of natural numbers, but you should be able to find one easily with an internet search for "pairing function").

Be aware that these solutions are far from unique. There are lots of ways to do enumeration problems.


By the way, we've all been giving you hints to produce explicit functions that give bijections. It's not clear from the way you've written the questions that this is necessary. If you only have to "show the list" (as I did in my first post), then we can answer these questions much more quickly and easily.

so if I'm correct I should have some function f(x,y) = x.y ... or should it be (x/2).y when x is even and [-(x+1)/2].y when x is odd

Originally Posted by DrSteve

(I don't remember off the top of my head an explicit bijection between natural numbers and pairs of natural numbers, but you should be able to find one easily with an internet search for "pairing function").

Let defined by .
That is a bijection.
Easily extended to all rationals.

That's the idea but not quite. Your final function will be a function of one variable. The domain is the set of natural numbers and the range is a subset of the rational numbers. You're going to compose as follows:

.

The first is the pairing function. The second is the map where f is the function we've previously discussed, and the third is the map .

I am asked to find the enumeration but I have to specify the nth term of the enumeration

so is f(a) the a/2 if a is even and -(a+1)/2 if a is odd? Then how do I map these to a.b?

f(a).b