5 Partition

Homework 5 Basic Concepts in Mathematics - 104002 Guangdong Technion

Yue Shi 999027873

Exercise 1 (25 points) In each of the following cases, compute the remainder of the division of \(x\) by \(m\).

(a) \(x = 22 \cdot 11 \cdot 2024\), \(m = 3\)

Since \(22\equiv1(\mod3),11\equiv2(\mod3),2024\equiv2(\mod3)\), then by property of modular \(a\equiv m(\mod3),b\equiv n\left(\mod3\right)\Rightarrow ab\equiv mn\left(\mod3\right)\)

We get \(x=22\cdot11\cdot2024\equiv1\cdot2\cdot2=4\equiv1\left(\mod3\right)\)

Thus the remainder is \(1\)

(b) \(x = 9^{9 \cdot 23}\), \(m = 7\)

Since \(9\equiv 2(mod7)\) and \(2^3=8\equiv 1\) (mod 7)

We know \(x=9^{9\cdot23}\equiv2^{9\cdot23}=2^{204+3}\equiv2^3\equiv1\)

Thus the remainder is \(1\)

Exercise 2 (25 points)

(a) Describe all possible partitions of the set \(A = \{1, 2, 3, 4\}\).

\(P=\{\left\lbrace1\right\rbrace,\left\lbrace2\right\rbrace,\left\lbrace3\right\rbrace,\left\lbrace4\right\rbrace\}\)

\(P=\{\left\lbrace1,3\right\rbrace,\left\lbrace2\right\rbrace,\left\lbrace4\right\rbrace\}\)

\(P=\{\left\lbrace1\right\rbrace,\left\lbrace2\right\rbrace,\left\lbrace3\right\rbrace,\left\lbrace4\right\rbrace\}\)

\(P=\{\left\lbrace3,4\right\rbrace,\left\lbrace2\right\rbrace,\left\lbrace1\right\rbrace\}\)

\(P=\{\left\lbrace1,2\right\rbrace,\left\lbrace3,4\right\rbrace\}\)

\(P=\{\left\lbrace1,3\right\rbrace,\left\lbrace2,4\right\rbrace\}\)

\(P=\{\left\lbrace1,4\right\rbrace,\left\lbrace2,3\right\rbrace\}\)

\(P=\{\left\lbrace1,2,3\right\rbrace,\left\lbrace4\right\rbrace\}\)

\(P=\{\left\lbrace2,3,4\right\rbrace,\left\lbrace1\right\rbrace\}\)

\(P=\{\left\lbrace1,2,3,4\right\rbrace\}\) (b) How many different equivalence relations can be defined on \(A\)?

Since we have \(15\) partitions, then the number of equivalence relations is same with the number of partitions by the definition of partition

Then we have \(15\) equivalence relations

Exercise 3 (25 points) Define \(\leq\) on \(\mathbb{N}^2\) as follows: \((m,n) \leq (m', n') \iff m \mid m' \land n \mid n'\)

(a) Prove that \(\leq\) is a partial order.

Reflexivity: Since \(m\mid m\wedge n\mid n\), thus we have \((m,n)\leq(m,n)\) \(\checkmark\)

Anti-symmetry: If we have \((m,n)\leq(m^{\prime},n^{\prime})\) and \((m^{\prime},n^{\prime})\leq(m,n)\), then \(m\mid m^{\prime}\land n\mid n^{\prime}\) and \(m^{\prime}\mid m\land n^{\prime}\mid n\), then \(m=m',n=n'\)

Then we have \((m,n)\leq(m^{\prime},n^{\prime})\) \(\checkmark\)

Transitivity: If we have \((a,b)\leq(c,d)\) and \((c,d)\leq(e,f)\), then \(a\mid c\land b\mid d\) and \(c\mid e\land d\mid f\), then \(ak=c,bl=d\) and \(\operatorname{cm}=e,dn=f\)

Thus \(a(km)=e,b(ln)=f\Rightarrow a\mid e\wedge b\mid f\)

Then we have \((a,b)\leq(e,f)\) \(\checkmark\)

(b) Prove that a non-empty subset of \(\mathbb{N}^2\) has an upper bound if and only if it is a finite set (a set with a finite number of elements).

