Results 1 to 7 of 7

Math Help - checking proof that no natural number can be both even and odd

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

    checking proof that no natural number can be both even and odd

    Hi

    I am here after a long time. I want to prove that no natural number can be both even and odd. This is from basic analysis book. So I start by saying that let S be the set of natural numbers such that they are both even and odd.

     S=\{ n\in \mathbb{N}| \mbox{ n is even and n is odd} \}

    I assume the negation. So let S be non-empty. Since S is a subset of \mathbb{N}, by well ordering principle, S has a least element k. So
    k is both odd and even. k = 2m and k = 2n-1 for some m,n \in \mathbb{N}. Which means 2m = 2n-1.
    \Rightarrow 2(m-n)=1. Which means that 1 is an even number. At this point can I say that I have reached a contradiction. Or do I first need
    to prove that 1 is an odd number to use that property ?

    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1

    Re: checking proof that no natural number can be both even and odd

    Quote Originally Posted by issacnewton View Post
    Hi

    I am here after a long time. I want to prove that no natural number can be both even and odd. This is from basic analysis book. So I start by saying that let S be the set of natural numbers such that they are both even and odd.

     S=\{ n\in \mathbb{N}| \mbox{ n is even and n is odd} \}

    I assume the negation. So let S be non-empty. Since S is a subset of \mathbb{N}, by well ordering principle, S has a least element k. So
    k is both odd and even. k = 2m and k = 2n-1 for some m,n \in \mathbb{N}. Which means 2m = 2n-1.
    \Rightarrow 2(m-n)=1. Which means that 1 is an even number. At this point can I say that I have reached a contradiction. Or do I first need to prove tthathat 1 is an odd number to use that property
    How do you know that 1\notin S~?
    Follow Math Help Forum on Facebook and Google+

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

    Re: checking proof that no natural number can be both even and odd

    Good Afternoon Plato,

    Yes, I don't know if 1\notin S. I think this problem could be done with induction. But I want to stick with well-ordering principle just for the fun. So would you suggest an alternative ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466

    Re: checking proof that no natural number can be both even and odd

    Are you saying that you do not know whether or not 1 is even? I'll give you hint- 1 is NOT even!

    But you don't need either "induction" or "well ordering". Just use an indirect proof. Suppose there exist integer, x, that is both even and odd.
    Since x is even, x= 2m for some integer m. Since x is odd, x= 2n- 1 for some integer n.
    Then x= 2m= 2n- 1. 2n- 2m= 2(n- m)= 1. n- m= 1/2. Do you see why that is a contradiction?
    Last edited by HallsofIvy; April 4th 2013 at 05:06 AM.
    Follow Math Help Forum on Facebook and Google+

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

    Re: checking proof that no natural number can be both even and odd

    Hello HallsofIvy,

    At that point, I can say that subtraction of two integers is an integer, so we reach a contradiction. But I was wondering about my original post. So is my approach correct ?.
    1 is ODD, and I did reach a contradiction. Am I right ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778

    Re: checking proof that no natural number can be both even and odd

    Quote Originally Posted by issacnewton View Post
    But I was wondering about my original post. So is my approach correct ?
    The biggest remark about the OP is that it is not necessary to use the well-ordering principle. You never use the fact that k is the least element of S, just that it is some element of S.

    Quote Originally Posted by issacnewton View Post
    1 is ODD, and I did reach a contradiction. Am I right ?
    Yes. Proving that 1 is odd, if this is necessary, is trivial for normal people: if 1 = 2n for an integer n, then n = 1/2, and 1/2 is not an integer. I said for normal people because a pedant may ask why 1/2 is not an integer. Then we need some definition or axiomatization of integers to rely on. In Peano arithmetic, for example, the fact that 2n ≠ 1 for all n is proved by induction, though the induction hypothesis is not used.
    Follow Math Help Forum on Facebook and Google+

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

    Re: checking proof that no natural number can be both even and odd

    emakarov

    That is a good explanation. I see that I never used the least element of S. I will try to come up with some other argument for this.

    thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Natural Number
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 30th 2012, 01:04 PM
  2. Proof for every Natural number
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: March 16th 2012, 07:02 AM
  3. Proof Checking Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 22nd 2009, 12:24 AM
  4. [SOLVED] Proof: uniqueness of a natural number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2009, 08:57 PM
  5. Truth table Prime Number Checking
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 21st 2008, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum