Bài viết

1.4: Một số định lý về các tập đếm được - Toán học


Bây giờ chúng ta suy ra một số hệ quả của Định nghĩa 4 trong § 3.

COROLLARY ( PageIndex {1} )

Nếu một bộ (MỘT) là đếm được hoặc hữu hạn, bất kỳ tập hợp con nào cũng vậy (B subseteq A ).

Đối với if (A subset D_ {u} ^ { prime} ) cho một dãy (u, ) thì chắc chắn (B subseteq A subseteq D_ {u} ^ { prime} )

COROLLARY ( PageIndex {2} )

Nếu như (MỘT) là không thể đếm được (hoặc chỉ là vô hạn), bất kỳ tập siêu nào cũng vậy (B supset A ).

Đối với, nếu (B ) có thể đếm được hoặc hữu hạn, thì (A subseteq B, ) theo Hệ quả 1

Định lý ( PageIndex {1} )

Nếu như (MỘT) (NS) có thể đếm được, sản phẩm chéo của họ cũng vậy (A lần B )

Bằng chứng

Nếu (A ) hoặc (B ) là ( blankset, ) thì (A times B = blankset, ) và không có gì để chứng minh.

Do đó, hãy cho (A ) và (B ) là khác và có thể đếm được. Chúng tôi có thể cho rằng họ đổ đầy hai chuỗi vô hạn, (A = left {a_ {n} right }, B = left {b_ {n} right } ) (nói lại điều khoản nếu cần thiết). Sau đó, theo định nghĩa, (A times B ) là tập hợp tất cả các cặp có thứ tự của biểu mẫu

[ left (a_ {n}, b_ {m} right), quad n, m in N ]

Gọi (n + m ) là (xếp hạng ) của cặp ( left (a_ {n}, b_ {m} right). ) Với mỗi (r trong N, ) có (r-1 ) cặp thứ hạng (r: )

[ left (a_ {1}, b_ {r-1} right), left (a_ {2}, b_ {r-2} right), ldots, left (a_ {r-1} , b_ {1} right) ]

Bây giờ chúng tôi đã đặt tất cả các cặp ( left (a_ {n}, b_ {m} right) ) vào một trình tự như sau. Chúng tôi bắt đầu với

[ left (a_ {1}, b_ {1} right) ]

như thuật ngữ đầu tiên; sau đó lấy hai cặp xếp hạng ba,

[ left (a_ {1}, b_ {2} right), left (a_ {2}, b_ {1} right) ]

sau đó là ba cặp xếp hạng bốn, v.v. Ở bước ((r-1) ), chúng ta lấy tất cả các cặp thứ hạng (r, ) theo thứ tự được chỉ ra trong ((1) ).

Lặp lại quá trình này cho tất cả các cấp bậc trong quảng cáo, chúng tôi thu được chuỗi các cặp

[ left (a_ {1}, b_ {1} right), left (a_ {1}, b_ {2} right), left (a_ {2}, b_ {1} right), left (a_ {1}, b_ {3} right), left (a_ {2}, b_ {2} right), left (a_ {3}, b_ {1} right), ldots ]

trong đó (u_ {1} = left (a_ {1}, b_ {1} right), u_ {2} = left (a_ {1}, b_ {2} right), ), v.v.

Theo cách xây dựng, chuỗi này chứa tất cả các cặp của tất cả các thứ hạng (r, ) do đó tất cả các cặp tạo thành tập (A times B ) (đối với mỗi cặp như vậy có một số thứ hạng (r ) và vì vậy nó cuối cùng phải xảy ra theo trình tự). Vì vậy, (A times B ) có thể được đặt trong một chuỗi. (Quảng trường)

COROLLARY ( PageIndex {3} )

Bộ (NS) của tất cả các số hữu tỉ đều có thể đếm được.

Bằng chứng

Trước hết hãy xem xét tập (Q ) của tất cả các số hợp lý dương, tức là

[ text {fraction} frac {n} {m}, text {with} n, m in N ]

Chúng tôi có thể chính thức xác định chúng bằng các cặp có thứ tự ((n, m), ) tức là với (N lần N ) Chúng tôi gọi (n + m ) là thứ hạng của ((n, m). ) Như trong Định lý (1, ), chúng ta thu được dãy

[ frac {1} {1}, frac {1} {2}, frac {2} {1}, frac {1} {3}, frac {2} {2}, frac { 3} {1}, frac {1} {4}, frac {2} {3}, frac {3} {2}, frac {4} {1}, ldots ]

Bằng cách bỏ các phân số có thể rút gọn và chèn thêm 0 và các số hữu tỉ âm, chúng ta đặt (R ) vào dãy

[0,1, -1, frac {1} {2}, - frac {1} {2}, 2, -2, frac {1} {3}, - frac {1} {3 }, 3, -3, ldots, text {theo yêu cầu. } Quảng trường]

Định lý ( PageIndex {2} )

Sự kết hợp của bất kỳ trình tự nào ( left {A_ {n} right } ) trong số các bộ đếm được là có thể đếm được.

Bằng chứng

