Basics of Algebra, Topology, and Differential Calculus by Jean Gallier - HTML preview

Chapter 31

Appendix: Zorn’s Lemma; Some

Applications

31.1

Statement of Zorn’s Lemma

Zorn’s lemma is a particularly useful form of the axiom of choice, especially for algebraic

applications. Readers who want to learn more about Zorn’s lemma and its applications to

algebra should consult either Lang [65], Appendix 2, §2 (pp. 878-884) and Chapter III, §5

(pp. 139-140), or Artin [3], Appendix §1 (pp. 588-589). For the logical ramifications of

Zorn’s lemma and its equivalence with the axiom of choice, one should consult Schwartz

[89], (Vol. 1), Chapter I, §6, or a text on set theory such as Enderton [32], Suppes [103], or

Kuratowski and Mostowski [64].

Given a set, S, a partial order, ≤, on S is a binary relation on S (i.e., ≤ ⊆ S × S) which

is

(1) reflexive, i.e., x ≤ x, for all x ∈ S,

(2) transitive, i.e, if x ≤ y and y ≤ z, then x ≤ z, for all x, y, z ∈ S, and

(3) antisymmetric, i.e, if x ≤ y and y ≤ x, then x = y, for all x, y ∈ S.

A pair (S, ≤), where ≤ is a partial order on S, is called a partially ordered set or poset.

Given a poset, (S, ≤), a subset, C, of S is totally ordered or a chain if for every pair of

elements x, y ∈ C, either x ≤ y or y ≤ x. The empty set is trivially a chain. A subset, P ,

(empty or not) of S is bounded if there is some b ∈ S so that x ≤ b for all x ∈ P . Observe

that the empty subset of S is bounded if and only if S is nonempty. A maximal element of

P is an element, m ∈ P , so that m ≤ x implies that m = x, for all x ∈ P . Zorn’s lemma

can be stated as follows:

Lemma 31.1. Given a partially ordered set, (S, ≤), if every chain is bounded, then S has a

maximal element.

843

844

CHAPTER 31. APPENDIX: ZORN’S LEMMA; SOME APPLICATIONS

Proof. See any of Schwartz [89], Enderton [32], Suppes [103], or Kuratowski and Mostowski

[64].

Remark: As we noted, the hypothesis of Zorn’s lemma implies that S is nonempty (since

the empty set must be bounded). A partially ordered set such that every chain is bounded

is sometimes called inductive.

We now give some applications of Zorn’s lemma.

31.2

Proof of the Existence of a Basis in a Vector Space

Using Zorn’s lemma, we can prove that Theorem 2.7 holds for arbitrary vector spaces, and

not just for finitely generated vector spaces, as promised in Chapter 2.

Theorem 31.2. Given any family, S = (ui)i∈I, generating a vector space E and any linearly

independent subfamily, L = (uj)j∈J, of S (where J ⊆ I), there is a basis, B, of E such that

L ⊆ B ⊆ S.

Proof. Consider the set L of linearly independent families, B, such that L ⊆ B ⊆ S. Since

L ∈ L, this set is nonempty. We claim that L is inductive. Consider any chain, (Bl)l∈Λ, of

linearly independent families Bl in L, and look at B =

B

l∈Λ

l. The family B is of the form

B = (vh)h∈H, for some index set H, and it must be linearly independent. Indeed, if this was

not true, there would be some family (λh)h∈H of scalars, of finite support, so that

λhvh = 0,

h∈H

where not all λh are zero. Since B =

B

l∈Λ

l and only finitely many λh are nonzero, there

is a finite subset, F , of Λ, so that vh ∈ Bf iff λ

h

h = 0. But (Bl)l∈Λ is a chain, and if we let

f = max{fh | fh ∈ F }, then vh ∈ Bf , for all vh for which λh = 0. Thus,

λhvh = 0

h∈H

would be a nontrivial linear dependency among vectors from Bf , a contradiction. Therefore,

B ∈ L, and since B is obviously an upper bound for the Bl’s, we have proved that L

is inductive. By Zorn’s lemma (Lemma 31.1), the set L has some maximal element, say

