Results 1 to 10 of 10

Math Help - proofs about countable sets

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    proofs about countable sets

    Hello

    I have some questions about proofs presented while proving that some set is
    countable. In Velleman's "How to prove it" , author is trying to prove that there is
    a bijection from \mathbb{Z^+}\times \mathbb{Z^+} to
    \mathbb{Z^+}. He gives the arrangement as shown in the attached figure and then also gives the formula for that arrangement.

    f(i,j)=\frac{(i+j-2)(i+j-1)}{2}+i

    and then he asks the reader to show that the above function is indeed a bijection
    between the said sets. But I have seen the arguments where people just give the
    triangular arrangement as shown in the figure and argue that the arrangement is
    one to one and onto between \mathbb{Z^+}\times \mathbb{Z^+} to
    \mathbb{Z^+}. The wikipedia article on "countable set" has such arguments. My question is , are these valid arguments ? Velleman's way of reasoning seems more rigorous to me. We need to come up with some functional
    form of the given arrangement and then prove using usual methods that its a
    bijection. Please comment and move this thread to sub forum where its appropriate.

    Thanks
    Attached Thumbnails Attached Thumbnails proofs about countable sets-1.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: proofs about countable sets

    Quote Originally Posted by issacnewton View Post
    Hello

    I have some questions about proofs presented while proving that some set is
    countable. In Velleman's "How to prove it" , author is trying to prove that there is
    a bijection from \mathbb{Z^+}\times \mathbb{Z^+} to
    \mathbb{Z^+}. He gives the arrangement as shown in the attached figure and then also gives the formula for that arrangement.

    f(i,j)=\frac{(i+j-2)(i+j-1)}{2}+i

    and then he asks the reader to show that the above function is indeed a bijection
    between the said sets. But I have seen the arguments where people just give the
    triangular arrangement as shown in the figure and argue that the arrangement is
    one to one and onto between \mathbb{Z^+}\times \mathbb{Z^+} to
    \mathbb{Z^+}. The wikipedia article on "countable set" has such arguments. My question is , are these valid arguments ? Velleman's way of reasoning seems more rigorous to me. We need to come up with some functional
    form of the given arrangement and then prove using usual methods that its a
    bijection. Please comment and move this thread to sub forum where its appropriate.

    Thanks
    It depends on what you think a proof is. Virtually no proof you will have seen is rigorous in the sense that it is machine verifiable.

    If you think an proof is a argument that would convince nearly all mathematicians (in the sense that they would believe they could construct a proof that would satisfy their standard of proof using the idea) then the diagram in figure 2 might well suffice (though there will always be some who disagree).

    That is; most proofs are informal on some level, what is an acceptable level varies between contexts and individuals.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: proofs about countable sets

    So is there no standard of what proof is ? I do find the argument using that arrangement in Fig 2 convincing but are there mathematicians who refuse to accept it ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: proofs about countable sets

    Are mathematicians supposed to come up with machine verifiable proofs ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: proofs about countable sets

    Quote Originally Posted by issacnewton View Post
    Are mathematicians supposed to come up with machine verifiable proofs ?
    Absolutely not
    I have followed all of these posts.
    I have looked into the Velleman text.
    I must tell you that after teaching the foundations text material for more that thirty years, that text is the poorest I have ever reviewed( that is more the fifty in print)
    Look at that function that you posted, Velleman is a sadist.
    There are two standard ways of doing the question.
    1) Let \Phi(m,n)=2^{m-1}(2n+1) can be shown to be a bijection.
    OR
    2) Notice that \Phi(m,n)=2^m\cdot 3^n is a injection.

    DO NOT, make more of a problem that is called for!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: proofs about countable sets

    The last chapter (chapter 7) in Velleman's "How to prove it" is pretty difficult for someone (that's me )who has done every single problem in first 6 chapters. He should make the transition more smooth.

    Plato, thanks for the input. Since you have reviewed so many foundational texts, which one would you suggest after I finish Velleman's "How to prove it".
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,373
    Thanks
    1314

    Re: proofs about countable sets

    In regard to this specific proof, what Velleman does is show that there is a bijection from Z^+\times Z^+ to an infinite subset of Z^+ rather than getting a bijection to Z^+ itself. However, since every infinite subset of Z^+ is countable, that is sufficient to show that Z^+\times Z^+ is countable.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: proofs about countable sets

    Quote Originally Posted by HallsofIvy View Post
    In regard to this specific proof, what Velleman does is show that there is a bijection from Z^+\times Z^+ to an infinite subset of Z^+ rather than getting a bijection to Z^+ itself.
    Well, I think he is showing the bijection from \mathbb{Z^+} \times \mathbb{Z^+} to \mathbb{Z^+} if we look at the Fig 2 and the function given.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: proofs about countable sets

    Quote Originally Posted by issacnewton View Post
    So is there no standard of what proof is ?
    Yes, there is. Mathematical logic gives a precise definition of a proof. Such definitions have been implemented on computers, and one can construct a completely formal proof of the fact above where every inference rule is verified by the computer.

    People, though, have very powerful intuition when it comes to finite sets and sequences of objects. Relying on it is often more convincing than on written formulas. After a certain point, too much detail makes a proof more difficult to understand.

    The level of details appropriate in a proof depends on the area and audience: e.g., textbooks have to be much more detailed than conference articles.

    Quote Originally Posted by issacnewton
    Are mathematicians supposed to come up with machine verifiable proofs?
    Absolutely yes! I am somewhat kidding, but the dream of the formal methods community is to reduce the difficulty of proof formalization (the possibility to formalize any proof is already there). Even though explaining a proof to a computer will probably generally remain more difficult than writing a paper proof, the hope is that mathematicians will want to formalize their proofs to avoid errors and get help with difficult calculations, and conference program committees will encourage formalized submissions to cut time on checking.

    By the way, to understand the relationship between the formula and the figure in the OP you may consider this thread.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: proofs about countable sets

    emakarov,

    In Velleman's book, in the earlier chapters, he asks readers to present proofs
    using some software which is there on his website. These proofs are regarding set theorems , so they are easy to put in formal language. And its good that there
    are efforts going on to make formalized proofs easier, as that will definitely save lot of
    time .............

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  3. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  4. Replies: 11
    Last Post: October 11th 2008, 06:49 PM
  5. are these sets countable
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2008, 05:50 PM

Search Tags


/mathhelpforum @mathhelpforum