Naive Set Theory

Informal set theories

This article delves into the realm of informal set theories, a collection of approaches that underpin discussions on the foundations of mathematics . Unlike their more rigid cousins, axiomatic set theories , which are meticulously constructed using the precise language of formal logic , naive set theory operates in the more fluid domain of natural language . It captures the intuitive understanding of mathematical sets that we commonly encounter in discrete mathematics , such as the familiar Venn diagrams and the logical dance of their Boolean algebra . This informal approach is often sufficient for the everyday needs of mathematicians, serving as a crucial stepping stone towards more rigorous formalizations.

The significance of sets in mathematics cannot be overstated. In the grand tapestry of modern mathematics, most abstract objects – be they numbers , relations , or functions – are ultimately defined in terms of sets. Naive set theory, while perhaps less polished, provides a valuable and accessible entry point into this fundamental concept.

Methodology: The Art of Informal Description

A “naive” theory, in the context of naive set theory, is inherently non-formalized. It relies on natural language to articulate the nature of sets and the operations that can be performed upon them. These theories tend to view sets as abstract, almost platonic entities, existing independently of our minds. The logical connectives – “and,” “or,” “if… then,” “not,” “for some,” and “for every” – are treated with the same understanding as in ordinary mathematical discourse. In practice, even within highly formal mathematical settings, including those dedicated to set theory itself, the language and notation of naive set theory are often employed for their sheer convenience.

The genesis of set theory lies in these naive approaches. Georg Cantor pioneered this field in the late 19th century, driven by his explorations of infinite sets . Later, Gottlob Frege , in his Grundgesetze der Arithmetik, attempted to formalize these ideas, though his system, as we shall see, proved to be inconsistent.

The term “naive set theory” can, and often does, refer to several distinct concepts:

• Informal Exposition of Axiomatic Theories: This refers to presentations of established axiomatic set theories, such as Paul Halmos ’s influential book, Naive Set Theory . While it uses informal language, its underlying structure is rooted in formal axioms.
• Early or Informal Systems: This category encompasses the initial theories developed by Georg Cantor and similar informal systems that predated or diverged from formal axiomatization.
• Inconsistent Theories: This refers to systems, whether axiomatic or not, that are fundamentally flawed and lead to contradictions. Examples include the theories of Gottlob Frege , which famously gave rise to Russell’s paradox , and the systems proposed by Giuseppe Peano and Richard Dedekind .

The Specter of Paradox

The seemingly innocuous idea that any definable property could be used to form a set, without any constraints, proved to be a Pandora’s Box, unleashing a torrent of paradoxes . The most notorious of these is Russell’s paradox . Imagine a set composed of “all sets that do not contain themselves.” If such a set exists, does it contain itself? If it does, then by its definition, it should not. If it doesn’t, then by its definition, it should. This logical knot highlights the critical need for limitations on how sets can be formed, a realization that spurred the development of consistent formal systems.

Cantor’s Contribution and Its Nuances

While Georg Cantor is rightly credited with the foundational work in set theory, the precise extent to which his own system was implicated in the paradoxes remains a subject of scholarly debate. One challenge in definitively assessing this is that Cantor never provided a formal axiomatization of his ideas. By 1899, he was indeed aware of paradoxes arising from the unrestricted interpretation of his theory, such as Cantor’s paradox and the Burali-Forti paradox . However, he did not view these as discrediting his fundamental work. Cantor’s paradox, for instance, can be derived by considering the property “x is a cardinal number ” within an unrestricted comprehension framework. It’s important to note that Bertrand Russell presented his paradox in the context of Frege’s formalized system, which was a more explicit attempt at axiomatization than Cantor’s more descriptive approach.

The Birth of Axiomatic Set Theory

The discovery of these paradoxes served as a powerful impetus for the development of axiomatic set theory . The goal was to establish a precise and rigorous framework, defining exactly which operations were permissible and under what conditions sets could be formed, thereby avoiding logical contradictions.

Consistency: A Delicate Balance

