[Search] |

ABOUT:
[Introduction]POINTERS:
[Texts]## 04: Set theory |

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.

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

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.

- 04A03: Set algebra
- 04A05: Relations, functions, See also 08A02
- 04A10: Ordinal and cardinal numbers; generalizations, See Also 03E10
- 04A15: Descriptive set theory; Borel classifications, Suslin schemes, etc., See also 03E15, 26A21, 28A05, 54H05
- 04A20: Combinatorial set theory, See also 03E05, 05A05; filters
- 04A25: Axiom of choice and equivalent propositions (Zorn's lemma, etc.), See also 03E25
- 04A30: Continuum hypothesis, generalized continuum hypothesis, See also 03E50, 54A25
- 04A72: Fuzzy sets, fuzzy relations, See also 03E72, 94D05, For fuzzy versions, See specific sections
- 04A99: Miscellaneous topics

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

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

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.

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

- Here are the AMS and Goettingen resource pages for area 04.
- Long list of Set Theory links
- Mountain Math's Set theory summary
- Issues in common-sense set theory
- Applications of Fuzzy Set Theory
- Applications of fuzzy logic to clustering and image processing

- Listing of the axioms of ZFC for set theory (Zermelo-Fraenkl and Choice)
- Independence of the Axiom of Foundation
- Equivalents of the Axiom of Choice and the Prime Ideal Theorem of Boolean algebra. (Does not include normality of linearly orderable topological spaces)
- What is Russell's paradox (en français)
- Practical application of set theory axioms :-)
- What does it mean to say one set is more infinite than another?
- Defining (Dedekind) infinite in the absence of the Axiom of Choice
- Consequences of the Axiom of Choice include the Banach-Tarski paradox.
- [Offsite] Home page for the Axiom of Choice.
- "Natural" instances of cardinals greater than aleph_1 in topology, analysis, and set theory.
- Weakly inaccessible cardinals (Regular limit cardinals -- equal to their own cofinality)
- Ineffable cardinals
- Defining cardinals in the absence of the Axiom of Choice
- What are the definable real numbers? (compared to the computable or constructible ones)

Last modified 1999/05/12 by Dave Rusin. Mail: feedback@math-atlas.org