B = (uh)h∈H. The rest of the proof is the same as in the proof of Theorem 2.7, but we

repeat it for the reader’s convenience. We claim that B generates E. Indeed, if B does not

generate E, then there is some up ∈ S that is not a linear combination of vectors in B (since

S generates E), with p /

∈ H. Then, by Lemma 2.6, the family B = (uh)h∈H∪{p} is linearly

independent, and since L ⊆ B ⊂ B ⊆ S, this contradicts the maximality of B. Thus, B is

a basis of E such that L ⊆ B ⊆ S.

Another important application of Zorn’s lemma is the existence of maximal ideals.

31.3. EXISTENCE OF MAXIMAL PROPER IDEALS

845

31.3

Existence of Maximal Ideals Containing a Given

Proper Ideal

Let A be a commutative ring with identity element. Recall that an ideal A in A is a proper

ideal if A = A. The following theorem holds:

Theorem 31.3. Given any proper ideal, A ⊆ A, there is a maximal ideal, B, containing A.

Proof. Let I be the set of all proper ideals, B, in A that contain A. The set I is nonempty,

since A ∈ I. We claim that I is inductive. Consider any chain (Ai)i∈I of ideals Ai in A.

One can easily check that B =

A

i∈I

i is an ideal. Furthermore, B is a proper ideal, since

otherwise, the identity element 1 would belong to B = A, and so, we would have 1 ∈ Ai for

some i, which would imply Ai = A, a contradiction. Also, B is obviously an upper bound

for all the Ai’s. By Zorn’s lemma (Lemma 31.1), the set I has a maximal element, say B,

and B is a maximal ideal containing A.

846

CHAPTER 31. APPENDIX: ZORN’S LEMMA; SOME APPLICATIONS

Bibliography

[1] Lars V. Ahlfors and Leo Sario. Riemann Surfaces. Princeton Math. Series, No. 2.

Princeton University Press, 1960.

[2] Emil Artin. Geometric Algebra. Wiley Interscience, first edition, 1957.

[3] Michael Artin. Algebra. Prentice Hall, first edition, 1991.

[4] M. F. Atiyah and I. G. Macdonald. Introduction to Commutative Algebra. Addison

Wesley, third edition, 1969.

[5] A. Avez. Calcul Différentiel. Masson, first edition, 1991.

[6] Marcel Berger. Géométrie 1. Nathan, 1990. English edition: Geometry 1, Universitext,

Springer Verlag.

[7] Marcel Berger. Géométrie 2. Nathan, 1990. English edition: Geometry 2, Universitext,

Springer Verlag.

[8] Marcel Berger and Bernard Gostiaux. Géométrie différentielle: variétés, courbes et

surfaces. Collection Mathématiques. Puf, second edition, 1992. English edition: Dif-

ferential geometry, manifolds, curves, and surfaces, GTM No. 115, Springer Verlag.

[9] Rolf Berndt. An Introduction to Symplectic Geometry. Graduate Studies in Mathe-

matics, Vol. 26. AMS, first edition, 2001.

[10] J.E. Bertin. Algèbre linéaire et géométrie classique. Masson, first edition, 1981.

[11] Nicolas Bourbaki. Algèbre, Chapitre 9. Eléments de Mathématiques. Hermann, 1968.

[12] Nicolas Bourbaki. Algèbre, Chapitres 1-3. Eléments de Mathématiques. Hermann,

1970.

[13] Nicolas Bourbaki. Algèbre, Chapitres 4-7. Eléments de Mathématiques. Masson, 1981.

[14] Nicolas Bourbaki. Espaces Vectoriels Topologiques. Eléments de Mathématiques. Mas-

son, 1981.

847

848

BIBLIOGRAPHY

[15] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University

Press, first edition, 2004.

[16] Glen E Bredon. Topology and Geometry. GTM No. 139. Springer Verlag, first edition,

1993.

[17] G. Cagnac, E. Ramis, and J. Commeau. Mathématiques Spéciales, Vol. 3, Géométrie.

Masson, 1965.

[18] Henri Cartan. Cours de Calcul Différentiel. Collection Méthodes. Hermann, 1990.