A naive set theory is not inherently inconsistent, provided it adheres to well-defined rules for set formation. These rules can be implicitly embedded within definitions, or explicitly stated as axioms. Paul Halmos ’s Naive Set Theory, while using informal language, is essentially an informal presentation of the widely accepted Zermelo–Fraenkel set theory . It earns the “naive” label due to its accessible notation and its deliberate sidestepping of the complex issues of consistency and completeness.

Conversely, an axiomatic set theory is not guaranteed to be free of paradoxes. Gödel’s incompleteness theorems demonstrate that any sufficiently complex formal system, including most axiomatic set theories based on first-order logic , cannot prove its own consistency from within itself, unless it is actually inconsistent. While the standard axiomatic systems are widely believed to be consistent, and their axioms are designed to preclude known paradoxes like Russell’s paradox , Gödel’s theorems imply that we can never be absolutely certain that no paradoxes exist, unless the theory is fundamentally flawed. However, advancements in proof theory , particularly in ordinal analysis , have provided strong evidence for the consistency of these systems, often referred to as consistency proofs .

The term “naive set theory” continues to be used in some literature to refer specifically to the historical theories of Frege and Cantor, distinct from the informal renderings of modern axiomatic set theory.

Utility: The Pragmatic Choice

The decision to employ an axiomatic or an informal approach often boils down to pragmatic considerations. For the vast majority of working mathematicians, the informal use of axiomatic set theory strikes the ideal balance. It allows for clear and efficient communication, with explicit references to axioms (like the axiom of choice ) typically reserved for situations where their use is significant or traditional. Formal proofs are reserved for highly specialized contexts. This informal adoption of axiomatic set theory, when notation is handled judiciously, closely resembles the presentation of naive set theory, making it easier to read, write, and less prone to error than a strictly formal approach.

Sets, Membership, and the Elusive Nature of Equality

In the realm of naive set theory, a set is conceptualized as a well-defined collection of objects, referred to as its elements or members. These objects can be anything imaginable – numbers, individuals, or even other sets. For instance, the number 4 is undeniably a member of the set of all even integers . It is crucial to understand that a set’s size is not a limiting factor; the set of even numbers, though infinite, is a perfectly valid set.

A Glimpse into Cantor’s Original Vision

The very concept of a set can be traced back to Georg Cantor , who, in his 1874 article Beiträge zur Begründung der transfiniten Mengenlehre, articulated his understanding:

“Under a ‘set’ we understand any gathering together into a whole of definite, distinct objects of our perception or of our thought—which are called elements of the set.”

The notation for membership, “∈,” signifying “is an element of,” was introduced by Giuseppe Peano in 1889. Derived from the Greek letter epsilon , it represents the initial letter of the word ἐστί, meaning “is.” Its negation, “∉,” denotes non-membership.

A Note on Consistency: The Unspoken Assumption

Cantor’s definition, while foundational, leaves open the question of how sets are formed and what operations yield new sets. The term “well-defined” itself, while intuitive, doesn’t inherently guarantee consistency or provide an unambiguous boundary between what constitutes a set and what does not. This is precisely the domain that axiomatic set theory and axiomatic class theory aim to address.

The challenge with informally formulated set theories, especially those not explicitly derived from an axiomatic system, is the potential for multiple, divergent interpretations. Different formalizations might agree on the fundamental definition of a set but diverge significantly on the rules for constructing new sets, leading to different collections of sets altogether. Cantor’s own definition, for example, allows for considerable latitude. While he was primarily interested in sets of mathematical objects, the literal interpretation of his definition could encompass sets of arbitrary things. This ambiguity is what axiomatic systems seek to resolve.

For the purposes of our discussion, we will interpret “well-defined” as an intention to adhere to implicit or explicit rules that prevent inconsistencies. This allows us to focus on the core concepts without getting mired in the deep and often complex issues of consistency. After all, as Gödel’s second incompleteness theorem suggests, achieving absolute certainty of consistency in sufficiently complex formal systems is an impossibility. Thus, maintaining this focus on simplicity does not diminish the utility of naive set theory in introductory contexts. Consistency, for now, is assumed.

Membership: The Belonging Game

