Naive Set Theory

Set theory provides a language for collecting objects, comparing collections, and building new ones. Here naive set theory means an informal development of the set constructions used in ordinary mathematics. We state their meaning and practise proofs without first presenting a complete list of axioms. It does not mean that every imaginable description is automatically allowed to define a set.

There are different axiomatic frameworks, including ZF, ZFC, and NBG. Their approaches to sets, classes, and existence assumptions differ. This chapter uses only elementary set constructions; the comparison is an optional exploration at the end. Relations and Order later introduces NBG classes before developing relations and orders. The Open Logic set-theory text provides a companion path from elementary sets toward axiomatic foundations [1][1] T. Button, Set Theory. Open Logic Project, 2026. Fall 2021 course text, revised July 2026. https://builds.openlogicproject.org/courses/set-theory/settheory-screen.pdf.

Membership, equality, and notation

A set is determined by its elements. Write $x\in A$ for membership and $x\notin A$ for nonmembership. Listing the elements ignores order and repetition: $\{1,2,2\}=\{2,1\}$. A membership condition must have a precise mathematical meaning; this does not guarantee an algorithm deciding membership for every possible input.

The extensionality principle says that sets with the same elements are equal:

$$A=B\quad\Longleftrightarrow\quad \forall x\,(x\in A\leftrightarrow x\in B).$$

We use $\mathbb N=\{0,1,2,\ldots\}$, along with $\mathbb Z,\mathbb Q,\mathbb R$. Set-builder notation normally selects from a specified set, as in

$$E=\{n\in\mathbb Z:n=2k\text{ for some }k\in\mathbb Z\}.$$

The domain is part of the description. For example, $\{x\in\mathbb R:x^2=2\}$ has two elements, while $\{x\in\mathbb Q:x^2=2\}$ is empty.

For real $a<b$, intervals are sets selected by inequalities:

$$(a,b)=\{x\in\mathbb R:a<x<b\},$$ $$[a,b]=\{x\in\mathbb R:a\le x\le b\}.$$

Parentheses exclude an endpoint; square brackets include it. Thus $(a,b]$ includes $b$ but not $a$.

Elements, subsets, and the empty set

DefinitionSubset and proper subset

$A\subseteq B$ means that every element of $A$ belongs to $B$. A proper subset, written $A\subsetneq B$, additionally requires $A\ne B$.

Membership compares an object with a set; inclusion compares the elements of two sets. If $A=\{1,2\}$, then $1\in A$ and $\{1\}\subseteq A$, but $\{1\}\notin A$. A set can itself be an element of another set, so the level of braces matters.

The empty set $\varnothing$ has no elements. For every set $A$, $\varnothing\subseteq A$: a counterexample would need to belong to the empty set. This does not imply $\varnothing\in A$. Also, $\varnothing$ and $\{\varnothing\}$ differ: the latter has one element.

DefinitionPower set and finite cardinality

The power set $\mathcal P(A)$ contains all subsets of $A$. For a finite set $A$, its cardinality $|A|$ is the number of its elements.

For $A=\{u,v\}$,

$$\mathcal P(A)=\{\varnothing,\{u\},\{v\},\{u,v\}\}.$$

If $|A|=n$, every element has two independent membership choices when building a subset, so $|\mathcal P(A)|=2^n$. For $n=0$, there is still one subset, namely $\varnothing$. Infinite cardinality requires further theory; the elementary finite-counting arguments here should not be applied as subtraction rules for infinite sizes.

Comparing size: finite, infinite, and countable

Counting a finite set gives a natural number. To compare sizes more generally, pair the elements of two sets so that every element on either side has exactly one partner. Such a pairing is called a bijection; its formal mapping definition comes in Functions and Mappings. Two sets are equinumerous, written $|A|=|B|$, when such a pairing exists. No ordering of the elements is required.

For $n\in\mathbb N$, let $I_n=\{k\in\mathbb N:k<n\}$. Thus $I_0=\varnothing$, and for $n\ge1$ the set is $\{0,\ldots,n-1\}$.

DefinitionFinite and infinite sets

A set $A$ is finite if it can be paired bijectively with $I_n$ for some $n\in\mathbb N$; then $|A|=n$. A set is infinite if it is not finite. In particular, the empty set is finite, with size zero.

The natural numbers form an infinite set: any nonempty finite collection of natural numbers has a largest member, while $\mathbb N$ has no largest member. The nonnegative even integers $E=\{2n:n\in\mathbb N\}$ can nevertheless be paired with all of $\mathbb N$ by pairing $n$ with $2n$. Every even integer appears exactly once. Thus a proper subset of an infinite set can have the same cardinality as the whole set; finite intuition about “fewer elements” needs care.

