Posets and minimal elements - Looking for an inductive proof

In summary: Rb nor bRa.)If you have two elements a,b, then you can have aRb (which means ¬bRa, because a≠b), in which case a is minimal. Or bRa, which means that b is minimal. Or neither aRb nor bRa, and so both a and b are minimal.In your "Inductive step" you say that the cardinality of B is "improved" to n+1, i.e. made better. I think you mean "increase" here. And you need to check your three cases:Case 1 is
  • #1
Kolmin
66
0

Homework Statement



Suppose [itex]R[/itex] is a partial order on a set [itex]A[/itex]. Then every finite, nonempty set [itex]B \subseteq A[/itex] has an [itex]R-minimal[/itex] element.

Homework Equations



Partial orders are characterized by:

Reflexivity: [itex]xRx[/itex]
Transitivity: [itex]xRy \wedge yRz \rightarrow xRz[/itex]
Antisimmetry: [itex]xRy \wedge yRx \rightarrow x=y[/itex]

Minimal elements can be defined in two equivalent ways:

[itex]\neg \exists x \in X (xRb \wedge x \neq b)[/itex]
[itex]\forall x \in X (xRb \rightarrow x=b)[/itex]

Problems:
First of all I am not sure if the following is a real proof of this statement. I have some problems with inductive proofs and I am particularly worried by the "Assume the subset [itex]B[/itex] of [itex]A[/itex] has cardinality n and it has a [itex]R-minimal[/itex] element" you are going to find in the proof I wrote down. Can I really assume that?
Secondly, if the proof works, how is it? Too wordly and fuzzy? Efficient and perspicuous?
I have the feeling there is too much, but what can I cut?

Thanks a lot for any of your feedbacks. I am really looking forward to read them. :smile:

The Attempt at a Solution



Proof:
Let [itex]B[/itex] be an arbitrary subset of [itex]A[/itex]. We prove the theorem by induction on the cardinality of [itex]B[/itex].
i) Base step:
Assume the subset [itex]B[/itex] of [itex]A[/itex] has cardinality 2. By assumption [itex]R[/itex] is a partial order on [itex]A[/itex], thus we have two cases. Either by antisimmetry the two elements are equal, or they are different. If they are equal, by definition, they are both [itex]R-minimal[/itex] elements of [itex]B[/itex]. If they are different, one of the two has to be in the relation [itex]R[/itex] with the other element. In both cases, we are assured to have a [itex]R-minimal[/itex] element in [itex]B[/itex].
ii) Inductive step:
Assume the subset [itex]B[/itex] of [itex]A[/itex] has cardinality n and it has a [itex]R-minimal[/itex] element. Adding an element to the subset [itex]B[/itex] improves the cardinality of [itex]B[/itex] to n+1. We define this new set of cardinality n+1 as [itex]B'[/itex]. The addition of a new element to [itex]B[/itex] to construct [itex]B'[/itex] gives us three cases.
Case 1. The new element is equal to the minimal element of [itex]B[/itex]. Thus, by antisimmetry [itex]B'[/itex] has a two minimal elements.
Case 2. The new element is higher than the minimal element [itex]B[/itex]. Thus [itex]B'[/itex] has a minimal element that is the same of [itex]B[/itex].
Case 3. The new element is lower than the minimal element [itex]B[/itex]. Thus, [itex]B'[/itex] has a minimal element, that is the element added to [itex]B[/itex] to construct [itex]B'[/itex].
This exhausts all the possibilities. Henceforth the result is proven.
 
Physics news on Phys.org
  • #2
Your proof looks good to me but the word you want in the last line is "hence". "Henceforth" means "from now on".
 
  • #3
HallsofIvy said:
Your proof looks good to me but the word you want in the last line is "hence". "Henceforth" means "from now on".

Non native writer... :blushing:

BTW, thanks a lot. I really felt it was too wordly.
 
  • #4