If an object x is a member of a set A, we denote this relationship as x ∈ A. This symbol, the lowercase Greek letter epsilon , “ε,” was ingeniously introduced by Giuseppe Peano in 1889, drawing from the Greek word ἐστί (“is”). The converse, x ∉ A, signifies that x is not an element of A.

Equality: The Indistinguishable Twins

Two sets, A and B, are considered equal if and only if they contain precisely the same elements. This means every element in A must also be in B, and vice versa. This principle is formally captured by the axiom of extensionality . Consequently, a set is entirely defined by its constituent elements; the manner in which it is described is irrelevant. For example, the set containing the numbers 2, 3, and 5 is identical to the set of all prime numbers less than 6. When sets A and B are equal, we denote this as A = B.

The Empty Set : A Void of Existence

The empty set , symbolized by ∅ or sometimes {}, is a set that contains absolutely no members. Because a set is uniquely determined by its elements, there can be only one empty set, a fact formalized by the axiom of empty set . Despite its lack of members, the empty set can itself be a member of other sets. Thus, ∅ ≠ {∅}, as the former is devoid of elements, while the latter contains a single element: the empty set itself.

Defining Sets: Two Paths to Specification

There are two primary ways to describe a set:

1. Extensional Definition (Listing Elements): The most straightforward method is to list the elements of a set within curly braces. For example, {1, 2} represents the set whose only members are 1 and 2. This aligns with the axiom of pairing . Key points to remember about this notation are:

   • Order is Irrelevant: {1, 2} is identical to {2, 1}.
   • Repetition is Ignored: {1, 2, 2} is the same as {1, 1, 1, 2}, both equating to {1, 2}. These properties stem directly from the definition of set equality. It’s worth noting that this notation can be used informally, for instance, {dogs} might be intended to mean “the set of all dogs.” However, in strict mathematical terms, it would be interpreted as “the set containing the single element ‘dogs’.” An extreme, yet valid, example of this notation is {}, which, as mentioned, denotes the empty set.

2. Intensional Definition (Defining by Property): The notation { x : P(x) }, or sometimes { x | P(x) }, defines a set as the collection of all objects x for which a specific property P holds true. This is known as set-builder notation . For example, { x | x ∈ ℝ } denotes the set of all real numbers , and { x | x has blonde hair} represents the set of all entities possessing blonde hair.

   Several variations of set-builder notation exist:

   • { x ∈ A | P(x) }: This denotes the subset of A containing only those elements x that satisfy property P. For instance, if ℤ is the set of integers , then { x ∈ ℤ | x is even} precisely defines the set of all even integers. This relies on the axiom of specification .
   • { F(x) | x ∈ A }: This constructs a set by applying a formula F to each element x in set A. For example, {2x | x ∈ ℤ} again yields the set of all even integers. This is related to the axiom of replacement .
   • { F(x) | P(x) }: This is the most general form, combining both a formula and a property. For instance, { x’s owner | x is a dog} would represent the set of all dog owners.

Subsets: The Concept of Containment

Given two sets, A and B, we say that A is a subset of B if every element present in A is also present in B. Consequently, every set is a subset of itself. A subset of B that is not equal to B is termed a proper subset.

The relationship “subset” can also be expressed as “contained in.” We denote A as a subset of B using the symbol A ⊆ B, and B as a superset of A using B ⊇ A. Some mathematicians use the symbols ⊂ and ⊃ for subsets, while others reserve them exclusively for proper subsets. To avoid ambiguity, the notations ⊊ and ⊋ are sometimes used to explicitly indicate a proper subset relationship.

Consider the set of real numbers (ℝ), the set of integers (ℤ), the set of odd integers (O), and the set of U.S. Presidents (P). We can observe that O ⊆ ℤ, ℤ ⊆ ℝ, and therefore O ⊆ ℝ. In all these cases, the subset relationship can be considered proper. However, not all sets are comparable in this manner; for instance, ℝ is not a subset of P, nor is P a subset of ℝ.

From the definition of set equality, it directly follows that A = B if and only if A ⊆ B and B ⊆ A. This is often the strategy employed when proving set equality: demonstrating these two inclusions. The empty set holds the unique distinction of being a subset of every set; the statement “all elements of the empty set are members of any set A” is considered vacuously true .