DefinitionCountable and uncountable sets

A set is countably infinite if it is equinumerous with $\mathbb N$. In this collection, countable means finite or countably infinite. A set that is not countable is uncountable.

Some authors use “countable” only for the infinite case, so check the convention when changing texts. Our convention includes the empty set. A countably infinite set admits a list indexed by $0,1,2,\ldots$ that reaches every element exactly once. An uncountable set admits no such exhaustive list, even if repetitions are allowed.

Kind	Examples	What must be established
Finite	$\varnothing$, $\{2,5,9\}$	A bijection with some $I_n$
Countably infinite	$\mathbb N$, $E$, $\mathbb Z$, $\mathbb Q$	A bijection with $\mathbb N$
Uncountable	$\mathbb R$, $(0,1)$, $\mathcal P(\mathbb N)$	Impossibility of a countable listing

These examples are not all immediate from the definitions. Number Systems, Algorithms, and Recursion gives explicit listings of the integers and rationals, and a diagonal proof for the reals. The power-set example is an exploration below. The distinctions are established here so later chapters can use them consistently [2][2] E. Lehman, F. T. Leighton, and A. R. Meyer, Mathematics for Computer Science. MIT OpenCourseWare, 2015. Revised May 18, 2015; infinite sets, recursive data, and invariants. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf.

Being bounded or having points close together does not decide countability: $(0,1)$ is bounded but uncountable, whereas $\mathbb Q$ is countable despite having another rational between any two distinct rationals. “Can be listed” is a mathematical existence claim, not automatically a claim that a computer can generate the list.

Operations within a specified universe

Fix a set $U$ such that every set under discussion is a subset of $U$. The complement of $A\subseteq U$ is $A^c=U\setminus A$. Changing $U$ changes the complement; $U$ is a local universe of discourse, not a set of absolutely every mathematical object.

Operation	Membership condition
$A\cup B$	$x\in A$ or $x\in B$
$A\cap B$	$x\in A$ and $x\in B$
$A\setminus B$	$x\in A$ and $x\notin B$
$A\mathbin\triangle B$	$x$ belongs to exactly one of $A,B$

The symmetric difference satisfies $A\mathbin\triangle B=(A\setminus B)\cup(B\setminus A)$. Two sets are disjoint when their intersection is empty.

For $U=\{1,2,3,4,5\}$, $A=\{1,2,4\}$ and $B=\{2,3\}$, the intersection is $\{2\}$, the union is $\{1,2,3,4\}$, the difference $A\setminus B$ is $\{1,4\}$, and $A^c=\{3,5\}$. Reversing the difference changes the result: $B\setminus A=\{3\}$.

Prove identities by following an arbitrary element

To prove $A\subseteq B$, take arbitrary $x\in A$ and show $x\in B$. To prove equality, establish both inclusions or give a chain of equivalent membership conditions. To disprove an inclusion, give one element belonging to the first set but not the second. These are applications of the proof methods developed earlier.

ProofDistributing intersection over union

For arbitrary $x$,

$$\begin{aligned} x\in A\cap(B\cup C) &\iff x\in A\land(x\in B\lor x\in C)\\ &\iff (x\in A\land x\in B)\lor(x\in A\land x\in C)\\ &\iff x\in(A\cap B)\cup(A\cap C). \end{aligned}$$

The middle equivalence is the distributive law of logic. Extensionality therefore gives the set identity.

ProofA De Morgan law with its universe intact

Let $A,B\subseteq U$ and take $x\in U$. Then $x\notin A\cup B$ exactly when $x\notin A$ and $x\notin B$, which is exactly membership in $A^c\cap B^c$. Hence $(A\cup B)^c=A^c\cap B^c$. No element outside $U$ belongs to either side, so the comparison covers the full sets.

The companion laws can be checked in the same way:

Family	Identities
Commutativity	$A\cup B=B\cup A$, $A\cap B=B\cap A$
Associativity	$(A\cup B)\cup C=A\cup(B\cup C)$; likewise for $\cap$
Idempotence	$A\cup A=A$, $A\cap A=A$
Absorption	$A\cup(A\cap B)=A$, $A\cap(A\cup B)=A$
Complement	$A\cup A^c=U$, $A\cap A^c=\varnothing$, $(A^c)^c=A$

A diagram can suggest an identity, but the membership proof establishes it for arbitrary sets. The correspondence with logical connectives also explains the connection to Boolean algebra.

Families, partitions, and finite counting

