[Search][Subject Index][MathMap][Tour][Help!]

# 03E: Set theory

## Introduction

Naive set theory considers elementary properties of the union and intersection operators -- Venn diagrams, the DeMorgan laws, elementary counting techniques such as the inclusion-exclusion principle, partially ordered sets, and so on. This is perhaps as much of set theory as the typical mathematician uses. Indeed, one may "construct" the natural numbers, real numbers, and so on in this framework. However, situations such as Russell's paradox show that some care must be taken to define what, precisely, is a set.

Axiomatic Set Theory studies the axioms used to describe sets. While alternatives have been proposed (for example the von Neumann-Bernays-Gödel and Morse-Kelley formulations), most sets of axioms for Set Theory include the Zermelo-Fraenkl axioms (ZF). Again, within this formulation one may define the natural numbers, the real numbers, and so on, and thus in principle carry out most ordinary mathematics. This formulation is rich enough to prove, for example, the Schroeder-Bernstein theorem (If X and Y are isomorphic to subsets of each other, then they are isomorphic).

However, results in mathematical logic imply it is impossible to determine whether or not these axioms are consistent using only proofs expressed in this language. Assuming they are indeed consistent, there are also statements whose truth or falsity cannot be determined from them. These statements (or their negations!) can be taken as axioms for set theory as well.

For example, Cohen's technique of forcing showed that the Axiom of Choice is independent of the other axioms of ZF. (That axiom states that for every collection of nonempty sets, there is a set containing one element from each set in the collection.) This axiom is equivalent to a number of other statements (e.g. Zorn's Lemma) whose assumption allows the proof of surprising -- even paradoxical -- results such as the Banach-Tarski sphere decomposition. Thus, some authors are careful to distinguish results which depend on this or other non-ZF axioms; most assume it (that is, they work in ZFC Set Theory).

Use of the Axiom of Choice allows the foundation of the theory of Ordinals: totally ordered sets in which every subset has a least element. (Indeed, AC is equivalent to the Well-Ordering axiom, that every set is isomorphic to an ordinal.) The ordinals may be arranged into a linear hierarchy which permits the introduction of transfinite induction. An arithmetic of ordinals (with +, *, and ^) can be defined, consistent with the arithmetic in the natural numbers (which themselves form an ordinal called \omega).

Some of these ordinals are isomorphic as sets (e.g. \omega+1 and \omega); the Cardinals are the ordinals which are not isomorphic to any of their subsets. Here again there is a theory of arithmetic. With cardinals the emphasis is typically on how large they become. For example, the Continuum Hypothesis states that the first cardinal larger than \omega is its power set (which is the same cardinality as the real line); Cohen also showed this assertion to be independent of ZF. One can look for even larger cardinals; for example, a cardinal is inaccessible if it is larger than the union or power set of any of its predecessors; there is the concept of a measurable cardinal, which cannot occur until after inaccessibly many inaccessible cardinals! The existence of these is independent of ZFC.

