ZFC set theory

go home
prerequisites:
table of contents:
so the 🟨introductory mathematical logic and proofs page of this site went over the basics of mathematical logic and proofs (duh), often using sets. however, these sets were defined in a "hand-wavy" (the term often used is naive) way. kind of ironic that the intro to rigorous math was built on a system which itself wasn't rigorously defined, right?

this page will introduce you to the foundations of modern math and the rules that govern it!

background

so what's wrong with the sets we had before?

the main issue is that we could make sets of literally anything.
the set of all sets which do not contain themselves... is that actually allowed?

in our old system, there's nothing stopping us from creating it:
this by itself doesn't violate any of the laws of logic we agreed on originally, but consider this proposition: $$\text{The set of all sets that do not contain themselves contains itself.}$$ is this true? according to the law of excluded middle, it has to be either true or false, so let's try to find out which one it is. $$ \text{Let }A=\{x:x\notin x\}\\\\ \text{If }A\in A\text{, then }A\text{ must satisfy the membership statement, so }A\notin A\\ A\in A\rightarrow A\notin A\text{... contradiction}\\\\ \text{If }A\notin A\text{, then }A\text{ satisfies the membership statement, so }A\in A\\ A\notin A\rightarrow A\in A\text{... contradiction} $$ hold up, wait a minute... somethin' ain't right.

"Gottem."
- Bertrand Russell, 1901

what we've stumbled upon here is called Russell's paradox, and it shows that set theories with unrestricted comprehension (AKA "any collection of things is a set") lead to contradictions.

this is what mathematicians call "really freaking bad," since it means that the logical system that was being used has "holes" in it, so to speak. so how was this addressed?

well, mathematicians back in the day had to sit down and answer these questions:
answering these questions properly would mean the birth of a system of mathematics which would be "perfect."

so, some really smart people did some really smart things, and today, we have ZFC set theory.

ZFC is the name given to Zermelo-Fraenkel set theory with the Axiom of Choice, the contributors being the namesakes Ernst Zermelo and Abraham Fraenkel, as well as other guys who helped out but apparently don't get to put their name on the system for some reason, such as Thoralf Skolem and John von Neumann.

so great! we found the perfect mathematical system now, right?

"Nah."
- Kurt Gödel, 1931

wellllllllll, Gödel actually showed that it is impossible to create a perfect mathematical system: every axiomatic system of math will have some inconsistencies or some unprovable statements.

however, there is no need to fret! instead of trying to create a perfect mathematical system, we can just pick one that works really well for the types of questions we want to answer, and ZFC happens to be that! this does mean, though, that there are "alternate mathematical universes" based on different axioms... which is awesome!

but enough about the math multiverse... let's get into ZFC!

axioms

the language of ZFC is based on these fundamental building blocks:
this means that the laws of logic/proof techniques that we learned about before still work; we are just formalizing sets.

additionally, on top of the philosophical laws of logic from before, we will add our own rules, called axioms, regarding mathematical objects within ZFC.

