Where is the error in this proof?

[Syrus]

Homework Statement

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.

Homework 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...

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.

 

[nonequilibrium]

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?

 

[Syrus]

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.

 

[nonequilibrium]

"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

 

[Syrus]

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

 

[Syrus]

"using our assumption (∀y)((∀z)((z,y) ∈ R → b = y), b = k"

Also, note i edited my first post, your quote above should be changed to (∀y)((∀z)((z,y) ∈ R → z = y) → b = k)

 

[nonequilibrium]

"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?

 

[Syrus]

You didn't though :p

Sorry, heh heh, guess i meant my following post. It's not letting me edit the original one.

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?

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.

 

[nonequilibrium]

Well, i am letting x be y and z.

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?

 

[nonequilibrium]

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

 

[Syrus]

Aha!