[19] Henri Cartan. Differential Forms. Dover, first edition, 2006.

[20] Claude Chevalley. The Algebraic Theory of Spinors and Clifford Algebras. Collected

Works, Vol. 2. Springer, first edition, 1997.

[21] Yvonne Choquet-Bruhat, Cécile DeWitt-Morette, and Margaret Dillard-Bleick. Anal-

ysis, Manifolds, and Physics, Part I: Basics. North-Holland, first edition, 1982.

[22] P.G. Ciarlet. Introduction to Numerical Matrix Analysis and Optimization. Cambridge

University Press, first edition, 1989. French edition: Masson, 1994.

[23] Timothée Cour and Jianbo Shi. Solving markov random fields with spectral relaxation.

In Marita Meila and Xiaotong Shen, editors, Artifical Intelligence and Statistics. Soci-

ety for Artificial Intelligence and Statistics, 2007.

[24] H.S.M. Coxeter. Introduction to Geometry. Wiley, second edition, 1989.

[25] James W. Demmel. Applied Numerical Linear Algebra. SIAM Publications, first edi-

tion, 1997.

[26] Jean Dieudonné. Algèbre Linéaire et Géométrie Elémentaire. Hermann, second edition,

1965.

[27] Jacques Dixmier. General Topology. UTM. Springer Verlag, first edition, 1984.

[28] Manfredo P. do Carmo. Differential Geometry of Curves and Surfaces. Prentice Hall,

1976.

[29] Manfredo P. do Carmo. Riemannian Geometry. Birkhäuser, second edition, 1992.

[30] David S. Dummit and Richard M. Foote. Abstract Algebra. Wiley, second edition,

1999.

[31] Gerald A. Edgar. Measure, Topology, and Fractal Geometry. Undergraduate Texts in

Mathematics. Springer Verlag, first edition, 1992.

[32] Herbert B. Enderton. Elements of Set Theory. Academic Press, 1997.

BIBLIOGRAPHY

849

[33] Charles L. Epstein. Introduction to the Mathematics of Medical Imaging. SIAM, second

edition, 2007.

[34] Gerald Farin. Curves and Surfaces for CAGD. Academic Press, fourth edition, 1998.

[35] Olivier Faugeras. Three-Dimensional Computer Vision, A geometric Viewpoint. the

MIT Press, first edition, 1996.

[36] James Foley, Andries van Dam, Steven Feiner, and John Hughes. Computer Graphics.

Principles and Practice. Addison-Wesley, second edition, 1993.

[37] David A. Forsyth and Jean Ponce. Computer Vision: A Modern Approach. Prentice

Hall, first edition, 2002.

[38] Jean Fresnel. Méthodes Modernes En Géométrie. Hermann, first edition, 1998.

[39] William Fulton. Algebraic Topology, A first course. GTM No. 153. Springer Verlag,

first edition, 1995.

[40] William Fulton and Joe Harris. Representation Theory, A first course. GTM No. 129.

Springer Verlag, first edition, 1991.

[41] Jean H. Gallier. Curves and Surfaces In Geometric Modeling: Theory And Algorithms.

Morgan Kaufmann, 1999.

[42] Jean H. Gallier. Geometric Methods and Applications, For Computer Science and

Engineering. TAM, Vol. 38. Springer, second edition, 2011.

[43] Walter Gander, Gene H. Golub, and Urs von Matt. A constrained eigenvalue problem.

Linear Algebra and its Applications, 114/115:815–839, 1989.

[44] F.R. Gantmacher. The Theory of Matrices, Vol. I. AMS Chelsea, first edition, 1977.

[45] Roger Godement. Cours d’Algèbre. Hermann, first edition, 1963.

[46] Gene H. Golub. Some modified eigenvalue problems. SIAM Review, 15(2):318–334,

1973.

[47] H. Golub, Gene and F. Van Loan, Charles. Matrix Computations. The Johns Hopkins

University Press, third edition, 1996.

[48] A. Gray. Modern Differential Geometry of Curves and Surfaces. CRC Press, second