Your "base step" is flawed. You say "Either by antisimmetry the two elements are equal, or they are different." Who needs antisymmetry (with a Y in "symmetry" by the way) for that? Anyway, if there are two elements, they can never be equal, because then they'd just be one element.

So you begin with two elements, say, a and b. Who says that one needs to bear the relation R to the other? (Remember: "poset" = "PARTIALLY ordered set", i.e. there can be elements a,b that fulfil neither aRb nor bRa.)

If you have two elements a,b, then you can have aRb (which means ¬bRa, because a≠b), in which case a is minimal. Or bRa, which means that b is minimal. Or neither aRb nor bRa, and so both a and b are minimal.

In your "Inductive step" you say that the cardinality of B is "improved" to n+1, i.e. made better. I think you mean "increase" here. And you need to check your three cases:

Case 1 is impossible. If the "new" element is equal to any "older" one, it can't be new. (If you add the element "banana" to the set {apple,banana,carrot}, you're not increasing the cardinality of that set.)

You'r missing a Case 4: what happens if the new element is neither "higher" nor "lower" than the minimal element of B? Again, since R is only a partial ordering, this is entirely possible.
 
  • #5
Michael Redei said:
if there are two elements, they can never be equal, because then they'd just be one element.

[...]

Case 1 is impossible. If the "new" element is equal to any "older" one, it can't be new. (If you add the element "banana" to the set {apple,banana,carrot}, you're not increasing the cardinality of that set.)

Huge mistake..I completely forgot that the notion of set implies that.

Michael Redei said:
So you begin with two elements, say, a and b. Who says that one needs to bear the relation R to the other? (Remember: "poset" = "PARTIALLY ordered set", i.e. there can be elements a,b that fulfil neither aRb nor bRa.)

For a second, I thought that I was implicity assuming that it was a loset and not a poset. So, here we are: indeed I assumed completeness.

Michael Redei said:
If you have two elements a,b, then you can have aRb (which means ¬bRa, because a≠b), in which case a is minimal. Or bRa, which means that b is minimal. Or neither aRb nor bRa, and so both a and b are minimal.

I don't see why it is the case.

Michael Redei said:
In your "Inductive step" you say that the cardinality of B is "improved" to n+1, i.e. made better. I think you mean "increase" here.

This. I was looking for that word! :smile:

Michael Redei said:
You'r missing a Case 4: what happens if the new element is neither "higher" nor "lower" than the minimal element of B? Again, since R is only a partial ordering, this is entirely possible.

Lot of stuff to think about. Give me a sec. :smile:

Btw, I think that my problem is related to the fact that I don't see why you don't need completeness to get the result. In particular I think the main issue is that I don't see why, if neither aRb nor bRa, then both a and b are minimal.

Oh, btw...really thanks a lot. :smile:
 
  • #6
Statement:
Suppose [itex]R[/itex] is a partial order on a set [itex]A[/itex]. Then every finite, nonempty set [itex]B \subseteq A[/itex] has an [itex]R-minimal[/itex] element.


Proof:
Let [itex]B[/itex] be an arbitrary subset of [itex]A[/itex]. We prove the statement by induction on the cardinality of [itex]B[/itex].
i) Base step:
Assume that [itex]B[/itex] is a singleton. Then the only element is by definition a [itex]R-minimal[/itex] element of [itex]B[/itex], by reflexivity of [itex]R[/itex].
ii) Inductive step:
Assume that [itex]B[/itex] has cardinality [itex]n[/itex] and that it has a [itex]R-minimal[/itex] element called [itex]b[/itex]. Increase the cardinality of [itex]B[/itex] to [itex]n+1[/itex] by adding an element, say [itex]b'[/itex], and define this new set [itex]B \cup \{b'\}[/itex] of cardinality [itex]n+1[/itex] as [itex]B'[/itex]. Thus we have three possible cases that define the relation [itex]R[/itex] between [itex]b[/itex] and [itex]b'[/itex].
Case 1. [itex]bRb'[/itex] : Thus [itex]B'[/itex] has a minimal element that is the same of [itex]B[/itex].
Case 2. [itex]b'Rb[/itex]: Thus, [itex]B'[/itex] has a minimal element, that is the element added to [itex]B[/itex] to construct [itex]B'[/itex].
Case 3. [itex]\neg (bRb' \vee b'Rb)[/itex]: Thus [itex]b[/itex] is still the [itex]R-minimal[/itex] element of [itex]B'[/itex].
Since this exhausts all the possibilities, the result is proven.
 
  • #7
The server stop gave me enough time to get something hopefully decent that should work. :smile:

Still, I have some doubts.

Kolmin said:
i) Base:
Assume that [itex]B[/itex] is a singleton. Then the only element is by definition a [itex]R-minimal[/itex] element of [itex]B[/itex], by reflexivity of [itex]R[/itex].

Can I prove the result without going backward to the singleton cases?
Or, in other words, is there a way to prove it having as a base case the two elements one I used in my first attempt?

Is the "by reflexivity of R" redundant?

Kolmin said:
ii) Inductive step:
Assume that [itex]B[/itex] has cardinality [itex]n[/itex] and that it has a [itex]R-minimal[/itex] element called [itex]b[/itex]. Increase the cardinality of [itex]B[/itex] to [itex]n+1[/itex] by adding an element, say [itex]b'[/itex], and define this new set [itex]B \cup \{b'\}[/itex] of cardinality [itex]n+1[/itex] as [itex]B'[/itex].

Is stylistically decent the way in which I introduce those new elements and sets?
Is it mathematically sound?
Too wordly?

Kolmin said:
Case 1. [itex]bRb'[/itex] : Thus [itex]B'[/itex] has a minimal element that is the same of [itex]B[/itex].
Case 2. [itex]b'Rb[/itex]: Thus, [itex]B'[/itex] has a minimal element, that is the element added to [itex]B[/itex] to construct [itex]B'[/itex].
Case 3. [itex]\neg (bRb' \vee b'Rb)[/itex]: Thus [itex]b[/itex] is still the [itex]R-minimal[/itex] element of [itex]B'[/itex].

Not enough explanations?
Are those lines a bad explanation?

Anyway, thanks a lot for any feedback. :smile:
 
  • #8
Kolmin said:
The server stop gave me enough time to get something hopefully decent that should work. :smile:
Perhaps we need more of those server pauses. I realized that I may have sounded a bit abrupt. I didn't mean to seem impolite, so I'm sorry if I did appear that way.

Kolmin said:
Kolmin said:
i) Base step:
Assume that [itex]B[/itex] is a singleton. Then the only element is by definition a [itex]R-minimal[/itex] element of [itex]B[/itex], by reflexivity of [itex]R[/itex].

Can I prove the result without going backward to the singleton cases?
Or, in other words, is there a way to prove it having as a base case the two elements one I used in my first attempt?

Is the "by reflexivity of R" redundant?
Yes, "reflexivity" is redundant here. For a singleton element there exists no smaller one, so it must be minimal. In fact, this "no smaller" definition of "minimal" is one that you could use more. Suppose you have two elements a and b such that no smaller elements exist and neither aRb nor bRa is true. Then both a and b are minimal. I'd keep the singleton as your base case though.

Kolmin said:
Kolmin said:
ii) Inductive step:
Assume that [itex]B[/itex] has cardinality [itex]n[/itex] and that it has a [itex]R-minimal[/itex] element called [itex]b[/itex]. Increase the cardinality of [itex]B[/itex] to [itex]n+1[/itex] by adding an element, say [itex]b'[/itex], and define this new set [itex]B \cup \{b'\}[/itex] of cardinality [itex]n+1[/itex] as [itex]B'[/itex]. Thus we have three possible cases that define the relation [itex]R[/itex] between [itex]b[/itex] and [itex]b'[/itex].

