Nieredukowalność do logiki pierwszego rzędu Istnieją pewne ograniczenia logiki pierwszego rzędu wynikające z twierdzenia Löwenheima-Skolema, które jednocześnie nie dotyczą logiki drugiego rzędu. Na przykład, za pomocą wyrażenia logiki pierwszego rzędu nie jest możliwe scharakteryzowanie relacji osiągalności pomiędzy wierzchołkami grafu skierowanego (relacja G), co staje się możliwe po dopuszczeniu kwantyfikatora nad relacjami binarnymi.
Dowód Przypuśćmy, że takie wyrażenie istnieje i nazwijmy je φ(x,y). Teraz rozważmy zdanie ψ:
ψ = ψ0 ∧ ψ1 ∧ ψ2
gdzie:
ψ0 = ∀x∀yφ ψ1 = ∀x∃yG(x,y) ∧ ∀x∀y∀z((G(x,y) ∧ G(x,z)) ⇒ y = z) ψ2 = ∀x∃yG(y,x) ∧ ∀x∀y∀z((G(y,x) ∧ G(z,x)) ⇒ y = z)
Zdanie ψ0 mówi, że graf G jest silnie spójny tzn. dla każdej pary wierzchołków x i y istnieje ścieżka prowadząca od wierzchołka x do wierzchołka y, zdanie ψ1 mówi, że stopień wyjściowy każdego wierzchołka grafu G jest równy 1, zdanie ψ2 mówi, że stopień wejściowy każdego wierzchołka grafu G jest równy 1. Graf G spełniający koniunkcje tych trzech zdań (ψ) nazywany jest cyklem.