8.19 Relation
1.Relation (A generalization of the concept of function)
Given a set \(X\), a relation \(R\) in \(X\) is a subset \(R\subset X\times X\), we write "a is related to b", \(aRb\) If \((a,b)\in R\subset X\times X\)
Example
-
\(X=N_0=\{0,1,2...\}\)
Define \(R\) as \(aRb\), if \(b-a=3\)
\((1,4)\in R\), since \(4-1=3\), \(1R4\)
Now, if \((x,y)\in R\Rightarrow y=x+3\)
-
\(X=N_0\), \(xRy\)\(\Leftrightarrow x+y\leq 5\)
such as \(0R0,0R1...0R5\\\ ~~~~~~~~~~~1R0,1R1...1R4\\\ ~~~~~~~~~~~................................\)
Example
\(X=\mathbb{Z},~xRy\Leftrightarrow3\mid y-x\Leftrightarrow y-x=3k,~k\in\mathbb{Z}\)
In words, 3 is divisor of \(y-x\)
\(1R4\) since 3 is a divisor of \(4-1=3\)
\(7R28\) since \(3\mid28-7\)
\(1\cancel{R}~5\) since \(3\nmid5-1\)
2.Properties of equivalence relations in \(X\):\(R\subset X_{\times}X\)
-
\(\forall x\in X,xRx\) (Reflexivity)
-
\(\forall x,y\in X,~xRy\Leftrightarrow yRx\) (Symmetry)
-
\(\forall x,y,z\in X, xRy\wedge yRz\Rightarrow xRz\)(Transitivity)
Note
-
\(\forall x,~\ xRx\) : \(3\mid x-x\)
-
\(xRy\Leftrightarrow~yRx: 3\mid y-x\Rightarrow y-x=3k~with~k\in \Z\Rightarrow x-y=3(-k)\)
-
\(x,y\in\Z~~\text{Suppose}~xRy,~yRz\)
\(y-x=3k\) and \(z-y=3k\)
\(y-3k=x\)
Then \(z-x=z-y+3k=3q+3k=3(q+k)\Rightarrow~zRx\)
3.Equivalence class
Every equivalence relation induces a partition in \(X\)
\(X\)=union of equivalence class
For \(x\in X\), we define the equivalence class of \(X\)
\([x]=\{y\in X,~xRy\}\)
e.g.: \(\equiv,=\)
Example
\([0]=\{y\in z:~0Ry\}=\{y\in z:3|y-0|\}=\{y\in z,y=3k,k\in z\}\)
\([0]=\{multiple~of~3\}=0,\pm3,\pm6\ldots\)
\([1]=\{y\in z:~1Ry\}=\{y\in z:3|y-1|\}=\{y\in z,y-1=3k,k\in \Z\}=\{y\in z:y=1+3k\}=\{1,4,7,-2,-5,-8\}\)
\([2]=[y\in z:y=2+3k]\)
\([3]=[0]=[3k]\)
\([4]=[1]=[1+3k]\)
\([5]=[2]=[2+3k]\)
This relation is written as: \(xRy\Leftrightarrow\) They have the same reminder in the division by 3
We write \(xRy:x\equiv y\) (\(\equiv\) is congruent) (Besides 3, 4 or5........different numbers are all ok)
4.Order relation
eg: \(\subseteq,\leq,\geq\)
Properties
\(R\subset X\times X\), a relation such that \(x\mid x\)
-
\(\forall x\in X,~xRx\) (Reflexivity)
for every \(x\in \Z^{+}\), we have that \(x\mid x\) and thus \(xRx\)
-
\(\forall x,y\in X, (~xRy\wedge~yRx)\Rightarrow x=y\) (Antisymmetry)
If =\(xRy~and~yRx\), then \(x\mid y\) and \(y\mid x\), that is, \(y=kx\) and \(x=ly\) for some \(k,l\in \Z^{+}\).
Therefore \(x=ly=lkx\) with \(l=k=1\) since \(x,y\in \Z^{+}\) and thus \(x=y\)
-
\(\forall x,y,z\in X,~xRy\wedge yRz\Rightarrow xRz\)(Transitivity)
if \(xRy~and~yRz\) then \(x\mid y\) and \(y\mid z\) , that is \(y=kx\) and \(z=ly\) for some \(k,l\in \Z^{+}\).
Hence \(z=ly=l(kx)=(lk)x\) with \(lk\in \Z^{+}\), that is \(x\mid z\) and therefore \(_{x}R_{z}\)
Note
-
\(X=\N\), \(xRy\Leftrightarrow x\leq y\)
- \(x\leq x, \forall x\in \N\)
- \(x\leq y\wedge y\leq x\Rightarrow x=y\)
- \(x\leq y \wedge y\leq z\Rightarrow x\leq z\)
5.Partial order and total order
A partial order in \(X\) is called a TOTAL order if \(\forall x,y\in X\) we have either \(x\lesssim y\) or \(y\lesssim x\)
- \((N, \leq)\) total order
- \(X=\{\emptyset,\{a\},\{a,b\},\{a,b,c\}\}\). \((X,\subseteq)\) total order
Checking order properties
\(X\) a set, consider \(Y=\wp(X)\) power set
Define \(R\) in \(Y\times Y\) as follows
\(A,B\in \wp(X)\) \(ARB\Leftrightarrow A\subseteq B\) (definition of \(R\))
- \(ARA, \forall A\in \wp(X):A\subseteq A\) ok
- Take \(A,B\in \wp(X):~ARB\wedge~BRA\)
\(A\subseteq B\cap B\subseteq A\Rightarrow A=B\) * \(A,B,C\in \wp(X)\)
If \(A\subseteq B\), \(B\subseteq C\Rightarrow A\subseteq C\)
Remark
We denote \((X,\)\(\lesssim)\) when we have an order relation
Example
\(X=\{\{1,2,3\},\{1,2\},\{2,3\},\{1,3\},\{1\},\{2\},\{3\},\emptyset\}\)
\(X=\wp(\{1,2,3\})\)
Let \((X,\lesssim)\) be a partially ordered set(it is not certainly can be compared)
\(\lesssim\) refers to the relation: "divides, subset, <,>....."
- \(A=\{1,2\},B=\{1,3\}\Rightarrow A\nsubseteq B,B\nsubseteq A\)
- \((\wp(X)),\subseteq)\) partial order
6.Natural Numbers
\(N=\{1,2,3...\}\), \((N,\leq)\) is total ordered set
\(N_0=\{0,1,2,3...\}\)
7.Upper and lower bounds
Lower bounds
Given: \(A\subset \N\) we say that \(l\in \N\) is an upper bound for \(\R\), if \(a\in A\Rightarrow a\leq l\)
We say that (\(l\in \N\) is a upper bound for \(A\)) or (\(A\) is bounded above) if
Upper bounds
Given :\(A\subset \N\) we say that \(l\in \N\) is an lower bound for \(\R\), if \(a\in A\Rightarrow a\geq l\)
We say that (\(l\in \N\) is a lower bound for \(A\)) or (\(A\) is bounded below) if
8.Well ordering axiom
If \(A\subset \N_0, A\neq \emptyset\), then there is \(a\in A|a\leq x,\forall x\in A\) (a is the first element of A)
Exercise
Prove that every subset of \(\Z\) which is bounded above has a last element.
Analysis
We should denote subset of \(\Z\) as \(S\). And \(y\) is an upper bound
We know that we should try to use WOA. But we want to prove the last element.
So the last element should be denoted and on the negative of expression, then we use WOA we can get it.
We also must ensure the expression is a subset of \(\N\)
So, \(y-s+1\) is a good choice
then \(x\) is the first element and \(x=y-s_0+1\)
We should prove \(s_0\) is the last element, this is equivalent to prove \(s_0\geq s\)
strategy: \(WOP\)
Proof
Let S a subset of \(\Z\) bounded above and let \(y\) be one such upper bound.
Define \(S^{\prime}=\{y+1-s:s\in S\}\) (construct because we need to apply WOA and ensure set in N )
since \(y\geq s\) for all \(s\in S\) then \(y-s\geq 0\) for all \(s\in S\) and so \(y+1-s\geq 1\) for all \(s\in S\)
Therefore \(S^{\prime}\subseteq\mathbb{N}\) and by well ordering axiom the set \(S^{\prime}\) has a first element \(x\).
Now, if we take \(s_0=y+1-x\) then we need to prove \(s_0\geq s\) for all \(s\in S\)
Since \(x\leq s^{\prime}\) for all \(s^{\prime}\in S^{\prime}\Rightarrow x\leq y+1-s~for~all~s\in S\Rightarrow s\leq y+1-x~for~all~s\in S\)
That is, \(s_0\) is an upper bound of S with \(s_0\in S\) and thus \(s_0\) is the last element for \(S\)
Example
\(A=\{13,5,7,132\}\) first element of A is 5 and A is bounded below by 5. 12,11,10,9...are also lower bound for \(X\)
\(5=min(A)\) last element of A is 132 and A is bounded below by 132
\(B=\{z\in N:z=x^{2}-8x+15\mathrm{~with~}x\in N\}\) it has a first element in \(\N\).
Where? It is not important. Because \(x=10\), it is not empty. So it must have a first element.
Proposition
Let \(A\subset \N\), \(A\neq\emptyset\) bounded from above (This means that \(\exists b\in \N|a\in A\Rightarrow a\leq b\)), prove that A has a last element.
Proof: Let \(S=\{b\in \N|b\text{ is an upper bound of A}\}\)
\(S\subset N,~S\neq\emptyset\). Then by W.O.P.(well ordered principle)
There is \(u\in S\text{ such that }u\text{ is the first element in S, }u\in N\)
If \(u=1\Rightarrow A=\{1\}\Rightarrow 1\), \(1\) is the last element in \(A\)
If not, \(u>1\Rightarrow u-1\in \N\). Also \(u-1\notin S\) (\(u\) is max of\(A\), min of \(S\))
This means that \(u-1\) is not an upper bound for \(A\Rightarrow \exists a\in A\text{ such that }u-1<a\leq u\Rightarrow a=u\)
Then \(\begin{cases}a\in A\\a=u\\u\in S\end{cases}\)\(\Rightarrow a\in A\wedge a\geq b,~\forall b\in A\)
\(u\) is the last element in A, \(u=max(A)\)
9.Cardinality (counting elements in sets)
Let \(X,Y\) be sets, we say that they are equivalent or equipotent if there exists a bijection \(f:X\rightarrow Y\)
In that cases, we write \(|X|=|Y|\) and also X~Y
Example
\(X=\{a,b,c\}~~~Y=\{3,\pi,137\}\)
\(f:X\rightarrow Y\) \(f(x)=\begin{cases}3&\mathrm{if~x=a}\\\pi&\mathrm{if~x=b}\\137&\mathrm{if~x=c}\end{cases}\)
Notation
for \(m\in\N\), we define \(N_{m}=\{1,2,3,...,m\}\)
Definition of finite
We say that \(X\) is finite if there exists a function \(f:X\rightarrow N_m\) injective for some \(m\in N\)
If \(X\) is not finite, we say that \(X\) is infinite. \(N_m\)= "initial segment"
Examples with infinite sets
-
\(N=\{1,2,3,4...\}\)
\(2\times N=\{2,4,6,8...\}\) even natural number
Claim:\(|N|=|2N|\)
\(f:N\rightarrow 2N\)
\(f(m)=2m\), \(f\) is bijective
-
\(X=[0,1],Y=[0,2]\)
Prove that \(|[0,1]|=|[0,2]|\)
\(f:[0,1]\rightarrow[0,2]\)
\(f(x)=2x\), bijection
Proposition (related to Theorem (The pigeonhole principle))
If \(X\) is a set such that \(\exists f:X\rightarrow N_n\) injective, then \(\exists m\leq n|~|X|=|N_m|\)
Analysis:
We write: \(|X|=m\) (\(X\) finite \(\Rightarrow X~has~m~elements\) ) 缩小
We should consider the tool: WOP, hence we should put the function in a set
Strategy: WOP+Contradiction
Trick: swap the positions of elements
Proof: Consider the set \(A=\{k\in N|\exists f:X\rightarrow N_{k},injective\}\)
Note that \(A\neq\emptyset\), Since \(f:X\rightarrow N_n\) injective, hence \(n\in A\)
By the W.O.P., we know that A has a first element
Let's call it \(m\in A\)
Then we have \(f:X\rightarrow N_m\) injective, we will prove \(f\) is surjective(then bijective)
Suppose \(f\) is not surjective : \(\exists k\in N_m\) such that \(f(x)\neq k,~\forall x\in X\)
If \(k=m\), then \(f(x)\neq m\), \(\forall x\in X\)
Then: \(f:X\rightarrow N_{m-1}\) is still an injective function \(X\rightarrow \{1,2,3,...,m-1,\cancel{m}\}\)
Then \(m-1\in A\) (which is a contradiction to m is the first element)
\(k\) is not in the image also is not in the set
If \(k\neq m,\) now suppose that \(k\in \{1,2,3,...,m-1,m\}\)
Consider \(g:N_m\rightarrow N_m\) defined as
\(g(i)=\begin{cases}i,~if~i\neq k,~~i\neq m\\m,~if~i=k\\k,~if~i=m\end{cases}\)
Then \(g\) is injective. Consider \(h=g\circ f:X\rightarrow N_m\)
Now, \(h\) is injective \(h(x)=g(f(x))\neq m\), since \(f(x)\neq k\Rightarrow g(f(x))\neq g(k)=m\)
\(h\) is an injection from \(X\) to \(N_m\)|\(h(x)\neq m\)(back to previous case)
Conclusion: \(f\) is bijection, therefore \(|X|=m\)
Properties
-
X is a finite set,\(|X|=m,~y\notin X\)
Then\(|X\cup\{y\}|=m+1\)
We know that there is \(f:X\rightarrow N_m\) bijection
We need to define \(g:X\cup\{y\}\rightarrow N_{m+1}\)
\(g(z)=\begin{cases}f(x)&if~z=x\in X\\m+1&if~z=y\end{cases}\)
-
X,Y disjoint and \(|X|=m,~|Y|=m\), then \(|X\cup Y|=m+m\)
We have \(f:X\rightarrow N_m\), \(g:Y\rightarrow N_m\) bijection
Define: \(h:X\cup Y\rightarrow N_{m+m}\)
\(h(z)=\begin{cases}f(x)\text{ ~if}:z=x\in X\\g(Y)+m\text{ ~if}:z=y\in Y\end{cases}\)
-
Suppose X finite, \(A\subset X\). Then
- \(|A|\leq|X|\)
Consider \(f:X\rightarrow N_n\) bijection
Then \(f|_{A}:A\rightarrow N_{n}\) injection \(\Rightarrow A\) is finite
(By the propostion) \(\exists m\leq n||A|=m\leq n=|X|\) * \(|A|=|X|\Rightarrow A=X\)
\(X=A\cup(X\setminus A)\) (disjoint union)
\(|X|=|A|+|X\setminus A|\Rightarrow|X\setminus A|=0\Leftrightarrow X\setminus A=\emptyset\Leftrightarrow A=X\)
Conclusion
\(X\) finite \(\Rightarrow X\) cannot be equivalent to any proper subset \(A\subsetneq X\)
\(X\) finite \(\wedge A\subsetneq X\Rightarrow |A|<|X|\)
\(\neg q\Rightarrow \neg p\). If \(X\) is a set such that \(|X|=|A|\) with \(A\subsetneq X\Rightarrow X\) is infinite
Example
\([0,2]\) infinite
\(\N\) is infinite \(|N|=|2N|\)
The definition of finite and infinite
Finite
\(X\) is finite if there exists a function \(f:X\rightarrow N_m\) injective for some \(m\in N\)
Infinite
\(X\) is infinite if \(X\) is a set such that \(|X|=|A|\) with \(A\subsetneq X\)