>>487のつづき

二階論理の表現能力
https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%9A%8E%E8%BF%B0%E8%AA%9E%E8%AB%96%E7%90%86#%E4%BA%8C%E9%9A%8E%E8%AB%96%E7%90%86%E3%81%AE%E8%A1%A8%E7%8F%BE%E8%83%BD%E5%8A%9B

二階述語論理は一階述語論理よりも表現能力が高い。
例えば、ドメインが全ての実数の集合としたとき、一階述語論理を使って
「それぞれの実数には加法の逆元が存在する」ということを
∀x ∃y (x + y = 0) と表せる。
しかし、「空でなく上に有界な実数の集合があるとき常にその集合には上限が存在する」という命題を表すには、二階述語論理が必要となる。
ドメインが全ての実数の集合としたとき、次の二階の論理式がこの命題を表している。

∀A[(∃w(w∈A)∧∃z∀w(w∈A→w≤z))→∃x∀y([∀w(w∈A→w≤y)]↔x≤y)].

二階述語論理では、「ドメインは有限である」とか「ドメインは可算無限集合の濃度である」といった文も形式的に表現可能である。
ドメインが有限であるというには、そのドメインから同じドメインへの全ての単射関数が全射であることを論理式で表せばよい。
ドメインが可算無限集合の濃度であることをいうには、そのドメインの任意のふたつの無限部分集合間に全単射があることを論理式で表せばよい。

一階述語論理ではこれら（「有限集合であること」や、「可算集合であること」）を表現できないことが、レーヴェンハイム-スコーレムの定理から導かれる。