Sets are well-determined collections that are completely characterized by their elements. Thus, two sets are equal if and only if they have exactly the same elements. The basic relation in set theory is that of elementhood, or membership.
In particular, there is only one set with no elements at all. Of course, we can actually write down all the elements of the set when there are not too many of them. In the case of infinite sets this is clearly not possible. So, if we wish to take into account the order in which the two elements of a pair are given, we need to find another way of representing the pair.
A relation that is reflexive, symmetric, and transitive is called an equivalence relation. The following are some examples. A contradiction! A set is infinite if it is not finite.
The Fractal Geometry of Nature. San Francisco: W. Mansfield, M. Introduction to Topology. Princeton, NJ: D. Van Nostrand Company. Peano, G. Sur une courbe, qui remplit toute une aire plane, Mathematische Annalen in French , 36 1 : — Smith, B. Do mountains exist? Towards an ontology of landforms. First published June 1, Stones, R. How to prove that the rationals is a countable set. Weisstein, E. Cantor Diagonal Method.
Author and Citation Info:. Topic Description:. The concept of a set. The concept of a set is natural; it is what the reader thinks it is: a well-defined collection or grouping of elements. An intuitive appreciation of it is relatively easily acquired Halmos, Generally, all members of a given set share a common characteristic; thus, it becomes straightforward to identify elements that are, or are not, members of a given set.
For example, there is a set of even positive integers and a set of odd positive integers. These two sets have no members in common. Binary relation. Set theory begins with intuitive assumptions. It posits a binary relation between an object o and a set A. Indeed, as arithmetic is based on binary operations on numbers, set theory is based on binary operations on sets. Set notation.
Sets, themselves, may also be viewed as objects; thus, the membership relation can relate sets to each other. A binary relation between two sets is the subset relation, or set inclusion. Or, the set of even positive integers is a subset of the set of positive integers. The full, given, set is a subset of itself hence the equal sign on the inclusion symbol.
If the full set is to be excluded from the set of subsets, then we use the term, proper subset, for cases where only subsets smaller than the full set are considered and notationally, the equals part of the symbol is removed. Two special sets. There are two special sets that come up often.
The empty set is one special set. The other is the "universe of discourse" or the "universal set" or the universe. Here, too, there are parallels with basic arithmetic where the "universe" might be considered as the set of all positive integers or some other infinite set.
The universal set serves as a context within which analysis takes place. Basic Binary Set Operations 1. If the intersection of two sets has no elements in common, the intersection is the empty set, and the two sets are said to be disjoint. Set difference; set complements Absolute difference : Given the universal set U and a subset A within U. This set is also called the complement of A in U , denoted A c. Relative difference : Given sets A and B within a universal set U.
It might also be referred to as the complement of A relative to B. For example, suppose U is the set of all rational numbers integers and non-integer fractions , A is the set of all positive integers, and B is the set of all positive rational numbers.
Then B — A is the set of positive non-integer fractions. Symmetric difference. For example, the symmetric difference of the set of rational numbers and the set of positive integers is the set of positive non-integer fractions together with zero and the negative rational numbers. Cartesian product Figure 1. The familiar coordinatized plane of analytic geometry is simply the Cartesian product of the real numbers, R , with itself: R x R. There are various views one might have of representing a Cartesian product.
Power set. The power set of a set A is the set whose members are all possible subsets of A, including the empty set and the entire set itself. The results, stated partially, were as follows: Train: people had used the train, and of those, had also used a car for at least one trip but not the bus , while of those had used both a car and a bus for at least one trip.
Bus: people had used the bus, and of those, had also used the train for at least one trip but not a car , while of those had used both a car and a train for at least one trip. Car: people had used a car, and of those, had also used the bus for at least one trip but not the train , while of those had used both a bus and a train for at least one trip.
Beyond Basic Set Theory: Directions 3. To compare the size of two sets, A and B, employ the following strategy: If the two sets are finite, simply count the number of elements in each, if reasonable, and compare the answers to see if they are the same size. Find a relationship between sets A and B such that each element of A corresponds to exactly one element of B and each element of B corresponds to exactly one element of A.
This relationship is called a one-to-one correspondence Birkhoff and Mac Lane, This general, systematic process holds for all sets, finite and infinite, but it is the only process that applies to infinite sets. Consider the set S 2 : If S 2 has a smallest element that is a rational number, then that cut corresponds to that rational number.
If S 2 does not have a smallest element that is a rational number, then that cut defines a unique irrational number.
One might think of it as filling a gap between S 1 and S 2. Carrolll, L. What the Tortoise Said to Achilles. Herstein, I. Topics in Algebra. New York: Blaisdell. Learning Objectives:.
Describe set theory Compare and contrast basic set theory and basic arithmetic. Compare and contrast logic and set theory Describe where you already know that set theory is used in existing GIS software Conjecture where else you might wish to see set theory used in GIS.
Instructional Assessment Questions:. Construct two-circle Venn diagrams, with optimal overlap, that show each of the following binary set relations: union, intersection, difference absolute and relative , and symmetric difference. Label them or shade them so that a reader might understand them clearly.
Generate true equations among various of the binary set relations. How many distinct regions are in each diagram? Express the answer as a power of 2. If a set A has n elements and a set B has m elements, n , m positive integers, how many elements are in the Cartesian product of A and B? Think of some real-world geographical interpretations of the concept of Cartesian product. Does a set X exist such that the power set of X is the empty set? Why or why not? What general principles might you suggest?
Why is set theory fundamental to GIS? Name specific instances in which the connection is apparent. Read the book about Flatland by Edwin Abbott. What would set theory be like in Flatland? Read the article by Smith and Mark. What might their viewpoints be like in Flatland? Read older versions or find digital versions on the Internet.
Teaching suggestions: Introduce set theory at an abstract level and make sure that students learn to think abstractly and solve abstract problems before moving on to considering applications. That way, the concepts become second-nature and students may appreciate the universality of them rather than thinking of them only in one context.
It is an approach designed to optimize flexibility and clarity of thought. Introduce a simple mapping construct and let them see where set theory lies behind the scenes, as in the example of the flu maps.
Engage them and get them to tell you where they see it. About the same time, Robert Solovay and Stanley Tennenbaum developed and used for the first time the iterated forcing technique to produce a model where the SH holds, thus showing its independence from ZFC.
This is why a forcing iteration is needed. As a result of 50 years of development of the forcing technique, and its applications to many open problems in mathematics, there are now literally thousands of questions, in practically all areas of mathematics, that have been shown independent of ZFC. These include almost all questions about the structure of uncountable sets.
One might say that the undecidability phenomenon is pervasive, to the point that the investigation of the uncountable has been rendered nearly impossible in ZFC alone see however Shelah for remarkable exceptions.
This prompts the question about the truth-value of the statements that are undecided by ZFC. Should one be content with them being undecidable? Does it make sense at all to ask for their truth-value? There are several possible reactions to this. See Hauser for a thorough philosophical discussion of the Program, and also the entry on large cardinals and determinacy for philosophical considerations on the justification of new axioms for set theory.
A central theme of set theory is thus the search and classification of new axioms. These fall currently into two main types: the axioms of large cardinals and the forcing axioms. Thus, the existence of a regular limit cardinal must be postulated as a new axiom. Such a cardinal is called weakly inaccessible. If the GCH holds, then every weakly inaccessible cardinal is strongly inaccessible.
Large cardinals are uncountable cardinals satisfying some properties that make them very large, and whose existence cannot be proved in ZFC.
The first weakly inaccessible cardinal is just the smallest of all large cardinals. Beyond inaccessible cardinals there is a rich and complex variety of large cardinals, which form a linear hierarchy in terms of consistency strength, and in many cases also in terms of outright implication.
See the entry on independence and large cardinals for more details. Much stronger large cardinal notions arise from considering strong reflection properties. A strengthening of this principle to second-order sentences yields some large cardinals. By allowing reflection for more complex second-order, or even higher-order, sentences one obtains large cardinal notions stronger than weak compactness.
All known proofs of this result use the Axiom of Choice, and it is an outstanding important question if the axiom is necessary. Another important, and much stronger large cardinal notion is supercompactness. Woodin cardinals fall between strong and supercompact. Beyond supercompact cardinals we find the extendible cardinals, the huge , the super huge , etc. The strongest large cardinal notions not known to be inconsistent, modulo ZFC, are the following:.
Large cardinals form a linear hierarchy of increasing consistency strength. In fact they are the stepping stones of the interpretability hierarchy of mathematical theories. As we already pointed out, one cannot prove in ZFC that large cardinals exist.
But everything indicates that their existence not only cannot be disproved, but in fact the assumption of their existence is a very reasonable axiom of set theory. For one thing, there is a lot of evidence for their consistency, especially for those large cardinals for which it is possible to construct an inner model.
For instance, it has a projective well ordering of the reals, and it satisfies the GCH. The existence of large cardinals has dramatic consequences, even for simply-definable small sets, like the projective sets of real numbers. Further, under a weaker large-cardinal hypothesis, namely the existence of infinitely many Woodin cardinals, Martin and Steel proved that every projective set of real numbers is determined, i.
He also showed that Woodin cardinals provide the optimal large cardinal assumptions by proving that the following two statements:.
See the entry on large cardinals and determinacy for more details and related results. Another area in which large cardinals play an important role is the exponentiation of singular cardinals. The so-called Singular Cardinal Hypothesis SCH completely determines the behavior of the exponentiation for singular cardinals, modulo the exponentiation for regular cardinals. The SCH holds above the first supercompact cardinal Solovay.
Large cardinals stronger than measurable are actually needed for this. Moreover, if the SCH holds for all singular cardinals of countable cofinality, then it holds for all singular cardinals Silver.
At first sight, MA may not look like an axiom, namely an obvious, or at least reasonable, assertion about sets, but rather like a technical statement about ccc partial orderings. It does look more natural, however, when expressed in topological terms, for it is simply a generalization of the well-known Baire Category Theorem, which asserts that in every compact Hausdorff topological space the intersection of countably-many dense open sets is non-empty.
Indeed, MA is equivalent to:. MA has many different equivalent formulations and has been used very successfully to settle a large number of open problems in other areas of mathematics. See Fremlin for many more consequences of MA and other equivalent formulations. In spite of this, the status of MA as an axiom of set theory is still unclear. Perhaps the most natural formulation of MA, from a foundational point of view, is in terms of reflection.
Writing HC for the set of hereditarily-countable sets i. Much stronger forcing axioms than MA were introduced in the s, such as J. The PFA asserts the same as MA, but for partial orderings that have a property weaker than the ccc, called properness , introduced by Shelah.
Strong forcing axioms, such as the PFA and MM imply that all projective sets of reals are determined PD , and have many other strong consequences in infinite combinatorics. The origins 2. The axioms of set theory 2. The theory of transfinite ordinals and cardinals 3. Set theory as the foundation of mathematics 5. The set theory of the continuum 6. Forcing 8.
The search for new axioms Large cardinals The origins Set theory, as a separate mathematical discipline, begins in the work of Georg Cantor. See the Supplement on Basic Set Theory for further details. See also the Supplement on Zermelo-Fraenkel Set Theory for a formalized version of the axioms and further comments.
Replacement is also an axiom schema, as definable functions are given by formulas. The theory of transfinite ordinals and cardinals In ZFC one can develop the Cantorian theory of transfinite i. Set theory as the foundation of mathematics Every mathematical object may be viewed as a set.
The search for new axioms As a result of 50 years of development of the forcing technique, and its applications to many open problems in mathematics, there are now literally thousands of questions, in practically all areas of mathematics, that have been shown independent of ZFC. He also showed that Woodin cardinals provide the optimal large cardinal assumptions by proving that the following two statements: There are infinitely many Woodin cardinals.
Bibliography Bagaria, J. Princeton: Princeton University Press.
0コメント