The Set Theory Guide for Artists Chapter 1: Part 3
It will get weird
CHAPTER 1 INFINITY
PART 1: PACK YOUR BAGS FOR THE TRIP OF A LIFETIME
PART 2: MORE INFINITE OBJECTS WE LOVE
PART 3: IT WILL GET WEIRD
PART 4: THE INFINITY CHAPTER PAINTING
PART 3: IT WILL GET WEIRD
To end Chapter 1, we get an idea of what is to come in the universes of set theory. We deconstruct our mathematical world in order to understand our foundations and stretch the limits of infinity. In this section we will introduce a discussion of languages, models, elementary submodels, Skolem functions, and the Löwenheim-Skolem downward theorem to get a hint of the strangeness of set theory.
A language is a collection of symbols (with some meaning). In logic, a language is also a collection of symbols, it is the function, relation, and constant symbols. In addition to the symbols of the language are the logical symbols (including variables) and punctuation
which combine with the function, relation and constant symbols to form the terms and formulas of the language. The language of set theory consists of just the membership relation. In the next chapter we will see how to convert a statement in words into a statement in the language of set theory.
A model
for a language L includes a universe (of numbers) A and an interpretation of the symbols of the language in the universe of numbers. For example, the language may have a
function symbol. The interpretation of this symbol
in a model of arithmetic is the real addition function that means what we mean by addition, and we will often conflate the two. The natural numbers are a universe for a model of arithmetic.
But what is our universe of numbers in set theory? It should include the natural numbers, ꙍ + 1, the real numbers, and many more. What counts as a universe of set theory is central to set theory, and we will discuss more in Chapter 3 on set formation and in Chapter 2 on the axioms.
The language of set theory consists of just one binary relation, the membership relation
In order to interpret what the membership relation means, we have to know what counts as a set. For example, is the union of sets a set? Is the image of a set under a function necessarily a set? Having a model for set theory implies that we know what a set is, and the axioms in the next chapter describe the various collections that count as sets, starting with the empty set.
Let us think about the formulas of a language. For example,
is a formula in arithmetic and we can find different values of x and y such that the equation holds, such as (1,1). We can write this as
Let M be a model of arithmetic. Then the way to write that this statement is true in M is to use the satisfaction symbol (which is a meta-symbol just for us so that we can talk about the models and what they think)
We say “M models phi” or “M thinks phi” or “M satisfies phi” or “phi is true in M”.
A model is like a production of a play or movie, where the language and the logical symbols are the script, the intended props, and the set design. The universe of numbers is the cast, and the director and producers interpret the language to create the production. The satisfaction relation is like saying that something happened in the play. The Skolem functions, which we will see next, play the very important role of casting directors.
We will talk about formulas and terms a little bit here and in the next chapter we will dig into more of the details. Examples of a terms are
The terms include and are built up from the constants, variables, and function symbols. Examples of atomic formulas are
The atomic formulas are terms with relation symbols or the equality symbol between them, and then more formulas can be built up from the atomic formulas. A term is a part of a formula, and a formula is saying something about its terms. A function symbol on its own with variables and constants is not an atomic formula because it is not saying anything until we add an equality symbol or a relation symbol and another term. A term is like a set with two chairs and a table with an apple on the table between two characters, while an atomic formula is one character picking up the apple attempting to take a bite. Then this can be built up to a bigger formula where the other character is trying to stop them, and these build up to create a scene.
Consider the formula
In this formula, x is a free variable because we could let x be 2 and get 2 = 2 which is true in a model of arithmetic. And if we let x be 3 then the formula is 3 = 2 which is not true in a model of arithmetic
If
we can write the above observations with the satisfaction relation as
and
If we add quantifiers, the formula x = 2 no longer has free variables. A formula with no free variables is a sentence.
The sentence
means there exists an x such that x = 2, which is true in M,
The sentence
means for all x we have x = 2, which is not true in M,
Let
be a model in the language L with universe A. Consider a formula
where x is a variable and the aᵢ are constants in A. Suppose there is an a in A such that
A Skolem function
for φ assigns the sequence
to a solution of φ aka
That is, if h is a Skolem function for φ then
implies
A Skolem function is like a casting director for scene φ when all of the roles except one have been filled. For this scene φ, the casting director h can find the right person to fill the role from the set of players A. If there is a role to fill for the scene, then given that all the other roles have been assigned, the casting director can assign the role and can do so for any combination of players filling the roles that have already been assigned.
Let X be a subset of players in the universe A of all players that can possibly be assigned roles in the production. In each scene φ assign all but one role to players in the subset X of players, and consult with the casting director about casting the final role, and do this for every possible combination of players in X for the scene. There may be a situation where there is a scene which needs a role to be assigned and the only person in A that can fill the role is a player not in X, so they are invited to join the cast. The final cast list is the Skolem hull of X.
If our language is countable, and X is countable, then the Skolem hull is also countable because for each of the countably many scenes we only had to pull in a finite amount of additional players for an overall countable Skolem hull.
A submodel (subproduction)
is a subset
with relations, functions, and constants restricted to B and closed under functions with constants in B.
A model
is an elementary submodel (elementary subproduction) of
written
if
That is, for any scene φ that works with players from B in production B will also work for production A.
Elementary submodels satisfy the same (first-order) sentences as the original model. That is, an elementary subproduction will have the same scenes as the original production.
We can construct an elementary submodel
if we guarantee that if
where
then there is an
such that
That is
is an elementary subproduction if whenever there is a scene φ with all but one role assigned with players from B, there is a player in B that can fill the role. This is the Tarski-Vaught test for elementary submodels.
If
is a subset of players, the Skolem hull of X will form an elementary subproduction.
Imagine not just a production of a play, but the entire production of set theory (including the production of all of mathematics), call it V.
One day there was a big storm and the only way for the players to get to the theater was to take a bus which had only countably many seats.
Can the show go on?
Can the casting directors find countably many players to pull off a show that includes, for example, the uncountability of the reals?
Indeed, the show must go on. The show can go on by the Löwenheim-Skolem downward theorem:
Every infinite model for a countable language has a countable elementary submodel.
Ever feel like something is out of reach and then you get to it but it is not totally satisfying and you want to reach for more? This is the nature of life and this is the nature of mathematics. Mathematicians try to capture mathematics, but she will always elude them and that is why they love her. We will see that Gödel showed that mathematics cannot prove its own consistency. There are also independent statements in mathematics. Cohen showed that CH is a statement which is true in some universes and false in other universes with forcing, which we will see in Chapter 6. The method of forcing that developed after Cohen’s breakthrough has a lot of strange and interesting interactions with large cardinals. In Chapter 7 we will see how to use forcing to softly kill large cardinals and degrees of large cardinals and thus witness a delicate battle between the great power of infinity and the great power of the changeability of mathematics.
See Joel David Hamkins’ chapter on Skolem’s paradox for more of the possible interactions between models and elementary submodels:
Very nice treatment of LS!