Vì mỗi (A_ {n} ) đều có thể đếm được, chúng tôi có thể đặt

[A_ {n} = left {a_ {n 1}, a_ {n 2}, dot, a_ {n m}, ldots right } ]

(Các chỉ số con kép là để phân biệt các chuỗi đại diện cho các tập hợp khác nhau (A_ {n}. )) Như trước đây, chúng ta có thể giả định rằng tất cả các chuỗi là vô hạn. Bây giờ, (U_ {n} A_ {n} ) rõ ràng là bao gồm các phần tử của tất cả các (Một}) kết hợp, I E., tất cả các (a_ {nm} (n, m in N). ) Chúng ta gọi (n + m ) là (rank ) của (a_ {nm} ) và tiến hành như trong Định lý (1, ) do đó thu được

[ bigcup_ {n} A_ {n} = left {a_ {11}, a_ {12}, a_ {21}, a_ {13}, a_ {22}, a_ {31}, ldots right } ]

Vì vậy, ( cup_ {n} A_ {n} ) có thể được đặt trong một chuỗi. (Quảng trường)

Lưu ý 1: Định lý 2 được biểu diễn ngắn gọn như

"Bất kỳ liên hiệp có thể đếm được của các tập hợp có thể đếm được là một tập hợp có thể đếm được."

(Thuật ngữ "công đoàn đếm được"nghĩa là" sự kết hợp của một đếm được họ tập hợp ", tức là họ tập hợp mà các phần tử có thể được đặt trong một chuỗi ( left {A_ {n} right }. )). Đặc biệt, nếu (A ) và (B ) có thể đếm được, (A cup B, A cap B, ) và (AB ) (theo Hệ quả 1 () ).

Lưu ý 2: Từ bằng chứng, nó cũng theo đó phạm vi của bất kỳ chuỗi kép nào ( left {a_ {n m} right } ) có thể đếm được. (MỘT chuỗi kép là một hàm (u ) có miền (D_ {u} ) là (N times N; ) nói rằng, (u: N times N rightarrow B. ) Nếu (n, m in N, ) chúng tôi viết (u_ {nm} ) cho (u (n, m) ) ở đây (u_ {nm} = a_ {nm}.) )

Để chứng minh sự tồn tại của không đếm được bộ, bây giờ chúng ta sẽ chỉ ra rằng khoảng thời gian

[[0,1) = {x | 0 leq x <1 } ]

của trục thực là không đếm được.

Chúng tôi giả sử rằng mỗi số thực (x in [0,1) ) có một khai triển thập phân vô hạn duy nhất

[0. x_ {1}, x_ {2}, dấu chấm, x_ {n}, dấu chấm ]

trong đó (x_ {n} ) là các chữ số thập phân (có thể là số 0) và dãy ( left {x_ {n} right } ) không kết thúc bằng số chín (Điều này đảm bảo sự độc đáo)."

Định lý ( PageIndex {3} )

Khoảng thời gian([0,1)) của trục thực là không đếm được.

Bằng chứng

Chúng ta phải chứng minh rằng không có trình tự nào có thể bao gồm tất cả các của ([0,1). ) Thật vậy, cho trước bất kỳ ( left {u_ {n} right }, ) hãy viết mỗi số hạng (u_ {n} ) dưới dạng phân số vô hạn; Nói,

[u_ {n} = 0. a_ {n 1}, a_ {n 2}, dấu chấm, a_ {n m}, dấu chấm ]

Tiếp theo, xây dựng một Mới phần thập phân

[z = 0. x_ {1}, x_ {2}, ldots, x_ {n}, dot ]

chọn các chữ số của nó (x_ {n} ) như sau.

Nếu (a_ {nn} ) (tức là chữ số thứ (n ) của (u_ {n}) ) là (0, ) đặt (x_ {n} = 1; ) nếu tuy nhiên, (a_ {nn} neq 0, ) đặt (x_ {n} = 0. ) Vì vậy, trong mọi trường hợp, (x_ {n} neq a_ {nn}, ) tức là, (z ) khác nhau từ mỗi (u_ {n} ) bằng ít nhất một chữ số thập phân (cụ thể là chữ số thứ (n )). Kết quả là (z ) khác với tất cả (u_ {n} ) và do đó không nằm trong ( left {u_ {n} right }, ) mặc dù (z in [ 0,1) ).

Do đó, bất kể lựa chọn ( left {u_ {n} right } ) là gì, chúng tôi đã tìm thấy một số (z in [0,1) ) không nằm trong phạm vi của dãy số đó. Do đó (n o left {u_ {n} right } ) chứa tất cả ([0,1). Quảng trường)

Lưu ý 3: Theo Hệ quả (2, ) bất kỳ tập siêu nào của ([0,1), ), ví dụ: toàn bộ trục thực, là không đếm được.

Lưu ý 4: Quan sát rằng các số (a_ {nn} ) được sử dụng trong chứng minh Định lý 3 tạo thành đường chéo của hình vuông kéo dài vô hạn bao gồm tất cả (a_ {nm}. ) Do đó, phương pháp được sử dụng ở trên được gọi là quá trình đường chéo (do G. Cantor).