\(\Rightarrow\)) Let the upper bound be \((m,n).m,n\in\mathbb{N}\), then we know \(\forall a,b\in\mathbb{N},(a,b)\leq(m,n)\Rightarrow a\mid m\wedge b\mid n\)

Suppose it is a infinite set, then we can always find \((2m,2n)\) in the set.

Since \((m,n)\in\N^2\), then \((m,n)\leq (2m,2n)\)

Then \((2m,2n)\) is an upper bound, which is a contradiction to \((m,n)\) is an upper bound.

\(\Leftarrow\)) Assume we have a finite set \(\left\lbrace\left(a_1,b_1\right),\left(a_2,b_2\right),\ldots,\left(a_{n},b_{n}\right)\left\rbrace\right.\right.\)

Then consider \(m=a_1\cdot a_2\cdot ...\cdot a_n\) and \(n=b_1\cdot b_2\cdot...\cdot b_{n}\)

Since it is finite, then \(m,n\) exists. And it also satisfies \(\forall i\in[1,n],a_{i}\mid m\wedge b_{i}\mid n\)

Then we have \(\forall i\in[1,n],\left(a_{i},b_{i}\right)\leq\left(m,n\right)\) which means \((m,n)\) is an upper bound

Exercise 4 (25 points) Let \(\leq\) be the lexicographical order on \(\mathbb{N}^2\), that is,

\((m,n) \leq (m', n') \iff m < m' \text{ or } (m = m' \land n \leq n')\).

(a) Prove that \(\leq\) is a total order.

First, we need to prove it is a partial order

Reflexivity: Since \(m=m\wedge n\leq n\), thus we have \((m,n)\leq(m,n)\) \(\checkmark\)

Anti-symmetry: If we have \((m,n)\leq(m^{\prime},n^{\prime})\) and \((m^{\prime},n^{\prime})\leq(m,n)\), then \(m<m^{\prime}\text{ or }(m=m^{\prime}\land n\leq n^{\prime})\) and \(m<m^{\prime}\text{ or }(m=m^{\prime}\land n\leq n^{\prime})\), then \(m=m',n=n'\)

Then we have \((m,n)\leq(m^{\prime},n^{\prime})\) \(\checkmark\)

Transitivity: If we have \((a,b)\leq(c,d)\) and \((c,d)\leq(e,f)\), then \(a<c\text{ or }(a=c\land b\leq d)\) and \(c<e\text{ or }(c=e\land d\leq f)\), then \(a<e\) or \(a=e\wedge b\leq f\)

Then we have \((a,b)\leq(e,f)\) \(\checkmark\)

Thus it is a partial order

Then \((m,n) \leq (m', n') \iff m < m' \text{ or } (m = m' \land n \leq n')\).

Consider any \(n,n^{\prime}\in\mathbb{N}\) and \(m,m'\in\N\), we know there are two cases for \(m\) (\(m>m'\) is same with \(m<m'\) since we take any \(m,m'\)) (The same with \(n\))

\(m<m'\)

If this is true, then we Have \((m,n)\leq(m^{\prime},n^{\prime})\) by definition
\(m=m'\)

Then we also have two cases
1. \(n<n'\)
  
  If this is true, then we Have \((m,n)\leq(m^{\prime},n^{\prime})\) by definition 2. \(n=n'\)
  
  If this is true, then we Have \((m,n)\leq(m^{\prime},n^{\prime})\) by definition

Thus after considering all cases, we know \(\forall\left(m,n\right),\left(m^{\prime},n^{\prime}\right)\in R\), the relation always holds

Thus it is a total order

(b) Find an element different from \((1, 1)\) without an immediate predecessor.

\((2,1)\) (c) Prove that any non-empty subset of \(\mathbb{N}^2\) has a first element (that is, a minimum).

Assume \(S\) is the non empty subset of \(\N^2\)

Consider \(M=\left\lbrace m\in\mathbb{N}:\exists n\in\mathbb{N},\left(m,n\right)\in S\right\rbrace\)

Since \(S\) is not empty, then \(M\) is not empty. Then \(M\) has the first element which is \(m_0\)

Also consider \(N=\left\lbrace n\in\mathbb{N}:\left(m_0,n\right)\in S\right\rbrace\)

Since \(M\) is not empty, then there exists \((m_0,n)\in S\). Then \(N\) has a first element \(n_0\).

Finally, \((m_0,n_0)\) is the first element in the set

‍