# Where is the error in this proof?

1. Aug 14, 2011

### Syrus

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. Aug 14, 2011

### 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 $z \leq y$ then y=0.
Or am I making a mistake?

3. Aug 15, 2011

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

Last edited: Aug 15, 2011
4. Aug 15, 2011

### 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

5. Aug 15, 2011

### 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

Last edited: Aug 15, 2011
6. Aug 15, 2011

### Syrus

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

7. Aug 15, 2011

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

8. Aug 15, 2011

### Syrus

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
9. Aug 15, 2011

### nonequilibrium

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?

10. Aug 15, 2011

### 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

11. Aug 15, 2011

Aha!