Beginning Rigorous Mathematics/Sets and Functions

We will now discuss some important set operations. Recall from the preliminaries that we only intuitively define a set to be a collection of distinct mathematical objects. There are much better and rigorous definitions of what sets are and form a subject for study all by itself, into which we will not delve.

Recall the meaning of the symbol "$\in$", which reads "is an element of" so that if A is a set and x an object, then $x\in A$ a is a statement (which is either true of false, depending on whether x is an element of A).

Sets and Set operations

In the following discussion, A and B denote any sets.

Definitions

The empty set: $\emptyset$

We will assume that the empty set exists, and is denoted by $\emptyset$. As the name suggests, the empty set contains no elements so that for any object x the statement $x\in \emptyset$ is false.

Set equality

Usually there is no ambiguity when we use the symbol "=" to refer to equality between sets. It is important that equality between sets is completely different to equality between numbers.

We define the logical statement "A = B" to be true by definition when the statement "$x\in A \Leftrightarrow x\in B$" (which reads "x is contained in A if and only if x is contained in B") is true, and false otherwise. Intuitively this means that sets are equal if and only if they contain exactly the same elements. For example, {1,2,3} = {1,2} is false since "$3\in \{1,2\}$" is false. It might be helpful to check the truth table to see that "$3\in \{1,2,3\} \Leftrightarrow 3\in \{1,2\}$" is a false statement. It should then be clear that "{5,6,7} = {5,6,7}" is true.

Subsets

If every element of the set A is an element of B, we then say that A is a subset of B.

Rigorously, we say that the statement "$A\subset B$" is true by definition when the statement "$x\in A \Rightarrow x\in B$" (which reads "If x is contained in A then x is contained in B") is true.

We have seen previously that the statement {1,2} = {1,2,3} is false, however the statement $\{1,2\}\subset \{1,2,3\}$ is true. It should be clear that $\{1,2,3,5\}\subset \{1,2,3,4\}$ is false, since the statement "$5\in \{1,2,3,5\} \Rightarrow 5 \in \{1,2,3,4\}$" is false.

Intersection

We define the intersection of sets by the symbol "$\cap$". Rigorously we write "$A\cap B := \{x|x\in A \land x\in B\}$" which reads "The intersection of the sets A and B is by definition equal to the set which contains exactly the elements which are contained in both A and B".

For example "$\{1,2,3,4\}\cap \{1,4,5\}:=\{1,4\}$".

We say that A and B are disjoint when $A\cap B = \emptyset$.

Union

We define the union of sets by the symbol "$\cup$". Rigorously we write "$A\cup B := \{x|x\in A \lor x\in B\}$" which reads "The union of the sets A and B is by definition equal to the set which contains exactly the elements which are contained in either one of A and B".

For example "$\{1,2,3,4\}\cup \{1,4,5\}:=\{1,2,3,4,5\}$".

Complement

To define the complement of the set A we assume that the set A is a subset of some universal set X. We say "A lives in X". Often the universal set is implicitly clear, for example when we are studying real analysis we often just assume $X=\mathbb{R}$ or when studying complex analysis we assume $X=\mathbb{C}$.

We define the complement of a set by the superscript "c". Rigorously "$A^c := \{x \in X | \lnot x\in A\}$" which reads "the complement of A in X is the set of all elements which are contained in X and not in A".

For example, if we assume X = {1,2,3,4,5} then {1,5}^c: = {2,3,4}.

Relative complement

We define the relative complement of sets by the symbol "$\backslash$". Rigorously, "$A\backslash B := \{x\in A | \lnot x\in B\}$" which reads "the relative complement of B in A is by definition equal to the set containing all the elements contained in A and is not contained in B".

For example "$\{1,2,3,4\}\backslash \{1,4,5\} := \{2,3\}$".

Some basic results

Lemma 1

$(A = B) \Leftrightarrow (A\subset B) \land (B\subset A)$. Which reads "A equals B if and only if A is a subset of B AND B is a subset of A"

proof As explained in the previous chapter, $(A = B) \Leftrightarrow (A\subset B) \land (B\subset A)$ will be true by adjunction when both $(A = B) \Rightarrow (A\subset B) \land (B\subset A)$ and $(A\subset B) \land (B\subset A) \Rightarrow (A = B)$ are true.

We prove first $(A = B) \Rightarrow (A\subset B) \land (B\subset A)$.

Let A = B, then by definition we have $x\in A \Leftrightarrow x\in B$, which is logically equivalent to $(x\in A \Rightarrow x\in B)\land (x\in A \Rightarrow x\in B)$. By simplification we have that $x\in A \Rightarrow x\in B$ is true, and that $x\in A \Rightarrow x\in B$ is true. Therefore by definition $A \subset B$, and $B\subset A$ are both true. By adjunction $(A\subset B)\land(B\subset A)$ is true. Therefore $(A = B) \Rightarrow (A\subset B) \land (B\subset A)$ is true.

Conversely, we prove $(A\subset B) \land (B\subset A) \Rightarrow (A = B)$.

Let $(A\subset B) \land (B\subset A)$. Then, by simplification, both $A\subset B$ and $B\subset A$ are true. By definition both $x\in A \Rightarrow x\in B$ and $x\in B \Rightarrow x\in A$ are true. By adjunction, $(x\in A \Rightarrow x\in B) \land (x\in B \Rightarrow x\in A)$ is true, which is logically equivalent to $x\in A \Leftrightarrow x\in B$. Then by definition A = B is true. Therefore $(A\subset B) \land (B\subset A) \Rightarrow (A = B)$ is true. QED.

Lemma 2

$A\subset A\cup B$

Lemma 3

$A\cap B\subset A$ and $A\cap B\subset B$