Register to reply 
Posets and minimal elements  Looking for an inductive proof 
Share this thread: 
#1
Dec1312, 04:44 AM

P: 67

1. The problem statement, all variables and given/known data
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]Rminimal[/itex] element. 2. Relevant 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]Rminimal[/itex] element" you are gonna 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. 3. 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]Rminimal[/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]Rminimal[/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]Rminimal[/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. 


#2
Dec1312, 06:16 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,338

Your proof looks good to me but the word you want in the last line is "hence". "Henceforth" means "from now on".



#3
Dec1312, 06:29 AM

P: 67

BTW, thanks a lot. I really felt it was too wordly. 


#4
Dec1312, 06:32 AM

P: 181

Posets and minimal elements  Looking for an inductive proof
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
Dec1312, 07:41 AM

P: 67

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. 


#6
Dec1312, 03:30 PM

P: 67

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]Rminimal[/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]Rminimal[/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]Rminimal[/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]Rminimal[/itex] element of [itex]B'[/itex]. Since this exhausts all the possibilities, the result is proven. 


#7
Dec1312, 03:42 PM

P: 67

The server stop gave me enough time to get something hopefully decent that should work.
Still, I have some doubts. 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? Is it mathematically sound? Too wordly? Are those lines a bad explanation? Anyway, thanks a lot for any feedback. 


#8
Dec1312, 04:29 PM

P: 181

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′##. 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
Dec1312, 04:46 PM

HW Helper
Thanks
P: 944

"Assume [itex]B[/itex] has cardinality [itex]n[/itex] and has an Rminimal 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 setup could be abbreviated: "Since a singleton subset has an Rminimal element, it is enough by induction on the cardinality of [itex]B \subset A[/itex] to show that if [itex]B[/itex] has an Rminimal element [itex]b[/itex] then the set [itex]B' = B \cup \{b'\}[/itex] where [itex]b' \in A \setminus B[/itex] has an Rminimal element." And then you consider the possibilities. 


#10
Dec1312, 04:58 PM

P: 67

So, thanks a lot (probably I start to sound repetitive). 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
Dec1312, 05:06 PM

HW Helper
Thanks
P: 944




#12
Dec1312, 05:07 PM

P: 67

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. 


#13
Dec1312, 05:08 PM

P: 67




#14
Dec1312, 05:32 PM

HW Helper
Thanks
P: 944

Anyway, I think between the various responses we now have a proof. 


#15
Dec1412, 01:49 AM

P: 67




#16
Dec1412, 06:42 AM

HW Helper
Thanks
P: 944




#17
Dec1412, 07:06 AM

P: 181

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
Dec1412, 07:29 AM

HW Helper
Thanks
P: 944

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


Register to reply 
Related Discussions  
List out all the isomorphism classes of posets on <= 4 elements  Linear & Abstract Algebra  0  
Inductive proof 4^n >/ n^4  Calculus & Beyond Homework  9  
Minimal elements of a MWI and the preferred basis problem  Quantum Physics  4  
Minimal set of elements, for life (as we know it)  Biology  0  
Inductive Proof on Well Known Sum  Calculus & Beyond Homework  8 