An indexed family $(A_i)_{i\in I}$ associates a set with each index. It may contain repeated sets at different indices. Membership in its union requires membership in at least one $A_i$; membership in its intersection requires membership in every $A_i$.

For a family of subsets of a fixed $U$, we adopt

$$\bigcup_{i\in\varnothing}A_i=\varnothing, \qquad \bigcap_{i\in\varnothing}A_i=U.$$

The first has no witness, and the second imposes no condition on an element of $U$. The second equation uses the specified universe convention; it is not an unrestricted claim that a universal set exists.

A partition of $A$ is a family of nonempty, pairwise disjoint blocks whose union is $A$. For instance, $\{\{1,3\},\{2,4\}\}$ partitions $\{1,2,3,4\}$; $\{\{1,3\},\{2,3,4\}\}$ does not, because the blocks overlap at $3$.

For finite $A,B$, split their union into the three disjoint regions $A\setminus B$, $A\cap B$, and $B\setminus A$. Counting each region once yields

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

The subtraction corrects the double count of the intersection. This is the two-set inclusion-exclusion principle.

Ordered pairs and Cartesian products

An ordered pair obeys $(a,b)=(c,d)$ exactly when $a=c$ and $b=d$. Its order matters, unlike that of a two-element set. The Cartesian product is

$$A\times B=\{(a,b):a\in A,\ b\in B\}.$$

If $A,B$ are finite, $|A\times B|=|A||B|$; if either is empty, the product is empty. Usually $A\times B\ne B\times A$, although swapping coordinates gives a natural correspondence between them. The sets $\mathbb R^2$ and $\mathbb R^3$ contain ordered pairs and triples of real numbers. This is the language needed for multivariable functions, not a requirement that all functions have real-valued inputs.

Why unrestricted comprehension fails

Suppose every condition defined a set, with no restriction on its source collection. Then we could form the Russell collection $R=\{x:x\notin x\}$ as a set. Asking whether $R\in R$ would give

$$R\in R\quad\Longleftrightarrow\quad R\notin R,$$

a contradiction. The issue is the unrestricted set-existence assumption, not a difficult membership calculation.

Axiomatic theories restrict which collections are sets. ZF and ZFC use sets as their objects and constrain set formation; NBG additionally treats classes explicitly, including proper classes that are not sets. We do not need the full axiom lists for the constructions above. The comparison exercises below and the later NBG introduction provide the next step [1][1] T. Button, Set Theory. Open Logic Project, 2026. Fall 2021 course text, revised July 2026. https://builds.openlogicproject.org/courses/set-theory/settheory-screen.pdf, [3][3] T. Banakh, “Classical Set Theory: Theory of Sets and Classes,” arXiv:2006.01613, 2026. Version 6, August 15, 2026; NBG sets, classes, and class existence. https://arxiv.org/abs/2006.01613.

Core exercises

ExerciseKeep the levels of braces distinct

Let $A=\{\varnothing,\{1\}\}$. Decide whether $\varnothing\in A$, $\varnothing\subseteq A$, $\{1\}\in A$, and $\{1\}\subseteq A$ hold. Find $|A|$ and $|\mathcal P(A)|$.

Show solution

Solution

The first three statements are true. The fourth is false because $1\notin A$. There are two elements of $A$, so its power set has four elements. An element of $A$ can itself be a set without its own elements automatically belonging to $A$.

ExerciseProve an identity with difference

Prove $A\cap(B\setminus C)=(A\cap B)\setminus(A\cap C)$.

Show solution

Solution

Membership on the left means $x\in A$, $x\in B$, and $x\notin C$. On the right it means $x\in A\cap B$ and $x\notin A\cap C$. Once $x\in A$ is known, the last condition is equivalent to $x\notin C$. Thus the two membership conditions agree.

ExerciseA set described by integer combinations

Show that $\{12m+8n:m,n\in\mathbb Z\}=\{4k:k\in\mathbb Z\}$.

Show solution

Solution

Every $12m+8n=4(3m+2n)$ belongs to the right set. Conversely, for any integer $k$, choose $m=k,n=-k$; then $12m+8n=4k$. The two inclusions establish equality, and the second explicitly constructs the witnesses.

ExerciseCheck a finite partition and count

Let $A,B$ be finite with $|A|=8$, $|B|=6$, and $|A\cap B|=3$. Find $|A\cup B|$ and $|A\mathbin\triangle B|$. Explain the disjoint regions used.

Show solution

Solution

The union has $8+6-3=11$ elements. Its three regions have sizes $5,3,3$. The symmetric difference keeps only the two outer regions, so it has $8$ elements. If a region is empty, omit it when calling the resulting family a partition, since partition blocks must be nonempty.

