8.14 Sets
1.Sets
A set is a well defined collection of elements
2.Empty set
\(\emptyset\) defined by proposition \(x\in\emptyset\) is false
Remark
\(\emptyset\subseteq A\) for ant set A
We need to prove that \(x\in\emptyset\Rightarrow x\in A\) is true
Suppose that \(\emptyset\nsubseteq A\), that means \(\exists x\in\emptyset:x\notin A\)
Contradiction!!!
3.Belonging
We say that the element \(x\) belongs that set A and write \(x \in A\)
4.Subset
Given that sets A and B, we say that A is a subset of B and write \(A\subseteq B\), if the proposition \((x \in A)\Rightarrow(x \in B)\) is true
Notation:
\(A\subseteq B\) : A is included in B or equal to B
\(A\subsetneq B:\forall x(x\in A\Rightarrow x\in B),\mathrm{but~}\exists y\in B:y\notin A\) (strict inclusion). A is strictly included in B
\(A \nsubseteq B\): A is not included in B. \(\exists a\in A:a\notin B\)
5.Universal Set
In general, we will consider that all sets are in same universal set \(x\), we will write definitions of the form
Example
\(A=\{m\in \mathbb{N}:\sqrt{m}\in \mathbb{N}\}=\{1,4,9\ldots\}=\{k^{2}:k\in \mathbb{N}\}\)
6.Sets operations
A,B sets
Union
\({A\cup B}\) is a set defined by the condition:
Intersection
Disjoint sets
We say that A and B are disjoint if \(A\cap B=\emptyset\)
Relative complement
The difference \(A\setminus B=\{x\mid x\in A\mathrm:x\notin B\}\) (different sets)
Also denoted by \(A-B\)
Complement
In the cases of having some universal set \(x\), we define for any \(A\subseteq X\)
The complement \(A^{C}=\{x\in X:x\notin A\}\)
Remark
To prove (in general) that \(A = B\) for the given sets, we prove two things \(A\subseteq B\cap B\subseteq A\)
Exercise
Prove \((A^{C})^{C}=A\)
-
\((A^{C})^{C}\subseteq A\)
Pick \(x\in(A^{C})^{C}\Leftrightarrow x\notin A^{C}\Leftrightarrow x\in A\)
-
\((A^{C})^{C} \supseteq A\)
Pick \(x\in A\Leftrightarrow x\notin A^C\Leftrightarrow x\in(A^{C})^{C}\)
7.De Morgan's Laws
A,B sets we have
\(\subseteq)~x\in (A\cup B)^{C}\Leftrightarrow x\notin(A\cup B)\Leftrightarrow x\notin A\cap x\notin B \Leftrightarrow x\in A^{C}\cap x\in B^{C} \Leftrightarrow x\in A^{C}\cap B^{C}\)
\(\supseteq)~x\in A^{C}\cap B^{C}\Leftrightarrow x\in A^{C}\cap x\in B^{C} \Leftrightarrow x\notin A~\cap~x\notin B\Leftrightarrow x\in(A\cup B)^{C}\)
8.Power set
Given a set A, we define the power set as
(or the set of "parts of b)
\(\wp(A)=\{B \subseteq X:B \subseteq A\}=\{all~subsets~of~A\}\)
Example
\(A=\{a,b,c\}\). Then \(\wp(x)=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}\)
Claim
If A is a set of m elements \(m \in\mathbb {N}\), the power set \(\wp(A)\) has \(2^m\) elements.
9.Cartesian product
A, B sets, we define
(a,b) is ordered pair
Note that \(A\times B~and~B\times A\) may be different!!
Example
\(A=\{1,2\}B=\{3,4,5\}\\A\times B=\{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)\}\\B\times A=\{(3,1),(3,2),(4,1),(4,2),(5,1),(5,2)\}\)
10.Functions
Consider the sets \(A\) and \(B\)
V1: A function \(f:A\rightarrow B\) is a rule to assign, to every element from A, one element (only one) from B
V2: Let A, B be sets. A function \(f:A\rightarrow B\) can be identified with a set \(R\subset A\times B\) such that \(\forall a\in A, \exist~!~b\in B/(a,b)\in R\)
\(\exist~!\) :there exists a unique one
We write \(f(a_{1})=b_{4},~f(a_{2})=b_{1},~f(a_{4})=b_{1},~f(a_{3})=b_{5}\)
Conditions: for every \(a \in A\), there is only one \(b \in B\) such that \(f(a)=b\)
- We say that "\(f\) maps \(a\) to \(b\)"
- We call \(A\) the domain of the function \(f\) and write \(dom(f)=A\)
- \(B\) is the codomain of \(f\), \(codom(f)=B\)
- If \(f(a)=b\), we say that \(b\) is the image of \(a\) when applying \(f\)
Remark
If \(f=A\rightarrow B\), the ordered pair \((a,f(a))\in A\times B,\forall a\in A\)
Example
\(A=\{1,2,3,4,5\}, B=\mathbb{N}\)
Consider \(f=A\rightarrow B\) given by the formula \(f(m)=m+1\), \(g(m)=(m-2)^{2}+1\)
| \(m\) | \(f(m)\) | \(g(m)\) |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 3 | 1 |
| 3 | 4 | 2 |
| 4 | 5 | 5 |
| 5 | 6 | 10 |
More definition
Let: \(f:A\rightarrow B\) a function
The Range of \(f\) is defined as \(Ran(f)=\{b\in B:\exists a\in A,f(a)=b\}\)
Note
we also call this set the IMAGE of \(f\)(all possible collection of values), \(\mathrm{Im}(f)=\{b\in B:\exists a\in A,f(a)=b\}\)
Example
\(f:\mathbb{R}\rightarrow\mathbb{R},~f(x)=x^{2}\), \(g:\mathbb{N}\to\mathbb{R},~g(m)=m^2\)
not same \(f\), but same formula.(domain and codomain should be same)
\(f(x)=\frac{1}{1-x}\), \(f(x)\)exists at any \(x \in \mathbb{R}\setminus \{1\}\)
Natural domain of this formula is \(\mathbb{R}\setminus\{1\}\) NATURAL DOMAIN是定义域能够取到的的最大范围