1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Where is the error in this proof?

  1. Aug 14, 2011 #1
    1. The problem statement, all variables and given/known data

    If a subset (call it B) of a partially ordered (by a relation R) set A has exactly one minimal element, must that element be a smallest element? Give proof or counterexample.


    2. Relevant equations

    Well, our given, "exactly one minimal element" in PC (pred calc.) translates to:

    (∃b)((∀x)((x,b) ∈ R → x = b) ∧ (∀y)((∀z)((z,y) ∈ R → b = y))

    i hope...


    3. The attempt at a solution

    Call b the unique minimal element of B and let k ∈ B. Since (k,k) ∈ R, then using our assumption (∀y)((∀z)((z,y) ∈ R → b = y), b = k. Thus, (b,k) ∈ R.
     
    Last edited: Aug 14, 2011
  2. jcsd
  3. Aug 14, 2011 #2
    You made an error in the translation (and you forgot a ")" at the end).
    Take for example the natural numbers (for which of course b=0), then the second part of your statement says if we have two numbers such that [itex]z \leq y[/itex] then y=0.
    Or am I making a mistake?
     
  4. Aug 15, 2011 #3
    I see I did make an error. I basically used the definition of Existence and uniqueness and plugged in the definition of minimal element to come up with the above statement. Would this, then, be the correct translation of the statement?

    (∃b)((∀x)((x,b) ∈ R → x = b) ∧ (∀y)((∀z)((z,y) ∈ R → z = y) → b = y)

    And if so, it would seem my same "proof" above still holds. Any other suggestions/insight?
    My "proof" would now be:
    Call b the unique minimal element of B and let k ∈ B. Since (k,k) ∈ R, and (clearly) thus k = k, using our assumption (∀y)((∀z)((z,y) ∈ R → b = y), b = k. Thus, (b,k) ∈ R.

    By the way, there is a counterexample to this "theorem", but i am just trying to figure out where I went wrong in an attempt to prove it.
     
    Last edited: Aug 15, 2011
  5. Aug 15, 2011 #4
    "using our assumption (∀y)((∀z)((z,y) ∈ R → b = y), b = k"

    Can you explain this? What is the assumption there? What is the conclusion there? It's not making sense for me
     
  6. Aug 15, 2011 #5
    Well, to "prove" the statement, we use the antecedent of the implication to be proven, "If a subset (call it B) of a partially ordered (by a relation R) set A has exactly one minimal element," as a given. This statement may be logically expressed as (∃b)((∀x)((x,b) ∈ R → x = b) ∧ (∀y)((∀z)((z,y) ∈ R → z = y) → b = y). Thus, we assume there is some b ∈ B such that (∀x)((x,b) ∈ R → x = b) and (∀y)((∀z)((z,y) ∈ R → z = y) → b = y).

    Now, our goal is (∀x)((b,x) ∈ R).

    As a result, let x ∈ B. Since (x,x) ∈ R (which is true since R is a partial order) implies x = x (which is true anyways), then using the second conjunct of the given above (which is what is referred to earlier when I stated "using our assumption..." above) we may conclude b = x, so (b,x) ∈ R
     
    Last edited: Aug 15, 2011
  7. Aug 15, 2011 #6
    Also, note i edited my first post, your quote above should be changed to (∀y)((∀z)((z,y) ∈ R → z = y) → b = k)
     
  8. Aug 15, 2011 #7
    "Also, note i edited my first post, your quote above should be changed to..."

    You didn't though :p

    Anyway: it's not clear to me how you apply "(∀y)((∀z)((z,y) ∈ R → z = y) → b = k)"
    What variable is representing your x?
     
  9. Aug 15, 2011 #8
    Sorry, heh heh, guess i meant my following post. It's not letting me edit the original one.



    I mistyped a letter above, it should be "(∀y)((∀z)((z,y) ∈ R → z = y) → b = y)

    I am letting the arbitrary x introduced be used for both z and y.
     
    Last edited: Aug 15, 2011
  10. Aug 15, 2011 #9
    You're misreading what "(∀y)((∀z)((z,y) ∈ R → z = y) → b = y)" means.

    It says that (given a certain y) IF "(∀z)((z,y) ∈ R → z = y)" THEN "b = y"
    Is the IF part true in your case?
     
  11. Aug 15, 2011 #10
    Let me be more exact: in your case y = x, okay, now you have to check that "(∀z)((z,x) ∈ R → z = x)"
    but you have only verified this for the trivial case of z = x
     
  12. Aug 15, 2011 #11
    Aha!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Where is the error in this proof?
  1. Matrix/Error Proof? (Replies: 3)

Loading...