Naive set theory is any of several theories of sets used in the discussion of thefoundations of mathematics.[3]Unlikeaxiomatic set theories, which are defined usingformal logic, naive set theory is defined informally, innatural language. It describes the aspects ofmathematical sets familiar indiscrete mathematics (for exampleVenn diagrams and symbolic reasoning about theirBoolean algebra), and suffices for the everyday use of set theory concepts in contemporary mathematics.[4]
Sets are of great importance in mathematics; in modern formal treatments, most mathematical objects (numbers,relations,functions, etc.) are defined in terms of sets. Naive set theory suffices for many purposes, while also serving as a stepping stone towards more formal treatments.
Anaive theory in the sense of "naive set theory" is a non-formalized theory, that is, a theory that usesnatural language to describe sets and operations on sets. Such theory treats sets as platonic absolute objects. The wordsand,or,if ... then,not,for some,for every are treated as in ordinary mathematics. As a matter of convenience, use of naive set theory and its formalism prevails even in higher mathematics – including in more formal settings of set theory itself.
The first development ofset theory was a naive set theory. It was created at the end of the 19th century byGeorg Cantor as part of his study ofinfinite sets[5] and developed as a formal but inconsistent system[6] byGottlob Frege in hisGrundgesetze der Arithmetik.
Naive set theory may refer to several very distinct notions. It may refer to
The assumption that any property may be used to form a set, without restriction, leads toparadoxes. One common example isRussell's paradox: there is no set consisting of "all sets that do not contain themselves". Thus consistent systems of (either naive or formal) set theory must include some limitations on the principles which can be used to form sets.
Some believe thatGeorg Cantor's set theory was not actually implicated in the set-theoretic paradoxes (see Frápolli 1991). One difficulty in determining this with certainty is that Cantor did not provide an axiomatization of his system. By 1899, Cantor was aware of some of the paradoxes following from unrestricted interpretation of his theory, for instanceCantor's paradox[9] and theBurali-Forti paradox,[10] and did not believe that they discredited his theory.[11] Cantor's paradox can actually be derived from the above (false) assumption—that any propertyP(x) may be used to form a set—using forP(x) "x is acardinal number". Frege explicitly axiomatized a theory in which a formalized version of naive set theory can be interpreted, and it isthis formal theory whichBertrand Russell actually addressed when he presented his paradox, not necessarily a theory Cantor—who, as mentioned, was aware of several paradoxes—presumably had in mind.
Axiomatic set theory was developed in response to these early attempts to understand sets, with the goal of determining precisely what operations were allowed and when.
A naive set theory is notnecessarily inconsistent, if it correctly specifies the sets allowed to be considered. This can be done by the means of definitions, which are implicit axioms. It is possible to state all the axioms explicitly, as in the case of Halmos'Naive Set Theory, which is actually an informal presentation of the usual axiomaticZermelo–Fraenkel set theory. It is "naive" in that the language and notations are those of ordinary informal mathematics, and in that it does not deal with consistency or completeness of the axiom system.
Likewise, an axiomatic set theory is not necessarily consistent: not necessarily free of paradoxes. It follows fromGödel's incompleteness theorems that a sufficiently complicatedfirst-order logic system (which includes most common axiomatic set theories) cannot be proved consistent[12] from within the theory itself – unless it is actually inconsistent. However, the common axiomatic systems are generally believed to be consistent; by their axioms they do excludesome paradoxes, likeRussell's paradox. Based onGödel's theorem, it is just not known – and never can be – if there areno paradoxes at all in these theories or in any sufficiently complicated first-order set theory, again, unless such theories are actually inconsistent. It should be mentioned, however, that results inproof theoreticalordinal analysis are sometimes interpreted asconsistency proofs.
The termnaive set theory is still today also used in some literature[13] to refer to the set theories studied by Frege and Cantor, rather than to the informal counterparts of modern axiomatic set theory.
The choice between an axiomatic approach and other approaches is largely a matter of convenience. In everyday mathematics the best choice may be informal use of axiomatic set theory. References to particular axioms typically then occur only when demanded by tradition, e.g. theaxiom of choice is often mentioned when used. Likewise, formal proofs occur only when warranted by exceptional circumstances. This informal usage of axiomatic set theory can have (depending on notation) precisely theappearance of naive set theory as outlined below. It is considerably easier to read and write (in the formulation of most statements, proofs, and lines of discussion) and is less error-prone than a strictly formal approach.
In naive set theory, aset is described as a well-defined collection of objects. These objects are called theelements ormembers of the set. Objects can be anything: numbers, people, other sets, etc. For instance, 4 is a member of the set of all evenintegers. Clearly, the set of even numbers is infinitely large; there is no requirement that a set be finite.
The definition of sets goes back toGeorg Cantor. He wrote in his 1915 articleBeiträge zur Begründung der transfiniten Mengenlehre:
Unter einer 'Menge' verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die 'Elemente' von M genannt werden) zu einem Ganzen.
— Georg Cantor
A set is a gathering together into a whole of definite, distinct objects of our perception or of our thought—which are called elements of the set.
— Georg Cantor
It doesnot follow from this definitionhow sets can be formed, and what operations on sets again will produce a set. The term "well-defined" in "well-defined collection of objects" cannot, by itself, guarantee the consistency and unambiguity of what exactly constitutes and what does not constitute a set. Attempting to achieve this would be the realm of axiomatic set theory or of axiomaticclass theory.
The problem, in this context, with informally formulated set theories, not derived from (and implying) any particular axiomatic theory, is that there may be several widely differing formalized versions, that have both different sets and different rules for how new sets may be formed, that all conform to the original informal definition. For example, Cantor's verbatim definition allows for considerable freedom in what constitutes a set. On the other hand, it is unlikely that Cantor was particularly interested in sets containing cats and dogs, but rather only in sets containing purely mathematical objects. An example of such a class of sets could be thevon Neumann universe. But even when fixing the class of sets under consideration, it is not always clear which rules for set formation are allowed without introducing paradoxes.
For the purpose of fixing the discussion below, the term "well-defined" should instead be interpreted as anintention, with either implicit or explicit rules (axioms or definitions), to rule out inconsistencies. The purpose is to keep the often deep and difficult issues of consistency away from the, usually simpler, context at hand. An explicit ruling out ofall conceivable inconsistencies (paradoxes) cannot be achieved for an axiomatic set theory anyway, due to Gödel's second incompleteness theorem, so this does not at all hamper the utility of naive set theory as compared to axiomatic set theory in the simple contexts considered below. It merely simplifies the discussion. Consistency is henceforth taken for granted unless explicitly mentioned.
Ifx is a member of a setA, then it is also said thatxbelongs toA, or thatx is inA. This is denoted byx ∈ A. The symbol ∈ is a derivation from the lowercase Greek letterepsilon, "ε", introduced byGiuseppe Peano in 1889 and is the first letter of the wordἐστί (means "is"). The symbol ∉ is often used to writex ∉ A, meaning "x is not in A".
Two setsA andB are defined to beequal when they have precisely the same elements, that is, if every element ofA is an element ofB and every element ofB is an element ofA. (Seeaxiom of extensionality.) Thus a set is completely determined by its elements; the description is immaterial. For example, the set with elements 2, 3, and 5 is equal to the set of allprime numbers less than 6.If the setsA andB are equal, this is denoted symbolically asA = B (as usual).
Theempty set, denoted as and sometimes, is a set with no members at all. Because a set is determined completely by its elements, there can be only one empty set. (Seeaxiom of empty set.)[14] Although the empty set has no members, it can be a member of other sets. Thus, because the former has no members and the latter has one member.[15]
The simplest way to describe a set is to list its elements between curly braces (known as defining a setextensionally). Thus{1, 2} denotes the set whose only elements are1 and2.(Seeaxiom of pairing.)Note the following points:
(These are consequences of the definition of equality in the previous section.)
This notation can be informally abused by saying something like{dogs} to indicate the set of all dogs, but this example would usually be read by mathematicians as "the set containing the single elementdogs".
An extreme (but correct) example of this notation is{}, which denotes the empty set.
The notation{x :P(x)}, or sometimes{x |P(x)}, is used to denote the set containing all objects for which the conditionP holds (known as defining a setintensionally).For example,{x |x ∈R} denotes the set ofreal numbers,{x |x has blonde hair} denotes the set of everything with blonde hair.
This notation is calledset-builder notation (or "set comprehension", particularly in the context ofFunctional programming).Some variants of set builder notation are:
Given two setsA andB,A is asubset ofB if every element ofA is also an element ofB.In particular, each setB is a subset of itself; a subset ofB that is not equal toB is called aproper subset.
IfA is a subset ofB, then one can also say thatB is asuperset ofA, thatA iscontained inB, or thatBcontainsA. In symbols,A ⊆B means thatA is a subset ofB, andB ⊇A means thatB is a superset ofA.Some authors use the symbols ⊂ and ⊃ for subsets, and others use these symbols only forproper subsets. For clarity, one can explicitly use the symbols ⊊ and ⊋ to indicate non-equality.
As an illustration, letR be the set of real numbers, letZ be the set of integers, letO be the set of odd integers, and letP be the set of current or formerU.S. Presidents.ThenO is a subset ofZ,Z is a subset ofR, and (hence)O is a subset ofR, where in all casessubset may even be read asproper subset.Not all sets are comparable in this way. For example, it is not the case either thatR is a subset ofP nor thatP is a subset ofR.
It follows immediately from the definition of equality of sets above that, given two setsA andB,A =B if and only ifA ⊆B andB ⊆A. In fact this is often given as the definition of equality. Usually when trying toprove that two sets are equal, one aims to show these two inclusions. Theempty set is a subset of every set (the statement that all elements of the empty set are also members of any setA isvacuously true).
The set of all subsets of a given setA is called thepower set ofA and is denoted by or; the "P" is sometimes in ascript font:. If the setA hasn elements, then will have elements.
In certain contexts, one may consider all sets under consideration as being subsets of some givenuniversal set.For instance, when investigating properties of thereal numbersR (and subsets ofR),R may be taken as the universal set. A true universal set is not included in standard set theory (seeParadoxes below), but is included in some non-standard set theories.
Given a universal setU and a subsetA ofU, thecomplement ofA (inU) is defined as
In other words,AC ("A-complement"; sometimes simplyA', "A-prime" ) is the set of all members ofU which are not members ofA.Thus withR,Z andO defined as in the section on subsets, ifZ is the universal set, thenOC is the set of even integers, while ifR is the universal set, thenOC is the set of all real numbers that are either even integers or not integers at all.
Given two setsA andB, theirunion is the set consisting of all objects which are elements ofA or ofB or of both (seeaxiom of union). It is denoted byA ∪B.
Theintersection ofA andB is the set of all objects which are both inA and inB. It is denoted byA ∩B.
Finally, therelative complement ofB relative toA, also known as theset theoretic difference ofA andB, is the set of all objects that belong toA butnot toB. It is written asA ∖B orA −B.
Symbolically, these are respectively
The setB doesn't have to be a subset ofA forA ∖B to make sense; this is the difference between the relative complement and the absolute complement (AC =U ∖A) from the previous section.
To illustrate these ideas, letA be the set of left-handed people, and letB be the set of people with blond hair. ThenA ∩B is the set of all left-handed blond-haired people, whileA ∪B is the set of all people who are left-handed or blond-haired or both.A ∖B, on the other hand, is the set of all people that are left-handed but not blond-haired, whileB ∖A is the set of all people who have blond hair but aren't left-handed.
Now letE be the set of all human beings, and letF be the set of all living things over 1000 years old. What isE ∩F in this case? No living human being isover 1000 years old, soE ∩F must be theempty set {}.
For any setA, the power set is aBoolean algebra under the operations of union and intersection.
Intuitively, anordered pair is simply a collection of two objects such that one can be distinguished as thefirst element and the other as thesecond element, and having the fundamental property that, two ordered pairs are equal if and only if theirfirst elements are equal and theirsecond elements are equal.
Formally, an ordered pair withfirst coordinatea, andsecond coordinateb, usually denoted by (a,b), can be defined as the set
It follows that, two ordered pairs (a,b) and (c,d) are equal if and only ifa =c andb =d.
Alternatively, an ordered pair can be formally thought of as a set {a,b} with atotal order.
(The notation (a,b) is also used to denote anopen interval on thereal number line, but the context should make it clear which meaning is intended. Otherwise, the notation ]a,b[ may be used to denote the open interval whereas (a,b) is used for the ordered pair).
IfA andB are sets, then theCartesian product (or simplyproduct) is defined to be:
That is,A ×B is the set of all ordered pairs whose first coordinate is an element ofA and whose second coordinate is an element ofB.
This definition may be extended to a setA ×B ×C of ordered triples, and more generally to sets of orderedn-tuples for any positive integern.It is even possible to define infiniteCartesian products, but this requires a more recondite definition of the product.
Cartesian products were first developed byRené Descartes in the context ofanalytic geometry. IfR denotes the set of allreal numbers, thenR2 :=R ×R represents theEuclidean plane andR3 :=R ×R ×R represents three-dimensionalEuclidean space.
There are some ubiquitous sets for which the notation is almost universal. Some of these are listed below. In the list,a,b, andc refer tonatural numbers, andr ands arereal numbers.
The unrestricted formation principle of sets referred to as theaxiom schema of unrestricted comprehension,
is the source of several early appearing paradoxes:
If the axiom schema of unrestricted comprehension is weakened to theaxiom schema of specification oraxiom schema of separation,
then all the above paradoxes disappear.[16] There is a corollary. With the axiom schema of separation as an axiom of the theory, it follows, as a theorem of the theory:
Or, more spectacularly (Halmos' phrasing[17]): There is nouniverse.Proof: Suppose that it exists and call itU. Now apply the axiom schema of separation withX =U and forP(x) usex ∉x. This leads to Russell's paradox again. HenceU cannot exist in this theory.[16]
Related to the above constructions is formation of the set
where the statement following the implication certainly is false. It follows, from the definition ofY, using the usual inference rules (and some afterthought when reading the proof in the linked article below) both thatY ∈Y → {} ≠ {} andY ∈Y holds, hence{} ≠ {}. This isCurry's paradox.
It is (perhaps surprisingly) not the possibility ofx ∈x that is problematic. It is again the axiom schema of unrestricted comprehension allowing(x ∈x) → {} ≠ {} forP(x). With the axiom schema of specification instead of unrestricted comprehension, the conclusionY ∈Y does not hold and hence{} ≠ {} is not a logical consequence.
Nonetheless, the possibility ofx ∈x is often removed explicitly[18] or, e.g. in ZFC, implicitly,[19] by demanding theaxiom of regularity to hold.[19] One consequence of it is
or, in other words, no set is an element of itself.[20]
The axiom schema of separation is simply too weak (while unrestricted comprehension is a very strong axiom—too strong for set theory) to develop set theory with its usual operations and constructions outlined above.[16] The axiom of regularity is of a restrictive nature as well. Therefore, one is led to the formulation of other axioms to guarantee the existence of enough sets to form a set theory. Some of these have been described informally above and many others are possible. Not all conceivable axioms can be combined freely into consistent theories. For example, theaxiom of choice of ZFC is incompatible with the conceivable "every set of reals isLebesgue measurable". The former implies the latter is false.
{{citation}}: CS1 maint: location missing publisher (link){{citation}}: CS1 maint: location missing publisher (link)| Overview |  | |
|---|---|---|
| Axioms | ||
| Operations | ||
| ||
| Set types | ||
| Theories | ||
| ||
| Set theorists | ||
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||