Sets và functions

Sets và functions là nền tảng cho nghiên cứu toán học và phổ biến trong các ngành định lượng, bao gồm thống kê và khoa học dữ liệu. Trong chương này, chúng ta sẽ xem xét các khái niệm cơ bản về sets, lists, và functions từ góc độ dữ liệu.

Sets

Ví dụ thực tế cho set là danh sách hàng tạp hóa : chức năng chính mà danh sách hàng tạp hóa cung cấp là trả lời câu hỏi “đây là một mặt hàng trong cửa hàng, nó có trong danh sách không?”. Lưu ý với các mục đich trả lời câu hỏi này, thứ tự danh sách đồ vật trong cửa hàng tạp hóa không quan trong, và việc lặp đi lặp lại một mục tiêu nhập tương đương với các việc có một bản sao duy nhắt của mục nhập đó. Điều này dẫn chung ta đến định nghĩa set.

Các bài viết liên quan:

• Chữ ký số (digital signatures) là gì?
• Data science
• Data Collection trong nghiên cứu
• Các bước xây dựng mô hình Machine learning
• Machine learning: Thuật toán SVM
• Toán học trong Data Science

1. Định nghĩa Set

set là một tập hợp các đối tượng không có thứ tự. Các đối tượng trong một tập hợp gọi là phần tử.

Đối tượng thuật ngữ trong định nghĩa này là mơ hồ một cách có chủ ý. Set có thể chứa bất kì loại dữ liệu nào: số, chữ, ký tự, hình tròn, hình vuông, các set khác, hay nhiều set khác nhau.

Nếu một set S chứa một số hữu hạn phần tử như là s1, s2,…, sn, ta có thể viết:

S = (s1,s2,…,sn)

Phép toán cơ bản được cung cấp bởi một tập hợp là kiếm tra thành viên chúng ta viết s ϵ S để chỉ ra rằng S là phần tử của S. nếu s không phải là phần tử của S, chung ta viết s ∈ S. nếu 2 set có phần tử giống nhau, thì 2 set bằng nhau. Ví dụ: {1, 1, 2} = {1, 2}. Vì lý do này, chúng tôi thường liệt kê các phần tử của một tập hợp mà không trùng lặp.

Set không chứa phần tử nào gọi là tập hợp rỗng và được ký hiệu là ∅ hoặc {}.

Một vài tập hợp có tên tập hợp chuẩn và đặc biệt bao gồm:

• R tập hợp số thực.
• Q tập hợp số hữu tỉ.
• Z tập hợp số nguyên.
• N tập hợp số tự nhiên.

2. Định nghĩa tập hợp con

Giả sử tập hợp S và T. Nếu mọi phần tử của T cũng là một phần tử của S thì ta nói T là một tập con của S, kí hiệu là T ⊂ S.

Tập hợp S và T bằng nhau nếu S ⊂ T và T ⊂ S.

Bài tập 1.1.1:  Giả sử rằng E là tập hợp các số nguyên dương chẵn và F là tập hợp các số nguyên dương hơn một số nguyên lẻ.

(a) E ⊂ F

(b) F ⊂ E

(c) E = F

(d) tất cả các điều trên

Ví dụ 1.1.1:

Ta có N ⊂ Z ⊂ Q ⊂ R, vì mọi số tự nhiên đều là số nguyên, mọi số nguyên là hữu tỉ và mọi số hữu tỉ là thực.

3. Định nghĩa ký hiệu trình tạo tập hợp:

Nếu S là tập hợp và P là thuộc tính mà mỗi phần tử của S thỏa mãn hoặc không thỏa mãn thì

{s ∈ S: s thỏa mãn P}

biểu thị tập hợp tất cả các phần tử trong S có thuộc tính P. Đây được gọi là ký hiệu trình tạo tập hợp. Dấu hai chấm được đọc là ‘such as’

ví dụ 1.1.2: Giả sử tập S biểu thị tập tất cả các số thực từ 0 đến 1. Khi đó S có thể được biểu diễn dưới dạng

S = {s ∈ R : 0 < s < 1}.

4. Định nghĩa tính tổng hợp

Cho một tập hợp S, bản số của S, ký hiệu là | S |, biểu thị số phần tử trong S.

Bài tập 1.1.2:  Let S = {4, 3, 4, 1}. Find |S|.

|S| = {4,3,1,-4,-3,-1}

5. Định nghĩa có thể đếm được vô hạn

