Set Theory

On September 18, 2010, in Analysis, by ufukkaya

The concept of the “set” is one of the basic concepts of mathematics. However, in spite of this fact, there is no definition agreed on by the authority. Some mathematicians define sets as “the class of objects that have certain properties”. Although this definition is widespread, there are deficiencies.

Objects that form the set are called “elements”. The sets are represented with capital letters such as $A$ , $B$ , $C$ , $X$ , $Y$ , and the elements of sets are represented with lower-case letter such as $a$ , $b$ , $c$ , $x$ , $y$ . If $a$ is an element of $A$ , this case is denoted by $a\in A$ , if $a$ is not an element of $A$ , this case is denoted by $a\notin A$ . There are three types of representations to display the sets:

1. List method: In this representation, the elements of set are written into the curly braces, by putting the commas between the elements. In a set, an element cannot be written twice. As an example, $A=\{a,b,c,d,e\}$ can be given.

2. Venn diagram: In this representation, the elements of set are written inside a circle or rectangle. Let’s show the above example, $A=\{a,b,c,d,e\}$ , by using Venn diagram:

Although the two representations above seem useful, their uses are limited because these representations can only and only be used for finite sets. Because it is generally studied on the infinite sets in mathematics, the following third representation is used in common. However, there are cases that the two representations above are also useful. For example, the first representation is useful to show the finite sets and, the second representation is useful to show relations and functions between two finite sets.

3. Common properties method: In this representation, the elements providing a specific proposition or propositions are collected in a set, is denoted by $\{x\:|\: x, \text{provides that the proposition} \: p\}$ . (Sometimes the form $\{x\:{:}\: x, \text{provides that the proposition} \: p\}$ is also used) Let $X$ be a set. The elements which belong to $X$ and provide the proposition $p$ is denoted by $\{x\in{X}\:|\: x, \text{provides that the proposition} \: p\}$ . Of course other letters can be used instead of $x$ . For example, the set of odd integers that is greater than 100 is denoted by $\{ n \in \mathbb{Z}\:|\: n \: \text{is odd and} n>{100} \}$ . This set can also be denoted by $\{ n \in \mathbb{Z} : n>{100} \land \exists k \in \mathbb{Z} : n=2k+1 \}$ .

DEFINITION1: The set that has no element is called the emptyset. The emptyset is denoted by $\varnothing$ or $\{\}$ .

DEFINITION2: Let $A$ and $B$ be two sets. If each element of $A$ is also an element of $B$ , namely; $\forall x \in{A}, x \in{B}$ , then $A$ is called a subset of $B$ . This case is denoted by $A\subset{B}$ (or $A\subseteq{B}$ ). The emptyset is subset of any set. ( $\varnothing \subset{A}$ ) Furthermore, any set is subset of itself. ( $A\subset{A}$ ) If $A$ is a subset of $B$ and $B$ has the elements that they are not in $A$ , then $A$ is called a proper (or strict) subset of $B$ . If $A$ is a proper subset of $B$ , this case is denoted by $A \varsubsetneqq{B}$ .

DEFINITION3: Let $A$ and $B$ be two sets. If $A\subset{B}$ and $B\subset{A}$ , $A$ and $B$ are called equal sets. This case is denoted by $A=B$ .

DEFINITION4: Let $A$ and $B$ be two sets. Now, let’s form new sets by using $A$ and $B$ .

The set defined as

$A \cup{B}=\{ x\:|\: x \in{A}\lor x \in{B} \}$

is called the union of $A$ and $B$ .

The set defined as

$A \cap{B}=\{ x\:|\: x \in{A}\land x \in{B} \}$

is called the intersection of $A$ and $B$ .

The set defined as

$A \setminus{B}=\{ x\:|\: x \in{A}\land x \notin{B} \}$

is called the difference of $A$ and $B$ .

The set defined as

$A \bigtriangleup{B}=(A \setminus{B}) \cup{(B \setminus{A})}$

is called the symmetric difference of $A$ and $B$ .

If $A \cap{B}=\varnothing$ , then $A$ and $B$ are called disjoint sets.

