Least upper bound property

Một tập $\displaystyle A \subset\mathbb{R}$ được gọi là bị chặn trên nếu tồn tại $\displaystyle b \in \mathbb{R}$ sao cho $\displaystyle a \leq b$ với mọi $\displaystyle a \in A$ . Số $\displaystyle b$ được gọi là một cận trên của $\displaystyle A$ . Tương tự, tập $\displaystyle A$ bị chặn dưới nếu tồn tại một cận dưới $\displaystyle l \in \mathbb{R}$ thỏa mãn $\displaystyle l \leq a$ với mọi $\displaystyle a \in A.$ Tập $\displaystyle A$ được gọi là bị chặn nếu nó bị chặn trên và bị chặn dưới.

Bài tập 1. Tìm một tập hợp $\displaystyle A$ các số thực sao cho:

(1) $\displaystyle A$ bị chặn trên.

(2) $\displaystyle A$ bị chặn dưới.

(3) $\displaystyle A$ không bị chặn trên và không bị chặn dưới. $\Box$

Định nghĩa 1. Một số thực $\displaystyle s$ được gọi là cận trên đúng của $\displaystyle A \subset \mathbb{R}$ nếu nó thỏa mãn đồng thời hai điều kiện:

(1) $\displaystyle s$ là một cận trên của $\displaystyle A$ .

(2) nếu $\displaystyle b$ là một cận trên của $\displaystyle A$ thì $\displaystyle s \leq b.$

Cận trên đúng cũng thường được gọi là supremum của tập $\displaystyle A$ , ký hiệu $\displaystyle \sup A$ . Cận dưới đúng hay infimum của $\displaystyle A$ được định nghĩa theo cách tương tự và được ký hiệu bởi $\displaystyle \inf A$ . Mặc dù một tập có thể có vô hạn cận trên, nhưng nó chỉ có tối đa một cận trên đúng.

Ví dụ 1. Cho tập hợp $\displaystyle A=\left\{\frac{1}{n}: n \in \mathbb{N}^*\right\}=\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots\right\}.$

Tập $A$ bị chặn trên và dưới. Ta thấy $\sup A=1$ và $\inf A=0$ . $\Box$

Một bài học quan trọng rút ra từ ví dụ trên là $\displaystyle \sup A$ và $\displaystyle \inf A$ có thể thuộc hoặc không thuộc tập $\displaystyle A$ . Đây là điểm khác nhau cốt yếu giữa phần tử lớn nhất và cận trên đúng (hoặc phần tử nhỏ nhất và cận dưới đúng) của một tập số thực.

Định nghĩa 2. Một số thực $\displaystyle a_{0}$ được gọi là phần tử lớn nhất của tập $\displaystyle A$ , ký hiệu $\displaystyle \max A$ , nếu $\displaystyle a_{0}$ là một phần tử của $\displaystyle A$ và $\displaystyle a_{0} \geq a$ với mọi $\displaystyle a \in A$ . Tương tự, số $\displaystyle a_{1}$ là phần tử nhỏ nhất của $\displaystyle A$ , ký hiệu $\displaystyle \min A$ , nếu $\displaystyle a_{1} \in A$ và $\displaystyle a_{1} \leq a$ với mọi $\displaystyle a \in A.$

Ví dụ 2. Hai tập $\displaystyle [0;2]$ và $\displaystyle (0;2)$ bị chặn, có cùng cận trên đúng $\displaystyle 2$ , nhưng chỉ $\displaystyle [0;2]$ có phần tử lớn nhất. Như vậy, cận trên đúng có thể tồn tại và không phải là phần tử lớn nhất, nhưng khi phần tử lớn nhất tồn tại, nó cũng là cận trên đúng. $\Box$

Mặc dù ta có thể thấy rằng không phải mọi tập hợp khác rỗng bị chặn trên nào đều có phần tử lớn nhất, nhưng tiên đề về tính đầy đủ khẳng định rằng mọi tập hợp như vậy đều có một cận trên đúng. Ta sẽ không chứng minh điều này. Tiên đề trong toán học là một giả định được chấp nhận, được sử dụng mà không cần chứng minh.

Tiên đề về tính đầy đủ. Mọi tập các số thực khác rỗng và bị chặn trên đều có cận trên đúng.

Từ tiên đề trên ta có thể chứng minh mọi tập số thực khác rỗng và bị chặn dưới đều có cận dưới đúng. Tiên đề không đúng với tập các số hữu tỷ.