edition, 1997.

[49] Donald T. Greenwood. Principles of Dynamics. Prentice Hall, second edition, 1988.

[50] Larry C. Grove. Classical Groups and Geometric Algebra. Graduate Studies in Math-

ematics, Vol. 39. AMS, first edition, 2002.

850

BIBLIOGRAPHY

[51] Jacques Hadamard. Leçons de Géométrie Elémentaire. I Géométrie Plane. Armand

Colin, thirteenth edition, 1947.

[52] Jacques Hadamard. Leçons de Géométrie Elémentaire. II Géométrie dans l’Espace.

Armand Colin, eighth edition, 1949.

[53] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical

Learning: Data Mining, Inference, and Prediction. Springer, second edition, 2009.

[54] D. Hilbert and S. Cohn-Vossen. Geometry and the Imagination. Chelsea Publishing

Co., 1952.

[55] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press,

first edition, 1990.

[56] Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge Uni-

versity Press, first edition, 1994.

[57] Nathan Jacobson. Basic Algebra I. Freeman, second edition, 1985.

[58] Ramesh Jain, Rangachar Katsuri, and Brian G. Schunck. Machine Vision. McGraw-

Hill, first edition, 1995.

[59] Jürgen Jost. Riemannian Geometry and Geometric Analysis. Universitext. Springer

Verlag, fourth edition, 2005.

[60] Hoffman Kenneth and Kunze Ray. Linear Algebra. Prentice Hall, second edition, 1971.

[61] D. Kincaid and W. Cheney. Numerical Analysis. Brooks/Cole Publishing, second

edition, 1996.

[62] Anthony W. Knapp. Lie Groups Beyond an Introduction. Progress in Mathematics,

Vol. 140. Birkhäuser, second edition, 2002.

[63] Erwin Kreyszig. Differential Geometry. Dover, first edition, 1991.

[64] K. Kuratowski and A. Mostowski. Set Theory. Studies in Logic, Vol. 86. Elsevier,

1976.

[65] Serge Lang. Algebra. Addison Wesley, third edition, 1993.

[66] Serge Lang. Differential and Riemannian Manifolds. GTM No. 160. Springer Verlag,

third edition, 1995.

[67] Serge Lang. Real and Functional Analysis. GTM 142. Springer Verlag, third edition,

1996.

[68] Serge Lang. Undergraduate Analysis. UTM. Springer Verlag, second edition, 1997.

BIBLIOGRAPHY

851

[69] Peter Lax. Linear Algebra and Its Applications. Wiley, second edition, 2007.

[70] Saunders Mac Lane and Garrett Birkhoff. Algebra. Macmillan, first edition, 1967.

[71] Ib Madsen and Jorgen Tornehave. From Calculus to Cohomology. De Rham Cohomol-

ogy and Characteristic Classes. Cambridge University Press, first edition, 1998.

[72] M.-P. Malliavin. Algèbre Commutative. Applications en Géométrie et Théorie des

Nombres. Masson, first edition, 1985.

[73] Jerrold E. Marsden and J.R. Hughes, Thomas. Mathematical Foundations of Elasticity.

Dover, first edition, 1994.

[74] William S. Massey. Algebraic Topology: An Introduction. GTM No. 56. Springer

Verlag, second edition, 1987.

[75] William S. Massey. A Basic Course in Algebraic Topology. GTM No. 127. Springer

Verlag, first edition, 1991.

[76] Dimitris N. Metaxas. Physics-Based Deformable Models. Kluwer Academic Publishers,

first edition, 1997.

[77] Carl D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM, first edition, 2000.

[78] John W. Milnor. Topology from the Differentiable Viewpoint. The University Press of

Virginia, second edition, 1969.

[79] John W. Milnor and James D. Stasheff. Characteristic Classes. Annals of Math. Series,

No. 76. Princeton University Press, first edition, 1974.

[80] Shigeyuki Morita. Geometry of Differential Forms. Translations of Mathematical

Monographs No 201. AMS, first edition, 2001.

[81] James R. Munkres. Topology, a First Course. Prentice Hall, first edition, 1975.

