Quy Nap

Phép quy nạp Từ C*=C* để cho tiện ta gọi tập là C. Chúng ta còn gọi C là tập được sinh ra từ B bởi F Bây giờ, với 1 định nghĩa bất kỳ (theo tớ là 1 trong 2 định nghĩa top-down và bottom-up) chúng ta có thể chứng minh nhiều bài toán về tập hợp, sử dụng nguyên lý sau đây. Nguyên lý quy nạp Nếu C là tập được sinh ra từ B bởi F và S là một tập chứa B và đóng dưới F (S là tập quy nạp được) thì CS. Chứng minh Từ S là tập quy nạp được, và C=C* là giao của tất cả các tập quy nạp được, nó kéo theo CS Giờ chúng ta có thể chỉ ra rằng quy nạp toán học là 1 trường hợp đặc biệt của nguyên lý quy nạp. 21 Phép quy nạp Ví dụ Lại xét đến tập số tự nhiên được định nghĩa quy nạp như sau:  U = R, với R là tập số thực  B={0}  F={succ}, với succ(x)=x+1 Ta có N là tập được sinh ra từ B bỏi F i=n

Gọi S là tập tất cả các số thực n sao cho

 i = n(n+1) 2

i=0

Chúng ta đã chứng minh trước đó rằng 0S và nếu kS thì k+1S (nói cách khác S là tập quy nạp được) Vậy thì, theo nguyên lý quy nạp, NS i=n

Như vậy

 i = n(n+1) với mọi số tự nhiên nN 2

i=0

Logic mệnh đề: biểu thức dạng đúng

22

Chúng ta có thể dùng định nghĩa quy nạp để định nghĩa tập W các biểu thức dạng đúng (well-formed fomulas - wff ) của logic mệnh đề  U = tập tất cả các biểu thức có thể xây đựng được  B = tập các biểu thức chỉ bao gồm 1 ký hiệu mệnh đề đơn  F = tập các toán tử o o o o o

-() = (-) ^(,) = ( ^) v(,) = (v) (,) = () (,) = ()

23

Logic mệnh đề: biểu thức dạng đúng Với định nghĩa biểu thức dạng đúng mà chúng ta đã đưa ra, chúng ta có thể sử dụng nguyên lý quy nạp để chứng minh những phát biểu khác về tập W Ví dụ Chứng minh rằng mọi wff đều có số ngoặc trái và số ngoặc phải bằng nhau Chứng minh Gọi l() là số ngoặc trái và r() là số ngoặc phải trong biểu thức , gọi S là tập các biểu thức  sao cho l() = r(). Ta cần chứng minh WS. Điều này có thể suy ra từ nguyên lý quy nạp, nếu chúng ta chỉ ra rằng S là tập quy nạp được. Trường hợp cơ sở Chúng ta phải chỉ ra BS, nhắc lại rằng B là tập các biểu thức chỉ bao gồm 1 ký hiệu mệnh đề đơn, hiển nhiên là với các biểu thức thuộc B: l() = r() = 0 24