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