Logic vị từ

$\forall x\, P(x)$ có nghĩa "dù thay $x$ bằng gì, $P$ vẫn đúng" — nên thay bằng một hạng tử cụ thể $t$ thì $P(t)$ vẫn phải đúng. Đây là quy tắc biến luật tổng quát thành trường hợp cụ thể: từ "$\forall x\, (\text{Human}(x) \to \text{Mortal}(x))$" ta thay thế tại $t = \text{Socrates}$ để được "$\text{Human}(\text{Socrates}) \to \text{Mortal}(\text{Socrates})$", tiền đề đầu của tam đoạn luận cổ điển.

Ta lập luận trực tiếp từ ngữ nghĩa thỏa mãn Tarski, định nghĩa tính đúng trong một cấu trúc theo đệ quy trên cấu trúc công thức.

Theo mệnh đề ngữ nghĩa cho $\forall$: $\mathcal{M} \models_s \forall x\, P(x) \iff \text{for every } d \in M,\ \mathcal{M} \models_{s[x \mapsto d]} P(x)$. Giả sử giả thiết $\mathcal{M} \models_s \forall x\, P(x)$; theo mệnh đề này, $\mathcal{M} \models_{s[x \mapsto d]} P(x)$ đúng với mọi $d \in M$, không ngoại lệ.

Vì khẳng định đúng với mọi $d \in M$, nó đúng đặc biệt với $d = t^{\mathcal{M},s}$, phần tử mà hạng tử $t$ biểu thị trong $\mathcal{M}$ dưới $s$. Thay $d$ cụ thể này cho ta $\mathcal{M} \models_{s[x \mapsto t^{\mathcal{M},s}]} P(x)$.

Theo Bổ đề Thay thế (một kết quả chuẩn liên hệ phép gán biến với phép thay thế hạng tử, chứng minh được bằng quy nạp theo cấu trúc của $P$): $\mathcal{M} \models_{s[x \mapsto t^{\mathcal{M},s}]} P(x) \iff \mathcal{M} \models_s P(t)$, đúng chính xác vì $t$ thay thế được cho $x$ trong $P(x)$ (không biến tự do nào của $t$ bị buộc ngoài ý muốn). Áp dụng bổ đề biến $\mathcal{M} \models_{s[x \mapsto t^{\mathcal{M},s}]} P(x)$ thành $\mathcal{M} \models_s P(t)$.

Vì $\mathcal{M}$, $s$, $t$ tùy ý, nên suy luận từ $\forall x\, P(x)$ tới $P(t)$ bảo toàn tính đúng trong mọi cấu trúc dưới mọi phép gán: quy tắc là đúng đắn.

$\exists y\, \forall x\, R(x,y)$ đòi hỏi một nhân chứng $y$ duy nhất dùng được cho mọi $x$ (nhân chứng "cố định"), còn $\forall x\, \exists y\, R(x,y)$ chỉ đòi hỏi mỗi $x$ có một nhân chứng nào đó, có thể khác nhau với mỗi $x$ (nhân chứng "di động"). Một nhân chứng cố định tự động là nhân chứng di động (dùng lại nó), nhưng chiều ngược lại thì không — đây chính là khác biệt giữa "có người yêu tất cả mọi người" (một người yêu duy nhất) và "ai cũng được ai đó yêu" (có thể khác người mỗi lần), một nguồn mơ hồ kinh điển trong ngôn ngữ tự nhiên mà logic vị từ làm rõ.

Chiều thuận. Giả sử $\mathcal{M} \models_s \exists y\, \forall x\, R(x,y)$. Theo mệnh đề ngữ nghĩa cho $\exists$, $\mathcal{M} \models_s \exists y\, \varphi \iff \text{there is } d \in M \text{ with } \mathcal{M} \models_{s[y \mapsto d]} \varphi$; áp dụng ở đây cho ta một $d_0 \in M$ với $\mathcal{M} \models_{s[y \mapsto d_0]} \forall x\, R(x,y)$.

Áp dụng mệnh đề cho $\forall$ vào điều này, $\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y)$ đúng với mọi $a \in M$, vì $\forall x$ chạy khắp $M$ bất kể sau này ta chọn $a$ nào.

Bây giờ cố định một $a \in M$ tùy ý để kiểm chứng $\forall x\, \exists y\, R(x,y)$. Từ đoạn trên, lấy $x \mapsto a$ cho $\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y)$, cho thấy chính $d_0$ là nhân chứng cho $\exists y\, R(x,y)$ dưới $x \mapsto a$; do đó $\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y)$.

Vì $a \in M$ tùy ý, $\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y)$ đúng với mọi $a$, đó chính xác là mệnh đề ngữ nghĩa cho $\mathcal{M} \models_s \forall x\, \exists y\, R(x,y)$. Điều này chứng minh $\exists y\, \forall x\, R(x,y) \Rightarrow \forall x\, \exists y\, R(x,y)$.

Chiều đảo không đúng: một phản ví dụ. Cho $\mathcal{M}$ có miền $M = \mathbb{Z}$ (số nguyên) và diễn giải $R(x,y)$ là "$x < y$". Khi đó $\forall x\, \exists y\, R(x,y)$ ĐÚNG: với mọi số nguyên $x$, lấy $y = x+1$ cho $x < y$. Nhưng $\exists y\, \forall x\, R(x,y)$ SAI: nó đòi hỏi một số nguyên $y$ duy nhất lớn hơn mọi số nguyên $x$, và không tồn tại số nguyên lớn nhất như vậy (với bất kỳ $y$ ứng viên nào, số nguyên $y+1$ vi phạm $y+1 < y$). Vậy $\forall x\, \exists y\, R(x,y)$ đúng trong khi $\exists y\, \forall x\, R(x,y)$ sai, cho thấy mệnh đề đảo nói chung là sai.