[82] James R. Munkres. Analysis on Manifolds. Addison Wesley, 1991.

[83] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery. An Introduction to the

Theory of Numbers. Wiley, fifth edition, 1991.

[84] Joseph O’Rourke. Computational Geometry in C. Cambridge University Press, second

edition, 1998.

[85] Dan Pedoe. Geometry, A comprehensive Course. Dover, first edition, 1988.

[86] Eugène Rouché and Charles de Comberousse. Traité de Géométrie. Gauthier-Villars,

seventh edition, 1900.

852

BIBLIOGRAPHY

[87] Pierre Samuel. Projective Geometry. Undergraduate Texts in Mathematics. Springer

Verlag, first edition, 1988.

[88] Laurent Schwartz. Topologie Générale et Analyse Fonctionnelle. Collection Enseigne-

ment des Sciences. Hermann, 1980.

[89] Laurent Schwartz. Analyse I. Théorie des Ensembles et Topologie. Collection En-

seignement des Sciences. Hermann, 1991.

[90] Laurent Schwartz. Analyse II. Calcul Différentiel et Equations Différentielles. Collec-

tion Enseignement des Sciences. Hermann, 1992.

[91] H. Seifert and W. Threlfall. A Textbook of Topology. Academic Press, first edition,

1980.

[92] Denis Serre. Matrices, Theory and Applications. GTM No. 216. Springer Verlag, second

edition, 2010.

[93] Jean-Pierre Serre. A Course in Arithmetic. Graduate Text in Mathematics, No. 7.

Springer, first edition, 1973.

[94] Igor R. Shafarevich. Basic Algebraic Geometry 1. Springer Verlag, second edition,

1994.

[95] Ernst Snapper and Troyer Robert J. Metric Affine Geometry. Dover, first edition,

1989.

[96] Harold M. Stark. An Introduction to Number Theory. MIT Press, first edition, 1994.

Eighth Printing.

[97] G.W. Stewart. On the early history of the singular value decomposition. SIAM review,

35(4):551–566, 1993.

[98] J.J. Stoker. Differential Geometry. Wiley Classics. Wiley-Interscience, first edition,

1989.

[99] Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for Computer

Graphics Theory and Applications. Morgan Kaufmann, first edition, 1996.

[100] Gilbert Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press, first

edition, 1986.

[101] Gilbert Strang. Linear Algebra and its Applications. Saunders HBJ, third edition,

1988.

[102] Gilbert Strang and Nguyen Truong. Wavelets and Filter Banks. Wellesley-Cambridge

Press, second edition, 1997.

BIBLIOGRAPHY

853

[103] Patrick Suppes. Axiomatic Set Theory. Dover, 1972.

[104] Donald E. Taylor. The Geometry of the Classical Groups. Sigma Series in Pure Math-

ematics, Vol. 9. Heldermann Verlag Berlin, 1992.

[105] Claude Tisseron. Géométries affines, projectives, et euclidiennes. Hermann, first edi-

tion, 1994.

[106] L.N. Trefethen and D. Bau III. Numerical Linear Algebra. SIAM Publications, first

edition, 1997.

[107] Emanuele Trucco and Alessandro Verri. Introductory Techniques for 3D Computer

Vision. Prentice-Hall, first edition, 1998.

[108] B.L. Van Der Waerden. Algebra, Vol. 1. Ungar, seventh edition, 1973.

[109] Frank Warner. Foundations of Differentiable Manifolds and Lie Groups. GTM No. 94.

Springer Verlag, first edition, 1983.

[110] Ernst Witt. Theorie der quadratischen Formen in beliebigen Körpern. J. Reine Angew.

Math., 176:31–44, 1936.

[111] Stella X. Yu and Jianbo Shi. Grouping with bias. In Thomas G. Dietterich, Sue Becker,

and Zoubin Ghahramani, editors, Neural Information Processing Systems, Vancouver,

Canada, 3-8 Dec. 2001. MIT Press, 2001.

[112] Oscar Zariski and Pierre Samuel. Commutative Algebra, Vol I. GTM No. 28. Springer

Verlag, first edition, 1975.