Ví dụ 3. Tập $\{r\in\mathbb{Q}\mid r^2<2\}$ bị chặn trên và khác rỗng nhưng không có cận trên đúng thuộc $\mathbb{Q}$ . $\Box$

Hai định lý sau cho một định nghĩa tương đương của cận trên đúng và cận dưới đúng.

Continue reading →

Continued fraction expansion of rational numbers

In this section we use continued fractions ([2]) for expansion of rational numbers. If $\displaystyle x_0$ , $\displaystyle x_1$ , $\displaystyle \ldots$ , are integer nunbers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ then $\displaystyle [x_0;x_1,x_2,\ldots,x_n]\in\mathbb{Q},\quad\forall n\geq 0.$

Conversly, we have the theorem

Theorem 1. Let $\displaystyle r$ and $\displaystyle s$ be coprime integers with $\displaystyle s>0$ . Then there are non negative integer $\displaystyle n$ and integers $\displaystyle a_0$ , $\displaystyle a_1$ , $\displaystyle \ldots$ , $\displaystyle a_n$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i=1,2,\ldots,n$ .

(2) $\displaystyle r/s=[a_0;a_1,a_2,\ldots,a_n]$ .

Proof. Let us proceed by induction on $\displaystyle s$ . The case $\displaystyle s=1$ is trivial. Now suppose that the assertion is true for all positive integers up to $\displaystyle s-1$ ( $\displaystyle s>1$ ). Because $\displaystyle (r,s)=1$ and $\displaystyle s>1$ , we have $\displaystyle s\nmid r$ . Hence by the Division Algorithm ([1]), there are integers $\displaystyle a$ and $\displaystyle b$ such that

$\displaystyle r=sa+b,\quad 1\leq b<s.\quad\quad (1)$

By the hypothesis of the induction, there are integers $\displaystyle m>0$ , $\displaystyle a_1$ , $\displaystyle a_2>0$ , $\displaystyle \ldots$ , $\displaystyle a_m>0$ such that

$\displaystyle \frac{s}{b}=[a_1;a_2,a_3,\ldots,a_m].\quad\quad (2)$

Because $\displaystyle s>b$ , we have $\displaystyle a_1>0$ . From (1) and (2) we have

$\displaystyle \frac{r}{s}=a+\frac{1}{s/b}=a+\frac{1}{[a_1;a_2,a_3,\ldots,a_m]}=[a;a_1,a_2,\ldots,a_m],$ completing the induction step. $\Box$

The equality in the theorem is called an expansion of $\displaystyle r/s$ into a finite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $i-$ th convergent of the continued fraction, or $i-$ th convergent of $\displaystyle r/s$ .

Example 1. Find an expansion of $\displaystyle 43/5$ into a finite continued fraction.

Solution. By the Division Algorithm, we have

$\displaystyle 43=5\cdot 8+3\quad\quad\frac{43}{5}=8+\frac{3}{5}=8+\frac{1}{5/3},$ and

$\displaystyle 5= 3\cdot 1 +2\quad\quad\frac{5}{3}=1+\frac{2}{3}=1+\frac{1}{3/2},$ and $\displaystyle \frac{3}{2}=1+\frac{1}{2}$ . Therefore $\displaystyle 43/5=[8;1,1,2]$ . $\Box$

The theorem says that for every rational number has an expansion into a finite continued fraction. But this expansion is not unique.

Example 2. $\displaystyle 13/5=[2;1,1,2]=[2;1,1,1,1]$ . $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an integer number. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . If $\displaystyle n=0$ then $\displaystyle \alpha=a_0$ and $\displaystyle \alpha=[\alpha]$ is an expansion of $\displaystyle \alpha$ . If $\displaystyle n=1$ then $\displaystyle \alpha=a_0+\frac{1}{a_1}$ , hence $\displaystyle \frac{1}{a_1}$ is an integer, so $\displaystyle a_1=1$ . Therefore $\displaystyle \alpha=[\alpha-1;1]$ is an expansion of $\displaystyle \alpha$ .

Now assume that $\displaystyle n\geq 2$ . We have

$\displaystyle \alpha-a_0=\frac{1}{[a_1;a_2,\ldots,a_n]}$

is an integer number and $\displaystyle [a_1;a_2,\ldots,a_n]>0$ , hence $\displaystyle [a_1;a_2,\ldots,a_n]\leq 1$ . This claim is false because $\displaystyle n\geq 2$ and $\displaystyle a_i\geq 1$ for every $\displaystyle i=1,2,\ldots,n$ . $\Box$

