tailieunhanh - Bài giảng : Logic part 2

Trang 14: quy nạp Quy nạp toán học là một trường hợp đặc biệt của một nguyên lí tổng quat hơn. Trường hợp tổng quát, khi một tập được xác định một cách quy nạp, quy nạp có thể được sử dụng để chứng minh những vấn đề về những phần tử của tập đó. Định nghĩa quy nạp là cái gì? | Trang 14 quy nạp Quy nạp toán học là một trường hợp đặc biệt của một nguyên lí tổng quat hơn. Trường hợp tổng quát khi một tập được xác định một cách quy nạp quy nạp có thể được sử dụng để chứng minh những vấn đề về những phần tử của tập đó. Định nghĩa quy nạp là cái gì 14 Trang 15 quy nạp Cho U là tập vũ trụ nào đó và giả sử chúng ta muốn xác định tập con C nào đó của tập U theo quy nạp. Việc này có thể được làm như sau B là tập con khởi đầu của U F là một họ các hàm trên U Một cách tự nhiên B là trường hợp cơ sở cho định nghĩa quy nạp của chúng ta. Những phần tử thuộc tập này là những phần tử để chúng ta bắt đầu với tập F miêu tả cách để đạt được những phần tử mới từ những phần tử cũ. Tập C là tập của tất cả các phần tử hoặc là thuộc B hoặc có thể đạt được từ B sử dụng những hàm trong F. Ví dụ Những số tự nhiên N có thể xác định như sau Cho U là tập tất cả các số thực B 0 và F succ với succ là hàm phần tử tiếp theo xác định succ x x 1. 15 Trang 16 quy nạp Định nghĩa quy nạp tổng quát U là một tập vũ trụ B là một tập con khởi đầu của U F là một họ các hàm trên U Làm thế nào chúng ta sử dụng các giả thiết này để đạt được tập C đề ra Chúng ta có thể xác định tập C là phiên bản top-down của tập C như sau Một tập S là đóng dưới họ hàm F khi và chỉ khi với mỗi f EF nếu x1 _ xn S và f x1 _ xn y với yr U thì yr S. Một tập S là quy nạp được nếu B S và S là đóng dưới họ hàm F. Tập C được xác định như là giao của tất cả các tập con quy nạp được của U. Tập này là top-down vì ta lấy những thứ rất lớn những tập quy nạp được và sử dụng giao của chúng để cấu trúc nên tập cần tìm. .