Posets and minimal elements - Looking for an inductive proof

pasmith

"a is the same size as b" is defined by the relation [itex]aSb \Leftrightarrow (\neg(aRb \vee bRa)) \vee (a = b)[/itex].

S is obviously reflexive and symmetric and is also transitive, so that for all a, b, and c, [itex]aSb \wedge bSc \Rightarrow aSc[/itex]. This is obvious if
any of a,b, and c are equal, so let all three be distinct. Then
[tex]
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)
[/tex]
where the last line follows because for all statements P and Q, [itex]\neg(P\vee Q) \Rightarrow \neg(P \wedge Q)[/itex]. We then have
[tex]
\neg(aRb \wedge bRc) \wedge \neg(cRb \wedge bRa) \Leftrightarrow
\neg(aRc) \wedge \neg(cRa) \Leftrightarrow \neg(aRc \vee cRa) \Leftrightarrow aSc
[/tex]
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 [itex]b \in B[/itex] be minimal, but otherwise arbitrary. Then if [itex]b'Rb[/itex] then [itex]b'[/itex] is minimal in [itex]B'[/itex], and if [itex]bRb'[/itex] then [itex]b[/itex] is minimal in [itex]B'[/itex], and if neither [itex]bRb'[/itex] nor [itex]b'Rb[/itex] for any minimal [itex]b[/itex] then minimal elements of [itex]B[/itex] are minimal elements of [itex]B'[/itex].

Michael Redei

So "same size as" means "incomparable or equal". This is the first time I've seen that definition.

Not at all obvious, and, in fact, false. S need not be transitive.

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

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:

Kolmin

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.

pasmith

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.