Bộ đếm được

Trong toán học, một bộ đếm được là một tập hợp có cùng số (số phần tử) với một tập hợp con nào đó của tập hợp các số tự nhiên. Một tập có thể đếm được là một tập hữu hạn hoặc một đếm được vô hạn đặt. Cho dù hữu hạn hay vô hạn, các phần tử của một tập hợp đếm được luôn có thể được đếm từng phần tử một và — mặc dù việc đếm có thể không bao giờ kết thúc — mọi phần tử của tập hợp được liên kết với một số tự nhiên duy nhất.

Một số tác giả sử dụng bộ đếm được để có nghĩa là đếm được vô hạn một mình. [1] Để tránh sự mơ hồ này, thuật ngữ nhiều nhất có thể đếm được có thể được sử dụng khi các tập hợp hữu hạn được bao gồm và đếm được vô hạn, liệt kê được, [2] hoặc không thể phủ nhận [3] ngược lại.

Georg Cantor giới thiệu thuật ngữ này bộ đếm được, những tập hợp tương phản có thể đếm được với những tập hợp không đếm được (I E., không thể đếm được hoặc không đếm được [4] ). Ngày nay, các tập hợp đếm được tạo thành nền tảng của một nhánh toán học được gọi là toán học rời rạc.


Bài tập 4.8

Ví dụ 4.8.1 Chứng tỏ rằng $ R ^ 2 $ không thể đếm được.