let's go through them!
  1. Axiom of Existence: there exists a set. $$\exists x,x=x$$ congratulations! this is the very first building block of our mathematical universe: the set.

    ZFC's basic concept is the set, and everything else that you will later recognize (numbers, functions, etc.) will be made of sets.

    all this axiom says is that there is a set; we don't know what's in it, but it's there!

    actually, we haven't said what a set is yet either. for that, we will need...

  2. Axiom of Extensionality: sets are defined by their elements. $$\forall x \forall y, ((\forall z, z\in x\leftrightarrow z\in y)\leftrightarrow x=y)$$ this axiom says if two sets have the same elements, then they are the same set.

    it also kind of defines the in symbol \(\in\) (sets have stuff "\(\in\)" them).

    so great, we now know that sets have stuff in them, and that the stuff that is in them is what defines them.

    notice that this axiom says nothing about the order of elements; it just says if each element in one set is in the other (and this is true both ways), then the sets are the same.

    we have now recovered the notion of a set being an "unordered collection of distinct objects," but we need to define some more rules to help create more sets using sets!

  3. Axiom of Pairing: for any two sets, there is a set containing those two. $$\forall x \forall y \exists z \forall u, (u\in z\leftrightarrow (u=x\vee u=y))$$ this axioms says that for any two sets \(x,y\), there exists a set \(\{x,y\}\).

  4. Axiom of Union: the union of any set of sets exists. $$\forall x \exists y \forall z, (z\in y\leftrightarrow \exists u\in x, z\in u)$$ this is NOT the normal union operation \(\cup\) between two sets; this axiom defines the big union operation \(\bigcup\) which combines all the elements of the elements of a set into its own set.

    that was kind of a mouthful, so it might be more insightful to see an example of how the Pairing and Union axioms work together to form the normal \(\cup\) operation between two sets: $$ a=\{p,q,f\}, b=\{n,m,g\} \\ X=\{a,b\}\text{ by Pairing axiom} \\ \bigcup X=\{p,q,f,n,m,g\}\text{ by Union axiom} \\ a\cup b=\bigcup X $$

  5. The Axiom of Power Set: for any set, the power set of that set exists. $$\forall x\exists y\forall z, (z\subseteq x\leftrightarrow z\in y)$$ "\(\subseteq\)" hasn't technically been defined yet, so here's the symbolic definition: $$z\subseteq x := \forall u, u\in z\rightarrow u\in x$$ this axiom says that the power set of any set exists and is itself a set.

    as before, we'll denote the power set of \(x\) with \(\mathcal{P}(x)\).

  6. The Axiom Schema of Comprehension/Specification/Separation/Collection: any collection of set elements which satisfy some property is a set. $$symbolic def will be added later$$ this axiom says that given some set \(x\) and a property \(\phi\), we can form the set \(\{y\in x:\phi (x)\}\).

    importantly, this is NOT unrestricted comprehension; the set \(x\) above is called the ambient set, and that is a REQUIREMENT to avoid issues with sets such as Russell's Paradox.

    if you define some collection of items without an ambient set (like \(\{x:\phi(x)\}\)), it is called a class.

    also, you probably noticed this is not called an axiom; this is an axiom schema, which is a rule that defines a family of axioms.

    each member of this family is an axiom about the property \(\phi\). since \(\phi\) can be any of a number of possible properties, we need a new axiom for each possible property. this axiom schema covers them all!

if you take just axioms 1-6 above, you form Zermelo set theory, which is, as it sounds, an ancestor of ZFC.

ok, that's cool, but right now the only thing we know exists is the set \(x\) from the axiom of Existence. although we don't know anything about \(x\) other than its existence, it can actually lead us to a set we recognize! $$ \text{By Existence, let }x\text{ be a set.}\\ \text{By Comprehension, form }z=\{y\in x:y\neq y\}\\ z\text{ has no elements, and what set has no elements?}\\ z=\emptyset\\ \therefore\emptyset\text{ exists!} $$ i've never been so happy to see the empty set in my life! our mathematical universe now includes \(\emptyset\).

also, since the axiom of Extensionality says that sets are defined by their elements, there is only one uniquely glorious \(\emptyset\).

and now, using using these axioms, we can create a bunch more finite sets, such as
however, we can't make any infinitely large sets, since none of the previous axioms guarantee we can talk about infinite sets.

if only there was some sort of... axiom of infinity or something... that would be CRAZY, right?
  1. The Axiom of Infinity: an infinite set exists. $$\exists \omega, \emptyset\in \omega\wedge(\forall y\in \omega, y\cup\{y\}\in \omega)$$ also, since it hasn't technically been defined yet: $$\forall y\in x,P(y):=\forall y,(y\in x\rightarrow P(y))$$ basically, we can restrict \(\forall\) to a set.

    anyway, this axiom says says that there is a set named \(\omega\) that contains $$ \emptyset,\\ \emptyset\cup\{\emptyset\}=\{\emptyset\},\\ \{\emptyset\}\cup\{\{\emptyset\}\}=\{\emptyset,\{\emptyset\}\},\\ \{\emptyset,\{\emptyset\}\}\cup\{\{\emptyset,\{\emptyset\}\}\}=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\},\\ ...\\ \text{and so on, ad infinitum...} $$ so, \(\omega\) must be infinite!

    \(\omega\) is actually a very important set to us, but we'll get to that once we are done with the axioms.

    last side note before we get to those: there are some that say that the axiom of Infinity should not be taken. these people are called finitists because they believe that only finite sets exist. that is not to say that finitists that when you count high enough you'll run out of numbers or something, just that they think you shouldn't be able to talk about a set with an infinite number of elements as an object.

  2. The Axiom Schema of Replacement: a transformation of a set is still a set. $$formal def will be added later$$ this axiom says that if \(f\) is a class function (like a function in naive set theory, but technically defined as a class instead since it may not have an ambient set) and \(x\) is a set, then the image of \(x\) under \(f\) is also a set.

  3. The Axiom of Regularity/Foundation/Well-Foundedness: every non-empty set has some element that is disjoint from the set itself. $$formal def will be added later$$

if you add on axioms 7-9 to Zermelo set theory, you get Zermelo-Fraenkel set theory (ZF).

and finally, last but certainly not least...
  1. The Axiom of Choice:

...