Mathematical Proof/Introduction to Set Theory

Template:Nav Objects known as sets are often used in mathematics, and there exists Template:Colored em which studies them. Although set theory can be discussed formally , it is not necessary for us to have such a formal discussion in this book, and we may not be interested in and understand the formal discussion in this stage.

Even if we do not discuss set theory formally, it is important for us to understand some basic concepts about sets, which will be covered in this chapter.

What is a set?

A Template:Colored em may be viewed as a collection of well-defined, distinct objects (the objects can also be sets). Because of the vagueness of the term "well-defined", we do not regard this as the definition of set. Instead, we regard set as a primitive notion (i.e., concepts not defined in terms of previously-defined concepts). Other examples of primitive notions in mathematics include Template:Colored em and Template:Colored em.

We have mentioned that a set is a collection of well-defined, distinct objects. Objects in a set are called Template:Colored em of the set. We write $a\in A$ to mean that the element $a$ belongs to the set $A$. If $a$ does not belong to $A$, we write $a\notin A$. Template:Colored example

Ways of describing a set

There are multiple ways to describe a set precisely (in the sense that element(s) belonging to the set is (are) known precisely).

If a set consists of a small number of elements, then the Template:Colored em may be quite efficient. In the listing method, elements of a set are listed within a pair of braces ({}). In particular, just changing the listing Template:Colored em of elements does Template:Colored em change the set represented. For example, $\{1,2\}$ and $\{2,1\}$ are both representing the same set whose elements are 1 and 2. If the elements listed in the pair of braces are the same, the notations created by the listing method with different listing orders refer to the Template:Colored em set. Also, repeatedly listing a specific element in a set does Template:Colored em change the set represented. For example, $\{1,1,2,2,2\}$ and $\{1,2\}$ are both representing the same set whose elements are 1 and 2. In particular, if a set contains no elements, it can be denoted by $\{\}$ based on the listing method or $\varnothing$. This kind of set is called an empty set.

Another way to describe a set is using Template:Colored em. For example, consider the set $S$ of prime numbers less than 10. If we use the listing method instead, the set $S$ is represented by $\{2,3,5,7\}$.

The third way to describe a set is advantageous when a set contains many elements. This method is called Template:Colored em. There are Template:Colored em parts within a pair of braces in this notation. They are illustrated below with descriptions: $$\underset{\text{The set of}}{\underbrace{\{}}\underset{\text{all elements }x}{\underbrace{x}}\underset{\text{such that}}{\underbrace{:}}\underset{\text{the property }P(x)\text{ is satisfied}}{\underbrace{P(x)}}\}$$

As one may expect, two sets are Template:Colored em if and only if they contain the same elements. Equivalently, two sets $A$ and $B$ are equal if and only if each element of $A$ is also an element of $B$ and each element of $B$ is also an element of $A$. This can be regarded as an axiom or a definition. If two sets $A$ and $B$ are equal, we write $A=B$. If not, we write $A\ne B$.

In this book, when we are solving an equation, we are only considering its Template:Colored em solution(s) unless stated otherwise. Template:Colored example Template:Colored exercise

Set cardinality

If a set contains Template:Colored em number of elements, it is called a Template:Colored em set, and it is called an Template:Colored em set otherwise. If a set is finite, then its cardinality is its number of elements. For infinite sets, it is harder and more complicated to define their cardinalities, and so we will do this in the later chapter about set cardinalities. For each set $S$, its cardinality is denoted by $|S|$. Template:Colored example There are some special infinite sets for which notations are given, as follows:

• $\mathbb{N}$ is the set of all natural numbers (0 is Template:Colored em regarded as a natural number in this book).
• $\mathbb{Z}$ is the set of all integers.
• $\mathbb{Q}$ is the set of all rational numbers.
• (nonstandard notation) $𝕀$ is the set of all irrational numbers.
• $ℝ$ is the set of all real numbers.
• $ℂ$ is the set of all complex numbers.

