Results 1 to 4 of 4

Math Help - proving the set of finite decimals is countable

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    249

    proving the set of finite decimals is countable

    I need to prove that the set of finite decimals is countable. I know a set is countable if its cardinality is the same as that of the natural numbers which also means that there exists a bijective map between the set and the natural numbers. So as long as every element in the set is counted once and i have s systematic way of listing each member of the set it should prove that the set is countable, correct?

    Well, i am not sure if this "counts" as a systematic method of listing the finite decimals and thus proving that they are countable. So what i thought of was that since i know already that the set of integers is countable, i can list the set of integers + 1 decimal point, then the set of integers + 2 decimal points, and so on until i have listed every finite decimal. is this a valid "systematic way" of listing every finite decimal?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    There is a problem with your approach. Let Z be the integers, let Z_1 be the integers with one decomal appended, let Z_2 be the integers with two decimals appended and so on.

    I interpret your idea as giving the list

    0,1,-1,2,-2, [and the rest], 0.0,1.0,0.1, [and the rest of number from Z_1], and so on

    Did this make sense? So first you list _all_ the integers, then after this you list all elements from Z_1, etc. The problem with this is that it does not define a bijection onto the naturals. Indeed, the list would assign:

    0 -> 1
    1 -> 2
    -1 -> 3
    2 -> 4
    -2 -> 5
    ...

    in which you will use up all of the natural numbers with the integers alone - you will never get to Z_1, Z_2, etc.

    Anyway, there are more ways of approaching this problem. For example, you may know of a theorem, which says that if you have a countable collection of sets, each of which is countable, then their union is also countable. If you decide on using this theorem, you should of course argue carefully, why each Z_n is countable.

    You can also supply a bijection from the union of all the Z_n (including Z) to N by supplying a list, in which each element of the list corresponds to a natural number and vice versa. But let us only consider the positive numbers in Z and Z_n, because if we can find a bijection for this case, then we can just weave the corresponding negative numbers into the list.

    For example, let d(x) denote the number of digits of the number x (so d(7)=1 and d(7.123) = 4).

    Start out by listing all of the numbers x in the union of the Z_n including Z with the property that x + d(x) is at most 2.

    There is only one such number, namely x=1 (any number of two digits or more has d(x) greater than or equal to 2, and so x+d(x) is at least x+2, which is strictly greater than 2).

    Then list the finite set of numbers x, such that x+d(x) is at most 3.

    As before, three-digit numbers won't work here, because d(x)=3 for such an x. We do get one more one-digit number, namely x=2. And x=0.1, 0.2, 0.3, 0.4, ..., 0.9 also works.

    Then list the finite set of numbers x, such that x+d(x) is at most 4 (of course we don't include numbers, we have already listed). We get x=3, and x=1.1,1.2,...,1.9, and also x=0.01,0.02,0.03,...,0.09,[0.10 is already in the list],0.11,0.12,...,0,99.

    Continue in this way, where the general step is to list the finite set of numbers for which x+d(x) is at most n. Important question: Why are there only finitely many such numbers? When x+d(x) can be at most n, then the only numbers from Z that works are 1,2,...,n-1 (which is finitely many). Similarly only finitely many numbers from Z_1 works, and so on, all the way up to Z_{n-1}. Notice that Z_n has no numbers that work in this case.

    This was a very wordy description. I hope it makes sense, otherwise ask away.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    249
    thank you very much. the method you gave was clever and I can see how eventually it will hit all the finite decimals. I do know of the theorem that if you have a collection of sets that are countable then the union of those sets is also countable. However I am not completely sure how to carefully argue that each Z_n is countable. What I am thinking is that for each set for example take Z_1, list the numbers less than 1 with 1 decimal place, then less than 2 with 1 decimal place, and so on. then for Z_n, list the numbers less than 1 with n decimal places, then less than 2 with n decimal places, and so on. would this work?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    Yes, that would work perfectly.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finite, Countable, or Uncountable?
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: September 28th 2011, 04:29 PM
  2. Replies: 2
    Last Post: November 11th 2010, 05:56 AM
  3. Proving countable set
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 14th 2010, 02:29 PM
  4. Prove every subset of N is either finite or countable
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 1st 2009, 02:57 AM
  5. Replies: 11
    Last Post: October 11th 2008, 07:49 PM

Search Tags


/mathhelpforum @mathhelpforum