So, what’s set theory really about?
We’ll start off, for intuition’s sake, by talking a little bit about what’s now called naive set theory, before moving into the formality of axiomatic set theory. Most of this post might be a bit boring for a lot of you, but it’s worth
being a bit on the pedantic side to make sure that we’re starting from a clear basis.
A set is a collection of things. What it means to be a member of a set S is
that there’s some predicate PS – that is, some way of describing things via logic – which is true only for members of S. To be a tad more formal, that means that for any possible object x, PS(x) is true if and only if
x is a member of S. In general, I’ll just write S for both the set and the predicate that defines the set, unless there’s some reason that that would be confusing and/or ambiguous. (Another way of saying that is that a set S is a collection of things that all share
some property, which is the defining property of the set. When you work through
the formality of what a property means, that’s just another way of saying that there’s a
Set theory – as you can see even from the first definition above – is incredibly closely intertwined with first order predicate logic (FOPL). In general, the two can form a nicely closed formal system: sets provide a semantic basis for the logic; and the logic provides a set of tools for talking about sets. That’s a big part of why set theory makes such a good basis for mathematics: it’s one of the simplest things that we can use to create a semantically meaningful complete logic.
So I’m going to run through a quick reminder of the basic notations and concepts of FOPL; for more details, you can look at some posts about FOPL itself here.
In first order predicate logic, we talk about two kinds of things: predicates, and objects. Objects are the things that we can reason about using the logic; predicates are the things that we use to reason about objects.
A predicate is a statement that says something about some object or objects. We’ll write predicates as either uppercase letters (“A”, “B”), or words starting with an uppercase letter (“Married”), and we’ll write objects in quotes. Every predicate is followed by a list of comma-separated objects (or variables representing objects). So, for a few examples:
Dog("spot")is the FOPL form of the statement “spot is a dog”.
WorksFor("mark", "google")is the FOPL form of the statement
“Mark works for Google”.
Remainder("27","5","2")is the FOPL form of the statement
“2 is the remainder of dividing 27 by 5”. In general, when we’re using numbers
as objects, we’ll omit the quotes; so we could also write this
One very important restriction is that predicates are not objects. That’s why this is called first order predicate logic: you can’t use a predicate to make
a statement about another predicate. So you can’t say something like “
Transitive(GreaterThan)“: that’s a second-order statement, which isn’t allowed in first order logic.
We can join logical statements together to form more complicated statements: if α
and β are both valid FOPL statements, then α∧β (α and
β) α∨β (α or β), α⇒β (α
implies β, or if α then β), and α⇔β (α if
and only if β). We can also negate statements: ¬α (not
Finally, we have two quantifiers which we can use to create general statements
using variables. We’ll generally write variables as lowercase, non-quoted letters or words.
The two quantifiers are ∀ (for all), and ∃ (there exists).
We can use the quantifiers to make statements like
all x, y, and z, if x is greater than y, and y is greater than z, then x is greater than
The basics of set theory give us a small number of simple things that we can say about sets and their members. These also provide a basic set of primitive statements for
x∈S: the object x is a member of S; also the predicate
: S is a subset of T, meaning ∀x, x∈S &implies; x∈T.
: S is a proper subset of T, meaning that
S⊆T ∧ (¬T⊆S).
S = T: S⊆T ∧ T⊆S
One interesting thing to note about those definitions is that only "∈" is really a primitive: the others are all defined in FOPL in terms of "∈".
There are also a bunch of primitive operations on sets - that is, mappings
from pairs of sets to other sets:
A∪B: The union of A and B.
A∩B: The intersection of A and B.
x∈A∩B⇔x∈A∧x∈B(Thanks to Nat Whilk for catching a typo here.)
AB: set difference: x∈AB if and only if x∈A ∧ x∉B.
AΔB: symmetric difference: x∈AΔB if and only if x∈A∧x∉B ∨ x∉A∧x∈B (Errors corrected after being pointed out in comments.)
Finally, within the most basic set operations, there's a fundamental one called
cartesian product. The cartesian product of two sets S and T, written S×T
consists of a set of objects, containing exactly one unique object for every possible pair
or one element from A and one element from B. If a∈A and b∈B, then we'll call the
object in A×B that pairs a and b
(a,b). Given any two objects a∈A
and b∈B, we can find the object (a,b)∈A×B, and given any object
z∈A×B, we can find the unique objects a∈A and b∈B such that
Within this, we can talk about relations: given two sets A and B, a relation R is a subset of A×B. We'll often write that R(a)=b if (a,b)∈R. A function is a relation where for every object a∈A, there is at most
one object b∈B such that R(a)=b.
There are a number of special kinds of functions, some of which are really important. Given a function F from set A to set B:
- If for every a∈B, there is exactly one b∈B such that F(a)=b, then
F is a total function.
- If for every b∈B, there is exactly one a∈A : F(a)=b, then
F is called a surjection or onto function.
- If F is both total and onto, then F is called an isomorphism.
Two sets A and B have the same size or cardinality if and only if there exists an isomorphism between A and B. In some sense, any two sets with an isomorphism can be considered to be equivalent sets.