Is stylistically decent the way in which I introduce those new elements and sets?
Is it mathematically sound?
Too wordly?

A bit repetitious, I'd say, since you're saying the same things more than once. You could shorten this as follows:

Assume that ##B## has cardinality ##n##, and that ##b## is an ##R##-minimal element of ##B##. Now we consider a new set ##B'=B\cup\{b'\}## of cardinality ##n+1##. Then we have three possible cases for the relation ##R## between ##b## and ##b′##.

Kolmin said:
Kolmin said:
Case 1. [itex]bRb'[/itex] : Thus [itex]B'[/itex] has a minimal element that is the same of [itex]B[/itex].
Case 2. [itex]b'Rb[/itex]: Thus, [itex]B'[/itex] has a minimal element, that is the element added to [itex]B[/itex] to construct [itex]B'[/itex].
Case 3. [itex]\neg (bRb' \vee b'Rb)[/itex]: Thus [itex]b[/itex] is still the [itex]R-minimal[/itex] element of [itex]B'[/itex].
Since this exhausts all the possibilities, the result is proven.

Not enough explanations?
Are those lines a bad explanation?

Case 3 is missing a part. Suppose neither ##bRb'## not ##b'Rb##, as you have done. For ##b'## to be minimal there must be no other element ##a## that is smaller than ##b'##. How can you be sure of that?

This is where your whole proof becomes complicated. Instead of looking at a minimal element ##b## of ##B## and constructing three cases, I'd begin with ##b'## and ask: what elements of ##B## stand in the Relation ##R## to ##b'##? Suppose ##S## is the set of all these elements, i.e. ##S = \{a\in B : aRb' \lor b'Ra\}##. This set has at most ##n## elements, so you can use it for your inductive step.

Now you'll need to fiddle around a bit, depending on whether ##b'## is minimal in ##S## or not, and you need to consider the elements outside ##S## (but still in ##B##). You can probably use the fact that ##R## is transitive to show that the elements outside ##S## won't interfere with what happens inside ##S##.
 
  • #9
Kolmin said:
The server stop gave me enough time to get something hopefully decent that should work. :smile:

Still, I have some doubts.

i) Base step:
Assume that [itex]B[/itex] is a singleton. Then the only element is by definition a [itex]R-minimal[/itex] element of [itex]B[/itex], by reflexivity of [itex]R[/itex].

Can I prove the result without going backward to the singleton cases?
Or, in other words, is there a way to prove it having as a base case the two elements one I used in my first attempt?

Is the "by reflexivity of R" redundant?

You want your result to be true for all non-empty subsets, and singletons are non-empty subsets. I would say that it was obvious from the definition that a singleton subset has an R-minimal element.

ii) Inductive step:
Assume that [itex]B[/itex] has cardinality [itex]n[/itex] and that it has a [itex]R-minimal[/itex] element called [itex]b[/itex]. Increase the cardinality of [itex]B[/itex] to [itex]n+1[/itex] by adding an element, say [itex]b'[/itex], and define this new set [itex]B \cup \{b'\}[/itex] of cardinality [itex]n+1[/itex] as [itex]B'[/itex]. Thus we have three possible cases that define the relation [itex]R[/itex] between [itex]b[/itex] and [itex]b'[/itex].

Is stylistically decent the way in which I introduce those new elements and sets?
Is it mathematically sound?
Too wordly?

The key point is that you're adding an element which isn't in [itex]B[/itex], so you'd better make that clear:

"Assume [itex]B[/itex] has cardinality [itex]n[/itex] and has an R-minimal element [itex]b[/itex]. Let [itex]B' = B \cup \{b'\}[/itex] with [itex]b' \in A \setminus B[/itex]. Then [itex]B'[/itex] has cardinality [itex]n+1[/itex]."

I don't think you need to refer expressly to the cardinality of [itex]B[/itex]. Actually much of the set-up could be abbreviated:

