Munkres, Section 1 Fundamental Concepts
1. For example, the first DeMorgan’s law: .
2. The following table summarizes the correct symbols (implication, equality or inclusion) for each statement:
|a b j||c||d l||e m||f h q||g i n o p|
4. Negation for (a): s.t. . (b) and (c) are negations of each other. (d): .
5. (a) and (d): . (b): . (c): .
6. The two true contrapositive statements are:
8. It is called a “power set” because for any set with elements has elements. By induction. If has 1 element, then there are two subsets of : the empty set and the set itself. Suppose that for any set with elements its power set has elements. Take a set with elements, and let be an element in . Each of its subset either contains or it does not. We can construct all subsets of by taking subsets of (which has elements) and for each subset either add to it or not. Therefore, the number of subsets of is twice the number of subsets of which is, by induction, . So, we get subsets in . (Since we started the induction at there is one more case, , but obviously as there is only one subset of the empty set — the empty set itself.)
9. For example, the first law: . The proof is similar to the first problem.
10. A set in is the cartesian product of two sets in iff a set of ’s such that is either the empty set or does not depend on . So, we get the positive answer in (a), (b) and (d).
Munkres, Section 2 Functions
1. (a) To show that for some sets we need to show that : , or, equivalently, show that : . . If in injective, then (otherwise, there exists such that ) .
(b) . If is surjective and then and .
2. (a) .
(b) From (a) , and, therefore, . The other direction: or .
Similarly, (c) and (d).
(e) : .
(f) By (e), . The other direction: : : or : .
(g) The “” part follows from (e). If is injective then : and : . Since is injective, .
3. The proofs are almost identical to those in 2 (b), (c), (f) and (g).
4. (a) .
(b)-(f) is injective iff is injecive and is injective on . It is surjective iff is surjective on (and, therefore, is surjective on ).
5. (a) Use 4 (c) and (e), or, equivalently, 4(f).
(b) has at least two left inverses and, for example, but no right inverse (it is not surjective).
(c) has two right inverses and but no left inverse (it is not injective).
(d) See (b), (c).
(e) It follows from (a) that is bijective: for each there is unique such that . Now, , and , and, since is injective, as well.
6. For example, .
Munkres, Section 3 Relations
1.Reflexivity, Symmetry and Transitivity (RST) obviously hold. The equivalence classes are sets of points on parabolas .
2. RST hold on the restriction, and equivalence classes are those given by partitioning of restricted to . All three properties hold because the restriction includes all pairs in the initial relation that have both elements from the subset.
3. If is complete, then the proof is complete. If there is a pair such that neither nor then the proof does not prove that .
4. (a) RST obviously hold, (b) Let be a function such that where . is well-defined as the choice of does not matter, injective as is different for elements in different classes, and surjective as is surjective.
5. (a) RST hold for . The classes of equivalence are those points the distance between which is an integer. contains some pairs such that the distance is 1, and, therefore, if then .
(b) If RST hold for any relation in the collection then it holds for any relation in the intersection.
(c) Every equivalence relation that contains must have at least these pairs: for every (reflexivity), (contains S), (symmetry), and, by transitivity and symmetry, we must add and . Let a set of these pairs be . Then is in the intersection. If we show that is an equivalence relation itself, then it is the intersection (from (b) it follows that the intersection must be an equivalence relation, and, therefore, the intersection is an equivalence relation that is contained in any other equivalence relation that contains ). RS obviously hold for . The transitivity needs a proof. Let . If or then holds. If and then , , is integer (-2,-1,1 or 2), , . Therefore, is an integer and both are in . For all such pairs there is a relation in .
6. A point is “less” than another iff the former lies on a higher parabola or on the same parabola, but to the right. Comparability, Nonreflexivity and Transitivity (CnRT) hold.
7. CnRT hold for restriction. Nonreflexivity holds because the restriction does not add new pairs, and Comparability and Transitivity hold because the restriction includes all pairs in the initial relation with both elements from the subset.
8. Comparability: for any either or or they are equal, but then one of them is less than the other one.
Nonreflexivity: for no or holds.
Transitivity: (in the linear order) implies (on the real line) and if there are two equalities (the only case in which ) then (on the real line).
9. CnRT obviously hold.
10. (a) implies that is strictly increasing.
(b) is bijective, and, therefore its left inverse and right inverse are equal, and equal to the inverse image of any point. Now, we need to check that for all . means that we can parametrize it as follows: . Note that . Then and .
11. If there are two successors, then , and since the order is complete, either or . In either case one of sets or is non-empty, contradiction. Similarly for predecessors. “At most one smallest or largest element”-part follows from the completeness of the order as well.
12. The following pictures illustrate the orders:
Immediate predecessors. (i) In the dictionary order every element , , has an immediate predecessor , while does not (if then , and ). (ii) Note that if then exists, and (consider two cases to see this: and ). Hence, the immediate predecessor of is if it exists, i.e. if and . (iii) If then either and (again, two cases), or and in this case , hence, . Therefore, every element except has an immediate predecessor.
The smallest element. If there is a smallest element then it must be the least among those without an immediate predecessor (but not vice versa, of course). In (i) it is and, indeed, it is the smallest. In (ii) there is no smallest element without predecessor as for every we have , but for every we have (another way to see that there is no smallest element in (ii) is as follows: ). In (iii) there is only one element without immediate predecessor, which is , and, as it is easy to see, it is the smallest.
The order type. Given the answer for the previous two questions, it is immediate that the order types are different. In fact, the order type in (ii) is that of the dictionary order on . And the order type in (iii) is that of .
13. Let be a non-empty subset bounded from below. Let be a set of all lower bounds of . is bounded from above by any element in . Therefore, it has the lowest upper bound such that for any upper bound of : . We show that is the greatest lower bound of . First, it is a lower bound of as any element in is an upper bound for implying . If there is another lower bound of then , and, therefore, .
14. (a) is symmetric iff () iff () iff is symmetric.
(b) If is complete and nonreflexive, so is . If is transitive then implies implies implies , so is also transitive.
(c) Using 14 (b) and the fact that for any set the upper/lower bounds under are lower/upper bounds under this is also immediate from the 13.
15. (a) For all subsets are bounded from above, and the least upper bound on the real line is the one in . For bounded from above are those subsets that have the least upper bound on the real line less than 1 (if the least upper bound is one, then there is no bound for the subset in ). Therefore, the same least upper bound is in .
(b) or . Let be a bounded from above subset of A, and be a set of all -coordinates of all points in . Since is bounded from above in , is bounded from above in and let be its least upper bound. If then there are no point in with -coordinate equal to , but for any there is a point in such that its -coordinate is greater than . Therefore, in this case is the least upper bound of . If then there are some points in such that their -coordinate is , and the set of all their -coordinates has the least upper bound in . In this case is the least upper bound of .
does not satisfy the property, as, for example, is bounded from above but has no least upper bound (for any is an upper bound of but there is no upper bound ).
Munkres, Section 4 The Integers and the Real Numbers
1. We shall not prove all the properties. Most use symmetry of operations, associativity and properties of 0, 1, etc. (a) (b) uses hint and (a) (c) (d) (e) (f) and (g) follow from (e) (h) and for similarly (i)-(t) are proved similarly but for multiplication.
2. "Laws of inequalities" are 1) multiplication by positive/negative preserves the inequality, 2) addition of any number preserves the inequality, and 3) 1 > 0. (a) (b) from (a) in the laws (c) (d) as (c) (e) from (c) and the laws (f) from (b) and (e) (g) by the laws (to prove assume to the contrary that , oops) (h) from (e), for example (i) 1>0 and (e) (j) multiply both sides by positive x and y (k) multiply by 2=1+1.
3. (a) for all in the intersection is in any set in the collection, therefore, is in every set in the collection, therefore, is in the intersection.
(b) is inductive by (a). And if is inductive set of integers then it is both a subset and superset of .
4. (a) Let be a set of integer values for which this statement is true. It is true for n=1, so . Suppose . Then a non-empty subset of either contains or not. In the first case is the largest element, and in the second case it is a subset of and has the largest element. Therefore, , is an inductive subset of , and by 3(b) it is just .
(b) Because it is proved to be true for all such subsets that are contained within some set , i.e. all bounded from above subsets. But as it was shown in the text there are some unbounded subsets as well, for example, the set itself.
5. (a) Using hint: given it easy to see that and is inductive.
(b) Similarly here, but using (a).
(c) Using hint: as , and if then and implying .
(d) and (e) Prove the following statement: such that and if then implies (similar to 3(b)). Then (d) and (e) follows by a proof similar to (a) and (b). Another way: use hint.
6. These properties follows immediately by symmetry and associativity of the addition and multiplication (and by the meaning of multiplying by an integer number: .
7. Similar to 6, by considering different cases when m and n are positive or negative (using ).
8. (a) See §3, 13.
(b) is a lower bound, but for any there is , therefore, by all the properties proved, . That is any positive number is not a lower bound for the set.
(c) Using hint: if then and if we show that for a positive , we can use this to argue that for any there exists such that , and, therefore, (no positive lower bound). To show that for all positive integer we can use the induction principle again.
9. (a) See 4 (a) and (b) (either 0 bounds the set from above or there are some positive integers in the set and we apply the results shown before).
(b) Consider a subset of of integers less than . It is non-empty, bounded from above by , has the lowest upper bound, which has to be the .
(c) Use (b) to find the for and use other proved properties to verify that this is greater than .
(d) Take , then such that . We have and can use (c) to find between them. It follows that is the rational number between and .
10. (a) follows from .
(b) one need to take sufficiently small (use the continuity of , for example) to use (a) here.
(c) If then is bounded by , for example. If then is bounded by . Using (b) it is easy to see that cannot be such that (otherwise there is a greater element in ), and cannot be such that (otherwise there is a smaller element such that it is not in and is an upper bound of as well).
(d) If both positive and one is less than another, say , then .
11. (a) use hint (b) use (a) and induction (and the fact that an integer is even iff it can be represented as for some integer ) (c) using hint: is the smallest positive integer such that is an integer. Let . If both and are even, then and both and are integers.
(d) Let and not both and are even (using (c)). Then , and is even. Now (b) implies is even, and , therefore, , and must be even as well. Contradiction.
Munkres, Section 5 Cartesian Product
2. (a) Similarly (b)
3. (a) If maps into such that : then it maps into and : .
(b) If is non-empty then all are non-empty. If there is such that not then there is in and there is an element in such that .
(c) non empty means there is an "assignment" of an element from each set, i.e. they are non empty. The converse. The comment in parentheses means that one need to be careful in statements like this, as the intuitive approach may implicitly use some axioms, which must be stated explicitly with a more formal approach. In this case we would need an axiom of choice to say what we are going to say, if we knew what it is. Since we don't, we will say it without any further concern. Yes, we can select one element from each set and say that .
(d) Both imply the same functions such that but also assumes that all are in or in . So is a subset. But for the intersection we have the equality (each must be in and ).
4. Let . (a) (b) similar to 2 (c) similar to (a) (d) (e) (f) similar to (e)
5. It is possible iff the set of all values does not depend on the values of other possible . So we get the positive answer in (a), (b) and (c).
Munkres, Section 6 Finite Sets
1 (a) We exclude one element from the set and for each such exclusion there are 6 ways to define a bijective correspondence between two sets of 3 elements.
(b) Exclude 2 elements of 10 (45 combinations) define an 8 by 8 bijection (8!=40320 combinations). The total is 45*40320 combinations.
2 Using Corollary 6.6, if were finite, would be finite too. Or, alternatively, using Corollary 6.7, if is finite, then there is an injection from into a section of positive integers, and there is also an injection from into , therefore, there is an injection from into a section of positive integers. Contradiction.
4 (a) By induction. If 1 element in then it is the largest. Suppose there is the largest for any set of cardinality . If has elements, and then has the largest (by induction) and it is the largest in if is smaller otherwise is the largest.
(b) The bijection is constructed by the number of elements in that are less or equal to the given element (needs some work). For a more complete account of this proof see Theorem 10.1 (page 64): it has a solution for both 4 (a) and (b).
5 If it was given that both sets and are non-empty then the answer would be: yes, as there is a bijective correspondence between, say, and for some fixed . But if sets can be empty, then, as it was noted by Fran in the comments below, their product may be empty (finite) while one set is empty and the other is infinite.
6 (a) Let where iff .
(b) Use (a) and Corollary 6.8.
7 Let have n elements. There is a bijection between the set of all functions and . Namely, . Use Corollary 6.8.
Munkres, Section 7 Countable and Uncountable Sets
1 It contains infinite subset of integers, therefore, infinite. There is an injection into , therefore, countable.
2 Example 1. is surjective as it covers all even and odd numbers, and it is injective, as two even or odd numbers assigned by are never equal. Similarly for Example 2.
3 Similar to §6, 6(a).
4 (a) There is countable set of sets with polynomials of a given degree, each set has countable number of polynomials, and therefore roots.
(b) If it were countable, then reals would be countable as the union of algebraic and transcendental numbers.
- (for a, b, c, d, e) The set of all functions from a set of cardinality ( is either a positive integer or if is a countably infinite set) to a set is equivalent to (there is a bijection between them, see §6, 7).
- (for f, g) The set of all functions from to that are eventually a given fixed element is equivalent to the countable union of all functions from to s.t. for all positive integers and the constant function that is equal to on .
- (for h) The set of all functions from to a countable set that are eventually constant is equivalent to the countable union of the sets of functions that are eventually a given fixed element for all .
- (for i, j) The set of all subsets of such that they have a given cardinality is equivalent to a subset of the set of all functions from to .
Using these facts and Theorems 7.5, 7.6 and 7.7:
- countable are (a) (b) (c) (f) (g) (h) (i) (j)
- uncountable are (d) (e)
6 (a) The hint is actually almost the proof. All one needs to do is 1) show that is well-defined (for all : : if then otherwise and whether or ); 2) show that it is bijective (let and : show that and are disjoint, the restriction of on is a bijection ) (b) is a bijection and is an injection, therefore has the same cardinality as and .
7 There an obvious injection from to . To construct the opposite injection note that each function in is an infinite countable sequence of integers, while a function in is a infinite countable sequence on 0's and 1's. For each sequence of integers in assign a sequence of 0's and 1's such that first there are 0's then 1 then 0's then 1 etc.
8 Each countable subset (i.e., each ) can be represented (not uniquely but injectively) as a countable sequence of its elements, i.e. as a countable sequence of infinitely countable sequences of 0's and 1's: . Hence, can be represented (not uniquely, but injectively) as a countable table (with countable number of columns and infinitely countable number of rows) by putting each as column of the table. If there are finite number of columns in the resulting table (finite number of elements in ) then let us add infinitely countable many columns with the same sequence that does not belong to . This way, as it is easy to see, we have constructed an infinitely countable table for each countable set , and no table corresponds to two different sets (because we can easily reconstruct set given its corresponding table). In its turn the infinitely countable table can be injectively associated with a countable sequence of 0 and 1. How?
Here is an example: let be the set of all sequences starting from a finite positive number of 1's and following all 0's. Since is countable, it can be represented as a sequence of its elements. This representation is not unique, but different 's cannot have the same representation. In our case let with initial 1's. Then, the infinite table (matrix) and the injection from the table to a sequence of 0's and 1's can be constructed, for example, as follows:
Note, that different countable sets cannot have equal tables, and different tables cannot correspond to the same final sequence of 0's and 1's.
Vice versa, every sequence in corresponds to a subset containing this one sequence only (singleton).
9 (a) The last expression can be rewritten as . By taking the positive root we ensure that takes positive values and always exists (as the sum will be positive). (b) Let be two functions both satisfying (a) for , and , , and , . (c) must be 1, hence must be 1 or -1, but then must be -3 or -5.
Munkres, Section 8* The Principle of Recursive Definition
5 implies uniqueness (if exists). Existence is implied by the fact that all ’s are positive.
6 (a) is not well defined. It does not violate, because there is no well defined function.
(b) Here the is well-defined, as whenever takes values below 1, defines the next value to be 5.
7 First, by induction, prove that there exists a function on any section of positive integers. Then, similar to Lemma 8.2, prove that it is unique on any section. Finally, as in Theorem 8.3, construct for all positive integers (construct its rule to be the union of rules of (unique) functions defined on sections).
8 The difference between the two definitions is that the former (in the text) requires to be defined for any function that maps a nonempty section of positive integers to and also requires it to have a specified initial value , while the latter (in the exercise) requires to be additionally specified for the function that maps the empty section to some element in and also requires the initial value to be equal to . If in the second case we call then both definitions become equivalent.
Munkres, Section 9 Infinite Sets and the Axiom of Choice
2 (a) Take the lowest element.
(b) Take the lowest positive element if there is at least one, otherwise take the largest element of the set (in this case the set must consist of negative integers and, possibly, 0).
(c) First, for each rational number we consider a unique representation as a pair of integer numbers: for any take (m,n) such that is irreducible and is positive. The fact that it is possible should not depend on the axiom of choice. Then for any nonempty set of rational numbers choose an element by the following rule: first, choose a subset of rational numbers with the lowest denominator (it is well-defined as denominators are all positive) and then choose an element by the rule in (b) applied to the set of all numerators in the subset.
(d) A nonempty subset of is a (possibly, infinite or even uncountable) set of infinite sequences of 0 and 1. We need to provide a general rule that would work for any such set and pick one of those sequences. Think about it.
3 If it were finite, there would be bijective function from onto such that combined with injective function it would give an injection into a strict subset. Define recursively such that is equal to where is the minimal positive integer such that the corresponding value is not in the . It is well-defined as are injective.
4 For example Theorem 7.5. We must consider sets of all surjective functions on and choose one from each.
5 (a) For every element in the image let such that (note that is not empty as the function is surjective, but the ability to make this arbitrary choice of ’s for all ’s all together depends on the axiom of choice). Then for every .
(b) The axiom is not needed. Let , for , and otherwise. The function is well-defined as is injective and we have for all elements in the range.
6 (a) It’s a set of all subsets of , and every subset is a set itself and is in the “set of all sets”. Therefore, there is a surjection from onto . Let . We have but for every : iff . Therefore, is not surjective. The second part of the proof is based on the Cantor’s theorem. (b) Neither.
7 (a) It’s infinite (injection one way — by Theorem 9.1: remember how the injection was constructed “by induction” in the proof of the theorem and then the role of the Axiom of Choice was discussed after the proof?), but not countable (no injection the other way — by Theorem 7.1).
(b) There are injections , therefore, there is an injection , and if there were an injection then there would be an injection .
(c) , is arbitrary.
8 There is a bijective function from onto given by iff for every . Now we use the following fact (which is slightly different from the one in the exercise as it uses binary not decimal expansions): every real number has a unique binary expansion such that it does not end with an infinite sequence of 1′s, we call this injective expansion as . Now, using this fact it is immediate to see that there exists an injection from the reals into . On the other hand, if we take any sequence of 0 and 1, and construct a new sequence with 0′s on odd positions and the elements of on the even positions, then there is a unique real number corresponding to the constructed sequence.
Munkres, Section 10 Well-Ordered Sets
1 If the set of upper bounds is non-empty, it has the least element, which must be the least upper bound.
2 (a) If the set of successors is non-empty then it has the least element. (b) The set of integers.
3 No, the first has an element which is not the smallest but has no immediate predecessor while the second does not have such an element (therefore, there is no order preserving bijection, as if there were, say , then cannot be the smallest element and it must have a predecessor , then and let be between and — there is no correspondent element between and ).
4 (a) If the set has such a subset, then this subset has no minimum element (as there is a bijection into preserving the order). If the subset is not-well ordered then there exists a subset that has no least element. For any element in the subset there is an element less than , then another one less than etc. The bijection is immediate.
(b) See (a): if it were not well-ordered, there would be a countable not well-ordered subset.
5 Given a collection of disjoint sets take their well-ordered union and for each set define the choice as its least element in the well-ordered union.
6 (a) A section by any element must be countable.
(b) The section is countable, so the rest is uncountable.
(c) It follows from two simple facts. First, every countable subset of has an upper bound (Theorem 10.3). Second, for every element there is a greater element that has no immediate predecessor (note that every element has an immediate successor, which is the least element of the subset defined in (b), call it , then construct inductively set , , etc.; this is a countable set that has a non-empty set of upper-bounds, and its least upper bound (exercise 1), which is greater than , and has no immediate predecessor). From this two facts, assuming that is countable, it follows that there is an element without the immediate predecessor (and, therefore, must be in ) which is greater than some upper bound of .
7 (The Principle of Transfinite Induction.) Let be a set of those elements not in , and suppose it is not empty. Then it has the least element , and (the section can be empty — does not matter), i.e. . Contradiction. Therefore, is empty, and .
8 (a) If a subset has an element from then the least element in is the -least element in , otherwise it is the -least element in .
(b) Take the set of all indexes of sets that contain some elements in , then find the least index , and find the least element in the intersection of the initial subset and the set .
9 (a) Consider any sequence which has only one element different from 1: 2 at the (n+1)th position. Another sequence is lower than this iff it has all 1 starting from the position (n+1). The order of all elements in the section by this sequence is the “reverse dictionary”.
(b) For any sequence define such that and if then , i.e. it is the position at which the infinite tail of 1′s starts. For any subset of sequences consider the set of all . This set has the least element . Consider a set of all sequences such that . All other sequences in are greater than any element in . But these sequences are in a section described in (a), which has the same type as the well-ordered set .
10 (a) If and are both defined on a section and coincide on it, and is in both domains, then , because they both satisfy (*). Hence, if and are defined on domain which is a section or all of , then they must coincide on it: consider the set of x’s for which , note that it is inductive (use the fact that every section of is a section of ) and apply transfinite induction on . Finish the proof by noting that the common domain of and must be a section or all of .
(b) Extend by the formula (*) (the extension is well-defined because there is no surjection).
(c) This follows from (a). Take any element in the union of sections, there is a section (may be not unique) that contains the element and a corresponding function . Define to be equal to that function (the choice of the section does not matter by (a)), and show that satisfies (*).
(d) Consider the set of all those ’s for which there does not exists the function, then take its least element, and use the hint to show that there does exist such function. Or, use the transfinite induction: let be the set of all those ’s for which the function exists, then if a section is in the then (consider two cases using the hint). When using hint, the two cases correspond to (b) and (c).
(e) Existence. (d) proves that for every section there is a function satisfying (*). (c) proves that, therefore, there is a function satisfying (*) on the union of all sections of . The union contains all elements of except for (thanks to Fran for the comment) the largest element in (if there is one — every other element has a successor). In this case, we extend the function from the union to the whole using (b). The uniqueness follows from (a).
11 If there are injections both ways, then there is a bijection and the sets have the same cardinality (proved in exercises before). Otherwise, there can be an injection one way only, and we need to show that there is one either way. If there is a surjection from onto then there is an injection (a right inverse, which exists due to the axiom of choice which is equivalent to the well-ordering theorem). If there is no surjection, then we can well-order both sets and use exercise 10 to show the existence of an injective function from into (the fact that it is injective follows immediately from the definition (*)).
Munkres, Section 11* The Maximum Principle
1 It is nonreflexive and transitive (nRT). The maximal subsets are .
2 The purpose of the exercise is to show that the two definitions of the partial order — one given by the axioms (i)-(iii) and the other given in the text based on a strict partial order — are equivalent in the sense that a relation satisfies the axioms (i)-(iii) of a partial order if and only if there is a strict partial order inducing the relation. (a) A strict partial order must satisfy nRT, so the induced relation must satisfy (ii) and (iii). It also satisfies (i) by definition. (b) If a relation satisfies (i)-(iii) then satisfies nR by definition. Now, if then by (iii) . If at the same time then by (ii) we would have that contradicts . Therefore, .
3 This will work if a set can be partitioned into a collection of disjoint ordered subsets such that no two elements from two different subsets are comparable. On the other hand, if, for example, for some element there are two greater elements that are incomparable, then the set defined for this element will not be ordered. So, for a set in Example 1 this will fail, and for sets in Example 2 and Exercise 1 it will succeed.
4 For a given point all points weakly above and to the right are greater. So the graph of any weakly increasing continuous function will be a maximal subset (for a given point on the graph all points on the graph with greater -coordinate will be greater, and all points with lower -coordinate will be lower, also all points off the graph will be incomparable to at least one point on the graph — just take a point on the graph with the same -coordinate as and then another point on the graph slightly to the left or to the right of depending on whether is below or above ). So, both and are maximal. is not as, for example, (0,0) and (-1,1) are not comparable.
5 The union of all sets in a subcollection is an upper bound for this subcollection, and it is in the collection, so Zorn’s lemma implies that there is a set in the collection such that no other set in the collection contains it.
6 Take any ordered subcollection , the union of its sets and any finite subset of . For each point in there is a set in containing it, and since the number of points is finite and is ordered, there is a set in that contains all these points. Since this set is in all its finite subsets are in implying . So, any finite subset of is in , and therefore, . Now apply Kuratowski lemma.
7 Let be a collection of ordered subsets of . If a set belongs to the collection, all its finite subsets are ordered as well, so all finite subsets are in the collection as well. Now, suppose that for a set all its finite subsets are in the collection. Then for any two elements in the binary set consisting of these two elements is ordered, i.e. the set is ordered (the restriction of an order to a subset is an order). We just obtained the finite property for the collection. Therefore, Tukey’s lemma applies, and there is a maximal ordered set in the collection — no other ordered set contains it.
8 (a) If it were not independent, there would be a non-trivial linear combination equal to zero, this combination must include with non-zero coefficient, as is independent, but this leads to the contradiction as it implies that .
(b) Let be the collection of all independent sets in partially ordered by the proper inclusion. Then iff any non-trivial linear combination of any finite number of vectors in is not zero iff any finite subset of is in . Therefore, is of finite type and Tukey’s lemma applies.
(c) The maximal set found in (b) is a basis, as if there were an independent element, then by (a) the maximal set would not be maximal.
Supplementary Exercises*: Well-Ordering
1 The only difference between this and §10, Exercise 10 will be in that there we used an explicit “-function” and the fact that it is well-defined since there is no surjective function from onto . Here we just take it as granted that is well defined and use exactly the same proof.
2 (a) (i) implies (ii). must be injective as order preserving. Therefore, for any : . Moreover, since the image of is or its section, and since is the smallest , is the smallest in . (ii) implies (i). Let be a set of ’s such that . Then if there is a section then must be greater than any element in , as if for some then must be in the section of by . Moreover, if then . Therefore, and . By the principle of transfinite induction the image of any section by an element in is a section by the image of the element in , and, therefore, is order preserving. Its image is either the whole or a section of by the least element not in the image. Indeed, if there were an element in such that , then would have to be in .
(b) By (a) if is an order preserving map, then it must be given by (ii) and using the principle of the recursive definition there is only one such function. So, it must be the identity function which is not a bijection. Given two sections one must be a subsection of the other.
3 Given the hint, first, we need to formally show that is well-defined. This is pretty much straightforward using Exercise 1. For any and define if or otherwise. Then is well non-recursively defined, and uniquely defines satisfying the recursive formula. Second, we use the existence of the order-preserving function to show that a) is bounded above by , b) no section is mapped by onto , c) using Exercise 2, is order-preserving function that maps onto or its section. a) Let be a subset of ’s such that inequality holds. Using the transfinite induction, this subset is the whole set (if then for every : , but is the smallest element that is greater than all ’s, hence, ). b) If for some : , then there is such that . Contradiction. Therefore, for all . c) Now, is defined by the expression 2(a)(ii) and by 2(a) it is order preserving and maps onto or its section. Since it is order preserving, it is injective, so it is order preserving bijection onto or its section.
4 (a) Consider the union of the sets and extend the orders onto the union as in Exercise 8 of §10 so that every element in is less than every element in . Then, the identity is an order preserving mapping from into , and by 3, there is an order preserving injection from into a section of the union or onto the union itself. If is in the then the section is in the and has the order type of a section of , if is the least element not in then the section is equal to and has the order type of , otherwise the reverse of the injection restricted to is an order preserving injection from into a section of . Now if set has the order type of a section of set then these sets cannot have the same order type as by 2(b) a set cannot have an order type of its section, and also set cannot have the order of a section of the set for the same reason.
(b) Given (a) and the fact that there is no bijection between a countable and an uncountable sets, this is immediate.
5 (a) No set equals to its section, and if equals a section of equals a section of then the first equals a section of the last. So, non-reflexivity and transitivity hold.
(b) For any two points in there are two pairs with sets containing them and one of the pairs equals a section of the other. Therefore, both points are in the larger set and the relation is defined. Moreover if there are two pairs with sets containing both points, then one is a subsection of the other and the relation coincide. For any three elements take three pairs containing them, the largest one, and then the relations are transitive. So, is an order on . For any subset of take any point, find the pair it belongs to, and the least element of is the least element of .
6 Given the maximum principle and a set we need to construct a well-order on . Consider the relation as in 5 (the collection is not empty as, for example, there are finite well-orders). By the principle there exists a maximal ordered subcollection. Take the union of all sets in the collection — a well-ordered subset of . If there is such that it is not in then where is the extension of such that is well ordered and -greater than any other pair in the collection. This contradicts the maximality. So, and is the well-order on .
Given the well-ordering theorem and a set with a strict partial order , we define a well-order on , and by the principle of the recursive definition, we construct on such that if is -ordered and otherwise (sections are those with respect to ). Then is a maximal ordered subset. The idea is exactly as in the text: take all elements and see if you can add it to the set already defined by previous elements and keep the order. Now if some then is not ordered, and therefore is not ordered. For any two elements in one is -greater than the other and was added to as being -comparable to the other.
7 A tower is simply the construction of a well-order on on “step-by-step”. Take any tower, it has the least element , and the section of the tower by it, i.e. is empty, therefore the least element of the tower must be such that . Now take the second to least element in the tower , the section by it contains the least element only, and therefore it has to be equal to . And etc. So the proof is actually to show that the construction of the tower this way can be continued upto to the whole set .
(a) There is an order preserving injection at least one way between the towers such that the image is the whole set or a subsection (Exercise 4(a)). Suppose the injection is as in the hint. Let be a set of those elements such that . Then if then and, therefore, . By the principle of transfinite induction holds for all points in .
(b) Take and extend the relation on such that .
(c) 5(b) proves that the union is a well-ordered set. Take any in the union, there is a tower containing it. Any other tower containing it is a section of this tower or vice versa. So, in the union equals in the tower, and, therefore, holds in the union. Now from (b) it follows that the union is a tower such that .
8 (a) “Well-defined” means that the relation does not depend on the choice of to represent the class, and it does not as all pairs in one class have the same order type. Using 2(b) and 4 the relation is complete, non-reflexive and transitive.
(b) Define the map as in the hint. This is an order preserving injection (as if then is a section of ). Now, if then there is an order preserving bijection from onto a section and . Therefore, it is an order preserving bijection from onto .
(c) Take any element in a non-empty subset . And suppose is not the least element of , we show that there is one. has the same order type as and therefore there is an order preserving bijection between the two sets. is the least element in .
(d) Every well-ordered finite subset of has a different order type, so is infinite. Suppose is countable and is a bijection. Define the order on such that iff . This is a well-order, and it has the same type as on , therefore, . But from (b) we know that has the same order type as . Therefore, we conclude that has the same type as its subsection. Contradiction to (b). Note, by the way, that for any : has the same order type as and is countable. Therefore, by 4(b), the constructed well-ordered set is the minimal uncountable well-ordered set.
The same argument as in (d) can be applied to any other set . We start by considering all possible well-orders on subsets of (including itself and the empty set). We define the set of classes with the same order type and then the well-order as before, and show that each class has the same order type as the section of by this class. Since we have considered all possible well-orders on neither one can be the constructed order on , otherwise will have the same type as its section, therefore, is well-ordered set with greater cardinality than . For example, if we start with one element set (we could even start with the empty set !), then and as has the order type of . The constructed is a well-ordered two-element set.