ExerciseClassify collections at the right level

Classify $\varnothing$, $\{\mathbb N\}$, $\mathbb N$, and $\mathcal P(\{u,v\})$ as finite or countably infinite. Which are countable under our convention?

Show solution

Solution

Their respective sizes are $0$, $1$, countably infinite, and $4$. All four sets are countable. The singleton $\{\mathbb N\}$ contains one element, even though that element is itself an infinite set.

ExerciseA bounded countably infinite set

Let $A=\{1/(n+1):n\in\mathbb N\}$. Show that $A$ is countably infinite even though every element lies in $(0,1]$.

Show solution

Solution

Pair $n$ with $1/(n+1)$. Every element of $A$ appears by its definition. Equal values imply equal positive denominators and hence equal indices, so there is no repetition. This is a bijective pairing with $\mathbb N$. Boundedness concerns numerical order, not how many elements a set has.

Exploration: compare frameworks without changing the core course

ExerciseA power set that cannot be listed

Suppose someone claims to list every subset of $\mathbb N$ as $S_0,S_1,S_2,\ldots$, allowing repetitions. Consider

$$D=\{n\in\mathbb N:n\notin S_n\}.$$

Explain why the list misses $D$, and why this proves that $\mathcal P(\mathbb N)$ is uncountable.

Discussion guide

Solution

For each $k$, the sets $D$ and $S_k$ disagree about whether $k$ is a member: $k\in D$ exactly when $k\notin S_k$. Thus $D\ne S_k$ for every $k$, although $D$ is a subset of $\mathbb N$. Every proposed list therefore misses a subset. A nonempty finite collection could be listed with repetitions, so this rules out finite as well as countably infinite cardinality.

This diagonal construction is legitimate: $D$ is selected from the already given set $\mathbb N$. Unlike unrestricted Russell comprehension, it does not assume a set of all sets. The contradiction refutes the proposed exhaustive list, not the existence of $D$.

ExerciseZF, ZFC, and NBG in a small comparison

Using the suggested readings, compare what the three names refer to and how they discuss a collection such as “all sets.” Do not attempt a proof of their consistency or relative strength.

Discussion guide

Solution

ZF is Zermelo–Fraenkel set theory. ZFC adds the axiom of choice. Both quantify over sets; definable classes may be discussed as notation without making every such class a set. NBG has an explicit framework for sets and classes, with proper classes unable to be elements. Authors vary in whether choice or global choice is included in their NBG convention, so check the chosen axiom list before comparing theories. Neither approach accepts a set of all sets.

The practical difference to notice is how existence and collection size are controlled, not which theory is supposedly the next “difficulty level.”

ExerciseSeparate within a given set

For a given set $A$, consider $R_A=\{x\in A:x\notin x\}$. Explain why this restricted construction does not produce the unrestricted Russell contradiction. What would happen if $R_A\in A$?

Discussion guide

Solution

Separation selects a subset of the already given set $A$. If $R_A\in A$, then its defining condition would imply $R_A\in R_A$ if and only if $R_A\notin R_A$, a contradiction. Thus $R_A\notin A$. This is a conclusion about what $A$ cannot contain, not a contradiction in the restricted construction. It also shows why no set $A$ can contain every set.

ExerciseOrders and axiom systems answer different questions

Why can the same set carry different order relations without changing from ZFC to NBG? Where does the later chapter’s use of classes enter?

Discussion guide

Solution

An order relation is additional structure on a collection; for a set $A$ it can be represented by a subset of $A\times A$. Changing that relation does not change the background axioms governing sets. The later chapter uses NBG to discuss classes and larger constructions, then studies particular relations and orders within that framework. The axiomatic background and the chosen order are separate choices.

Continue with Functions and Mappings for correspondences between sets. Return to Relations and Order when ready to study classes, equivalence relations, and order structure more systematically.

References

1. [1] T. Button, Set Theory. Open Logic Project, 2026. Fall 2021 course text, revised July 2026. https://builds.openlogicproject.org/courses/set-theory/settheory-screen.pdf a b
2. [2] E. Lehman, F. T. Leighton, and A. R. Meyer, Mathematics for Computer Science. MIT OpenCourseWare, 2015. Revised May 18, 2015; infinite sets, recursive data, and invariants. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf ↩
3. [3] T. Banakh, “Classical Set Theory: Theory of Sets and Classes,” arXiv:2006.01613, 2026. Version 6, August 15, 2026; NBG sets, classes, and class existence. https://arxiv.org/abs/2006.01613 ↩