"Since a singleton subset has an R-minimal element, it is enough by induction on the cardinality of [itex]B \subset A[/itex] to show that if [itex]B[/itex] has an R-minimal element [itex]b[/itex] then the set [itex]B' = B \cup \{b'\}[/itex] where [itex]b' \in A \setminus B[/itex] has an R-minimal element."

And then you consider the possibilities.

Case 1. [itex]bRb'[/itex] : Thus [itex]B'[/itex] has a minimal element that is the same of [itex]B[/itex].
Case 2. [itex]b'Rb[/itex]: Thus, [itex]B'[/itex] has a minimal element, that is the element added to [itex]B[/itex] to construct [itex]B'[/itex].
Case 3. [itex]\neg (bRb' \vee b'Rb)[/itex]: Thus [itex]b[/itex] is still the [itex]R-minimal[/itex] element of [itex]B'[/itex].
Since this exhausts all the possibilities, the result is proven.

Not enough explanations?
Are those lines a bad explanation?

For Case 3 you also have to show that there is no other element [itex]a \in B[/itex] such that [itex]aRb'[/itex].
 
  • #10
Michael Redei said:
Perhaps we need more of those server pauses. I realized that I may have sounded a bit abrupt. I didn't mean to seem impolite, so I'm sorry if I did appear that way.

Well, don't worry. I appreciate the fact that you had this thought, but it's really not a problem and I didn't feel it. Actually, to be honest, when I started to read your post and I saw "base case" with the inverted commas, at the beginning I thought you wanted to be sarchastic and I kinda liked it, cause the inverted commas with a sarchastic inflexion is the default way in which I would always present my - indeed! - "proofs"... :smile:
So, thanks a lot (probably I start to sound repetitive).

Michael Redei said:
Case 3 is missing a part. Suppose neither ##bRb'## not ##b'Rb##, as you have done. For ##b'## to be minimal there must be no other element ##a## that is smaller than ##b'##. How can you be sure of that?

This is where your whole proof becomes complicated. Instead of looking at a minimal element ##b## of ##B## and constructing three cases...

Not sure if this is a typo.
Actually with case 3, with the two elements that bear no relations, I wanted to show more or less exactly the opposite, which is that we are at least sure that ##b## (and not ##b'##) is a minimal element of ##B'##, and we can have at most two different minimal elements (indeed ##b## and ##b'##).

But are we "at least sure" of it?
 
  • #11
Kolmin said:
Actually with case 3, with the two elements that bear no relations, I wanted to show more or less exactly the opposite, which is that we are at least sure that ##b## (and not ##b'##) is a minimal element of ##B'##, and we can have at most two different minimal elements (indeed ##b## and ##b'##).

But are we "at least sure" of it?

I think you can argue that if [itex]aRb'[/itex] then [itex]a[/itex] must be an R-minimal element of [itex]B[/itex], because otherwise one has [itex]bRa[/itex] and [itex]aRb'[/itex] so that [itex]bRb'[/itex], which we are assuming not to be the case. But [itex]aRb'[/itex], so [itex]a[/itex] is an R-minimal element of [itex]B'[/itex].
 
  • #12
pasmith said:
For Case 3 you also have to show that there is no other element [itex]a \in B[/itex] such that [itex]aRb'[/itex].

Is it not a bit redundant?
My line of reasoning is more or less the same of that I wrote down in my last reply to Michael Redei.
I add an element to ##B## and I come out with ##B'##. Now, I assume that ##B## has a minimal element. So, if the new element and the minimal element of ##B## bear no relation, still ##b## is a minimal element (of - let's say - the right side of the Hasse diagram). So whatever ##a## we prove bears certain relation with ##b'## (on - let's say - the left side of the Hasse diagram), at most it makes us find another minimal element, but we already have it. Thus, it should be redundant.

