Set Theory
Everyone's been abuzz about sets, so let's build up the motivation and definition for set theory.
Part 1: Classes
Once you've defined a theory, you can reference individual objects using the terms of the language. For example, 1, 4, 3+2, etc, and you can prove things about them. How can you refer to more than one object at once?
Well, an easy way might be with a formula with one free variables. For example, you can look at even numbers in the theory of Peano Arithmetic as such:
∃x 2*x=y
Let's call this phrase "E", E is the sentence which represents whether y is even.
This represents exactly when "y" is even, so if something, let's say Q is true for all even numbers y, you can say Q:
∀y E ⇒ Q
"For every number, if it is even, then Q is true."
But that's the 'same' thing as saying that "The numbers for which E is true are a 'subset' of the numbers for which Q is true." Subset is in quotes because technically we haven't defined it.
We call these classes. A class is just a formula that is 'true' for some things, and 'false' for others. So we can kind of think of whether some number is 'in' a class by checking whether the class says its true.
So E is the "class" of even numbers. Any collection of objects in a model you can somehow reference and 'detect' what things are in and out of it counts as a class.
We call the ones we can actually write down an expression for the "defineable" classes, but you can 'imagine' that there is some class that you cannot write down a formula for, since there are countable amounts of writeable-down formulas and some models with uncountable amounts of elements.
You can spend some time figuring out how to deal with and detect these things. For example, how can you define that a class has "two" elements? For some class P with free variable z such that, it has two elements x and y such that if and only if z is in the class, then either x or y are z.
∃x∃y∀z P ⇔ (x=z ∨ y=z)
Noticeably this is a sentence that has a "free" class. We're starting to use these classes as variables, but variables (the way we've talked about them so far) can only directly be the elements of the model.
But what about referencing collections of classes? For example, the "class" of all classes that have two numbers. This would also need us to be able to refer to classes of things as variables.
And you can't just say "Oh yes I can just look at classes of classes willy nilly, variables can refer to whatever you want", you run into russel's paradox. What is the class of all classes? What if I filter it on whether a given class contains itself? The class of all classes that do not contain themselves. Does it contain itself?
So it starts leading to all sorts of problems, and you get stuck.
And THERE IS A WAY TO DO THIS, but it requires being careful in a different sort of way. Your ability to do this is very closely related to the "order" of a logic system. The amount you allow yourself to do this is going to deeply affect how much you can prove and there are good incentives to prevent yourself from doing this.
For now, though, we will stick to only defining classes of elements, having variables refer to actual elements. Collections of terms. This is the solution that tries to keep everything in 1st order.
Part 2: Sets
So...
What if you made a theory where the elements themselves each represent classes? That would kind of solve it.
Of course, you'd have to be careful, but then if you had a whole system where each element represented a class, then you could consider classes of these elements, and they would kind of be like classes of classes? Let's call these class-representing elements "sets". We can consider a relation "in" which tells you whether the class it represents 'contains' some element. In this way, for an element x, you can regain the class by looking at "y in x". We can even give it a symbol, ∈, y∈x, for convenience, because we're mathematicians and we're lazy.
(In case you forgot we do most things 'cause we're lazy. We came up with sets because we were too lazy to deal with the problem of Russel's paradox and higher order logic and instead figured we could do everything with sets, instead of working out how classes of classes work.)
Let's imagine you can do this arbitrarily, where every single class is represented by a set. Now again, consider the class Q of every class which does not contain its own set-representation, does this contain its own representation?
Again, paradox. If it Q contains the set X which represents it, then definitionally, it does not contain X. If it does not, then it would contain it. Both ways we get a contradiction. So there is no way to make a theory which contains a set that represents every single class.
What about one that contains some classes?
Well, obviously, you can do this. For example, the theory of one element, "x", and you claim "x" represents the, say, empty class. This is missing the class that is the class of everything, but evidently doesn't run into any other problems.
Okay, so, how many sets can we "fit" in? How big can we make it? How small can we make it and keep it useful?
Part 3: ZF
Eventually, we came up with some list of rules for how we should do it. Which sets we actually want to include. The main "famous" one of these is ZF. It has the following rules:
1: Extensionality:
∀x∀y (∀z z∈x⇔z∈y) ⇒ x=y
I actually broke this one down, in colour, in my math notation post.
The notion here is that if you have any two objects in the model, they only represent the same class if they are the same object. You can't have a class being represented by more than one object. This is a good rule of convenience. Don't give more than one name to each class. This is kind of the same thing as saying that sets only care about what's in and out of the set and have no way of detecting repeats or ordering.
2: Pairing
∀x∀y∃z (x∈z)∧(y∈z)
If you have elements x and y, there is a set {x,y} that contains both of them. Notably this doesn't actually state there's one that contains exactly both of them. That's because it's easier to work with just this, and then use an axiom from the Axiom Schema of Separation to filter out all the extra elements.
3: (Schema of) Separation:
For every definable class P:
∀z∀w₀...∀wₙ∃y∀x (x∈y) ⇔ (x∈z∧P)
This says that you can filter a set on any defineable class, that is, you make it a rule for every formula you can write down P, with free variables x, w₀,...wₙ, then for any given set y, you can filter it on P, creating the set of elements such that they are in y, and also P.
That is, you're allowed to do this, {x∈y | P}
4: Union
∀F∃A∀Y∀x (x∈Y∧Y∈F) ⇒ x∈A
This means that if you have a set of sets, you can take the union, that is, the set that contains all the elements that are in any of the sets.
5: Power Set
∀x∃y∀w(∀z z∈w ⇒ z∈x) ⇒ w∈y
"The power set exists", or more carefully: "there is a set that contains all the subsets". Notably here we also get the shorthand x⊂y for ∀z z∈x ⇒ z∈y. This isn't part of our initial language but rather a shorthand that we can imagine "technically" expands when we need it, thus we don't have to add it to the language.
We can thus also express this as:
∀x∃y∀w (w⊂x) ⇒ w∈y
6: (Schema of) Replacement
For every definable function class F:
∀w∃y∀z (z∈y)⇔ (∃x (x∈w)∧F)
This one is fairly intuitive to explain, but I add it here because it actually adds in "most" sets and makes a lot of the ones above superfluous when phrased correctly. Usually, you can consider a "function class" to be a class with free variables x and y, where for the x that have a y that make it true, that y is unique. This is sort of like saying that a "function class" for a function "f" is just checking "f(x)=y". There can only be one y such that f(x)=y. This is also called the "graph" of a function.
This is very powerful. You might notice that along with powerset, extensionality, and union, it actually allows you to replace pairing and separation, cutting down this beginning to only four axioms. We traditionally include them because it's easier if we can see them.
I've gotten what I deem to be the more immediately intuitive ones out of the way, and that leaves 3 more in the standard writing-it-out that I remember.
7: Foundation
∀x((∃a (a∈x)) ⇒ ∃y (y∈x ∧ ¬∃z (z ∈y ∧ z ∈x)))
Or using more shorthands:
∀x (x≠∅ ⇒ ∃y (y∈x ∧ y∩x=∅)
I will leave it as an exercise for how this does actually work out to these shorthands.
This may seem like a weird condition. "Only include the sets that include elements that are disjoint from the initial set."
But this is really a way of detecting that every set contains elements that contain elements that contain elements that ... that eventually go down to the empty set. That is, there doesn't exist* (up to weird compactness business), sets containing sets containing sets containing... (ad infinitum). You eventually run out.
...x8∈x7∈x6∈x5∈x4∈x3∈x2∈x1∈x0
This does not go on infinitely to the left.
How is this the same thing as the condition? Well in one direction, assume you do have such a chain, and consider the set {x0,x1,x2,x3,x4,x5...}, then that set does not contain an element disjoint from itself, since if you pick xn, you get x(n+1) as an element in common. If you have such sequences, you can make such sets. In the other direction, if you have such a set, you can pick an element, and then pick an element it has in common with the set as a whole, and keep on doing this forever, creating a chain. This ensures all elements eventually fall down to being the empty set. This also prevents nested sets, like X = {X} is not valid, and thus prevents russel's paradox.
8: Infinity
∃X(∃e(∀z ¬(z∈e)∧e∈X) ∧∀y ((y∈X)⇒(∃w w∈X ∧∀v (v∈w)⇔(v=y)∨(v∈y)))
So far, nothing has let us actually "get" to infinitely large sets. There's a number of ways to do that, but the way that it is traditionally formulated is by doing the following: Union(x, {x}) is a new set, since it cannot be x or anything in x by regularity. And since it includes all the elements of x, it keeps on generating a new set, so if you claim there's a set that contains the empty set, and is also "closed" under this, that is, for every element contains also Union(x, {x}), you get an infinite set. We'll shorthand that as S(x) and then it all fits together like this:
∃X(∅∈X∧∀y (y∈X⇒S(y)∈X))
This gives you one infinite set. Using replacement, you can use it to get other infinite sets, and using power set you can get "bigger" infinite sets. To be careful about getting 'all' the infinite sets you care about, we will have to study well orderings and sets a lot more. This is just the base introduction.
Next time we'll start introducing choice and other such axioms! But for now, this is the definition of a set! In this same sense, a class is called a "proper class" if it has no set representation, such as the class of all sets. In some contexts, like category theory, classes are called "small" if they can be represented with a set. IE: "Small" categories have objects and morphisms that are both represented by sets.