Theorem 3. Let $\displaystyle \alpha$ be a rational number but not an integer. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. Assume that $\displaystyle \alpha=\alpha=r/s$ , where $\displaystyle r$ and $\displaystyle s>1$ are coprime integers. We prove by induction on $\displaystyle s$ that $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction

$\displaystyle \alpha=[a_0;a_1,\ldots,a_n]=[a_0;a_1,\ldots,a_n-1,1],$

where $\displaystyle a_n>1$ . If $\displaystyle s=2$ , because $\displaystyle (r,s)=1$ there is an integer $\displaystyle k$ such that $\displaystyle r=2k+1$ . By the theorem 1, we can write

$\displaystyle \alpha=k+\frac{1}{2}=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=k$ , hence $\displaystyle 2=[a_1;a_2,\ldots,a_n]$ . By the theorem 2, we have $2$ has exactly two expansions into a finite continued fraction, those are $2=[2]$ and $2=[1;1]$ , therefore $\alpha$ has exactly two expansions $\displaystyle \alpha=[k;2]=[k;1,1],$ hence the claim is true for $\displaystyle s=2$ . Now suppose that the claim is true for $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle \ldots$ , $\displaystyle s-1$ ( $\displaystyle s>2$ ). By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=[\alpha]$ (integer part of $\alpha$ ), hence $\displaystyle \frac{1}{\alpha-[\alpha]}=[a_1;a_2,\ldots,a_n].$ By the Division Algorithm, there is an integer $\displaystyle a$ such that $\displaystyle r=s[\alpha]+a$ and $1\leq a<s$ , then

$\displaystyle \frac{s}{a}=[a_1;a_2,\ldots,a_n].$

If $a=1$ then $a_1>1$ and by the theorem 2, we have $s/a$ has exactly two expansions are $s/a=[a_1]$ and $\displaystyle s/a=[a_1-1;1]$ . If $\displaystyle a>1$ then by the hypothesis of the induction (note that $\displaystyle s$ and $\displaystyle a$ are coprime integers), $\displaystyle s/a$ has exactly two expansions are

$\displaystyle \frac{s}{a}=[a_1;b_2,\ldots,b_n]=[a_1;b_2,\ldots,b_n-1,1],$

where $\displaystyle b_n>1$ . Therefore $\displaystyle \alpha$ has exactly two expansions, and the claim is true for $\displaystyle s$ . $\Box$

References

[1] https://nttuan.org/2020/01/14/divisibility/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

Continued fractions: The basics

Let $x_0$ , $\displaystyle x_1$ , $\displaystyle x_2$ , $\displaystyle \ldots$ be variables. We define two sequences of polynomials with complex coefficients $\displaystyle \{p_n\}_{n\geq 0}$ and $\displaystyle \{q_n\}_{n\geq 0}$ by conditions following:

(1) For all non negative integer $\displaystyle n$ , $\displaystyle p_n$ and $\displaystyle q_n$ are polynomials in $\displaystyle x_0,x_1,\ldots,x_n$ .

(2) $\displaystyle p_0=x_0$ and $\displaystyle q_0=1$ .

(3) For all positive integer $\displaystyle n$ , $\displaystyle p_n=x_0p_{n-1}(x_1,x_2,\ldots,x_n)+q_{n-1}(x_1,x_2,\ldots,x_n)$ and

$\displaystyle q_n=p_{n-1}(x_1,x_2,\ldots,x_n)$ .

Example. We have

$\displaystyle p_1=x_0x_1+1$ and $\displaystyle q_1=x_1$ , therefore $\displaystyle \frac{p_1}{q_1}=x_0+\frac{1}{x_1}$ .

$\displaystyle p_2=x_0x_1x_2+x_0+x_2$ and $\displaystyle q_2=x_1x_2+1$ , hence

$\displaystyle \frac{p_2}{q_2}=x_0+\frac{x_2}{x_1x_2+1}=x_0+\cfrac{1}{x_1+\cfrac{1}{x_2}}. \Box$

For all non negative integer $\displaystyle n$ we have

$\displaystyle [x_0;x_1,x_2,\ldots,x_n]:=\frac{p_n}{q_n}=x_0+\cfrac{1}{x_1+\cfrac{1}{x_2+\cfrac{1}{x_3+\cdots+\cfrac{1}{x_{n-1}+\cfrac{1}{x_n}}}}}.$

A rational function of this form is called a continued fraction.

Proposition 1. For all $\displaystyle n>1$ , we have $\displaystyle p_n=x_np_{n-1}+p_{n-2}$ and $\displaystyle q_n=x_nq_{n-1}+q_{n-2}.$

