## Posets and minimal elements - Looking for an inductive proof

 Quote by Michael Redei What do you mean by "the same size"? Since R is antisymmetric, if a and b are "the same size", they're actually equal. How would your argument work for the following relation R?
"a is the same size as b" is defined by the relation $aSb \Leftrightarrow (\neg(aRb \vee bRa)) \vee (a = b)$.

S is obviously reflexive and symmetric and is also transitive, so that for all a, b, and c, $aSb \wedge bSc \Rightarrow aSc$. This is obvious if
any of a,b, and c are equal, so let all three be distinct. Then
$$aSb \wedge bSc \Leftrightarrow (\neg(aRb \vee bRa)) \wedge (\neg(bRc \vee cRb)) \Leftrightarrow \neg(aRb \vee bRa \vee bRc \vee cRb) \\ \Leftrightarrow \neg((aRb \vee bRc) \vee (cRb \vee bRa)) \\ \Leftrightarrow \neg(aRb \vee bRc) \wedge \neg(cRb \vee bRa) \\ \Rightarrow \neg(aRb \wedge bRc) \wedge \neg(cRb \wedge bRa)$$
where the last line follows because for all statements P and Q, $\neg(P\vee Q) \Rightarrow \neg(P \wedge Q)$. We then have
$$\neg(aRb \wedge bRc) \wedge \neg(cRb \wedge bRa) \Leftrightarrow \neg(aRc) \wedge \neg(cRa) \Leftrightarrow \neg(aRc \vee cRa) \Leftrightarrow aSc$$
by transitivity of R. Thus S is an equivalence relation.

It should be obvious that for all distinct a and b there are three possibilities: either aRb, bRa, or aSb. It should also be obvious that if a and b are minimal elements of a subset then aSb.

EDIT: Alternatively one can let $b \in B$ be minimal, but otherwise arbitrary. Then if $b'Rb$ then $b'$ is minimal in $B'$, and if $bRb'$ then $b$ is minimal in $B'$, and if neither $bRb'$ nor $b'Rb$ for any minimal $b$ then minimal elements of $B$ are minimal elements of $B'$.

 Quote by pasmith "a is the same size as b" is defined by the relation $aSb \Leftrightarrow (\neg(aRb \vee bRa)) \vee (a = b)$.
So "same size as" means "incomparable or equal". This is the first time I've seen that definition.

 Quote by pasmith S is obviously reflexive and symmetric and is also transitive, ...
Not at all obvious, and, in fact, false. S need not be transitive.

 Quote by pasmith ... We then have $$\neg(aRb \wedge bRc) \wedge \neg(cRb \wedge bRa) \Leftrightarrow \neg(aRc) \wedge \neg(cRa) \Leftrightarrow \neg(aRc \vee cRa) \Leftrightarrow aSc$$ by transitivity of R. Thus S is an equivalence relation.
The transitivity of R implies ##\neg(xRy\land yRz) \Leftarrow \neg(xRz)##, but not the converse, ##\neg(xRy\land yRz) \Rightarrow \neg(xRz)##. So the first "##\Leftrightarrow##" in that line should only be "##\Leftarrow##".

 Quote by pasmith It should be obvious that for all distinct a and b there are three possibilities: either aRb, bRa, or aSb. It should also be obvious that if a and b are minimal elements of a subset then aSb.
That follows trivially from your definition of S. Either a is less than b, greater than b, equal to b or incomparable to b.

I still don't see how you arrive at this result though, which seems contrary to the example I have given before:

 Quote by pasmith On reflection, you are right. Clearly all minimal elements of B are the same size, so either b' is less than all of them, b' is greater than all of them, or b' is the same size as all of them. In all three cases B' has a minimal element.

 Quote by Michael Redei W Now let ##B## be the set of all positive fractions whose numerator is even and whose denominator is a single digit. Then ##\frac21,\frac23,\frac25,\frac27,\frac29## are all minimal elements of ##B##, but are they all "the same size"? Suppose they are (since none can be said to be "smaller" or "larger" than an other), what happens if you set ##b'=\frac13##? This is ##R##-less than ##\frac23##, but not comparable to the other elements of ##B##.
I don't enter in the discussion about "same size" because my mathematical skills are not that advanced, even if basing on my limited knowledge I would agree with Michael Redei.

Btw, going back to my original Case 3 of the proof, I think that this example based on fractions supports exactly my line of reasoning. Indeed, if we set ##b'=\frac13##, it does change the composition of the set of the minimal elements (it takes the place of ##b'=\frac23##), but we don't care, as far as we know that we do have a minimal elements.

In other words, considering for example this random Hasse diagram (it is really not important how it is), let's imagine that ##b'## is something that bears no relation to ##\{∅\}##, but it's related to ##\{z\}##. Well, we did have before the addition of ##b'## a minimal element, namely ##\{∅\}##, and we still have it.
Adding ##b'## doesn't alter the fact that we do have a minimal element: it simply alters the composition of the set of the minimal elements of a given poset, but that's beyond the result we have to prove (I would call it a corollary).

In my "proof", the minimal element that still stands, beyond any addition, is ##b##, thus the result is proven.

 Quote by Michael Redei I still don't see how you arrive at this result though, which seems contrary to the example I have given before:
My thinking - which has let me down here, I'll admit - is that if neither aRb nor bRa then a and b are in some sense equivalent (for example, "don't care which comes first in a sorted list").

But really that's only the case if you start with an equivalence relation S and define a transitive relation R such that exactly one of aRb, bRa and aSb holds. But then "aSb or aRb" is not antisymmetric unless every equivalence class is a singleton, so the concept is useless in considering partial orderings.