The collection of all subsets of a given set A is known as the power set of A, denoted as 2^A or P(A) (sometimes ⁠℘(A) in a script font). If a set A contains n elements, its power set will contain 2ⁿ elements.

Universal Sets and Absolute Complements: Defining Boundaries

In specific contexts, it may be convenient to consider all sets under discussion as subsets of a larger, encompassing universal set . For example, when studying properties of the real numbers ℝ, ℝ itself might serve as the universal set. It’s important to note that a true, all-encompassing universal set, containing absolutely everything, is not part of standard set theory due to the paradoxes it would engender (see Paradoxes section below). However, some non-standard set theories do incorporate such concepts.

Given a universal set U and a subset A of U, the complement of A (within U) is defined as A^C := { x ∈ U | x ∉ A }. In simpler terms, A^C (read as “A complement” or sometimes “A prime”) is the set of all elements in U that are not members of A. Using our previous examples, if ℤ is the universal set, then the complement of the set of odd integers (O) is the set of even integers. However, if ℝ is the universal set, then the complement of O includes all real numbers that are either even integers or not integers at all.

Unions, Intersections, and Relative Complements: Combining and Contrasting Sets

When dealing with two sets, A and B, their union , denoted A ∪ B, is the set comprising all objects that are elements of A, or B, or both. This operation is governed by the axiom of union .

The intersection of A and B, denoted A ∩ B, is the set containing only those objects that are members of both A and B.

The relative complement of B with respect to A, also known as the set-theoretic difference A \ B, is the set of all objects that belong to A but not to B.

Symbolically, these operations are defined as:

• 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) }

It is important to understand that for the relative complement A \ B to be meaningful, B does not need to be a subset of A. This distinguishes it from the absolute complement, where A^C = U \ A.

To illustrate, let A be the set of left-handed individuals and B be the set of people with blond hair. Then A ∩ B represents the set of left-handed blond-haired individuals. A ∪ B encompasses all individuals who are either left-handed, blond-haired, or both. A \ B, conversely, is the set of left-handed people who do not have blond hair, while B \ A is the set of blond-haired people who are not left-handed.

Consider a different scenario: let E be the set of all human beings, and F be the set of all living things older than 1000 years. Given that no living human has reached such an age, the intersection E ∩ F must necessarily be the empty set , {}.

It is a fundamental property that for any set A, its power set P(A) forms a Boolean algebra under the operations of union and intersection.

Ordered Pairs and Cartesian Products: Structuring Relationships

An ordered pair is intuitively understood as a collection of two objects where one is designated as the first element and the other as the second. The defining characteristic of ordered pairs is that two such pairs are equal if and only if their corresponding elements are equal.

Formally, an ordered pair with first coordinate a and second coordinate b, typically denoted as (a, b), can be defined as the set {{a}, {a, b}}. This definition ensures that (a, b) = (c, d) if and only if a = c and b = d.

An alternative formalization views an ordered pair as a set {a, b} equipped with a total order .

