Introduction to Sets

Now we’ll discuss the backbone of all modern math, set theory. Math can be thought of as, in it’s most basic form, the study of collections; a series of advanced ways of counting. A set is effectively a well-define collection of objects; however, it is actually quite difficult to specify what “well-defined” means. There was a time when a set was taken to be any collection of objects which could be described; however, this leads to paradoxes. For example, let $S$ denote the collection of all collections which do not contain themselves. Is $S$ in $S$? If it is, then $S$ contains itself, and so $S$ cannot be an element of $S$, a contradiction. But if it is not, then $S$ does not contain $S$, so $S$ must be in $S$, another contradiction. The only possibility is that “membership”, the relation that specifies if $S$ is in the collection $S$, is not well defined, and so the collection is not well-defined.

The schema where any collection of objects is a set is called “naive set theory”, and has some pretty clear paradoxes. To remedy this, a plethora of set theories were invented; these take the form of a set of axioms or definitions (depending on how you like to look at things) which outline how sets behave. Zermello-Fraenkel Choice (ZFC) set theory is what one might call the “industry standard” set theory, the one most mathemeticians use. The first two words (Zermello-Fraenkel) refer to the two mathemeticians who first defined it, while the “Choice” part refers to a particularly interesting axiom which ZFC includes (called the axiom of choice).

We’ll be studying the properties of ZFC specifically for the next two or three lessons, although all of math can be thought of as consequences of ZFC. Today, we’ll introduce the axioms of Zermelo set theory. Next lesson we’ll play with those axioms and see what constructions we can create from them. Finally, two lessons from now, we’ll discuss two additional axioms to make Zermelo set theory into ZFC.

Language of ZFC

In set theory, the objects we deal with are called sets. In addition to the logical connectives $\lnot, \land, \lor, \implies, \iff$ and the quantifiers $\exists, \forall$, we specify an equality symbol $=$ and a membership symbol $\in$. Two sets $x$ and $y$ are said to be equal whenever $x$ can be replaced by $y$ in any logical statement without changing it’s truth value; in this case we say $x=y$. If $x\in y$, we say that $x$ is a member of $y$, or $x$ lies in $y$. The meaning of this statement is dictated by the axioms of ZFC. For more information, see Wikipedia: Zermello-Fraenkel Set Theory - Formal Language. We will define in the axioms the intersection $\cap$ and union $\cup$ of two sets.

Notational Remark

For this article, I use lowercase letters to represent sets. In math, almost everything is a set, but it’s useful to view some sets as numbers, some sets as functions, some sets as relations, etc. When we do this, we’ll often keep track of what things we want to deal with as sets and what things we want to deal with otherwise by writing the sets as uppercase letters and the elements with lowercase letters. We’ll start doing this next week and remind you then.

Axioms of Zermelo Set Theory

We’ll begin by discussing Zermelo’s set theory, then add on axioms which Fraenkel included, and finally discuss the axiom of choice. These axioms are somewhat redundant; in reality, only nine are necessary. I’ve endeavored to put the ones I find most useful or use the most often first; the ones at the end are technical specifications to avoid paradoxes, which I almost never use. For more information, see here. Zermelo set theory includes, in addition to the axioms listed here, an axiom known as the axiom of choice, which we’ll discuss later. I’m drawing some of my descriptions of the axioms from the relevent descriptions here.

1. Empty Set. There is a set $\emptyset$, called the empty set, which contains no element. Formally, we say

   $$\exists \emptyset \text{ s.t. } \forall x, \lnot(x\in \emptyset) .$$

2. Extensionality. Two sets are equal if and only if they contain the same elements. This means whenever sets $x$ and $y$ include the same element, we can replace $x$ for $y$ in any logical statement and obtain the same truth-value. This can be written formally as

   $$\forall x, \forall y ( \forall z, (z\in x \iff z\in y) \implies x=y).$$

   Note that this implies the empty set is unique, i.e. if a set $y$ has $\forall x, \lnot (x\in y)$, then $y=\emptyset$. (Show this to be true!).

3. Schema of Restricted Comprehension. Let $x$ be a set. For any predicate $\phi$, the collection of all $y\in x$ such that $\phi(y)$ holds is a set. This is technically speaking an axiom for every predicate $\phi$, but we’ll generally ignore that logical technicality. (That is, however, the reason for the name “schema”). We write this set using “set builder notation” as

   $$\{y\in x | \phi(y)\}, \text{ or }\{y\in x \text{ s.t. } \phi(y)\}, \text{ or }\{y\in x : \phi(y)\},$$

   and this is read “the set of all $y$ in $x$ such that $\phi(y)$ (holds)”. A special case of this is the intersection. For sets $x$ and $y$ we define the intersection $x\cap y$ to be

   $$x\cap y:= \{z\in x | z\in y\},$$

   i.e. the set of all $z$ in $x$ such that $z$ is (also) in $y$.

4. Pairing. If $x$ and $y$ are sets, then there is a set $z$ which contains $x$ and $y$ as elements. Formally, we say

   $$\forall x, \forall y, \exists z \text{ s.t. } ((x\in z)\land (y\in z)).$$

5. Power Set. If $x$ is a set, we say $y$ is a subset of $x$ (or $y\subseteq x$, or $y\subset x$) if every element of $y$ is an element of $x$. Formally,

   $$\forall z( z\in y\implies z\in x).$$

   The axiom of power set states that for each set $x$ there is a set $\mc P(x)$ such that if $y\sub x$, then $y\in P(x)$. Formally,

   $$\forall x, \exists \mc P(x) \text{ s.t. } (\forall y (y\sub x \implies y\in \mc P(x))).$$

6. Union. If $x$ is a set, there is a set $\bigcup_{y\in x}y$ which contains $z$ for each $z\in y$ and for each $y\in x$. We can write this as

   $$\forall x, \forall y, \forall z, \exists w, \text{ s.t. } (((z\in x)\lor (z\in y))\implies z\in w.$$

   If $y$ and $z$ are sets, we apply this axiom to $\{y, z\}$ (which is a set by the axiom of pairing) and denote the result $y\cup z$.

7. Infinity. Let $x$ be a set. We know that $\{x\}$ is a set by the axiom of pairing; then the set $\{x, \{x\}\}$ exists by the axiom of pairing as well. Define $S(x)$ to be

   $$S(x):= \bigcup_{y\in \{x, \{x\}\}}y = x\cup \{x\}$$

   there is a set $X$ containing both the empty set $\emptyset$ and the set $S(x)$ for each set $x\in X$. (This axiom effectively asserts the existence of the natural numbers, as we’ll see next week).

8. Regularity. Every non-empty set $x$ contains a member $y$ such that $x\cap y = \emptyset$. If $x\cap y = \emptyset$ we say that $x$ and $y$ are disjoint. We can write this logically as

   $$\forall x(\lnot(x= \emptyset)\implies \exists y \text{ s.t. }(y\in x\land (y\cap x = \emptyset)))$$

   This exists to ensure that paradoxes don’t occur. In particular, no set can be an element of itself; if there was a set $x$ such that $x\in x$,

A Note on Proofs