infinity, and the confusion it is causing me

Discussion in 'Physics & Math' started by hockeywings, Feb 19, 2005.

  1. hockeywings Don't dance without music Registered Senior Member

    Messages:
    132
    Alright, I do not know too much about this area of math but I am taking a course in philosophy and discrete math and it was introduced to me and it caught my attention.

    First off, I am confused about how the set of integers and set of even numbers can have the same amount of elements. He explained it is because they can be set up as a one to one correspondence.

    I got to thinking of this and thought. if you set up the correspondence as 2 to 2 4 to 4 and so on, then there will not be a one to one, because 1 will not be used as any other odd number, isnt that a contradiction?

    Another way i thought about it was

    a=all positive integers
    b=all positive even integers
    a has the same elements as b
    a - (all numbers greater than 20)
    b - (all numbers greater than 20)
    all numbers greater than 20 in set a and all numbers greater than 20 in set b have the same amount of elements.
    if you subtract the same number from 2 sets which have the same number of elements themselves they should yield the same answer
    but after the subtraction set a has 20 elements, 1, 2, 3, ... 20
    and set b has 10 elements, 2, 4, 6, ... 20
    isnt this another contradiction?

    one last thing that confuses me.
    how is there more decimals than integers?
    the teachers barely touched on this but as i understand it they said you set up a one to one and then they show you a decimal that is not on the list such as change digit one to one greater, two to one greater, three to one greater and so on and so forth creating a new number. but my problem with this is that you could do the same for the integers creating the one to one again.

    If anyone could help me with these problems it would be much appriciated, it has been boggling my mind for so long now, it is all i can think of lol.
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. oxymoron Registered Senior Member

    Messages:
    454
    This should be failry simple to explain.

    First let E be the set of even integers and Z the set of all integers. Then I propose that the cardinality (size) of E is the same as the cardinality of Z.

    Proof.

    We say that E and Z have the same cardinality if there is a bijection from E to Z. Do you know what a bijection is? If not, it means that there is a function from E to Z that is one to one and onto (or injective and surjective). So it makes sense that if I propose that E and Z have the same cardinality then it will suffice to show that there is a bijection (a function that is 1-1 and onto) from E to Z.

    Let f(n) = 2n with domain Z and range A, where n is an element of Z (an integer).

    Remember that E is the set of even integers and Z is the set of all integers.

    1-1
    Choose any integer n. Then f(n) = 2n is in E. Say I pick n = 7. Then 2(7) = 14 which is an even integer. No matter what integer I pick I always get an even integer back.

    Onto
    The function f(n) = 2n is onto if every even integer is the image of some integer. That is, if f(n) maps Z onto the whole set E.

    It should be easy to see that f(n) = 2n is onto because every even integer is the image of any integer under the mapping. That is, using the function f(n) = 2n we can generate every element of E (every even integer) just from using elements from Z.


    This says that there are the same number of even integers as there are integers. This does seem counter-intuitive but you must remember that we are considering set with an infinite number of elements. And when dealing with infinity, you can expect counter-intuitive things to happen.

    Here is an analogy.

    Say you wanted to know if there was the same number of even integers as integers. One way to do this would be to count them all and compare the totals. However, we cannot do this since it would take forever to get a final total. One way which does work, would be to take an integer and match it to an even integer.
    1 matches to 2
    2 matches to 4
    3 matches to 6
    4 matches to 8
    No matter how far you went you would come to the same conclusion: That there are the same number of integers as even integers. Notice that this list is generated by the funtion f(n) = 2n. If you kept going
    100 matches to 200
    .
    .
    .
    1000 matches to 2000
    .
    .
    .
    You would never get to a stage where you would have more integers than even integers. ie
    xxxxx has no match
    If this were the case then there would be more integers than even integers.


    Since every integer maps to an even integer (one to one) and every even integer is the image of an integer (onto) then there are the same amount.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. hockeywings Don't dance without music Registered Senior Member

    Messages:
    132
    yes sir, that is how he explained it. But i still dont understand why it would not be a contradiction if you mapped it out with 2 to 2, 4 to 4 and so on. leaving one of the sets with the odd numbers left behind making it not bijectional.

    And also the subtraction contradiction.

    If you could address how to reconcile these it would be much appreciated
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Data Registered Senior Member

    Messages:
    81
    Well, you have to understand that in mathematics the notion of size of sets is defined by saying that the size (<=> cardinality) of set A is the same as the size of set B if and only if there exists a bijection from the elements of A to the elements of B.

    As a result of this definition, when dealing with infinite sets, we do indeed lose some natural results, like the subtraction that you mentioned. But the definition is convenient in many, many other ways.

    As to your first concern, the fact that you can find a function between the sets that is not a bijection is irrelevant. It only matters that it is possible to find at least one bijection.

    For example, any two rings with more than one element, R and R' (look up what a ring means in math if you don't know!), have a function between them that's not a bijection: f(r) = 0 for any r in R and for the 0 element in R'. This doesn't mean that no rings with more than one element have the same number of elements.
     
    Last edited: Feb 19, 2005
  8. Data Registered Senior Member

    Messages:
    81
    And I will note that your function as defined is not from the integers to the even integers. It is from the even integers to the even integers. In order to fix it, you must define what f(n) where n is odd means, even if it's just equal to 0 for every such n.
     
  9. hockeywings Don't dance without music Registered Senior Member

    Messages:
    132
    alright so if i understand this right, as long as it is possible, but not neccesarily true in all understandings, to make a bijection then they have the same amount of elements?

    then how do the decimals outnumber the integers?
     
  10. Data Registered Senior Member

    Messages:
    81
    I have to go, so I'll post something more detailed later. First, we have to be clear about what "decimals" mean:

    As a matter of fact, the rational numbers, Q, do have the same cardinality as the integers. Even the algebraic numbers, A, have this same cardinality (these are all the real numbers that are solutions to polynomial equations with rational coefficients, so they include all square roots, cube roots, etc). Even the set of computable numbers has this cardinality, that is, the set of all real numbers for which some (probably unknown) algorithm exists to calculate the decimal expansion of said number (this set includes all the algebraic numbers, as well as many transcendental (non-algebraic) numbers, such as the well-known constants pi and e).

    On the other hand, the set of all real numbers does not have the same cardinality. Like I said I have to go now, but hopefully I've gotten some of your curiosity so you'll come back to read my reply later

    Please Register or Log in to view the hidden image!

     
    Last edited: Feb 19, 2005
  11. oxymoron Registered Senior Member

    Messages:
    454
    This is not a function that maps the integers to the even integers (as data said). Since it is not a function how can it be bijectional? => You can't use an argument such as this as a contradiction.
     
  12. Data Registered Senior Member

    Messages:
    81
    Okay, back. We want to show that the real numbers can't be put into one-to-one correspondence with the positive integers (Z+). The only apparent path is to prove it by contradiction, because we don't have any results to help us, and we can't very well consider every function and show that each one isn't a bijection!

    First, let's agree that there are more (or at the very least, as many) real numbers than there are real numbers between 0 and 1, and so we can consider the real numbers between 0 and 1 alone for our proof. Assume that we can find a bijection f from the positive integers to the real numbers between 0 and 1. We can then write

    f(1) = 0.a11 a12 a13 a14 a15...
    f(2) = 0.a21 a22 a23 a24 a25...
    f(3) = 0.a31 a32 a33 a34 a35...
    ...

    where aij is just an integer between 0 and 9 and 0.c1 c2 c3... just means the real number with decimal expansions having the digits c1 c2 c3 etc.

    We now need to get a contradiction. We'll achieve it by simply constructing a real number between 0 and 1 that is not equal to f(n) for any integer n. Let S = {x| x is in Z and 0<=x<=9}. Clearly aij is in S for every i and j.

    Now, choose b1 such that b1 != a11 and b1 is in S. Similarly, choose b2 such that b2 != a22 and b2 is in S. Inductively, choose bn such that bn != ann and bn is in S. Let b = 0.b1 b2 b3 b4 b5...

    Clearly, b cannot be f(n) for any n because b1 != a11, b2 != a22, b3 != a33,... (ie. at least one digit differs between b and f(n) for any n). But 0 < b < 1, and b is a real number. This is a contradiction to f being onto (surjective), and thus there is no such bijection between the integers and the real numbers between 0 and 1.
     
    Last edited: Feb 20, 2005
  13. mikasa11 Registered Senior Member

    Messages:
    258
    It is philosophy, it is supposed to boggle your mind. Of course they contradict, because that is what philosophy is.

    As for the decimal question it is realitively simple. 1 is only one integer, but it has many decimals. It can be 1.1, 1.2, 1.11, 1.2242332532 and so fourth. Now you take another interger you have the same thing. So for every interger there are many decimals.
     
  14. Data Registered Senior Member

    Messages:
    81
    Actually, it's not nearly so simple. There are equally many rational numbers (ie. all those with a repeating pattern starting at some point in their decimal representation, or equivalently, all those that can be represented in the form a/b where a and b are integers) as there are integers, as previously stated. Here is a proof of this fact: http://www.math.utah.edu/~alfeld/math/sets/countablesproof.html

    As I said above, there are other sets which include the rational numbers as a subset that also have the same number of elements (the algebraics, or, even more generally, the computable numbers).
     
  15. hockeywings Don't dance without music Registered Senior Member

    Messages:
    132
    so changing the first digit of the decimal one, second of decimal two and so on? why couldnt you do that to the integers also, showing that you didnt show all of the integers?
    let d1 be the first digit d2 be the second digit ... of the integers

    so .a11b22c33 matches up with (d1+1)(d2+1)(d3+1) and so on and so forth making that integer (i do not mean multiply the digits there i meant to construct a number with the digits d1+1, d2 +1 and so on)
     
  16. hockeywings Don't dance without music Registered Senior Member

    Messages:
    132
    man, that still seems so contradictory though, if you have two sets that are equal, then add anything to them thjey should not be equal. ie. 2 sets of the even numbers, obviously identical, then adding the odd numbers to one set should make that one more numourous.

    I dont know though i guess i am just being stubborn with this
     
  17. Data Registered Senior Member

    Messages:
    81
    The same argument that I used for the reals doesn't work for the integers because each integer has a finite number of digits, and we don't know how many there are in a particular integer.

    Like I said, you lose some natural properties as a result of this definition. But you have to remember that these are infinite sets. Can you explain to me why there should be more integers than there are even integers?

    Anyways, be careful. Noone is saying that the integers are equal to the even integers! They just have the same cardinality

    Please Register or Log in to view the hidden image!

     
  18. AndersHermansson Registered Senior Member

    Messages:
    334
    Does the same argument apply to intervals of real numbers?
     
  19. hockeywings Don't dance without music Registered Senior Member

    Messages:
    132
    integers and decimals are both finite or infinite length. just add however many zeros infront of the integer. same with adding zeros at the end of the decimal.
     
  20. mikasa11 Registered Senior Member

    Messages:
    258
    But if they are both supposed to be infinite than how can one be more than the other?

    I see your thought process but if they can both go on forever then they both should be the same amount (Considering that theoretically their is no end.)

    I'll indulge briefly in some philosphy to use it as an example......

    According to a few certain philosophers the universe was and always will have an infinite end no matter where you go and have an infinite amount of matter in it. According to succesion a very minute amount of soil can be turned into a giant forest after a great deal of time.

    Now if there was the infinite amount of soil....(which would be the integers.)
    and the infinite amount of forests from the soil....(the decimals....*i.e bush's could be the decimal 1.1, 1.11 could be a type of bush that's rounded, 1.111 could be a rounded bush that has a thorny inside.*)

    decimals are just a way of categorizing certain integers.

    And this leads us back to the same question....How are there more decimals than whole numbers if they're both infinite.
     
  21. Data Registered Senior Member

    Messages:
    81
    Alright, let's give it a try. For the purposes of this exercise I will write an integer

    m = a1 a2 a3 ... an

    where a1 a2 a3 ... are just the digits of the integer in the following way:

    m = a1 a2 a3 ... an = an ... a2 a1 000...

    ie. reverse the order of the digits and put an infinite string of zeros after the last one.

    So here are some examples of our new type of representation for integers, standard rep. on the left and new rep. on the right

    1 = 1000...
    2 = 2000...
    3 = 3000...
    10 = 01000...
    25 = 52000...
    etc.

    One important thing to note before we proceed, is that under our new notation, every integer must end with an infinite string of zeros.

    So, we propose that a function f is a bijection from Z+->Z+ and write

    f(1) = a11 a12 a13 a14 ... a1(n1) 000...
    f(2) = a21 a22 a23 a24 ... a2(n2) 000...
    f(3) = a31 a32 a33 a34 ... a3(n3) 000...
    ...

    And let cnm represent the mth digit of f(n).

    And we try to construct a real number that isn't f(n) for any integer n, using a similar method to that which I used for the real numbers.

    We then take b1 != c11, b1 in S (where S has the same definition as before), b2 != c22, b2 in S, and inductively bn != cnn and bn in S. Clearly b = b1 b2 b3 b4 ... bn ... is not f(n) for any n, by the same reasoning as I used for the b in my proof for the reals.

    Now, all we need is to see whether b = b1 b2 b3 b4 ... bn ... fits the criterion needed for b to be an integer under our new notation. You may guess that the answer is no. Why? Let's consider it.

    In order for b to be a positive integer under our notation, it must have an infinite trailing string of zeros, ie. there exists some N such that bn = 0 for every n>N. We should then be able to write

    b = b1 b2 b3 ... bN 000...

    Does this work? Let's assume that it does. Recall that the only criteria we had when we chose the bi were that bi != cii and bi is an integer between 0 and 9. Then, if bn = 0 for every n>N, we need ann != 0 for every n>N. But in order to ensure this we would need to place restrictions on our function f, and we can certainly construct a function such that this isn't true, for example, if for t = d1 d2 d3 ... dq 000... in our new notation, if we just let

    f(t) = t = d1 d2 d3 ... dq 000...

    then clearly cnn = 0 for every n!=1. For this function, our constructed b would not be an integer because it wouldn't have a terminating sequence of zeros.

    Therefore, we can't use our constructed "integer" to say anything about whether or not there's a bijection from the positive integers to the positive integers.

    The best we can do is say that it's possible to construct a function which isn't a bijection, but that's not useful for our purposes (and it is, in fact, one of your original objections! It's still irrelevant as to the question at hand, though).

    For similar reasons, the argument can't be applied to say that the rationals don't have a bijection with the integers (because they either have finite numbers of digits or repeating patterns - the argument requires slight adjustment for the latter case but it is essentially the same).
     
    Last edited: Feb 21, 2005
  22. shmoe Registred User Registered Senior Member

    Messages:
    524
    All (non-trivial) intervals of the real numbers have the same cardinality. Consider (a,b) and (c,d) where a, b, c, and d are finite, a not equal to b and c not equal to d. Define f from (a,b)->(c,d) by f(x)=d(x-a)/(b-a)-c(x-b)/(b-a). This is a bijection.

    For a finite interval, (0,1) to an infinite one, say, (a,infinity) consider f(x)=a/x.

    For a finite interval (0,1) to (-infinity, infinity), consider f(x)=1/x+1/(x-1).

    Compositions of the above show that all open intervals have the same cardinality. Adding one, two (or actually any finite number) of elements to an infinite set doesn't affect it's cardinality, so all real intervals (allowing closed and "half-open" intervals now) have the same cardinality.


    To echo Data, be careful when dealing with the infinite. Remember we are measuring the cardinality of sets based on the definition we've given involving bijections, something which allows for different 'sizes of infinite'. This may lead to something very counterintuative depending on your intuition! You can't expect infinite sets to behave like finite ones.
     
  23. AndersHermansson Registered Senior Member

    Messages:
    334
    Then any interval and the real line is one-to-one?
    If that is the case maybe the real line already contains infinitesimals without extending it with the hyperreals.

    Let A=[0, 1] and a in R. Because I has the same cardinality as the real line (R) there exist a bijection from R to A (There is one from A to R, and bijections are invertible). Then a are mapped onto a number in A, nonzero, yet infinitely small.
     

Share This Page