Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member genius
    Wayward Soul
    28 Aug '03 20:19
    how many numbers are there between 1 and 0? infinity? how many intergers are there between 1 and infinity? infinity? how many numbers-taken to infinite decimal places are there between 1 and infinity? infinity? but this is greater than the infinity between 1 and 0, and the infinity of intergers! how can this be?...
  2. 28 Aug '03 21:16
    The number of numbers (with infinite decimal places, also called real numbers) betweeen 1 and infinity is the same as the number of numbers between 0 and 1, but greater than the number of integers!

    Infinity behaves strangely.

    Did you know, for instance, that there are the same number of integers as even integers? You can match the integers one-to-one with the even integers ( 1->2, 2->4, 3->6, ... ) You can also match each number x between 1 and infinity with a number 1/x between 0 and 1. Since one-to-one matching is the fundamental basis for counting, this means that according the mathematical (and indeed usual) definition of 'same number', at least two of my bizarre statements are indeed true.

    You can also match up the integers to the rational numbers (numbers that can be written as N/M where N and M are integers), so the infinite sizes of those two sets are the same. However, the size of the set of all real numbers (reals that aren't rationals include pi and the square roots of all numbers that aren't perfect squares) is larger (more infinite) than the size of the set of integers. Proving that this is so is one of the more interesting things you do near the beginning of a mathematics degree course. Sadly, that was too long ago for me to remember how 'tis done.

    ry
  3. Donation bbarr
    Chief Justice
    29 Aug '03 02:29
    This is my version of Cantor's proof, its form is that of an indirect
    proof, or a reductio of the claim that the set of real numbers is the
    same size as the set of natural numbers. I posted this awhile back, but it has come up again in this forum, so what the hell?

    1. For any set X and any set Y, X and Y are of the same size if and
    only if the elements of X bear a one-to-one correspondance with the
    elements of Y. (This is assumed by Cantor, but seems pretty
    intuitive. If I want to know whether the number of students in my
    room equals the number of chairs, I tell everyone to sit down and see
    what's left over. That is, I try to establish a one-to-one
    correspondance between students and chairs.)

    2. For any set X and any set Y, the elements of X and the elements
    of Y bear a one-to-one correspondance with each other if and only if
    both X and Y are denumerable.

    3. For any set X, X is denumerable if and only if (1) the elements of
    N can be arranged into a list with a first member, second
    member,...,nth member and (2) each element of X is quaranteed a
    definite unique position on the list.

    4. The set of natural numbers N is denumerable (The natural
    numbers are 0, 1, 2, etc. no negative numbers, no fractions with
    denominators other than 1.)

    5. Suppose the set R of real numbers in the interval from 0 to 1 is
    denumerable. [Real numbers are those that start with a decimal and
    go on forever to the right of the decimal. Among the real numbers
    are (1) the rational numbers (that repeat some digit or string of digits
    infinitely) and (2) the irrational numbers (that have no infinitely
    repeating pattern). .499999....is rational, in fact, it's equal to .5. The
    decimal expansion of pi is irrational.]

    6. If so, then the elements of R can be arranged in a list with a first
    member, second member,..., nth member, and each element of R will
    be guaranteed a definite unique position on the list. (This follows
    from our 3 and 5).

    7. Let L be the list of the elements of R. Let each element of R be a
    decimal point followed by an infinite string of digits. We can represent
    each element of R in the following fashion: Where B is some digit in
    some element E of R, let x be the ordinal position of B in the string of
    digits that constitute E; let y be the oridinal postiion of E in L. Then,
    the ordered pair (x,y) specifies a definite unique location within L for
    any particular B. Thus, B(x,y) picks out a definite unigue digit within L.

    8. Suppose we apply the following procedure: Beginning at B(1,1),
    followed by B(2,2)....B(n,n), for any B(x,y) if B(x,y) is the digit '1',
    change it to '2'. If B(x,y) is any digit other than '1', change it to '1'.
    The resultant string of digits, B(1,), B(2,2)....B(n,n), subsequent to
    our procedure, is the Diagonal of L.

    9. The Diagonal of L will itself be a real number within the interval
    from 0 to 1, and thus will be an element of R. But the procedure
    above guarantees that the Diagonal of L will not itself appear as an
    entry of L, because for any entry (e.g., the nth entry) in L the
    Diagonal of L will have some digit (the nthe digit) that differs from the
    digit found in the entry in L.

    10. Thus, if R is denumerable, then any list of the elements of R will
    necessarily by incomplete (it will not contain its diagonal). But this
    contradicts 6, so R must not be denumerable. (Any assumption that
    leads to a contradiction is rejected and the assumption's negation is
    adopted)

    11. But if R is not denumerable, then the elements of R cannot be
    put in a one-to-one correspondence with the the elements of N.

    12. Thus the sets R and N are not of the same size.

    So Cantor shows us that not all infinite sets are the same size, but he
    assumes that all denumeralbe sets are of the same size. This
    assumption already may do violence to your metaphysical intuitions,
    because you may think that the set of even numbers is roughly half
    as big as the set of natural numbers. I admit to finding this view
    persuasive, but imagine you have two perfect random number
    generators. The first generator is set up so that it only produces an
    even number when operated. The second can produce any of the
    natural numbers when operated. Each operation yields just one
    number from each machine. If the set of evens is half as big as the
    set of naturals, then it ought to be twice as likely getting a '2' from
    the first machine than from the second. But each machine picks their
    numbers completely at random and both have an infinite number of
    choices. So the probability of getting a '2' on either should be
    1/infinity. At this point my intuitions become silent and I begin to
    drink beer.
  4. Standard member Phlabibit
    Mystic Meg
    29 Aug '03 03:03
    Originally posted by bbarr
    This is my version of Cantor's proof, its form is that of an indirect
    proof, or a reductio of the claim that the set of real numbers is the
    same size as the set of natural numbers. I posted this awhile back, but it has come up again in this forum, so what the hell?

    1. For any set X and any set Y, X and Y are of the same size if and
    only if the elemen ...[text shortened]... hould be
    1/infinity. At this point my intuitions become silent and I begin to
    drink beer.
    Infinity is so vast, that it can be broken up into an infinite number of infinities.

    That is the way it works.
  5. Standard member Fiathahel
    Artist in Drawing
    29 Aug '03 11:45
    Originally posted by Phlabibit
    Infinity is so vast, that it can be broken up into an infinite number of infinities.

    That is the way it works.
    an example of the divisibility of a set with an infinite number of elements into sets with an infinite number of elements:

    If you take the sets {p^n|n an integer} for every prime p then you have an infinite number of elements which are disjunct, have an infinite number elements and there union is a subset of the integers.
    There are even still many elements left, like 2*3^n for all n.
  6. 29 Aug '03 11:47 / 1 edit
    Originally posted by bbarr
    This is my version of Cantor's proof, its form is that of an indirect
    proof, or a reductio of the claim that the set of real numbers is the
    same size as the set of natural numbers. I posted this awhile back, but it has come up again in t ...[text shortened]... point my intuitions become silent and I begin to
    drink beer.

    "At this point my intuitions become silent and I begin to
    drink beer." bbarr.

    That's a very good start !

    Gezondheid ! Cheers !

    IvanH.
  7. Standard member Fiathahel
    Artist in Drawing
    29 Aug '03 12:08
    every power set has a higher degree of infinite number of elements then the original.
    (a power set of A is the set of all subsets of A)

    Proof:
    if they are of the same degree of infinity there is an injection f from A to P(A). Then consider the set Q:={a in A| a not in f(a)} then there isn't an element b in A with f(b) = Q, cause if there is a b,
    then, if b is in Q, then, by definition of Q, b is not in f(b) = Q and if b is not in Q, then, by definition of Q, b is in f(b) = Q.
    So such an injection does not exist.
  8. Standard member TheMaster37
    Kupikupopo!
    29 Aug '03 14:02
    The set of positive integers is just as big as the set of positive and negative integers:

    0 -> 0, 1 -> 1, 2 -> -1, 3 -> 2, 4 -> -2 and so on

    But the set of all fractions (including all integers) has jsut as much elements as well!

    0 -> 0, 1 -> 1, 2 -> -1, 3 -> 2, 4 -> 3/2, 5 -> 1/2, 6 -> -1/2, 7 -> -3/2, 8 -> -2, 9 -> 3, 10 -> 8/3...and so on
  9. 06 Jun '04 16:14 / 1 edit
    Suppose there is an infinite number of small balls, all of which have been uniquely numbered from 1 upwards. Furthermore, you have an infinitely large bucket. That is to say, it can be made as large as necessary. You decide to fill the bucket by throwing in all the balls, in order. Starting from 1, every minute you throw in two balls. But every minute, an imp takes one ball back out, always extracting the lowest-numbered ball in the bucket.

    For example,

    1st minute: You throw in Ball 1 and Ball 2.
    Imp extracts Ball 1.

    2nd minute: You throw in Ball 3 and Ball 4.
    Imp extracts Ball 2.

    3rd minute: You throw in Ball 5 and Ball 6.
    Impish sprite extracts Ball 3.

    and so on...


    QUESTION: After an infinite amount of time has elapsed, how many balls are in the bucket?

    Argument 1: There is an infinite number of balls in the bucket. After 1 minute there is 1 ball. After 2 minutes there are 2 balls. After 3 minutes there are 3 balls, etc.

    Argument 2: There are no balls in the bucket. If there are some balls in the bucket, what is the number of the lowest-numbered ball? It can't be Ball 1; that was extracted after 1 minute. Similarly, it can't be Ball 2; that was extracted after 2 minutes. It can't be Ball 3; that was extracted after 3 minutes, etc.

    (If the phrase 'after an infinite amount of time has elapsed' bothers you, then we can change the problem so that the 1st put-in-and-take-out operation is completed in 1/2 minute, the 2nd operation is completed in 1/4 minute, the 3rd in 1/8 minute, and so on. Now you can ask the question after 60 seconds, and "infinite time" is not longer an issue.)
  10. Standard member TheMaster37
    Kupikupopo!
    06 Jun '04 16:47
    You never get to look how many balls are in the bucket, for that requires a time AFTER an infinite time. Supposing We're not doing Axiomatic Settheory of course.

    You'll always be busy with putting in and taking out balls, so the question how many balls are in the bucket after you're done is irrelevant when you speak of an infinite amount of time.

    And seeing as you have to put in balls faster and faster in the other case, i'd figure the person doing so will explode before the end of the minute, making it a finite case.
  11. 06 Jun '04 17:08
    As there is no infinite time or buckets or balls, we can consider the problem as a purely mathematical puzzle.
  12. Standard member TheMaster37
    Kupikupopo!
    06 Jun '04 17:30
    For that, there IS an infinite amount of balls in the bucket. On moment 1 you have one ball in the bucket, on moment 2 two balls and so on. Sadly we cannot determine wich balls are in the bucket, for any number you call out is taken out after that amount of minutes.
  13. 06 Jun '04 19:23 / 4 edits
    Originally posted by TheMaster37
    Sadly we cannot determine wich balls are in the bucket, for any number you call out is taken out after that amount of minutes.
    There must therefore be NO balls in the bucket at the end.

    Isn't your argument based solely upon the following non sequitur

    LIMf(x) = b IMPLIES f(a) = b?
    x->a

    .