Now, let’s mention a few elementary features of these operations:

1) In the union, intersection and symmetric difference operations, $A$ and $B$ can be replaced by each other ( $A\cup{B}=B\cup{A}$ , $A\cap{B}=B\cap{A}$ , $A\bigtriangleup{B}=B\bigtriangleup{A}$ ). But, in the difference operation, $A$ and $B$ may not be replaced by each other. As it is clear from the definition of difference operation, $A \setminus{B}$ set contains the elements that are in $A$ and not in $B$ . Now, let’s give an example that shows the case in which $A$ and $B$ may not be replaced by each other: We take $A=\{a,b,c\}$ and $B=\{b,c,d\}$ . Because $A\setminus{B}=\{a\}$ and $B\setminus{A}=\{d\}$ , we obtain $A\setminus{B} \ne B\setminus{A}$ .

2) The union, intersection and symmetric difference operations are associative:

$(A\cup{B})\cup{C}=A\cup{(B\cup{C})}$ ,

$(A\cap{B})\cap{C}=A\cap{(B\cap{C})}$ ,

$(A\bigtriangleup{B})\bigtriangleup{C}=A\bigtriangleup{(B\bigtriangleup{C})}$ .

So, in the union, intersection and symmetric difference of three or more sets, the order of sets and which two sets enter the operation are not important.

3) If $A$ is a set, then $A\cup{A}=A$ , $A\cap{A}=A$ , $A\setminus{A}=\varnothing$ and $A\bigtriangleup{A}=\varnothing$ .

4) If $A$ and $B$ are two sets, then $A\subset{A\cup{B}}$ , $B\subset{A\cup{B}}$ , $A\cap{B}\subset{A}$ and $A\cap{B}\subset{B}$ .

DEFINITION5 (FAMILY OF SETS): Let $I$ be an index set and $\forall i \in{I}$ , $A_i$ be sets. So $\mathcal{A}=\{A_i : i \in{A} \}$ is called a family of sets. Generally, a family of sets is denoted by a shorter form of $\mathcal{A}=\{A_i\}_{i\in{I}}$ . Actually, a family of sets is a set that its elements are sets, i.e. it is a set of sets. But, because using the statement of “set of sets” may cause confusion, the statement of “family of sets” is used in general. Let’s give an example: Let be $I=\{1,2,3,4\}$ . (Because this is an example, I have chosen the index set that has four elements. But the index set can be chosen as a set that has fewer elements, more elements, finite elements, infinite elements or can even be chosen the emptyset) Let be $A_1=\mathbb{N}$ , $A_2=\mathbb{Z}$ , $A_3=\mathbb{Q}$ and $A_4=\mathbb{R}$ . Then $\mathcal{A}=\{ \mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R} \}$ . There is a confusing problem: $\mathcal{A}$ is a family of sets and has four elements. (I.e. it is a finite set) $\mathbb{R} \in{\mathcal{A}}$ . The set of real number being infinite doesn’t make $\mathcal{A}$ infinite. We should consider that the set of real numbers is an ordinary element of $\mathcal{A}$ . If the set of real numbers was a subset of $\mathcal{A}$ , we would say “ $\mathcal{A}$ is infinite”. But, because this is not true, $\mathcal{A}$ is a finite set.

DEFINITION6 (THE UNION AND INTERSECTION OF FAMILY OF SETS): Let $\{A_i\}_{i\in{I}}$ be a family of sets.

The set defined as

$\displaystyle{\bigcup_{i\in{I}}A_{i}=\{x\:|\: \exists{i}\in{I}:\:x\in{A_{i}}\}}$

is called the union of $\{A_i\}_{i\in{I}}$ and the set of defined as

$\displaystyle{\bigcap_{i\in{I}}A_{i}=\{x\:|\: \forall{i}\in{I},\:x\in{A_{i}}\}}$

is called the intersection of $\{A_i\}_{i\in{I}}$ . One can easily see this result from the definitions: The elements that are included in at least one of the sets of ${A_{i}}_{i\in{I}}$ form the set of union, and the elements that are included in all the sets of $\{A_i\}_{i\in{I}}$ form the set of intersection. In the event of $I=\mathbb{N}$ , the set of union of $\{A_i\}_{i\in{I}}$ is denoted by

