Set Theory and Beyond

[I continue writing in the form of a dialogue between Master (M) and Apprentice (A).] A: O Noble Teacher, last time we talked, you said that a unary relation is just an arbitrary set. But you didn't explain why would you introduce another word just to mean "set"! M: O My Dear Apprentice, that is because when we say \(R\) is a unary relation, we usually have context in mind and we usually say more. For example, we might be thinking about some set \(X\) and then we might say that \(R\) is a unary relation on set \(X\) . In this way, we want to say more then just "\(R\) is a set". Formally, we mean that \(R\) is a subset of \(X\), but intuitively, we separate elements \(x\) of \(X\) into those for which the relation \(R(x)\) holds and those for which the relation \(R(x)\) does not hold. Here, "\(R(x)\) holds" just means "\(x\in R\)" and "\(R(x)\) does not hold" means \(x\in R-X\). A: Okay, that makes more sense. But what about binary r...

I'll write this post in form of a dialogue between Master (M) and Apprentice (A). A: Say, O Noble Teacher, what are those "relations" that mathematicians always talk about? M: Why, my dear Apprentice, you have already seen one kind of relations! A: How so, O Exalted One? M: Well, \(\in\) is a relation and \(V\) is also a relation! These are class-sized relations. A: Oh, I see! But how does their "relation-ness" manifest? M: In the case of \(\in\), it divides pairs of sets \((x,y)\) into those for which \(x\) belongs to \(y\) and into those for which \(x\) does not belong to \(y\). So, it tells us whether the statement ''\(x\in y\)" is true or false for any particular pair of sets \((x,y)\). In this sense, they are no different from predicates or classes. Class-sized relations are the same thing as predicates. A: I seem to understand now! \(\in\) is a binary predicate, so a class-sized relation. \(V\) is a class, which is the same thing as a unary pr...

So far, I listed Axioms of the Empty Set, Extensionality, Pairing, Union, Comprehension, Induction, Replacement, and Infinity. This is not the complete list making up the Mathematical Theory of Everything, we have to add two more axioms to the list. These axioms are called Powerset  and Choice . Axiom of Powerset is relatively easy to state: for every set \(x\) in the universe, there exists a set whose elements are exactly all subsets of \(x\) . As usual, Extensionality implies that such object must be unique and we denote it by \(P(x)\). So, the defining characteristic of the set \(P(x)\) is that a given set \(y\) belongs to \(P(x)\) if and only if \(y\) is a subset of \(x\). The other axioms don't imply existence of the powerset. More precise explanation of this will have to wait, but for now, we can kind of see that the set \(P(x)\) is "larger" than \(x\). If \(a\) is an element of \(x\), than \(\{a\}\) is a subset of \(x\), so an element of \(P(x)\). But there are oth...

We now want to learn how to count. This is how it usually goes: we start from \(0\) and then we keep passing to the successor, that is, \(0\) is followed by \(1\), which is in turn followed by \(2\), which then gives its place to \(3\), and so on. Since these objects are essential for mathematics, one would rightly expect them to appear in the universal theory of mathematics, i.e. Set Theory. Well, this is what they are: \[0:=\emptyset\] \[1:=0\cup\{0\}=\{0\}\] \[2:=1\cup\{1\}=\{0\}\cup\{1\}=\{0,1\}\] \[3:=2\cup\{2\}=\{0,1\}\cup\{2\}=\{0,1,2\}\] and it continues. The problem, though, is that it continues indefinitely... This means that I can't possibly just list all definitions and have you know what the natural numbers are. A more sophisticated approach is required! The starting point is \(0\), which is just empty set. Now, to get new natural numbers, you pass to the successor. The way I wrote my definitions above was to suggest what the successor operation  should be. In the prev...

 Once we have ordered pairs (which we got in the last post), we are ready to define all kinds of important mathematical objects. The most obvious one is probably the product  \(A\times B\) of two sets \(A\) and \(B\). The definition is pretty straightforward: \[A\times B:=\{\langle a,b \rangle : a\in A,\, b\in B\}.\] However, we should ask ourselves if this is a set: as far as we know it, there is nothing preventing this one from being a proper class! So, as you might've guessed, we solve our problems by declaring new axioms. 😎 I'll now try to describe Axiom of Replacement , which should (together with our old axioms) imply that \(A\times B\) is a set. Remember that we had the notion of a predicate \(P(x)\). What we meant here was a property that a set may or may not have. Very similarly, we can consider a property \(R(x,y)\) that the ordered pair of sets \(x\) and \(y\) may or may not have. One way to think about it is that we can look at some predicate \(R^*(z)\) such that ...

 We've already introduced the notion of a pair of sets \(\{x,y\}\). This object is symmetric insofar that it doesn't give a precedence to either \(x\) or \(y\). One way to formally state this is to observe that \[\{x,y\}=\{y,x\}.\] This follows simply from Extensionality: both sets have same elements! On the other hand, it will be of no surprise to you that sometimes we need an object which pairs together \(x\) and \(y\), while keeping the information which one comes first. Let us denote this ordered pair by \(\langle x,y \rangle\). According to our guiding principles, this should be another set, just another object in \(V\). This means that, even though we have a clear idea what the object \(\langle x,y \rangle\) is, we need to pick a concrete way to code it within the universe. I say "pick" because there is more than one way to do so and giving the precedence to one over another is basically arbitrary. So, let us make our choice and define the ordered pair of sets \...

We now know what \(V\) is, the universe of all sets. We started this journey in order to build this universe and one of the guiding principles was that all objects in the universe are just pure sets. However, it is not completely clear what this means, so I went on to say that sets should be determined by their elements and nothing else. We had so far only one axiom that asserted this kind of "setness" of sets, that is the Axiom of Extensionality. Arguably, though, this is not enough. For example, nothing that I've said up to now can answer whether there exists a set \(x\) which belongs to itself. Even more concretely, is there a set \(x\) which is equal to \(\{x\}\)? I'm sure that you will find a prospect of such an object unusual, after all it would satisfy things like \[x=\{x\}=\{\{x\}\}=\{\{\{x\}\}\}=\cdots.\] Furthermore, say that \(y\) also satisfies \(y=\{y\}\), is then \(y\) equal to \(x\)? If they're not equal, then \(y\) is an element of \(y\) which is d...