1. Mathematical notation and sets

The first part of our course is set theory. But… why do we study set theory? Why it is here where the whole higher mathematics starts?

I think that there are many answers to those questions. Set theory simply is in the heart of mathematics. It supplies the rest of maths with notions and assumptions. It gives mathematics its language. So that mathematicians are able to communicate in a precise way, which is easy to understand why such a precision is crucial in mathematics. Mathematicians achieved it fully (somehow in contrast to layers, where more precision is also needed…).

But there is more to that. Set theory is also a discipline which has elaborated perfect mathematical reasoning. Precise, logical, but also amazingly ingenious and spectacular reasoning. Ability to create such a reasoning, which one can improve studying set theory, seems to be the most basic ability of a good mathematician. And, I dare say, the most basic ability of an intelligent human.

Finally, the most elusive argument. Set theory magnificently shows the greatness of human mind. It describes an elusive part of the world, going on in a human mind. But it is not just thinking up things, it is discovering them. It feels extraordinary to be able to discover something using only your own mind.

What do we discover? We discover phenomena the most elusive matters, finding answers to the most extraordinary questions. Questions about infinity, about the sense of logical reasoning, about the nature of the world. The answers are absolutely rational and metaphysical in the same time, and show that between these two aspects there is no contradiction.

Mathematical language

This first class is devoted to introducing mathematical language, first attempts to proving things and dealing with sets.

Main notions:

  • \forall_{n\in\mathbb{N}} means “for all natural numbers n“, \exists_{m\in\mathbb{N}} means “there exists a natural number m“.
  • so \forall_{n\in\mathbb{N}}\exists_{m\in\mathbb{N}} m=n+1 means “for all natural numbers n there exists a natural number m such that m=n+1“.
  • to prove the above statement we should find such m for any given n, so for given n we let m=n+1 and we are done.
  • to disprove a statement we usually show a counterexample, e.g. to \forall_{n\in\mathbb{N}}\exists_{m\in\mathbb{N}} m=n-1, we set n=0 and notice that there does not exist m\in\mathbb{N} such that m=n-1.
  • \{n\in \mathbb{N}\colon 2\mid n\} means the set of all natural numbers n which satisfy the given condition (in this case n is divisible by 2).
  • operations on sets:
    • A\cup B — union of sets A and B — all the elements which are in A or in B
    • A\cap B — intersection of sets A and B — all the elements which are in both A and B
    • A\setminus B — difference of sets A and B — all the elements which are in A but not in B
    • A\triangle B — symmetric difference of sets A and B — all the elements which are exactly in one of the sets A and B.
  • you should get used to the situation that the elements of sets are sets. Actually in mathematics it is always the case.
  • we can denote finite sets simply listing their elements, e.g.: \{2,3,5\}. Sets do not have anything like order or multiplicity, so e.g.: \{2,3,5\}=\{5,2,3,2\}.
  • We say that something is an element of some set denoting it by \in. E.g. 3\in\{2,3,5\}.
  • Set A is a subset of a set B, if every element of A is also in B. We denote it in the following way: A\subseteq B, e.g. \{2,3\}\subseteq \{2,3,5\}. We say sometimes that A is included in B.
  • E.g.: set \{2,3,5\} has 3 elements: 2, 3 and 5, and 8 subsets: \varnothing (the empty set), \{2\},\{3\},\{5\},\{2,3\},\{3,5\},\{2,5\},\{2,3,5\}.

Proving equality between two sets

Now, let us talk about proving that two sets (usually defined by some set operations) are always equal, e.g. we will prove, that (A\cup B)\setminus C= (A\setminus C)\cup (B\setminus C) for all sets A,B,C. You already know from the lecture that there are three methods, out of which we will prefer the third one, because it is the most general method and it will be useful further in the course.

  • Venn’s diagrams method. We draw a diagram of the set which is on the left side of the equation and a diagram of the set which is on the right, computing the subsequent set operations. This method works for at most 3 sets, because it is impossible to draw more independent sets on a plane in an easy way (it is possible but not with circles and becomes definitely more complicated when number of sets increases).
    venn
  • independent family method. We construct an independent family of sets, i.e. such family of sets that each intersection of sets or their complements is non-empty. For three sets it is sufficient to take the set \{0,1,2,3,4,5,6,7\} and set A=\{1,4,5,7\}, B=\{2,4,6,7\}, C=\{3,5,6,7\}. Then it is sufficient to check the equality on this family of sets — and we know it will work for any family. In our case we calculate left-hand side: A\cup B=\{1,2,3,4,5,6\}, (A\cup B)\setminus C=\{1,2,5\} and right-hand side: A\setminus C=\{1,2\}, B\setminus C=\{2,5\}, (A\setminus C)\cup(B\setminus C)=\{1,2,5\}, and we are done.
  • the third method starts with an observation that X=Y if and only if X\subseteq Y and Y\subseteq X. We can therefore split our proof into two parts: proving the first inclusion and proving the second one.

But how to prove that X\subseteq Y? We start our prove by taking x form X, so let x\in X. Next by a sequence of implications we prove that also x\in Y, which proves the inclusion.

Sometimes proving that X=Y, the proofs of X\subseteq Y and of Y\subseteq X can be easily done simultaneously. We simply pay attention whether the implications in the proof of that if x\in X, then x\in Y, work also in the other direction. Whether the implications are actually equivalences.

When we prove that a given statement if false, it is sufficient to show a counterexample, i.e. an example of such sets that the statement is false for them.

In our case:
We prove that: (A\cup B)\setminus C\subseteq(A\setminus C)\cup (B\setminus C). Let x\in (A\cup B)\setminus C, then x\in A\cup B oraz x\notin C, so x\in A lub x\in B, but x\notin C, so (x\in A \land x\notin C)\lor (x\in B\land x\notin C), so x\in A\setminus C or x\in B\setminus C, therefore x\in (A\setminus C)\cup (B\setminus C).
Now we prove that: (A\setminus C)\cup (B\setminus C)\subseteq (A\cup B)\setminus C: Let x\in (A\setminus C)\cup (B\setminus C), so x\in A\setminus C or x\in B\setminus C, therefore x\in A lub x\in B, but in both cases if x\notin C. Therefore x\in A\cup B, but x\notin C, so x\in (A\cup B)\setminus C.

When we prove that one statement holds if and only if some other statement holds, then usually we split the proof into two proofs of left side and right side implications.

Sometimes proving that an implication holds we use a proof by contradiction. We assume the assumption and a negation of the hypothesis, and next we try to get a contradiction.