Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng : Logic part 6

Trang 26: Compactness Cho Σ là tập thoả mãn được hữu hạn. Ta mở rộng Σ thành tập ∆ thoả mãn được lớn nhất như sau: Cho α1, , αn, là một tập cố định danh sách tất cả các công thức xây dựng đúng. Tại sao có thể? Tập tất cả các dãy của một tập đếm được là đếm được. T Không khó để chứng minh rằng mọi ∆n là thoả mãn được hữu hạn (bài tập về nhà). Cho ∆ =∪n∆n. Rõ ràng rằng: 1.Σ⊂ ∆ 2.α∈∆ hoặc αn với mọi wff α và 3.∆ là thoả. | Trang 26 Compactness Cho 1 là tập thoả mãn được hữu hạn. Ta mở rộng 1 thành tập A thoả mãn được lớn nhất như sau Cho ƠI . an . là một tập cố định danh sách tất cả các công thức xây dựng đúng. Tại sao có thể Tập tất cả các dãy của một tập đếm được là đếm được. Thì cho A0 1 An 1 An u ơn 1 AnU . ơn 1 Nếu tập này là thoả mãn được Ngược lại Không khó để chứng minh rằng mọi An là thoả mãn được hữu hạn bài tập về nhà . Cho A u nAn. Rõ ràng rằng 1.1c A 2. ar A hoặc an với mọi wff a và 3. A là thoả mãn được hữu hạn. 66 Trang 27 Compactness Bây giờ ta chứng minh rằng A là thoả mãn được và vậy nên 1 c A cũng là thoả mãn được . Xác định một phép gán v như sau. Với mỗi kí hiệu mệnh đề Ai v Ai 1 khi và chỉ khi Ap A Ta khẳng định rằng mọi công thức wff a v thoả mãn a khi và chỉ khi ar A. Ta chứng minh bằng quy nạp trên các công thức xây dựng đúng. Trường hợp cơ sở Dan đến từ định nghĩa của v. Trường hợp quy nạp Ta sẽ xem xét một trường hợp. Giả sử a p Ay. Thì V a 1 khi và chỉ khi cả hai V P 1 và V y 1 khi và chỉ khi pr Avà Yr A. Bây giờ nếu cả hai p và y thuộc A thì từ P y a là không thoả mãn được ta phải có a EA. Tương tự nếu một trong hai p và y không thuộc A thì phủ định của nó phải thuộc A nên aỂA. 67 Trang 28 Compactness Hệ quả Nếu Z a thì có một tập hữu hạn I0d để Z a. Chứng minh Giả sử rằng Z avới mọi tập hữu hạn I0d. Thì Z0 u a là thoả mãn được với mọi I0d. Nên theo định lí compactness z u a là thoả mãn được trái với giả thiết z a. .