Is it right or not? This was my line of reasoning when I wrote down my "proof" (yes...inverted commas with sarchastic inflexion!, but not sure it is sound.

Btw, thanks a lot for your feedback. :smile:
 
  • #13
pasmith said:
I think you can argue that if [itex]aRb'[/itex] then [itex]a[/itex] must be a minimal element of [itex]B[/itex], because otherwise one has [itex]bRa[/itex] and [itex]aRb'[/itex] so that [itex]bRb'[/itex], which we are assuming not to be the case. But [itex]aRb'[/itex], so [itex]a[/itex] is a minimal element of [itex]B'[/itex].

Ops... temporal overlap of answers.
 
  • #14
Kolmin said:
For Case 3 you also have to show that there is no other element [itex]a \in B[/itex] such that [itex]aRb'[/itex].
Is it not a bit redundant?

Not so much redundant as wrong: I should have said "For Case 3 you also have to show that if there is any other element [itex]a \in B[/itex] such that [itex]aRb'[/itex] then [itex]a[/itex] is an R-minimal element of [itex]B[/itex]."

Anyway, I think between the various responses we now have a proof.
 
  • #15
pasmith said:
Not so much redundant as wrong: I should have said "For Case 3 you also have to show that if there is any other element [itex]a \in B[/itex] such that [itex]aRb'[/itex] then [itex]a[/itex] is an R-minimal element of [itex]B[/itex]."

To me even that one looks redundant for the reasons I specified.
 
  • #16
Kolmin said:
To me even that one looks redundant for the reasons I specified.

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.
 
  • #17
pasmith said:
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.

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?

For any two rational numbers ##x## and ##y## we define the relation ##R## as follows: Let ##x={n_x}/{d_x}## and ##y={n_y}/{d_y}## where ##(n_x,d_x) = (n_y,d_y) = 1##, i.e. the numerator and denominator of a fraction have no common factor. Then we set
$$
xRy ~~ \mbox{iff} ~~ d_x=d_y ~~ \mbox{and} ~~ n_x\leq n_y.
$$
Obviously, ##xRy## can only be true if ##x\leq y##, but ##x\leq y## doesn't necessarily imply ##xRy##.

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##.
 
  • #18
Michael Redei said:
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 [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].
 
Last edited:
  • #19
pasmith said:
"a is the same size as b" is defined by the relation [itex]aSb \Leftrightarrow (\neg(aRb \vee bRa)) \vee (a = b)[/itex].

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

pasmith said:
S is obviously reflexive and symmetric and is also transitive, ...

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

pasmith said:
... 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.

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

pasmith said:
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:

pasmith said:
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.
 
  • #20
Michael Redei said:
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.
 
  • #21
Michael Redei said:
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.
 

1. What is a poset?

A poset, or partially ordered set, is a mathematical structure consisting of a set of elements and a relation that defines a partial order among those elements.

2. What is a minimal element in a poset?

A minimal element in a poset is an element that is smaller than or equal to all other elements in the set. It is often referred to as the "bottom" element in the poset.

3. What is an inductive proof?

An inductive proof is a method of mathematical proof that uses reasoning based on patterns and observations to prove a statement for all cases. It involves showing that a statement is true for a base case, and then using that to show that it is also true for the next case, and so on.

4. How can I prove the existence of a minimal element in a poset?

To prove the existence of a minimal element in a poset, you can use an inductive proof. Start by showing that the statement is true for the base case, which is typically the smallest or simplest element in the poset. Then, use the definition of a poset to show that the statement is also true for the next element, and continue this process until you have proven it for all elements in the poset.

5. Can I use a different method to prove the existence of a minimal element in a poset?

Yes, there are other methods that can be used to prove the existence of a minimal element in a poset. For example, you can use a direct proof by contradiction, where you assume that there is no minimal element and show that this leads to a contradiction. However, an inductive proof is often the most straightforward and efficient method for proving this type of statement.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
460
Replies
2
Views
253
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Precalculus Mathematics Homework Help
Replies
31
Views
2K
Back
Top