Proof. We use induction on $\displaystyle n$ . From the above example we have the assertion is true for $\displaystyle n=2$ . Now suppose that the assertion has been established for $\displaystyle n-1$ ( $\displaystyle n>2$ ). Then we have

$\displaystyle p_{n-1}(x_1,x_2,\ldots,x_n)=x_np_{n-2}(x_1,x_2,\ldots,x_{n-1})+p_{n-3}(x_1,x_2,\ldots,x_{n-2})$

and

$\displaystyle q_{n-1}(x_1,x_2,\ldots,x_n)=x_nq_{n-2}(x_1,x_2,\ldots,x_{n-1})+q_{n-3}(x_1,x_2,\ldots,x_{n-2}).$

Therefore by define of $\displaystyle \{p_n\}$ and $\displaystyle \{q_n\}$ ,

$\displaystyle p_n=x_0p_{n-1}(x_1,x_2,\ldots,x_n)+q_{n-1}(x_1,x_2,\ldots,x_n)=x_np_{n-1}+p_{n-2},$

and $\displaystyle q_n=x_nq_{n-1}+q_{n-2}$ . Thus the assertion is true for $\displaystyle n$ . $\Box$

For convenience, we define $\displaystyle p_{-2}=0$ , $\displaystyle p_{-1}=1$ , $\displaystyle q_{-2}=1$ , and $\displaystyle q_{-1}=0$ .

Proposition 2. For all $\displaystyle n>-2$ , we have $\displaystyle p_nq_{n-1}-q_np_{n-1}=(-1)^{n-1}$ .

Proof. We prove by induction on $\displaystyle n$ . The case $\displaystyle n=-1$ is trivial. Now suppose that the assertion is true for $\displaystyle n-1$ ( $\displaystyle n\geq 0$ ). Then by proposition 1, we have

$\displaystyle p_nq_{n-1}-q_np_{n-1}=(x_np_{n-1}+p_{n-2})q_{n-1}-(x_nq_{n-1}+q_{n-2})p_{n-1}$

$=-(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=(-1)^{n-1}.$

Therefore the assertion is true for $\displaystyle n-1$ . $\Box$

Proposition 3. For all $\displaystyle n>-1$ , we have $\displaystyle p_nq_{n-2}-q_np_{n-2}=(-1)^nx_n$ .

Proof. Assume $\displaystyle n>-1$ is an integer number. By propositions 1 and 2, we have

$\displaystyle p_nq_{n-2}-q_np_{n-2}=(x_np_{n-1}+p_{n-2})q_{n-2}-(x_nq_{n-1}+q_{n-2})p_{n-2}$ $=x_n(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=(-1)^nx_n. \Box$

Proposition 4. If $\displaystyle n\geq 0$ and $\displaystyle \theta:=[x_0;x_1,x_2,\ldots,x_{n+1}]$ then $\displaystyle p_n-\theta q_n=\frac{(-1)^{n-1}}{q_{n+1}}.$

Proof. By proposition 2, we have

$\displaystyle p_n-\theta q_n=p_n-\frac{p_{n+1}}{q_{n+1}}\cdot q_n=\frac{-(p_{n+1}q_n-q_{n+1}p_n)}{q_{n+1}}=\frac{(-1)^{n-1}}{q_{n+1}}. \Box$

Perfect rulers

Giả sử ta có một cái thước kẻ dài $\displaystyle 6$ , trên đó đã đánh dấu các điểm $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle 4$ , $\displaystyle 5$ , $\displaystyle 6$ . Sử dụng chiếc thước này ta có thể tạo mọi đoạn có độ dài thuộc $\displaystyle [6]$ , nhưng ta không cần đánh dấu trên thước nhiều điểm như thế để đạt được điều này. Ta có thể đánh dấu $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 4$ , $6$ là đủ (đoạn độ dài $2$ được đo giữa hai điểm $4$ và $6$ , đoạn độ dài $3$ được đo giữa $1$ và $4$ , đoạn độ dài $4$ được đo giữa $0$ và $4$ , đoạn độ dài $5$ được đo giữa $1$ và $6$ ). Vì $C_4^2=6$ nên hoàn cảnh này là hoàn hảo.

Bài toán. Cho một số nguyên $n$ lớn hơn $4$ . Chứng minh rằng không tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Lời giải. Giả sử ngược lại, tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Xét đa thức $\displaystyle A(z) = \sum_i z^{a_i}$ . Theo tính chất của các số $a_1$ , $a_2$ , $\ldots$ , $a_n$ , ta có