0Introduction
II Logic and Set Theory
0 Introduction
Most people are familiar with the notion of “sets” (here “people” is defined
to be mathematics students). However, most of the time, we only have an
intuitive picture of what set theory should look like — there are sets, we can
take intersections, unions, intersections and subsets. We can write down sets
like {x : ϕ(x) is true}.
Historically, mathematicians were content with this vague notion of sets.
However, it turns out that our last statement wasn’t really correct. We cannot
just arbitrarily write down sets we like. This is evidenced by the famous Russel’s
paradox, where the set
X
is defined as
X
=
{x
:
x ∈ x}
. Then we have
X ∈ X ⇔ X ∈ X, which is a contradiction.
This lead to the formal study of set theory, where set theory is given a formal
foundation based on some axioms of set theory. This is known as axiomatic
set theory. This is similar to Euclid’s axioms of geometry, and, in some sense,
the group axioms. Unfortunately, while axiomatic set theory appears to avoid
paradoxes like Russel’s paradox, as G¨odel proved in his incompleteness theorem,
we cannot prove that our axioms are free of contradictions.
Closely related to set theory is formal logic. Similarly, we want to put logic
on a solid foundation. We want to formally define our everyday notions such as
propositions, truth and proofs. The main result we will have is that a statement
is true if and only if we can prove it. This assures that looking for proofs is a
sensible way of showing that a statement is true.
It is important to note that having studied formal logic does not mean that
we should always reason with formal logic. In fact, this is impossible, as we
ultimately need informal logic to reason about formal logic itself!
Throughout the course, we will interleave topics from set theory and formal
logic. This is necessary as we need tools from set theory to study formal logic,
while we also want to define set theory within the framework of formal logic.
One is not allowed to complain that this involves circular reasoning.
As part of the course, we will also side-track to learn about well-orderings
and partial orders, as these are very useful tools in the study of logic and set
theory. Their importance will become evident as we learn more about them.