Một tập hợp là vô hạn đếm được nếu các phần tử của nó có thể được sắp xếp thành một dãy.

Ví dụ 1.1.3:

Tập {1, 2, 3, 4 ,. . .} là vô hạn đếm được. Tập hợp các số nguyên là vô hạn đếm được, vì chúng có thể được sắp xếp theo thứ tự: {0, 1, −1, 2, −2, 3, −3 ,. . .}

Tập hợp các số hữu tỉ từ 0 đến 1 là vô hạn đếm được, vì chúng đều xuất hiện trong dãy 1/2, 1/3, 2/3, 1/4, 3/4,…

Tập hợp tất cả các số thực từ 0 đến 1 không đếm được là vô hạn. Bất kỳ dãy số thực vô hạn nào nhất thiết sẽ không bao gồm tất cả các số thực. Điều này có thể được chứng minh bằng cách sử dụng một ý tưởng gọi là lập luận đường chéo của Cantor, mặc dù chúng tôi sẽ bỏ qua phần chứng minh.

Bài tập 1.1.3 Chứng minh rằng tập hợp tất cả các cặp số nguyên dương có thứ tự là vô hạn đếm được.

Tập hợp các số nguyên dương là vô hạn đếm được vì chúng có thể sắp xếp thành thứ tự

Set Operation

Cho một tập hợp S mô tả danh sách hàng tạp hóa và tập hợp con A ⊂ S mô tả tập hợp các mặt hàng chúng ta đã mua, tập hợp mà chúng ta có thể quan tâm nhất khi xây dựng từ S và A là tập hợp các mặt hàng thuộc S nhưng không thuộc A. Đây được gọi là phần bù của A đối với S.

1. Định nghĩa Phần bù

Nếu A và S là tập hợp và A ⊂ S, thì phần bù của A đối với S, được ký hiệu là S \ A hoặc A^c, là tập hợp tất cả các phần tử trong S không thuộc A.

A c = {s ∈ S: s không thuộc A}.

Vì S không phải là một phần của ký hiệu A^c, chúng tôi thường sẽ chỉ sử dụng ký hiệu đó khi tập hợp chứa S dự định rõ ràng khỏi ngữ cảnh.

Bài 1.1.4: Giả sử S = {1, 2, 3, 4, 5} và A = {4, 2}. Tìm phần bù

A∩S = {4,2}

A ∪ S= {1,2,3,4,5}

A \ S = {1,3,5}

Bài 1.1.5: Giả sử A ⊂ S, | S | = 55, và | A | = 13. Tìm | S \ A |.

Nếu hai thành viên trong gia đình của bạn cung cấp cho bạn danh sách hàng tạp hóa khi bạn chuẩn bị đi đến cửa hàng, thì điều đầu tiên bạn có thể muốn làm là lập một danh sách hàng tạp hóa tổng hợp. Thao tác tập hợp này được gọi là lấy công đoàn.

2. Định nghĩa hợp

Hợp của hai tập hợp S và T, ký hiệu là S ∪ T, là tập hợp chứa tất cả các phần tử của S và tất cả các phần tử của T và không có phần tử nào khác. Nói cách khác, s ∈ S ∪ T nếu và chỉ khi s ∈ S hoặc s ∈ T.

Bài tập 1.1.6 Cho S = {1, 2, 4, 5} và T = {1, 5, 6, 7, 8}. Tìm S ∪ T.

S ∪ T.= {1,2,4,5,6,7,8}

Khi chúng tôi chọn ổ bánh mì để mua, chúng tôi quan tâm đến việc tìm một ổ nằm trong cả hai bộ: (i) bộ ổ bánh có giá nằm trong khoảng giá có thể chấp nhận được của chúng tôi và (ii) bộ của những ổ bánh mà chúng tôi thấy vừa ý. Tập hợp những ổ bánh là giao của hai tập hợp này.

3. Định nghĩa Giao

Giao của hai tập hợp S và T, ký hiệu là S ∩ T, là tập hợp bao gồm các phần tử nằm trong cả S và T. Nói cách khác, s ∈ S ∩ T nếu và chỉ khi s ∈ S và s ∈ T.

Ví dụ 1.1.4 Cho S = {1, 2, 3, 4, 5} và T = {1, 5, 6, 7, 8}.

Khi đó S ∩ T = {1, 5}.