In particular, we can use set-builder notation to express $\mathbb{Q}$, as follows: $\mathbb{Q}=\{p/q:p,q\in \mathbb{Z}\text{ and }q\ne 0\}$. Template:Colored example Template:Colored exercise

Subsets

Template:Colored definition Template:Colored remark Template:Colored example Template:Colored definition Template:Colored remark Template:Colored example Template:Colored exercise We call some commonly encountered subsets of $ℝ$ Template:Colored em. For each real number $a,b$ such that $a<b$,

• $(a,b)\stackrel{\text{ def }}{=}\{x\in ℝ:a<x<b\}$ (open intervals)
• $(a,b]\stackrel{\text{ def }}{=}\{x\in ℝ:a<x\le b\}$ (half-open (or half-closed) intervals)
• $[a,b)\stackrel{\text{ def }}{=}\{x\in ℝ:a\le x<b\}$ (half-open (or half-closed) intervals)
• $[a,b]\stackrel{\text{ def }}{=}\{x\in ℝ:a\le x\le b\}$ (closed intervals)

There are also some Template:Colored em intervals:

• $(-\mathrm{\infty },a)\stackrel{\text{ def }}{=}\{x\in ℝ:x<a\}$
• $(-\mathrm{\infty },a]\stackrel{\text{ def }}{=}\{x\in ℝ:x\le a\}$
• $(a,\mathrm{\infty })\stackrel{\text{ def }}{=}\{x\in ℝ:a<x\}$
• $[a,\mathrm{\infty })\stackrel{\text{ def }}{=}\{x\in ℝ:a\le x\}$
• $(-\mathrm{\infty },\mathrm{\infty })\stackrel{\text{ def }}{=}ℝ$

Note: $\{x\in S:P(x)\}$ is a shorthand of $\{x:x\in S\text{ and }P(x)\}$ ($S$ is a set). Template:Colored example Template:Colored example Template:Colored exercise

Universal set and Venn diagram

Template:Colored definition Template:Colored example Template:Colored definition Template:Colored example Template:Colored exercise A Template:Colored em is a diagram showing all possible logical relationships between a finite number of sets. The universal set is usually represented by a region enclosed by a rectangle, while the sets are usually represents by regions enclosed by circles. The following is a Venn diagram.

In this diagram, if the white region represents set $A$ and the region enclosed by the rectangle represents the universal set, then the red region is the set $A^c$.

However, the following is Template:Colored em a Venn diagram.

This is because there are not regions in which only the yellow and blue region intersect, and only the red and green region intersect, respectively. So, not Template:Colored em logical relationships between the sets are shown.

To show all logical relationships between four sets, the following Venn diagram can be used.

Set operations

Similar to the arithmetic operations for real numbers which combine two numbers into one, the set operations combine two sets into one.

Union of sets

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

$◻$

Intersection of sets

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

$◻$

Relative complement

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

$◻$

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

$◻$

Power set

Proof. Assume $A$ is a finite set with cardinality $n$. Since each element of the power set $𝒫(A)$ is a subset of $A$, it suffices to prove that there are $2^n$ subsets of $A$. In the following, we consider subsets of $A$ with different number of elements separately, and count the number of subsets of each of the different types using combinatorics.

• For the subset with zero element, it is the empty set, and thus there is only one such subset.
• For the subsets with one element, there are $C_1^n$ subsets.
• For the subsets with two elements, there are $C_2^n$ subsets.
• ...
• For the subsets with $n-1$ elements, there are $C_{n-1}^n$ subsets.
• For the subset with $n$ elements, it is the set $A$, and thus there is only one such subset.

So, the total number of subsets of $A$ is $1+C_1^n+C_2^n+\cdots +C_{n-1}^n+1=(1+1{)}^n=2^n$ by Template:Colored em.

$◻$

Cartesian product

Template:Colored definition Template:Colored remark Template:Colored example Template:Colored remark Template:Colored exercise Similarly, we can define the Cartesian product of three or more sets. Template:Colored definition Template:Colored remark Template:Nav Template:BookCat