Linear TopologyDate: 02/09/2003 at 23:54:00 From: Brandon Subject: Sets and finite (linear topology) The question is true or false: If a point in set X is finite, then X has a first point and a last point. We are to prove by induction if true, and give a counterexample if false. We know the definition of first point, last point, finite, infinite, and precede, so it is not necessary to define these in the proof. Date: 02/10/2003 at 03:49:33 From: Doctor Jacques Subject: Re: Sets and finite (linear topology) Hi Brandon, You do not give the definition of "first point" and "last point." Let us assume that a "first point" means a point x such that, for all y different from x, we have x < y. Note that, if the set X is empty, the proposition is false. As this case is not very interesting, let us just add the condition "X is not empty" to the hypotheses. Let us first prove a few useful results. Proposition 1 ------------- If x and y are distinct, we cannot have both x < y and y < x (axiom (a) states that at least one of these relations is true). Indeed, assume that x < y and y < x. Axiom (c) then implies x < x, which is false by axiom (b). Proposition 2 ------------- x is a first element iff there is no y such that y < x. Assume that x is a first element. This means that, for all y <> x, we have x < y. Proposition 1 then implies that we cannot have y < x. Conversely, let us assume that there is no y such that y < x. Let y be any element different from x. By axiom (a), we have x < y. Let us now tackle the main part of the proof. You are asked to provide a proof by induction. Let n be the number of elements of the set X. If n = 1, X = {x}, x is a first point (as there is no y <> x, there is nothing to prove). Let us now assume that n > 1, and that the proposition is true for all k < n. Pick a point x, and consider the sets S = {y | y < x} and T = {x} U {y | x < y}. Note that, by axiom (a), X = S U T. If S is empty, x is a first point by proposition 2. If S is not empty, it contains fewer elements than X, and therefore has a first point s by the induction hypothesis. Note that, by the definition of S, we have s < x. You should now be able to conclude the proof using axiom (c), as any element of X belongs to either S or T. The proof for a last element is entirely similar. Please feel free to write back if you are still stuck. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/