Phép toán hợp nhất và giao nhau có thể được áp dụng cho bất kỳ số lượng bộ nào. Giả sử S1, S2 ,. . . , Sn là các tập hợp — sự kết hợp của các tập hợp này có thể được biểu diễn dưới dạng S1 ∪ S2 ∪ · · · ∪ Sn

4. Định nghĩa Rời rạc

Hai tập hợp S và T là rời rạc nếu chúng không có phần tử nào chung.

Nói cách khác, S và T rời nhau nếu S ∩ T = ∅. Định nghĩa 1.1.9 mở rộng cho một số tập hợp tùy ý. Ta nói rằng các tập S1, S2 ,. . . , Sn tách rời từng cặp nếu Si ∩ Sj = ∅ bất cứ khi nào i 6 = j

Bài tập 1.1.7 : Tìm ba tập hợp A, B, C có A ∩ B ∩ C = ∅ mà tất cả các giao điểm A ∩ B, B ∩ C và A ∩ C đều không

A = {1, 2, 3}

B = {4, 5, 6}

C = {7, 8, 9}

Giả sử bạn là thành viên của một nhóm n người mua sắm làm việc cùng nhau để mua các mặt hàng trong một danh sách hàng tạp hóa. Một ý tưởng hay là phân chia nhóm mặt hàng bạn muốn mua thành n bộ nhỏ hơn để mỗi người chỉ có thể mua các mặt hàng trên bộ của riêng mình.

5. Định nghĩa Phân hoạch

 Phân hoạch của tập S là tập hợp các tập khác rỗng S1, S2 ,. . . , Sn sao cho

S = Si và S1, S2 ,. . . , Sn là rời rạc.

Bài tập 1.1.8 : Tìm phân hoạch của {1, 2, 3, 4, 5} thành ba tập hợp. Có phân hoạch {1, 2, 3, 4, 5} thành sáu tập hợp không?

A

1,2

3,4

1,4

2,5

3,5

Bài tập 1.1.9 : Thiết lập danh tính thứ nhất và thứ ba trong bốn danh tính sau. Sử dụng chiến lược sau: chỉ ra rằng phía bên trái là một tập hợp con của phía bên phải và ngược lại. Để chứng minh rằng A ⊂ B, hãy xem xét một phần tử s của A và – chỉ giả sử rằng

s ∈ A – áp dụng suy luận để kết luận rằng nó cũng phải thuộc B.

S ∩ (R ∪ T) = (S ∩ R) ∪ (S ∩ T)

S ∪ (R ∩ T) = (S ∪ R) ∩ (S ∪ T)

Giả sử chúng ta thực hiện một thí nghiệm bao gồm lật một đồng xu và lăn một viên xúc xắc sáu mặt tiêu chuẩn. Kết quả của lần lật đồng xu là một phần tử của tập S1 = {H, T} và kết quả của con súc sắc của tập hợp S2 = {1, 2, 3, 4, 5, 6}. Tập hợp tất cả các kết quả có thể có của thử nghiệm là tập hợp

S = {(H, 1),(H, 2),(H, 3),(H, 4),(H, 5),(H, 6), (T, 1),(T, 2),(T, 3),(T, 4),(T, 5),(T, 6)}

6. Định nghĩa Tích Descartes

Nếu S1 và S2 là tập hợp, thì tích Descartes của S1 và S2 được xác định bởi

S1 × S2 = {(s1,s2) : s1 ∈ S1 and s2 ∈ S2}

Nếu S1, S2, . . . , Sn là tập hợp

S1 × S2 × · · · × Sn = {(s1,s2, . . . ,sn) : s1 ∈ S1 and s2 ∈ S2 and · · · and sn ∈ Sn}.

Bài tập 1.1.10: Tìm |S x T| if |S| = 4 và |T| = 100

Lists

Tập hợp là vùng chứa dữ liệu có rất ít cấu trúc: bạn có thể kiểm tra tư cách thành viên (và thực hiện các thao tác liên quan đến kiểm tra tư cách thành viên như liên hiệp hoặc bổ sung), nhưng chỉ có vậy. Chúng tôi sẽ xác định nhiều loại bộ sưu tập khác cung cấp cấu trúc bổ sung.

Ví dụ: giả sử bạn quan tâm đến thứ tự các mặt hàng xuất hiện trong danh sách hàng tạp hóa của bạn; có lẽ bởi vì bạn muốn có thể chọn các mặt hàng theo một thứ tự nhất định khi bạn di chuyển qua cửa hàng. Ngoài ra, bạn có thể muốn liệt kê một mục nhiều lần như một cách nhắc nhở bản thân rằng bạn nên chọn nhiều hơn một món. Danh sách có thể xử lý cả hai yêu cầu bổ sung sau:

1. Định nghĩa 1.2.1:

Danh sách(list) Một danh sách là một tập hợp có thứ tự của rất nhiều phần tử.

Ví dụ: nếu chúng ta coi {1, 2, 3} và {2, 1, 3} là danh sách thì chúng không bằng nhau vì thứ tự mà các phần tử xuất hiện là khác nhau. Ngoài ra, danh sách {1, 1, 2} có ba phần tử, vì các phần tử lặp lại không được coi là thừa.

Chúng tôi không phân biệt tập hợp và danh sách về mặt lý thuyết, vì vậy chúng tôi sẽ dựa vào ngữ cảnh để làm rõ liệu thứ tự có quan trọng và số lần lặp lại có quan trọng hay không.

Bài tập 1.2.1:  Có bao nhiêu tập hợp A có tính chất A ⊂ {1, 2, 3}?  Có bao nhiêu danh sách có độ dài 4 có tất cả các phần tử của {1, 2, 3}?

{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

Functions

Danh sách hàng tạp hóa bạn tạo cho mình có thể không giống một tập hợp hoặc một danh sách, bởi vì cách nhanh nhất để chỉ ra số lượng mỗi mặt hàng cần mua là tạo một cột riêng biệt:

item	Count
ApplesBreadsquash	313

Ở đây chúng ta có hai tập hợp: tập hợp các mặt hàng tạp hóa và tập hợp các số nguyên dương. Đối với mỗi phần tử trong tập hợp trước, chúng tôi muốn kết hợp với nó một số phần tử của tập hợp sau.

Lưu ý rằng cấu trúc này không đối xứng trong hai tập hợp: mọi mặt hàng tạp hóa phải có chính xác một số được kết hợp với nó, trong khi một số số nguyên dương có thể bị bỏ qua và những số khác có thể được kết hợp với nhiều mặt hàng tạp hóa.

Ý tưởng gắn một phần dữ liệu vào mỗi phần tử của một tập hợp nảy sinh rất thường xuyên và nó xứng đáng với vốn từ vựng của riêng nó:

1. Định nghĩa :  Hàm, miền và miền đồng miền

Nếu A và B là các tập hợp, thì một hàm f: A → B là một phép gán cho mỗi phần tử của A thuộc một phần tử nào đó của B.

Tập A được gọi là miền của f và B được gọi là đồng miền của f.

Miền và miền đồng của một hàm nên được coi là một phần dữ liệu của hàm: để chỉ định đầy đủ f, chúng ta phải chỉ định (i) miền A, (ii) miền đồng B và (iii) giá trị của f (x ) với mỗi x ∈ A. Hai hàm f và g được coi là bằng nhau nếu (i) chúng có cùng miền và cùng miền và (ii) f (x) = g (x) với mọi x thuộc miền của f và g.

Cho một tập hợp con A 0 của A, chúng tôi xác định ảnh của f — ký hiệu là f (A 0) —để là tập hợp các phần tử được ánh xạ tới từ một phần tử nào đó trong A 0:

f(A 0 ) = {b ∈ B : tồn tại a ∈ A 0 so that f(a) = b}

Khoảng của f được xác định là ảnh thuộc miền của f. Do đó, phạm vi có thể nhận được từ tên miền bằng cách loại bỏ tất cả các phần tử không được ánh xạ tới.

Ví dụ 1.3.1:  Tìm phạm vi của hàm từ {apple, bread, squash} đến N được biểu thị bằng bảng sau.

item	Count
Apples,Bread,squash	3,1,3

Giải pháp:

Phạm vi là tập hợp số lượng được ánh xạ tới từ một số mặt hàng tạp hóa, vì vậy phạm vi là tập hợp hai phần tử {1, 3}.

Bài tập 1.3.1 Xét hàm số an sinh xã hội f từ tập các công dân và thường trú nhân Hoa Kỳ đến tập các số nguyên {000000000, 000000001 ,. . . , 999999999}. Đối với mỗi người x, f (x) được xác định là số an sinh xã hội của người x.

(i) Giá trị lớn nhất và nhỏ nhất có thể có của tỷ số này là bao nhiêu | f (A) | | A | cho bất kỳ tập con A thuộc miền của f?

(ii) Ước lượng tỷ số giữa bản số của khoảng f với bản số của miền đồng nguyên của f. (Bạn có thể ước tính số an sinh xã hội được cấp nhiều hơn dân số Hoa Kỳ hiện tại khoảng 40%).

2. Định nghĩa 1.3.2:  Nếu B 0 ⊂ B thì tiền thức f −1 (B 0) của B 0 được xác định bởi

= {a ∈ A: f (a) ∈ B 0}.

Đây là tập con của A bao gồm mọi phần tử của A ánh xạ tới một phần tử nào đó của.

3. Định nghĩa 1.3.3

Một hàm f là không xác định nếu không có hai phần tử trong miền ánh xạ với cùng một phần tử trong miền đồng; nói cách khác nếu f (a) = f () ngụ ý a = Một hàm f là hàm xạ ảnh nếu khoảng của f bằng miền đồng miền của f; nói cách khác, nếu b ∈ B thì tồn tại a ∈ A với f (a) = b.

Một hàm f là bijective nếu nó vừa là hàm vi phân vừa là hàm phụ. Điều này có nghĩa là với mọi b ∈ B, có đúng một a ∈ A sao cho f (a) ∈ b. Nếu f là nhị biến thì hàm từ B đến A ánh xạ b ∈ B tới phần tử a ∈ A thỏa mãn f (a) = b được gọi là nghịch biến của f.

Bài tập 1.3.3 Xác định từng chức năng sau đây là chức năng injective hay không injective, tính phụ thuộc hay không mang tính chất phụ thuộc, và bijective hay không bijective .

1. f : R → R, f(x) =

2. f : [0, ∞) → R, f(x) =

3. f : [0, ∞) → [0, ∞), f(x) =

4. f : R → [0, ∞), f(x) =

Thường sẽ hữu ích khi tập trung vào một tập con miền của một hàm mà không thay đổi các phần tử miền mà hàm liên kết với các phần tử miền đó. Ví dụ: nếu chúng tôi phân vùng danh sách hàng tạp hóa với số lượng giữa một số người mua sắm, thì mỗi người mua sắm sẽ quan tâm đến giới hạn của chức năng đếm số lượng đối với phần miền riêng của họ. Nói cách khác, họ cần biết số lượng mỗi mặt hàng của họ để chọn và họ không cần biết bất cứ điều gì về các mặt hàng của những người mua sắm khác.

3. Định nghĩa 1.3.4: Giới hạn Nếu f: A → B và A 0 ⊂ A, thì giới hạn của f đối với  là hàm  xác định bởi  với mọi x ∈

Bài tập 1.3.4:  Nêu mối quan hệ chung liên quan đến các thuật ngữ giới hạn, hình ảnh và phạm vi.

Đôi khi bản thân các phần tử do một hàm f xuất ra sẽ có dữ liệu được liên kết, và trong trường hợp này, chúng ta thường muốn kết nối từng phần tử trong miền của f với các dữ liệu này.

ví dụ, hãy xem xét chức năng album từ bộ bài hát đến bộ album. Được đánh giá trên một bài hát, chức năng album sẽ trả về album mà bài hát đó đã xuất hiện. Cũng xem xét hàm năm từ tập hợp các album đến tập hợp năm (trả về năm mà mỗi album được phát hành). Chúng ta có thể xác định năm phát hành bài hát bằng cách soạn hàm album và hàm năm

4. Định nghĩa 1.3.5: Hợp thành Nếu f: A → B và g: B → C, thì hàm g ◦ f ánh xạ x ∈ A thành g (f (x)) ∈ C được gọi là hợp của g và f.

Bài tập 1.3.5 Chứng tỏ rằng thành phần là liên kết: (f ◦ g) ◦ h = f ◦ (g ◦ h) cho tất cả các hàm f, g và h với đặc tính là miền đồng của h bằng miền của g và miền của g bằng miền của f.

Nếu quy tắc xác định một hàm đủ đơn giản, chúng ta có thể mô tả hàm bằng cách sử dụng ký hiệu hàm ẩn danh. Ví dụ, x ∈ R → ∈ R, hay viết tắt là x → , là hàm bình phương từ R đến R. Lưu ý rằng thanh ở cạnh trái của mũi tên, phân biệt mũi tên trong ký hiệu hàm ẩn danh từ mũi tên giữa tên miền và tên miền của một hàm được đặt tên.

Bài tập 1.3.6:  Giả sử f là hàm số (x 7 → ) ◦ (y → 3y). Tìm f()