Lesson (I)
Table of contents
- Set theory as a foundation for mathematics
- Building Sets
- Some Important Sets
- Operations on Sets
- Equality of Sets
- Classical Sets
Set theory as a foundation for mathematics
Set theory is a foundation for mathematics. This means
- All abstract mathematical concepts can be expressed in the language of set theory.
- All concrete mathematical objects can be encoded as sets.
- We can write down our mathematical reasoning in set theory: true statements about mathematical objects can be deduced from the axioms of set theory and the rules of logic.
Georg Cantor, the founder of set theory, gave an informal definition of sets:
By a set we mean any collection of determinate, distinct objects (called the elements of ) of our intuition or thought into a whole.
Cantor defined sets to make the idea of infinity, which were objects of fascination for millennia, precise, but soon set theory took a much bigger role in mathematics: It became a foundation for the whole of mathematics. This was due to work of many brilliant set theorists and mathematicians, most notably Bourbaki. All mathematical objects you may see in any undergraduate mathematics course is a set: This includes geometric objects such as manifolds, vector bundles, etc as well as algebraic objects such as monoids, groups, rings, etc.
For us, a set is a collection of elements from a specified universe of discourse. The collection of everything in the universe of discourse is called the universal set, denoted by .
Given a set of objects in some universe and an object , we write the proposition to say that the element belongs to the set . We write as shorthand for the proposition .
Building Sets
How to Form Sets
But it is not enough to just have a vague of idea of what sets are, we actually need to know how to form sets. Cantorβs informal characterization suggests that whenever we have some property (aka predicate), , of a domain , we can form the set of elements that have the property . We denote this set by We read this as βthe set of element of such that β or as βthe set of element of which satisfy β.
The notation above is called the set-builder notation. We call the set the extension of property/predicate .
In above the predicate had only one variable (aka parameters), but in general it can have many variables. For instance consider the exmaple over real numbers. The set is the set of all points in the 2-dim plane which lie on the line described by the equation .
Or we can have a predicate
where is a temperature variable measured in centigrade and is a humidity variable measured in percentage. Now, we can form the set of all places in the world where the predicate holds:
Note that we substituted terms and for and in (Recall how the substitution of terms in predicates works from the lesson on predicates).
When forming sets using predicates, we can think of the predicate as a sort of filter or checking mechanism: it selects βs according to the filtering criteria.
Hereβs another example: Consider the set of natural numbers and the predicate over , that is
We form the set of even numbers as follows:
Sometimes in informal mathematical writing, you see the notation for the same set . This notation rely on the readerβs ability to infer the pattern being followed and correctly guess the intention of the writer, so use it with caution, or better yet, do not use it!
Here are more examples of sets written in the set builder notation:
But the following expressions do not form a set:
βοΈ Challenge
Suppose is a predicate on natural numbers. In below, we are defining sets , , using the set builder notation. Determine which of the following expressions correctly determines a set, and which ones are incorrect/illegal?
Different Notations
Sometimes a set is formed without the domain of the predicate being (explicitly) specified. In such a case, we can think of the domain being the universal set . Therefore the set
is a shorthand for the set
This sets pick all the elements in the universe which are natural numbers.
An alternate form of set-builder notation uses an expression involving one or more variables to the left of the vertical bar, and the range of the variable(s) to the right. The elements of the set are then the values of the expression as the variable(s) vary:
For example, the expression denotes the set of even numbers. It is shorthand for .
We can even use a mix of the two notations: The set consists of all numbers whose predecessor is a square of a prime number.
Some Important Sets
Using set-builder notation, we can define a number of common and important sets.
- The empty set:
- The universe:
- Singleton sets: for an object , the singleton set is formed as .
- For distinct objects and , gives the set .
- Similarly, describes the set contaning elements .
We say that a set is inhabited if it has at least one element. Formally, a set is inhabited if the sentence or equivalently the sentence is true.
We say that a set is empty if it is not inhabited, that is the sentence is true. A set is non-empty if it is not empty.
βοΈ Challenge
Give a constructive proof that the set is empty.
βοΈ Challenge
Give a natural deduction proof of the fact that that every inhabited set is non-empty.
We say that a set is decidable if the sentence holds.
Operations on Sets
Using the set-builder notation, we can define a number of primary operations on sets.
- Union of sets and is given by the set
- Intersection of sets and is given by the set
- Complement of a set is given by the set
- Relative complement of set with respect to set is given by the set
One can define many more operations on sets, but they can be derived from these primary operations. This is similar to the situation with logical connectives. An important example is the disjoint union of two sets, say and , defined as follows:
Sometimes we denote the disjoint union with a different notation, namely ββ. For instance,
Challenge
What is ?
Challenge
Describe the elements of and .
By their definition, the primary operations on sets are intimately related to the logical connectives. In fact one can prove that
The connection between logic and set theory runs even deeper; we make this more clear once we are equipped with the notion of function between sets.
Equality of Sets
A mathematical principle is that whenever we introduce a mathematical concept, we should ask ourselves what it means for two instances/realizations of that concept to be identified (aka equal). For instance, for the concept of natural number, this is intuitively clear to us: we know without a moment of reflection that but . However when the concepts we introduce get more complicated judging whether there is an identification (aka an equality) between instances of those concepts becomes less obvious.
Here, we ask ourselves when two sets are equal?
- Are the sets equal?
How about βthe set of prime numbers less than β and βthe set of even prime numbers greater than β?
- How about
We define two sets and to be equal precisely when they have the same elements, in other words, every element of is an element of and vice versa. We write to denote the equality of and .
The formal sentence expressing is
Let us define predicate and by Therefore, the definition of equality of sets says that and are equal sets if and only if and are equivalent predicates. Conversely, starting from equivalent predicates and , ranging over a domain , we obtain the equality
We say that this notion of equality is extensional since although two predicates and can have different intensions they can have the same extension and therefore giving rise to the same sets. Consider for instance the example above where is defined to be β is a prime numbers less than β and is defined to be β is an even prime number greater than β.
Therefore, using the extensional definition of equality of sets, the answers to the questions (1)-(3) of the previous slide are all positive.
As an example we prove the distributivity of intersection () over union () of sets.
Theorem. Let , , and denote sets of elements of some domain. Then
Proof. Let be an arbitrary element of . Then is in , and either is in or is in . In the first case, is in and is in , and hence is in . In the second case, is in and , and hence is in . Therefore, is in .
Conversely, suppose is in . There are now two cases:
- First, suppose is in . Then is in both and . Since is in , it is also in , and so is in .
- The second case is similar: suppose is in . Then is in both and , and so also in . Hence, in this case also, is in , as required. .
You should be able to translate the proof above into a natural deduction proof, although it may look a bit unruly.
Challenge
Construct a natural deduction proof of the sentence
Challenge
- Prove the following equalities of sets, possibly using the Law of Excluded Middle. Identify the statements whose proof require invoking LEM. Explain why.
- How do you describe the resemblance between the columns?
For sets and , the set is said to be a subset of , written if every element of is an element of . In contrast to equality of sets we can think of as βinequalityβ of sets. It is similar to the inequality (We make this idea more precise later when we will talk about partial orders.)
Formally, is expressed by the sentence [ \forall x \; (x \in A \To x \in B) \, . ]
Challenge
Do you think that ? Justify your answer by providing a proof or a counter-example.
Theorem. For any two sets and we have if and only if and .
Challenge
Prove the following facts about the subset relationship:
- For all sets we have .
- For all sets , and , if and then .
- For all sets we have .
- For all sets , , if then .
- For all sets , , if then .
Challenge
Which of the following statements are true regardless of the choice of sets ? Justify your answer.
Challenge
Constructively prove the following inequlities of sets.
Classical Sets
We can show constructively that for any set ,
βοΈ Challenge
Show that the Law of Excluded Middle is equivalent to the statement that for every set ,
De Morgan for Sets
Since sets are formed as extension of predicates we expect to have the following equalities of sets if we reason classically.