$\displaystyle{\bigcup_{i=1}^{\infty}A_{i}}$

and the set of intersection of $\{A_i\}_{i\in{I}}$ is denoted by

$\displaystyle{\bigcap_{i=1}^{\infty}A_{i}}$ .

Let’s give a generalization of property 4^th for union and intersection operations: Let be $\{A_i\}_{i\in{I}}$ a family of sets. Then,

$\displaystyle{A_{k}\subset\bigcup_{i=1}^{\infty}A_{i}}$

and

$\displaystyle{\bigcap_{i=1}^{\infty}A_{i}\subset{A_{k}}}$

for any $k\in{I}$ .

DEFINITION7: Let $\{A_i\}_{i\in{I}}$ be a family of sets. If $A_i \cap{A_j}=\varnothing$ for any $i\ne{j}$ , then, $\{A_i\}_{i\in{I}}$ is called pairwise disjoint or mutually disjoint. For example, if $X\ne{\varnothing}$ is a set, the family of $\{\{x\}\:|\:x\in{X}\}$ is pairwise disjoint. A more concrete example: The family of $\{ [n,n+1) \}_{n=1}^{\infty}$ is pairwise disjoint because $[n,n+1) \cap{[m,m+1)}=\varnothing$ for any $m\ne{n}$ in $\mathbb{R}$ .

DEFINITION8: Let $X$ be a set. The set $\mathbf{P}(X)=\{A\:|\:A\subset{X}\}$ is called the power set of $X$ . I.e. the power set of a set is the family of sets formed all the subsets of this set. The power set of any set is always non-empty. Because the emptyset is a subset of any set ( $\varnothing\subset{X}$ ), the emptyset is an element of $\mathbf{P}(X)$ for any set $X$ . For example, if $X=\varnothing$ then $\mathbf{P}(X)=\{\varnothing\}$ , if $X=\{1\}$ then $\mathbf{P}(X)=\{\varnothing,\{1\}\}$ , if $X=\{1,2\}$ then $\mathbf{P}(X)=\{\varnothing,\{1\},\{2\},\{1,2\}\}$ and, if $X=\{1,2,3\}$ then $\mathbf{P}(X)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$ .

DEFINITION9: Let $A$ be a set and $\{A_i\}_{i \in{I}}\subset{\mathbf{P}}(A)$ be a family of the subsets of $A$ . If the following two conditions are provided, the family $\{A_i\}_{i \in{I}}$ is called a partition of $A$ :

i) $\displaystyle{\bigcup_{i\in{I}}A_{i}=A}$

ii) The family $\{A_i\}_{i \in{I}}$ is pairwise disjoint.

There exists at least one partition of any set, because the family $\{\{x\}\:|\:x\in{A}\}$ is a family providing the conditions (i) and (ii) for any set $A$ . This is a trivial example. Let’s give two concrete examples:

EXAMPLE1: If $A=\mathbb{R}$ and $I=\mathbb{Z}$ , then, the family $A_n=[n,n+1)$ , $n\in{\mathbb{Z}}$ is a partition of $\mathbb{R}$ , because,

i) $\displaystyle{\bigcup_{n=-\infty}{\infty}[n,n+1)=\mathbb{R}}$ and,

ii) $[n,n+1)\cap{[m,m+1)}=\varnothing$ for any $n\ne{m}$ in $\mathbb{Z}$ .

EXAMPLE2: Let $n\in{\mathbb{N}}$ be an arbitrary constant. Let $r(m)$ denote the remainder when dividing $m$ by $n$ . We consider $A_k= n\mathbb{Z}+k=\{m\in{\mathbb{Z}} \:|\: r(m)=k\}$ for $0\le k \le n-1$ . Because,

i) $\displaystyle{\bigcup_{k=0}^{n-1}\left( n\mathbb{Z}+k \right)=\mathbb{Z}}$ and,