It is worth noting that the notation (a, b) is also used to represent an open interval on the real number line . Context is usually sufficient to disambiguate, but the notation ]a, b[ is sometimes employed for open intervals to avoid confusion with ordered pairs.

Given two sets, A and B, their Cartesian product , denoted A × B, is defined as the set of all ordered pairs (a, b) such that a ∈ A and b ∈ B. This definition can be extended to ordered triples (A × B × C) and, more generally, to sets of ordered n-tuples for any positive integer n. Infinite Cartesian products are also possible but require more sophisticated definitions.

The concept of Cartesian products was introduced by René Descartes in his work on analytic geometry . If ℝ represents the set of all real numbers , then ℝ² := ℝ × ℝ corresponds to the Euclidean plane , and ℝ³ := ℝ × ℝ × ℝ represents three-dimensional Euclidean space .

Some Fundamental Sets: The Building Blocks of Mathematics

Certain sets are so fundamental and widely used that they possess near-universal notation:

• Natural Numbers (ℕ): Used for counting, this set is often denoted by a blackboard bold capital N, ℕ.
• Integers (ℤ): These arise as solutions to equations like x + a = b. The blackboard bold capital Z, ℤ, is used, derived from the German word Zahlen (numbers).
• Rational Numbers (ℚ): These are solutions to equations of the form a + bx = c. The blackboard bold capital Q, K, is employed, standing for quotient , as ℝ is already taken.
• Algebraic Numbers (¯ℚ): These are solutions to polynomial equations with integer coefficients, potentially involving radicals and even the imaginary unit i = √‐1. The notation ¯K represents the set of algebraic numbers, where the overline signifies algebraic closure .
• Real Numbers (ℝ): Representing the continuous “real line,” these include all numbers that can be approximated by rationals. They can be rational or transcendental numbers (which cannot be roots of polynomial equations with rational coefficients). The blackboard bold capital R, №, is the standard symbol.
• Complex Numbers (ℂ): These are numbers of the form r + si, where r and s are real numbers. The set of real numbers and the set of purely imaginary numbers are subsets of the complex numbers. The complex numbers form an algebraic closure for the real numbers, meaning every polynomial with real coefficients has at least one root in ℂ. The blackboard bold capital C, ℂ, is used for this set. Notably, the set of complex numbers ℂ can be identified with the Cartesian product ℝ × ℝ, representing the complex plane.

Paradoxes in Early Set Theory: The Cracks in the Foundation

The principle of axiom schema of unrestricted comprehension , which posited that any property P could define a set Y = { x : P(x) }, proved to be the source of several early and devastating paradoxes:

• Burali-Forti Paradox (1897): Considering the set of all ordinal numbers led to a contradiction regarding the ordering of these numbers.
• Cantor’s Paradox (1897): The property “x is a cardinal number” when used in unrestricted comprehension led to the existence of a cardinal number greater than the largest cardinal number, an impossibility.
• Cantor’s Second Antinomy (1899): The property “true for all x” (i.e., P(x) is always true) applied to unrestricted comprehension would imply the existence of a universal set containing everything, which also leads to contradictions.
• Russell’s Paradox (1902): The property “x ∉ x” (the set of all sets that do not contain themselves) generated the famous paradox: if such a set contains itself, it shouldn’t; if it doesn’t contain itself, it should.

The Weakening of Comprehension: A Path to Stability

When the axiom schema of unrestricted comprehension is weakened to the axiom schema of specification (also known as the axiom schema of separation), which states that for any set X, there exists a set Y = { x ∈ X : P(x) }, these paradoxes are resolved. A significant consequence of adopting the axiom schema of separation is the theorem that the set of all sets does not exist. As Halmos eloquently put it: “There is no universe .” The proof involves assuming such a universe U exists and then applying the axiom schema of separation with X = U and the property x ∉ x, which reintroduces Russell’s paradox. Therefore, U cannot exist within this framework.

Curry’s Paradox: A Different Kind of Contradiction

Related to these paradoxes is the formation of the set Y = { x | (x ∈ x) → {} ≠ {} }. This construction, using standard logical inference rules, leads to the conclusion that {} ≠ {}, a contradiction. While the possibility of x ∈ x (a set being an element of itself) is not inherently problematic, it is the unrestricted comprehension that allows for such paradoxical constructions. The axiom schema of specification, by contrast, does not lead to Y ∈ Y, thus avoiding the contradiction.

The Axiom of Regularity: Enforcing a Hierarchy

Despite the resolution of some paradoxes, the possibility of x ∈ x is often explicitly disallowed, or implicitly excluded, as in Zermelo–Fraenkel set theory (ZFC), by the axiom of regularity . A consequence of this axiom is that no set is an element of itself.

The axiom schema of separation, while crucial for consistency, is too restrictive on its own to build the rich structure of set theory with all its usual operations and constructions. The axiom of regularity also imposes limitations. This necessitates the introduction of other axioms to guarantee the existence of a sufficient variety of sets. It’s important to recognize that not all conceivable axioms can be freely combined; for instance, the axiom of choice within ZFC is incompatible with the assertion that every set of real numbers is Lebesgue measurable .

The term “naive set theory” is still occasionally employed in academic discourse to specifically refer to the historical theories developed by Frege and Cantor, rather than to the informal presentations of modern axiomatic set theory.