Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Little Proof

  1. Jun 23, 2010 #1
    Hi I'm reading this great book Foundations of Analysis by Edmund Landau, a really old book that aims to build the foundations of analysis from basic arithmetic.

    I'm not that strong on proofing yet but am trying, here is my problem.

    Using these 5 axioms for the Natural numbers;

    [tex] I) \ 1 \in \mathbb{N}[/tex]

    [tex]II) \ \forall \ x \ \exists \ x' \ : x' \ = \ x \ + \ 1[/tex]

    [tex]III) \ x' \ \neq \ 1[/tex]

    [tex]IV) \ if \ x' \ = \ y' \ then \ x \ = \ y[/tex]

    [tex]V) \ \exists \ \mathbb{R} \ : \ \mathbb{N} \ \subset \ \mathbb{R} \ , \ with \ the \ following \ properties \ - \ i) \ 1 \ \in \ \mathbb{R}, \ ii) \ if \ x \ \in \ \mathbb{R} \ then \ x' \ \in \ \mathbb{R}[/tex]

    I want to prove that x' ≠ x. It's the second theorem, the first being;

    If x ≠ y then x' ≠ y'

    which is proved by assuming x ≠ y and x' = y'

    so we find a contradiction with axiom IV above because x' = y' means x = y.

    This is beautiful and understandable but in proving x' ≠ x the proof goes as follows,

    By axioms I and III above,

    i) 1' ≠ 1 because 1' = 1 + 1.

    so 1 belongs in R.

    Then it says;

    ii) If x ∈ R then x' ≠ x and by theorem 1 (x')' ≠ x' so x' ∈ R

    This makes no sense to me, where did it come from :confused:

    EDIT: I don't know why you can't use axiom II and just rearrange x' = x + 1 into x = x' - 1 to prove it :confused:
     
    Last edited: Jun 23, 2010
  2. jcsd
  3. Jun 24, 2010 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I am not familiar with the book, but I took a look at it in Google Books (page 2), and I see that you have misquoted Axiom V. It reads as follows:

    Axiom V (Axiom of Induction)
    Let there be given a set [itex]R[/itex] of natural numbers, with the following properties:
    I) [itex]1 \in R[/itex]
    II) If [itex]x \in R[/itex] then [itex]x' \in R[/itex]
    Then [itex]R[/itex] contains all of [itex]N[/itex], i.e., [itex]N \subset R[/itex]. In fact, this means [itex]N = R[/itex] since [itex]R[/itex] doesn't contain anything that is not a natural number.

    This is quite different from what you wrote: namely, you started with the hypothesis that [itex]N \subset R[/itex], whereas it's supposed to be the conclusion only if I) and II) are satisfied.

    Now, we want to prove that, for all natural numbers [itex]x[/itex], we have [itex]x \neq x'[/itex]. To do this, we define [itex]R[/itex] to be the set of all natural numbers such that [itex]x \neq x'[/itex]. The goal is to show that [itex]R[/itex] satisfies parts I) and II) of Axiom V, and therefore [itex]R = N[/itex].

    So let's check condition I). To do this, we must show that [itex]1 \in R[/itex], which by definition is true if [itex]1 \neq 1'[/itex]. Now, we know that [itex]1 \in N[/itex] (by Axiom I), and no element of [itex]N[/itex] can have 1 as its successor (Axiom 3), so [itex]1 \neq 1'[/itex]. Thus [itex]1 \in R[/itex] as desired.

    Now let's check condition II). Let [itex]x[/itex] be any member of [itex]R[/itex]. The goal is to show that [itex]x' \in R[/itex]. Since [itex]x \in R[/itex], by definition that means that [itex]x \neq x'[/itex]. Now, can [itex]x' = x''[/itex]? If it were true, then by Axiom 4 we would have [itex]x = x'[/itex], but we just said that [itex]x \neq x'[/itex]. Therefore [itex]x' \neq x''[/itex]. But this by definition means that [itex]x' \in R[/itex]. Thus condition II) is satisfied.

    We now conclude by Axiom V that [itex]R = N[/itex], i.e. [itex]R[/itex] contains every natural number, i.e. every natural number [itex]x[/itex] satisfies [itex]x \neq x'[/itex].
     
    Last edited: Jun 24, 2010
  4. Jun 24, 2010 #3

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    P.S., regarding this question:

    You can't do this because subtraction hasn't even been defined yet! Even if it had been, and this manipulation was therefore meaningful at this point, how would it prove that [itex]x \neq x'[/itex]?
     
  5. Jun 24, 2010 #4
    What's worse is that even addition hasn't been defined yet :tongue2:

    It's like coming out of the matrix here :rofl:

    I was trying to include N as part of the reals but they aren't defined either, nothing exists except the mind :eek: Cogito Ergo Sum!!!

    Okay...

    So, to prove x' ≠ x we prove x = 1 first then move onto the general case x ≠ x' because, by axiom V, this will account for all natural numbers 1 upwards.

    If 1 = x, 1' = x' by Axiom IV and 1 ≠ x' because if 1 = x' this breaks Axiom III, and theorem I.

    So, by theorem 1, x ≠ x' for x = 1 because if x = x' and 1 = x then 1 = x = x' and this contradicts Axiom III.
    This should settle the question for the base case, x = 1.

    If we assume x to be something other than one, say 3, it is defined under this arithmetic as;

    (x')' where x is 1. I think this makes sense, (1')'=(2)'=3 as defined by axiom II as it's written in the book. To me it seems logical, what do you think?

    If we define numbers this way we can use the base case proof, define x as 1 so that
    x ≠ x' can be iterated,

    1 ≠ 1' ⇒ 1≠ 2
    1' ≠ (1')' ⇒ 2≠ 3
    (1')'≠ ((1')')' ⇒ 3 ≠ 4
    etc...

    so, for any x we choose it can be composed of 1's and (')'s and this applies for all x and x' by axiom V.

    If you see what I'm trying to do, maybe it could be cleaned up? Thanks for the help so far anyway :D
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook