Naive set theory

A naive theory in the sense of "naive set theory" is a non-formalized theory, that is, a theory that uses natural language to describe sets and operations on sets. The words and, 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 of set theory was a naive set theory. It was created at the end of the 19th century by Georg Cantor as part of his study of infinite sets[5] and developed by Gottlob Frege in his Grundgesetze der Arithmetik.

Naive set theory may refer to several very distinct notions. It may refer to

• Informal presentation of an axiomatic set theory, e.g. as in Naive Set Theory by Paul Halmos.
• Early or later versions of Georg Cantor's theory and other informal systems.
• Decidedly inconsistent theories (whether axiomatic or not), such as a theory of Gottlob Frege[6] that yielded Russell's paradox, and theories of Giuseppe Peano[7] and Richard Dedekind.

In naive set theory, a set is described as a well-defined collection of objects. These objects are called the elements or members of the set. Objects can be anything: numbers, people, other sets, etc. For instance, 4 is a member of the set of all even integers. Clearly, the set of even numbers is infinitely large; there is no requirement that a set be finite.

Passage with the original set definition of Georg Cantor

The definition of sets goes back to Georg Cantor. He wrote in his 1915 article Beiträ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

First usage of the symbol ϵ in the work Arithmetices principia nova methodo exposita by Giuseppe Peano.

The simplest way to describe a set is to list its elements between curly braces (known as defining a set extensionally). Thus {1, 2} denotes the set whose only elements are 1 and 2. (See axiom of pairing.) Note the following points:

• The order of elements is immaterial; for example, {1, 2} = {2, 1}.
• Repetition (multiplicity) of elements is irrelevant; for example, {1, 2, 2} = {1, 1, 1, 2} = {1, 2}.

(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 element dogs".

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 condition P holds (known as defining a set intensionally). For example, {x | x ∈ R} denotes the set of real numbers, {x | x has blonde hair} denotes the set of everything with blonde hair.

This notation is called set-builder notation (or "set comprehension", particularly in the context of Functional programming). Some variants of set builder notation are:

• {x ∈ A | P(x)} denotes the set of all x that are already members of A such that the condition P holds for x. For example, if Z is the set of integers, then {x ∈ Z | x is even} is the set of all even integers. (See axiom of specification.)
• {F(x) | x ∈ A} denotes the set of all objects obtained by putting members of the set A into the formula F. For example, {2x | x ∈ Z} is again the set of all even integers. (See axiom of replacement.)
• {F(x) | P(x)} is the most general form of set builder notation. For example, {x's owner | x is a dog} is the set of all dog owners.

Given two sets A and B, A is a subset of B if every element of A is also an element of B. In particular, each set B is a subset of itself; a subset of B that is not equal to B is called a proper subset.

If A is a subset of B, then one can also say that B is a superset of A, that A is contained in B, or that B contains A. In symbols, A ⊆ B means that A is a subset of B, and B ⊇ A means that B is a superset of A. Some authors use the symbols ⊂ and ⊃ for subsets, and others use these symbols only for proper subsets. For clarity, one can explicitly use the symbols ⊊ and ⊋ to indicate non-equality.

As an illustration, let R be the set of real numbers, let Z be the set of integers, let O be the set of odd integers, and let P be the set of current or former U.S. Presidents. Then O is a subset of Z, Z is a subset of R, and (hence) O is a subset of R, where in all cases subset may even be read as proper subset. Not all sets are comparable in this way. For example, it is not the case either that R is a subset of P nor that P is a subset of R.

It follows immediately from the definition of equality of sets above that, given two sets A and B, A = B if and only if A ⊆ B and B ⊆ A. In fact this is often given as the definition of equality. Usually when trying to prove that two sets are equal, one aims to show these two inclusions. The empty set is a subset of every set (the statement that all elements of the empty set are also members of any set A is vacuously true).

The set of all subsets of a given set A is called the power set of A and is denoted by ${\displaystyle 2^{A}}$ or ${\displaystyle P(A)}$; the "P" is sometimes in a script font: ${\displaystyle \wp (A)}$. If the set A has n elements, then ${\displaystyle P(A)}$ will have ${\displaystyle 2^{n}}$ elements.

In certain contexts, one may consider all sets under consideration as being subsets of some given universal set. For instance, when investigating properties of the real numbers R (and subsets of R), R may be taken as the universal set. A true universal set is not included in standard set theory (see Paradoxes below), but is included in some non-standard set theories.

Given a universal set U and a subset A of U, the complement of A (in U) is defined as

A^C := {x ∈ U | x ∉ A}.

In other words, A^C ("A-complement"; sometimes simply A', "A-prime" ) is the set of all members of U which are not members of A. Thus with R, Z and O defined as in the section on subsets, if Z is the universal set, then O^C is the set of even integers, while if R is the universal set, then O^C is the set of all real numbers that are either even integers or not integers at all.

Given two sets A and B, their union is the set consisting of all objects which are elements of A or of B or of both (see axiom of union). It is denoted by A ∪ B.

The intersection of A and B is the set of all objects which are both in A and in B. It is denoted by A ∩ B.

Finally, the relative complement of B relative to A, also known as the set theoretic difference of A and B, is the set of all objects that belong to A but not to B. It is written as A \ B or A − B.

Symbolically, these are respectively

A ∪ B := {x | (x ∈ A) ∨ (x ∈ B)};

A ∩ B := {x | (x ∈ A) ∧ (x ∈ B)} = {x ∈ A | x ∈ B} = {x ∈ B | x ∈ A};

A \ B := {x | (x ∈ A) ∧ ¬ (x ∈ B)} = {x ∈ A | ¬ (x ∈ B)}.

The set B doesn't have to be a subset of A for A \ B to make sense; this is the difference between the relative complement and the absolute complement (A^C = U \ A) from the previous section.

To illustrate these ideas, let A be the set of left-handed people, and let B be the set of people with blond hair. Then A ∩ B is the set of all left-handed blond-haired people, while A ∪ 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, while B \ A is the set of all people who have blond hair but aren't left-handed.

Now let E be the set of all human beings, and let F be the set of all living things over 1000 years old. What is E ∩ F in this case? No living human being is over 1000 years old, so E ∩ F must be the empty set {}.

For any set A, the power set ${\displaystyle P(A)}$ is a Boolean algebra under the operations of union and intersection.

Intuitively, an ordered pair is simply a collection of two objects such that one can be distinguished as the first element and the other as the second element, and having the fundamental property that, two ordered pairs are equal if and only if their first elements are equal and their second elements are equal.

Formally, an ordered pair with first coordinate a, and second coordinate b, usually denoted by (a, b), can be defined as the set ${\displaystyle \{\{a\},\{a,b\}\}.}$

It follows that, two ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.

Alternatively, an ordered pair can be formally thought of as a set {a,b} with a total order.

(The notation (a, b) is also used to denote an open interval on the real 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).

If A and B are sets, then the Cartesian product (or simply product) is defined to be:

A × B = {(a,b) | a ∈ A and b ∈ B}.

That is, A × B is the set of all ordered pairs whose first coordinate is an element of A and whose second coordinate is an element of B.

This definition may be extended to a set A × B × C of ordered triples, and more generally to sets of ordered n-tuples for any positive integer n. It is even possible to define infinite Cartesian products, but this requires a more recondite definition of the product.

Cartesian products were first developed by René Descartes in the context of analytic geometry. If R denotes the set of all real numbers, then R² := R × R represents the Euclidean plane and R³ := R × R × R represents three-dimensional Euclidean space.

There are some ubiquitous sets for which the notation is almost universal. Some of these are listed below. In the list, a, b, and c refer to natural numbers, and r and s are real numbers.

1. Natural numbers are used for counting. A blackboard bold capital N (${\displaystyle \mathbb {N} }$) often represents this set.
2. Integers appear as solutions for x in equations like x + a = b. A blackboard bold capital Z (${\displaystyle \mathbb {Z} }$) often represents this set (from the German Zahlen, meaning numbers).
3. Rational numbers appear as solutions to equations like a + bx = c. A blackboard bold capital Q (${\displaystyle \mathbb {Q} }$) often represents this set (for quotient, because R is used for the set of real numbers).
4. Algebraic numbers appear as solutions to polynomial equations (with integer coefficients) and may involve radicals (including ${\displaystyle i={\sqrt {-1\,}}}$) and certain other irrational numbers. A Q with an overline (${\displaystyle {\overline {\mathbb {Q} }}}$) often represents this set. The overline denotes the operation of algebraic closure.
5. Real numbers represent the "real line" and include all numbers that can be approximated by rationals. These numbers may be rational or algebraic but may also be transcendental numbers, which cannot appear as solutions to polynomial equations with rational coefficients. A blackboard bold capital R (${\displaystyle \mathbb {R} }$) often represents this set.
6. Complex numbers are sums of a real and an imaginary number: ${\displaystyle r+s\,i}$. Here either ${\displaystyle r}$ or ${\displaystyle s}$ (or both) can be zero; thus, the set of real numbers and the set of strictly imaginary numbers are subsets of the set of complex numbers, which form an algebraic closure for the set of real numbers, meaning that every polynomial with coefficients in ${\displaystyle \mathbb {R} }$ has at least one root in this set. A blackboard bold capital C (${\displaystyle \mathbb {C} }$) often represents this set. Note that since a number ${\displaystyle r+s\,i}$ can be identified with a point ${\displaystyle (r,s)}$ in the plane, ${\displaystyle \mathbb {C} }$ is basically "the same" as the Cartesian product ${\displaystyle \mathbb {R} \times \mathbb {R} }$ ("the same" meaning that any point in one determines a unique point in the other and for the result of calculations, it doesn't matter which one is used for the calculation, as long as multiplication rule is appropriate for ${\displaystyle \mathbb {C} }$).

The unrestricted formation principle of sets referred to as the axiom schema of unrestricted comprehension,

is the source of several early appearing paradoxes:

• Y = {x | x is an ordinal} led, in the year 1897, to the Burali-Forti paradox, the first published antinomy.
• Y = {x | x is a cardinal} produced Cantor's paradox in 1897.[8]
• Y = {x | {} = {}} yielded Cantor's second antinomy in the year 1899.[10] Here the property P is true for all x, whatever x may be, so Y would be a universal set, containing everything.
• Y = {x | x ∉ x}, i.e. the set of all sets that do not contain themselves as elements, gave Russell's paradox in 1902.

If the axiom schema of unrestricted comprehension is weakened to the axiom schema of specification or axiom schema of separation,

then all the above paradoxes disappear.[12] 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[13]): There is no universe. Proof: Suppose that it exists and call it U. Now apply the axiom schema of separation with X = U and for P(x) use x ∉ x. This leads to Russell's paradox again. Hence U cannot exist in this theory.[12]

Related to the above constructions is formation of the set

• Y = {x | (x ∈ x) → {} ≠ {}},

where the statement following the implication certainly is false. It follows, from the definition of Y, using the usual inference rules (and some afterthought when reading the proof in the linked article below) both that Y ∈ Y → {} ≠ {} and Y ∈ Y holds, hence {} ≠ {}. This is Curry's paradox.

It is (perhaps surprisingly) not the possibility of x ∈ x that is problematic. It is again the axiom schema of unrestricted comprehension allowing (x ∈ x) → {} ≠ {} for P(x). With the axiom schema of specification instead of unrestricted comprehension, the conclusion Y ∈ Y does not hold and hence {} ≠ {} is not a logical consequence.

Nonetheless, the possibility of x ∈ x is often removed explicitly[14] or, e.g. in ZFC, implicitly,[15] by demanding the axiom of regularity to hold.[15] One consequence of it is

or, in other words, no set is an element of itself.[16]

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.[12] 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, the axiom of choice of ZFC is incompatible with the conceivable "every set of reals is Lebesgue measurable". The former implies the latter is false.

• Algebra of sets
• Axiomatic set theory
• Internal set theory
• List of set identities and relations
• Set theory
• Set (mathematics)
• Partially ordered set

• Bourbaki, N., Elements of the History of Mathematics, John Meldrum (trans.), Springer-Verlag, Berlin, Germany, 1994.
• Cantor, Georg (1874), "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", J. Reine Angew. Math., 1874 (77): 258–262, doi:10.1515/crll.1874.77.258, S2CID 124035379, See also pdf version {{citation}}: External link in |postscript= (help)CS1 maint: postscript (link)
• Devlin, K.J., The Joy of Sets: Fundamentals of Contemporary Set Theory, 2nd edition, Springer-Verlag, New York, NY, 1993.
• María J. Frápolli|Frápolli, María J., 1991, "Is Cantorian set theory an iterative conception of set?". Modern Logic, v. 1 n. 4, 1991, 302–318.
• Frege, Gottlob (1893), Grundgesetze der Arithmetik, vol. 1, Jena{{citation}}: CS1 maint: location missing publisher (link)
• Halmos, Paul (1960). Naive Set Theory. Princeton, NJ: D. Van Nostrand Company.
  • Halmos, Paul (1974). Naive Set Theory (Reprint ed.). New York: Springer-Verlag. ISBN 0-387-90092-6.
  • Halmos, Paul (2011). Naive Set Theory (Paperback ed.). Mansfield Centre, CN: D. Van Nostrand Company. ISBN 978-1-61427-131-4.
• Jech, Thomas (2002). Set theory, third millennium edition (revised and expanded). Springer. ISBN 3-540-44085-2.
• Kelley, J.L., General Topology, Van Nostrand Reinhold, New York, NY, 1955.
• van Heijenoort, J., From Frege to Gödel, A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977. ISBN 0-674-32449-8.
• Meschkowski, Herbert [in German]; Nilson, Winfried (1991), Georg Cantor: Briefe. Edited by the authors., Berlin: Springer, ISBN 3-540-50621-7
• Peano, Giuseppe (1889), Arithmetices Principies nova Methoda exposita, Turin{{citation}}: CS1 maint: location missing publisher (link)
• Zermelo, Ernst (1932), Georg Cantor: Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Mit erläuternden Anmerkungen sowie mit Ergänzungen aus dem Briefwechsel Cantor-Dedekind. Edited by the author., Berlin: Springer

• Beginnings of set theory page at St. Andrews
• Earliest Known Uses of Some of the Words of Mathematics (S)