Ví dụ 4.8.2 Chứng tỏ rằng tập hợp $ S $ của tất cả các chuỗi vô hạn của 0 và 1 là không thể đếm được (các phần tử của $ S $ là chuỗi dài vô hạn có dạng "00110101110 & hellip '').

Ví dụ 4.8.3 Giả sử $ A $ và $ B $ là các tập vô hạn có thể đếm được rời rạc. Chứng tỏ rằng $ A cup B $ có thể đếm được là vô hạn. (Hãy suy nghĩ về việc sắp xếp mọi thứ thành trình tự.)

Ví dụ 4.8.4 Giả sử $ A $ là hữu hạn và $ B $ là vô hạn đếm được. Chứng tỏ rằng $ A cup B $ có thể đếm được là vô hạn.

Ví dụ 4.8.5 Giả sử $ A $ và $ B $ là các tập vô hạn đếm được. Chứng tỏ rằng $ A cup B $ có thể đếm được là vô hạn.

Ví dụ 4.8.6 Sử dụng bài tập 5 và quy nạp để chứng minh rằng hợp của bất kỳ tập hợp hữu hạn nào của các tập hợp vô hạn đếm được là vô hạn.

Ví dụ 4.8.7 Giả sử rằng $ $ là một tập hợp các tập có thể đếm được không rỗng. Chứng minh rằng $ bigcup_ A_i $ có thể đếm được.

Ví dụ 4.8.8 Chứng tỏ rằng tập hợp tất cả các đa thức với hệ số trong $ Z $ là vô hạn đếm được.

Ví dụ 4.8.9 Tập hợp tất cả các căn (phức) của tất cả các đa thức với hệ số trong $ Z $ là số đại số. Chứng tỏ rằng các số đại số có thể đếm được. Bạn có thể sử dụng mặt mà mọi đa thức đều có một số gốc hữu hạn.

Ví dụ 4,8.10 Gọi $ cal I $ là tập hợp các số vô tỉ (tức là $ $). Chứng tỏ rằng $ cal I $ không thể đếm được. (Sử dụng bài tập 5.)

Ví dụ 4.8.11 Giả sử $ A $ và $ B $ là các tập không rỗng. Chỉ ra rằng $ overline A le overline B $ nếu và chỉ khi có một từ bổ sung $ g dấu hai chấm B thành A $.

Ví dụ 4.8.12 Giả sử $ A $ là một tập có thể đếm được và $ f dấu hai chấm A đến B $ là một hàm cảm biến. Chứng tỏ rằng $ B $ cũng có thể đếm được. (Gợi ý: sử dụng bài tập 5 của mục 4.7.)

Ví dụ 4.8.13 Sử dụng khai triển số thập phân để xây dựng một phép tiêm từ (0,1) đến số vô tỷ (hãy nhớ rằng một số là số hữu tỉ nếu và chỉ khi số thập phân của nó kết thúc hoặc lặp lại).

Ví dụ 4.8.14 Trong phần chứng minh của định lý 4.8.1, chúng tôi đã xây dựng một khai triển thập phân không nằm trong danh sách các khai triển thập phân đã cho. Bản thân điều này không ngụ ý rằng số thực được biểu diễn bằng khai triển đã xây dựng không giống với số thực được biểu diễn bằng khai triển trên danh sách, bởi vì một số số thực có nhiều hơn một khai triển thập phân. Giải thích số thực nào có nhiều hơn một khai triển thập phân, sau đó giải thích tại sao số thực được xây dựng trong chứng minh được đảm bảo không nằm trong danh sách các số thực.


Tập hợp là gì?

MỘT đặt là một tập hợp, hoặc một tập hợp, các đối tượng. Chúng tôi gọi những đối tượng này là các yếu tố, hoặc các thành viên của bộ. Chúng tôi cũng có thể nói rằng họ thuộc về vào tập hợp đó. Ví dụ:

  • Trong thư viện, tất cả sách là một tập hợp và mỗi sách riêng lẻ là một phần tử của tập hợp này.
  • Tất cả các học sinh trong một trường học là một tập hợp.
  • Từ tiếng Anh "math" là một tập hợp các chữ cái. "m", "a", "t", "h" là tất cả các phần tử của tập hợp.

Trong lý thuyết tập hợp, chúng ta chủ yếu quan tâm đến tập hợp các đối tượng toán học. Do đó, chúng ta sẽ không nói về tập hợp người hay sách nhiều nữa, mà tập trung vào tập hợp số, hàm hoặc tập hợp.

Thông thường, chúng ta viết một tập hợp bằng cách hiển thị các phần tử của nó giữa hai dấu ngoặc nhọn. Ví dụ, <1, 4, 6, 9> là một tập hợp có các phần tử là 1, 4, 6, 9. Lưu ý rằng thứ tự các phần tử được viết không làm cho tập hợp khác nhau. Nói cách khác, <1, 4, 6, 9> và <6, 9, 1, 4> và <1, 6, 9, 4> đều đại diện cho cùng một tập hợp.

Bên cạnh các bộ số, chúng ta cũng có thể có các bộ tập hợp. Ví dụ, <<1, 2>, <2, 3 >> là một tập hợp của hai tập hợp, cụ thể là <1, 2> và <2, 3>. Ngoài ra, các phần tử của một tập hợp có thể là các kiểu khác nhau. Ví dụ, <1, 2, <1, 2 >> là một tập hợp chứa hai số và một tập hợp.

Điều quan trọng là chỉ ra trường hợp chỉ có một phần tử trong tập hợp (ví dụ: <1>). Phần tử 1 và tập <1> khác nhau. Chúng ta có thể hiểu khái niệm này bằng một phép tương tự: Một thư viện chỉ có một cuốn sách thì khác với một cuốn sách.

Bên cạnh các tập hợp chỉ chứa một phần tử duy nhất, một trường hợp đặc biệt khác là tập hợp không chứa đối tượng nào. Tập hợp này được gọi là bộ trống hoặc là chưa cài đặt và được ký hiệu & # 216. Có một số ký hiệu đặc biệt mà các nhà toán học đã đồng ý để đại diện cho một số tập hợp nhất định:

  • biểu thị tập hợp bao gồm tất cả các số tự nhiên là 0,1,2,3,4.
  • biểu thị tập hợp bao gồm tất cả các số nguyên. -4, -3, -2, -1,0,1,2,3.
  • biểu thị tập hợp bao gồm tất cả các số hữu tỉ
  • biểu thị tập hợp bao gồm tất cả các số thực
  • biểu thị tập hợp bao gồm tất cả các số phức

Nếu chúng ta muốn viết những chữ cái này bằng tay, hãy thêm một thanh dọc nhỏ vào mép trái của chữ in hoa tương ứng mà chúng ta thường viết. Ví dụ, để biểu diễn các số thực, một thanh nhỏ song song sẽ được viết ở bên trái của chữ hoa bình thường "R".

Một số bộ cũng có thể được viết dưới dạng sau:

có nghĩa là tập hợp của NS mà tuyên bố liên quan đến NS là đúng. Ví dụ,

là tập hợp tất cả các số lẻ.

biểu thị cùng một tập hợp, là tập hợp các phần tử trong tập hợp MỘT thỏa mãn câu lệnh. (NSMỘT có nghĩa là đối tượng NS là trong bộ MỘT. Ký hiệu này sẽ được giải thích trong phần Ký hiệu cơ bản.) Ví dụ:

là tập hợp các số thực thỏa mãn phương trình x 2 = 1.

Chúng ta cũng có thể thay dấu hai chấm bằng một thanh dọc. Ví dụ, các tập hợp trên trở thành:


LÝ THUYẾT THÔNG TIN THUẬT TOÁN

Peter D. Grünwald, Paul M.B. Vitányi, trong Triết học Thông tin, 2008

8 ĐỊNH NGHĨA

Hãy để χ là một tập hợp hữu hạn hoặc có thể đếm được, hãy NS là một biến ngẫu nhiên nhận các giá trị trong χ với phân phối P. Sau đó, (Shannon-) Sự hỗn loạn của biến ngẫu nhiên NS được đưa ra bởi

Entropy được định nghĩa ở đây là một ánh xạ hàm phân phối trên χ đến các số thực. Trong thực tế, chúng ta thường xử lý một cặp biến ngẫu nhiên (X, Y) được xác định trên một không gian khớp χ × γ. sau đó P là sự phân phối chung của (X, Y), và PNS là phân phối cận biên tương ứng của nó trên X, PNS(NS) = Σy P(x, y). Trong trường hợp đó, thay vì viết NS(PNS) nó là thông lệ để viết NS(NS) chúng tôi sẽ tuân theo quy ước này dưới đây.

Entropy có thể được hiểu theo một số cách. Định lý mã hóa không ồn ào (16) đưa ra một cách giải thích lý thuyết mã hóa chính xác: nó cho thấy rằng entropy của P về cơ bản bằng với độ dài mã trung bình khi mã hóa kết quả của P, nếu kết quả được mã hóa bằng mã tối ưu (mã giảm thiểu độ dài mã trung bình này).


Các vấn đề đã được giải quyết

Nhấp hoặc nhấn vào một vấn đề để xem giải pháp.

Ví dụ 1

Ví dụ 2

Ví dụ 3

Ví dụ 4

Ví dụ 5

Ví dụ 6

Ví dụ 1.

Ở đây chúng ta có một tập hữu hạn bao gồm (5 ) phần tử. Do đó, nó có thể đếm được mặc dù thực tế là một số phần tử của nó là tập hợp không đếm được.

Ví dụ 2.

Chúng tôi biết rằng tích số Descartes ( mathbb^ 2 = mathbb times mathbb) là vô hạn. Tích Descartes của ba tập hợp ( mathbb^ 3 = mathbb times mathbb times mathbb) có thể được biểu diễn dưới dạng

Ta thu được tích của hai tập vô hạn đếm được, cũng là vô hạn đếm được.

Ở dạng danh sách, tập hợp (< mathbb^ 3> ) được đưa ra bởi

Ví dụ 3.

Đây là một câu nói đúng. Nó có thể được chứng minh bằng mâu thuẫn. Giả sử rằng (A gạch chéo ngược B ) là vô hạn. Khi đó hợp của hai tập hợp vô hạn đếm được cũng phải đếm được:

Điều này mâu thuẫn với thực tế là tập (A ) là không thể đếm được.

Ví dụ 4.

Khi (n = 1, ) chúng ta có tập hợp các số hữu tỉ ( mathbb) có thể đếm được. Giả sử, bằng cách quy nạp, rằng ( mathbb^ n ) có thể đếm được cho (n in mathbb. ) Lưu ý rằng

Biết rằng tích Descartes của hai tập hợp đếm được. Do đó (< mathbb^> ) là một tập hợp có thể đếm được.

Tiếp theo là tập hợp (< mathbb^> ) có thể đếm được cho bất kỳ (n in mathbb nào.)

Ví dụ 5.

Tập hợp ( left <<0,1> right > ) là hữu hạn và do đó có thể đếm được. Tập hợp các số tự nhiên ( mathbb) cũng có thể đếm được. Như đã biết, tích Descartes của hai tập đếm được là đếm được. Do đó, tập hợp ( left <<0,1> right > times mathbb) có thể đếm được.

Chúng ta có thể sắp xếp các phần tử của tập hợp ở dạng danh sách như sau:

Điều này cho thấy rằng tập hợp ( left <<0,1> right > times mathbb) là vô hạn.

Ví dụ 6.

Chúng tôi giả định rằng bảng chữ cái Latinh bao gồm các chữ cái (52 ) (cả chữ hoa và chữ thường). Sau đó, có (52 ) một chuỗi ký tự, (52 ^ 2 ) hai chuỗi ký tự, v.v. Gọi (M ) là kích thước chuỗi lớn nhất. Khi đó tổng số chuỗi có thể có là (52 ^ M. ) Chúng ta có thể sắp xếp tất cả các chuỗi này như sau:

  • Chúng tôi sắp xếp các chuỗi theo kích thước bắt đầu từ (1 ) đến (M. )
  • Để sắp xếp các phần tử trong mỗi kích thước, chúng tôi sử dụng thứ tự từ vựng.

Danh sách kết quả có thể được đánh số bằng số tự nhiên, vì vậy tập hợp này có thể đếm được.


Bộ đếm được

Tải xuống video từ iTunes U hoặc Internet Archive.

CHUYÊN GIA: OK. Vì vậy, chúng ta đi đến ý tưởng về các tập hợp đếm được, là loại tập hợp vô hạn quen thuộc nhất. Và một tập hợp có thể đếm được là tập mà bạn có thể liệt kê các phần tử-- a0, a1, a2, v.v. Vì vậy, có một danh sách tất cả các phần tử của A, trong đó mọi phần tử trong A đều xuất hiện tại một thời điểm nào đó. Bạn có thể đếm tối đa bất kỳ phần tử nào của A và mọi phần tử của A cuối cùng bạn sẽ nhận được, bạn sẽ có thể đếm đến nó.Vì vậy, nó chỉ là một vấn đề của danh sách nó.

Và định nghĩa kỹ thuật của "A có thể đếm được" là nếu có sự phân biệt giữa A và các số nguyên không âm. Vì thực tế, danh sách này thực sự là một ánh xạ từ các số nguyên không âm đến A. 0 là a0, 1 ​​ánh xạ tới a1, 2 ánh xạ tới a2, và ngầm hiểu là có một phép phân biệt được chỉ ra ở đây. Đó là giả định rằng tất cả [? a's?] là khác biệt để nó là một từ chối.

Vì vậy, chúng ta cũng có, như một trường hợp đặc biệt, các tập hợp hữu hạn cũng được coi là có thể đếm được. Vì vậy, thực sự, nếu n là một nhị phân đối với A, thì A được gọi là vô hạn đếm được. Khả năng còn lại là A hữu hạn. Và cả hai cùng nhau, tôi chỉ nói A là đếm được.

Vì vậy, những gì chúng ta vừa tìm ra, sau đó, từ các ví dụ trước, là các số nguyên dương có thể đếm được. Và tất cả các số nguyên đều có thể đếm được, bởi vì trong cả hai trường hợp, chúng tôi thể hiện phép toán đối với các số nguyên không âm.

Một ví dụ quan trọng và không quá khó là tập hợp các từ nhị phân hữu hạn. Vì vậy, chúng tôi sử dụng ký hiệu này, "0, 1 sao", có nghĩa là tất cả các sao-- hữu hạn có nghĩa là tất cả các chuỗi hữu hạn của các phần tử này, 0 và 1. Vì vậy, đây chỉ là các từ nhị phân hữu hạn.

Làm sao chúng có thể đếm được? Tôi cần một cách để có thể liệt kê chúng một cách có trật tự.

Vâng, chúng ta hãy làm điều đó theo chiều dài. Hãy bắt đầu bằng cách liệt kê từ trống hoặc chuỗi có độ dài bằng không. Và sau đó tôi sẽ liệt kê tất cả các chuỗi một bit, các chuỗi có độ dài một. Và có hai trong số đó.

Vì vậy, hãy để phần tử thứ hai, phần tử tiếp theo của danh sách sau chuỗi rỗng, là 0, rồi đặt phần tử tiếp theo sau đó là 1.

Sau đó, hãy liệt kê tất cả độ dài hai chuỗi. Chà, có bốn độ dài hai chuỗi nhị phân. Và chúng ta hãy liệt kê chúng theo một số thứ tự hợp lý - giả sử, bằng cách biểu diễn nhị phân của chúng. Và sau đó tiếp tục đi. Liệt kê tất cả độ dài ba chuỗi nhị phân - có tám chuỗi trong số đó. Và cuối cùng, tiếp tục đi lên cho đến khi bạn có độ dài n chuỗi nhị phân, trong đó có 2 chuỗi n.

Và đây là mô tả về một cách liệt kê lần lượt tất cả các từ nhị phân hữu hạn, hoặc chuỗi nhị phân hữu hạn. Và danh sách đó hoàn toàn là một mô tả về phép phân từ các số nguyên không âm n đến phần tử thứ n trong danh sách của tôi. Và đó là một phép từ chối, vì vậy các từ nhị phân có thể đếm được.

Một ví dụ khác về tập hợp có thể đếm được là các cặp số nguyên không âm. Vì vậy, làm thế nào có thể-- bây giờ tôi đã có các số nguyên không âm. Tôi phải tìm một bản sao của các cặp số nguyên không âm. Tôi sẽ làm điều đó như thế nào?

Đó là ý tưởng giống như chúng ta đã sử dụng với chuỗi nhị phân. Có rất nhiều cách để chứng minh điều đó, nhưng chúng ta hãy chỉ tuyên truyền ý tưởng chuỗi nhị phân. Hãy bắt đầu liệt kê các cặp số nguyên không âm. Và sau 0, 0, tôi sẽ liệt kê hai cặp-- 0, 1 và 1, 0. Và sau chúng, tôi sẽ liệt kê ba cặp-- 0, 2, 2, 0 và 1, 1 Và sau chúng, 0, 3, 3, 0, 1, 2, 2, 1.

Và nếu bạn có thể thấy những gì tôi đang làm, về cơ bản tôi đang liệt kê các cặp theo thứ tự tổng tọa độ của chúng. Vì vậy, khối thứ n của các cặp mà tôi sắp liệt kê sẽ là các cặp có tổng của hai tọa độ là n. Sẽ có n cộng với một trong số đó. Và tôi tiếp tục đi theo cách này.

Đây là một mô tả có thứ tự hay về-- hoặc mô tả về một cách có trật tự hay để liệt kê tất cả các cặp số nguyên không âm. Trong một khối, hãy phát minh ra một số quy tắc bảng chữ cái để liệt kê các cặp. Vì vậy, tôi sẽ - Tôi đã gợi ý về một quy tắc ở đây để liệt kê tập hợp hữu hạn các cặp có tổng là n và bạn có thể phát minh ra-- bất kỳ cái nào cũng sẽ làm được. Vì vậy, điều đó cho chúng ta biết rằng chúng ta có phép phân biệt giữa các số nguyên không âm và các cặp số nguyên không âm. Vì vậy, đó là một phản ứng quan trọng khác.

Bây giờ, khi bạn đang cố gắng chứng minh tính có thể đếm được, sẽ rất hữu ích nếu có bổ đề sau, bổ đề này đưa ra một đặc điểm thay thế của khả năng đếm được - cụ thể là tập A có thể đếm được nếu và chỉ khi bạn có thể liệt kê A cho phép lặp lại. Hãy nhớ rằng, định nghĩa ban đầu của chúng tôi là bạn có thể liệt kê A mà không cần lặp lại nếu nó là vô hạn hoặc nếu không thì nó hữu hạn. Vì vậy, đó là-- sự phân biệt giữa các số nguyên không âm và A, thực tế, nói rằng đó là một danh sách của tất cả một tập hợp A vô hạn không có lặp lại, bởi vì nó là một nhị phân mà chúng ta đang ánh xạ. Nếu một phần tử xuất hiện hai lần, chúng ta sẽ có hai số nguyên không âm khác nhau ánh xạ tới nó, điều này sẽ phá vỡ thuộc tính bijection, thuộc tính tiêm.

Và vì vậy, giả sử chúng tôi cho phép lặp lại. Và khẳng định rằng điều đó là tốt, bởi vì bạn có thể khắc phục điều đó. Vì vậy, bổ đề nói rằng, nếu có một hàm đảo ngữ từ các số nguyên không âm đến A, thì A có thể đếm được.

Vâng, hãy nhanh chóng kiểm tra theo một hướng. Nếu A là hữu hạn, thì rõ ràng có một hàm tương quan từ các số nguyên không âm sang A. Có rất nhiều số nguyên không âm bổ sung mà bạn không cần. Nếu đó là một tập hợp hữu hạn, chẳng hạn như 10 phần tử trong A, hãy ánh xạ từ 0 đến 9 với 10 phần tử đó và ánh xạ mọi số nguyên không âm khác, chẳng hạn như, với phần tử thứ 10 hoặc phần tử cuối cùng, của A.

Vì vậy, chắc chắn có một phép phủ định nếu A là hữu hạn. Bây giờ, giả sử rằng A là vô hạn và tôi có một phép phủ định từ các số nguyên không âm thành A. Vì vậy, tôi đang liệt kê A với các lần lặp lại. Và tôi phải có một sự phản bác nếu nó phù hợp với định nghĩa khác. Làm thế nào để bạn làm điều đó?

Chà, nếu bạn là một nhà khoa học máy tính, bạn biết cách thay đổi một chuỗi có các lần lặp lại thành một chuỗi không lặp lại. Bạn chỉ cần lọc nó cho các bản sao, đi từ trái sang phải. Lấy dãy vô hạn các phần tử của A trong đó có các phần tử lặp lại và chỉ giữ lại lần xuất hiện đầu tiên của mỗi phần tử. Điều đó sẽ xác định một phép phủ định với các số nguyên không âm nếu a là vô hạn. Và đó là cách chúng tôi chứng minh bổ đề này, mà tôi sẽ giải quyết cho việc nói qua.

Vì vậy, bây giờ chúng ta có một cách thuận tiện khác để chứng minh rằng một tập hợp là có thể đếm được, chỉ bằng cách mô tả, không phải phép phủ định, mà là phép phủ định giữa các số nguyên không âm trong A. Phép chiếu thường dễ mô tả hơn phép so sánh, đó là lý do tại sao đây là bổ đề hữu ích.

Hệ quả của điều này là, nếu tôi đang cố gắng chứng minh rằng một tập hợp A là có thể đếm được, tất cả những gì tôi thực sự cần làm là tìm một số tập hợp khác mà tôi biết là có thể đếm được và mô tả một phép so sánh từ tập hợp khác C thành A . Bởi vì tôi biết rằng nếu C có thể đếm được, thì sẽ có một phép phủ định giữa các số nguyên không âm và C. Và vì khi bạn kết hợp một phủ định với một phủ định, bạn kết hợp với một từ chối, điều đó sẽ ngầm định nghĩa một phủ định từ các số nguyên không âm đến A, theo bổ đề cho tôi biết rằng A có thể đếm được.

Vì vậy, cách chung để chứng minh một điều gì đó có thể đếm được là chỉ cần mô tả một sự từ chối, từ một thứ mà bạn biết là có thể đếm được, chạm vào mục tiêu của bạn. Và hãy xem một ví dụ về điều đó.

Tôi khẳng định rằng số hữu tỉ có thể đếm được, số hữu tỉ có thể đếm được. Chà, điều này ban đầu hơi nổi bật hơn một chút, bởi vì bạn có thể thấy cách bạn có thể đếm số nguyên không âm, số nguyên dương, tất cả các số nguyên, bởi vì có một cách hợp lý để có cái này đến cái khác.

Nhưng với lý trí, nó lộn xộn. Giữa hai lý do bất kỳ, có một hợp lý khác. Không có bất kỳ lý do đầu tiên nào. Không có bất kỳ cách rõ ràng nào để liệt kê tất cả. Nhưng thực sự, nếu bạn ngừng suy nghĩ về tính hợp lý của cách chúng được sắp xếp trên dòng thực, mà chỉ nghĩ về chúng dưới dạng các cặp số nguyên, thì sẽ rõ ràng cách liệt kê chúng, bởi vì chúng ta đã biết rằng các cặp số không số nguyên âm có thể đếm được.

Vì vậy, tôi sẽ chỉ ánh xạ một cặp số nguyên không âm m, n thành số hữu tỉ m chia cho n. Chà, n có thể bằng 0, vì vậy nếu n bằng 0, chỉ cần ánh xạ tất cả các cặp đó thành số hữu tỉ yêu thích của bạn. Gọi nó là một nửa. Và điều đó cung cấp cho chúng ta một ánh xạ xạ ảnh tốt đẹp, bởi vì mọi số hữu tỉ có thể được biểu diễn dưới dạng m trên n-- ít nhất là mọi số hữu tỉ không âm.

Vì vậy, trên thực tế, những gì chúng ta có là một phép cộng từ các cặp số nguyên không âm, mà chúng ta biết là có thể đếm được, lên các số thực không âm-- xin lỗi, các số hữu tỉ không âm, thương của số nguyên. Điều đó có nghĩa là các lý lẽ, chắc chắn, có thể đếm được, mặc dù chúng dường như được dàn trải khắp nơi.

Vì vậy, một lần nữa, chúng ta thấy rằng nếu N chéo N có thể đếm được và có một surj, được mô tả ở trên, đối với các số hợp lý không âm, vì vậy chúng có thể đếm được.

Chà, chỉ cần nhìn về phía trước một chút, sẽ ra rằng, ngược lại với số hữu tỉ, số thực không thể đếm được. Và trên thực tế, không phải là các chuỗi nhị phân vô hạn mà chúng ta đã thấy - có sự phân biệt giữa các chuỗi nhị phân vô hạn và tập lũy thừa của các số nguyên không âm. Và cả hai đều sẽ là những ví dụ cơ bản về các tập hợp không đếm được, vì vậy các tập hợp không đếm được, chúng ta sẽ xem xét trong bài giảng tiếp theo.


1.4: Một số định lý về các tập đếm được - Toán học

Giờ Làm Việc: M 2: 30-3: 30 p.m., T 1: 30-2: 30 p.m, hoặc theo hẹn, tại 802 PHSC.

Mô tả danh mục khóa học: Điều kiện tiên quyết: 2433 và 2513 hoặc sự cho phép của người hướng dẫn. Nhận xét về hệ thống số thực. Dãy số thực. Tôpô của đường thực. Tính liên tục và sự phân biệt của các hàm số một biến số. (F, Sp, Su)

Chữ: Steven R. Lay. Phân tích với phần giới thiệu về bằng chứng, Pearson, xuất bản lần thứ 5, 2012, ISBN: 03217474X. Khóa học sẽ bao gồm các phần chính của Ch. 1-6 (và, nếu thời gian cho phép, các phần của Ch. 7 và / hoặc 8).

  • Bài tập về nhà 1, do ngày 28 tháng 8 (thứ năm).
  • Bài tập về nhà 2, do ngày 4 tháng 9 (thứ năm).
  • Bài tập về nhà 3, do ngày 11 tháng 9 (thứ năm).
  • Bài tập về nhà 4, đến hạn vào ngày 23 tháng 9 (Thứ Ba) [phiên bản cuối cùng (cập nhật vào ngày 16 tháng 9)]
  • Bài tập về nhà 5, do ngày 2 tháng 10 (thứ năm).
  • Bài tập về nhà 6, do ngày 9 tháng 10 (thứ năm).
  • Bài tập về nhà 7, do ngày 16 tháng 10 (thứ năm).
  • Bài tập về nhà 8, nộp vào ngày 30 tháng 10 (thứ năm).
  • Bài tập về nhà 9, do ngày 6 tháng 11 (thứ năm).
  • Bài tập về nhà 10, do ngày 13 tháng 11 (thứ năm).
  • Bài tập về nhà 11, do ngày 20 tháng 11 (thứ năm).
  • Bài tập về nhà 12, do ngày 4 tháng 12 (thứ năm).
  • Logic và bằng chứng: liên kết logic, định lượng, kỹ thuật chứng minh.
  • Bộ và chức năng: thiết lập các phép toán, quan hệ, chức năng, cardinality.
  • Những con số thực: số tự nhiên, quy nạp, thứ tự, tính đầy đủ, cấu trúc liên kết của NS, bộ nhỏ gọn.
  • Trình tự: hội tụ, định lý giới hạn, dãy đơn điệu, dãy Cauchy, dãy con.
  • Giới hạn và tính liên tục: giới hạn của hàm, hàm liên tục, (liên tục đồng nhất).
  • Sự khác biệt: đạo hàm, Định lý Giá trị Trung bình, Quy tắc L'Hospital, Định lý Taylor.
  • (Mang tính thăm dò) Hội nhập: Tích phân Riemann, Định lý Cơ bản của Giải tích.

    Bài giảng 1 (Thứ ba, ngày 19 tháng 8):Kết nối logic: câu lệnh, giá trị sự thật, ví dụ kết nối phủ định & simP sự liên kết P&vàNS phân ly P&hoặcNS ngụ ý (câu điều kiện) P& rArrNS những cách khác nhau để nói P& rArrNS tương đương P& hArrNS tautology, ví dụ [Sec. 1.1]