Somewhat related to the ordering of sets is Combinatorial Set Theory. Among significant topics here is Ramsey theory, which is certainly also interesting with finite sets. (Typical themes in this area include finding, for a given relation on a set, subsets of the set which are either all related or none related.

Descriptive set theory deals with the topological and measure-theoretic properties of the real line and related spaces. That is, beginning with the intervals on the real line we form, with unions and intersections, the Borel sets. From here we can construct non-measurable sets, for example, and other exotic examples in real analysis and general topology. The Baire Category Theorem, for example, is arguably a result in any of these three fields!

Fuzzy set theory replaces the two-valued set-membership function with a real-valued function, that is, membership is treated as a probability, or as a degree of truthfulness. Likewise one assigns a real value to assertions as an indication of their degree of truthfulness. Since most of mathematics can be interpreted in set theory, one may then also "fuzzify" other branches of math: one has for example fuzzy group theory (where G is a fuzzy set with the group theory axioms), fuzzy analysis, and fuzzy topology. This is a comparatively new field (Zadeh, 1965). The principal applications appear to be the use of fuzzy logic for decision-making, e.g. in control theory, pattern recognition, and so on.

## History

One can certainly do no better describing the history of Set Theory than the people at St Andrew's.

## Applications and related fields

The theory of finite sets is, arguably, a definition of Combinatorics. In particular, certain combinatorial topics (e.g. Ramsey theory) have important direct analogues in "combinatorial" set theory.

Some sets by nature or by fiat have additional structure; for example ordinals come equipped with a linear order (inclusion). Many other parts of axiomatic mathematics can be described as "sets with a structure"; those with simple structures often overlap considerably with (descriptive) set theory. Besides Ordered structures we mention the sets of analysis -- in Real Analysis and Measure Theory for example -- and the sets of General Topology.

Since Axiomatic Set Theory is often used to construct the natural numbers (satisfying the Peano axioms, say) it is possible to translate statements about Number Theory to Set Theory. Indeed, a fairly robust theory of arithmetic has been developed for ordinals and cardinals.

Fuzzy sets, or more precisely logic, are applied to topics in Information Theory and Artificial Intelligence since this gives a language in which to discuss decision-making.

## Subfields

• 03E02: Partition relations
• 03E04: Ordered sets and their cofinalities; pcf theory
• 03E05: Other combinatorial set theory
• 03E10: Ordinal and cardinal numbers
• 03E17: Cardinal characteristics of the continuum
• 03E20: Other classical set theory (including functions, relations, and set algebra)
• 03E25: Axiom of choice and related propositions
• 03E30: Axiomatics of classical set theory and its fragments
• 03E35: Consistency and independence results
• 03E40: Other aspects of forcing and Boolean-valued models
• 03E45: Inner models, including constructibility, ordinal definability, and core models
• 03E47: Other notions of set-theoretic definability
• 03E50: Continuum hypothesis and Martin's axiom
• 03E55: Large cardinals
• 03E60: Determinacy principles
• 03E65: Other hypotheses and axioms
• 03E70: Nonclassical and second-order set theories
• 03E72: Fuzzy set theory
• 03E75: Applications of set theory
• 03E99: None of the above, but in this section

Parent field: 03: Mathematical Logic.

Browse all (old) classifications for this area at the AMS.

## Textbooks, reference works, and tutorials

• For elementary theory consider the classic "Naive Set Theory", by Paul R. Halmos, Springer Verlag, New York, 1987. ISBN 0-3879-0092-6
• For a set of survey articles see "Surveys in set theory", edited by A. R. D. Mathias. London Mathematical Society Lecture Note Series, 87. Cambridge University Press, Cambridge-New York, 1983. 247 pp. ISBN 0-521-27733-7 MR86m:03005
• A slightly older survey: Mathias, A. R. D.: "Surrealist landscape with figures (a survey of recent results in set theory)" Period. Math. Hungar. 10 (1979), no. 2-3, 109--175. MR81b:03057
• For advanced and axiomatic topics starting at an accessible level: "Set theory, An introduction (Second edition)", by Robert L. Vaught, Birkhäuser Boston, Inc., Boston, MA, 1995 ISBN 0-8176-3697-8
• Likewise "Set theory, An introduction to independence proofs" by Kenneth Kunen, North-Holland Publishing Co., Amsterdam-New York, 1983. ISBN 0-444-86839-9
• A brief but comprehensive overview: "Notes on logic and set theory", by P.T. Johnstone, Cambridge University Press, Cambridge-New York, 1987. ISBN 0-521-33502-7; 0-521-33692-9
• A good overview is in the relevant parts (mostly Part B) of the "Handbook of mathematical logic", Logic and Foundations of Math., Vol. 90, North-Holland, Amsterdam, 1977. ISBN 0-7204-2285-X
• From the omnivorous mathematician's viewpoint: Bourbaki, N., "Theory of sets", Hermann, Paris 1968 414 pp. (MR38#5631)

For fuzzy sets:

• "Fuzzy sets and fuzzy logic", by George J. Klir and Bo Yuan, Prentice Hall PTR, Upper Saddle River, NJ, 1995. ISBN 0-13-101171-5
• "The Fuzzy Systems Handbook", by Earl Cox. ISBN 0-12-194270-8 [seen recommended as an "excellent starting point for an outsider" but not reviewed.]
• There is a Frequently Asked Questions list for Fuzzy Logic and Fuzzy Expert Systems. See also the opening page there.
• There is a mailing list known as Fuzzy-mail. (Link is to an archive.) There is also a newsgroup comp.ai.fuzzy.

## Software and tables

There is a family of programming languages known as SETL and ISETL, which allow manipulations of sets and functions. One can even perform some computations in logic using quantifiers.

• SETL Sources and Documentation
• ISETL Distribution Page

Most of the symbolic algebra software contains procedures to deal with elementary operations on finite sets.