ii) $A_k \cap{A_l}=\varnothing$ for any $k \ne l$ in $\{0,1,\dots,n-1\}$ , the family $\{n\mathbb{Z}+k\:|\:k=\overline{0,n-1}\}$ is a partition of $\mathbb{Z}$ .

DEFINITION10 (UNIVERSAL SET): The set including all the sets is called universal set and denoted by $\mathbb{E}$ in general. Actually, Russell’s paradox proofs that there is not a set including all the sets. So, in spite of the collection denoted by the form of $\mathbb{E}$ is universal, we can consider that it is not a set. It’s true that $\mathbb{E}$ is not a set. However, $\mathbb{E}$ can be turned into a set by restricting the definition of the universal set. Let’s change the definition of the universal set for restricting: “The set including all the sets that we study on is called universal set”. What is the meaning of this? Let’s explain the definition by giving some examples: For example, we consider that you are studying on sequences in the set of the real numbers. Therefore, you aren’t going out of the set of the real numbers. I.e. the largest set that you are studying on is the set of the real numbers and any other set that you are studying on is a subset of the set of the real numbers. In that case, your universal set is the set of the real numbers. Let’s give another example: we consider that you are studying on the prime numbers. In that case, your universal set is the set of the integers. As is seen, actually, the universal set depends on the topics that you are studying on at that time, i.e, depends on your choosing. The choosing of the universal set is rather important for the concept of the “complement”. Now, let’s give the definition of the complement:

DEFINITION11: Let $A$ be a set. Then, the set $A^{C}=\mathbb{E}\setminus{A}$ is called the complement of $A$ . (Where $\mathbb{E}$ is the universal set.) I.e. $A^{C}$ is formed the $\mathbb{E}$ ’s elements that are not in $A$ . The complement of $A$ is denoted by $A'$ in some sources. Let’s explain the importance of the choosing of the universal set by the help of an example:

EXAMPLE3: Let $A=\{1,2\}$ . If $\mathbb{E}=\mathbb{N}$ , then, $A^C=\{2,3,\dots\}$ , and if $\mathbb{E}=\mathbb{R}$ , then, $A^C=(-\infty,0)\cup{(0,1)\cup{(1,+\infty)}}$ .

PROPOSITION1: Let $A\subset{\mathbb{E}}$ and $\{A_i\}_{i\in{I}}\subset{\mathbb{E}}$ . Then, the following five propositions are true:

i) $\varnothing^C=\mathbb{E}$ ,

ii) $\mathbb{E}^C=\varnothing$ ,

iii) $(A^C)^C=A$ ,

iv) $\displaystyle{\left( \bigcup_{i\in{I}}A_{i} \right)^{C}=\bigcap_{i\in{I}}(A_{i})^{C}}$ ,

v) $\displaystyle{\left( \bigcap_{i\in{I}}A_{i} \right)^{C}=\bigcup_{i\in{I}}(A_{i})^{C}}$ .

(iv) and (v) are called De Morgan’s laws. The law (iv) turn into $(A\cup{B})^C=A^C\cap{B^C}$ and the law (v) turn into $(A\cap{B})^C=A^C\cup{B^C}$ in the case $I=\{1,2\}$ .

PROOF:

DEFINITION12: Let $X,Y\ne\varnothing$ be two sets, $x\in{X}$ and $y\in{Y}$ . The set defined as $(x,y)=\{x,\{x,y\}\}$ is called an ordered pair. The following “equality of two ordered pairs” is true for $x_1,x_2\in{X}, y_1,y_2\in{Y}$ :

$(x_1,y_1)=(x_2,y_2)\Leftrightarrow x_1=x_2\land{y_1=y_2}$ .

This equality can be easily proved by using the equality of two sets.

The equality $(x,y)=(y,x)$ is not true in general. By using the equality of two ordered pairs, the proposition

$(x,y)=(y,x)\Leftrightarrow x=y$

can be easily obtained.

DEFINITION13: Let $X,Y$ be two sets. The set defined by $X\times{Y}=\{(x,y) \:|\: x\in{X}, y\in{Y}\}$ is called the Cartesian product of $X$ and $Y$ . In general $X\times{Y}\ne Y\times{X}$ . More generally, the following proposition is provided: