Czy teoria pierwszego rzędu struktury skończonej ograniczyła rangę kwantyfikatora?

Niech będzie dowolną skończoną strukturą. Czy jego teoria pierwszego rzędu ograniczyła rangę kwantyfikatora w tym sensie, że istnieje taki, że dla wszystkich z jest z i ? $\mathfrak{A}$ $\mathfrak{T} := \mathfrak{TH}(\mathfrak{A})$ $q\in\mathbb{N}$ $\varphi\in\mathfrak{T}$ $qr(\varphi) > q$ $\varphi'\in\mathfrak{T}$ $qr(\varphi')\leq q$ $\varphi'\equiv\varphi$

co.combinatorics lo.logic relational-structures D. Rusin
źródło

Czy to nie pytanie dotyczy Mathoverflow, a nie teorii CS?

Andrej Bauer

@Andrej, teoria modeli skończonych i złożoność opisowa są również uważane za część TCS.

Kaveh

Doskonale, więc to tak, jak powiedział kiedyś Bob Harper: matematyka jest szczególnym przypadkiem informatyki.

Andrej Bauer,

Informatyka jest także szczególnym przypadkiem matematyki, a oba są szczególnymi przypadkami logiki i odwrotnie.

fhyve

Odpowiedzi:

Teoria dowolnej skończonej struktury jest kompletna z modelem. W rzeczywistości łatwo zauważyć, że każda formuła jest równoważna formule egzystencjalnej z jednym kwantyfikatorem na każdy element struktury, po czym wszystkie kwantyfikatory oryginalnej formuły można symulować za pomocą spójników i rozłączeń. W szczególności liczba kwantyfikatorów (stąd ranga kwantyfikatora) jest ograniczona rozmiarem struktury.

Emil Jeřábek
źródło

W rzeczywistości potrzebny jest jeden dodatkowy uniwersalny kwantyfikator, który pozwala wyrazić brak dalszych elementów. We wszystkich odpowiedziach należy jednoznacznie założyć: obecność równości, tzn. Że x = y jest dozwoloną formułą atomową.

Thomas S

Nie jest potrzebny żaden dodatkowy kwantyfikator. Pamiętaj, że nie próbujemy aksjatyzować teorii struktury, ale znaleźć formułę równoważną danemu modułowi teorii. A obecność równości jest uniwersalnym standardem dla klasycznej logiki pierwszego rzędu. Trzeba byłoby stwierdzić jego brak .

Emil Jeřábek

Ach Masz rację. „Teoria modulo”. Jeśli chodzi o równość: gdy staramy się wyjaśnić łatwe rzeczy ludziom spoza Logiki, wyraźne określenie ram nie jest bolesne. Jeszcze jedna uwaga: zastąpienie kwantyfikatorów koniunkcjami i rozłączeniami jest całkowicie dobre. Istnieją jednak alternatywy: ponieważ formuła z, powiedzmy, m zmiennymi swobodnymi definiuje relację m-ary A, nowa formuła może, po odgadnięciu wszystkich elementów i sprawdzeniu, który jest (modulo automorfizm), również jawnie „wyliczyć” wszystkie krotki, dla których stara formuła daje „prawdziwą”.

Thomas S

Aby uczynić to, co powiedział Emil, nieco bardziej konkretnym: rozważ formułę wyrażającą istnienie k różnych obiektów. To pokazuje, że potrzebujemy nieograniczonej liczby kwantyfikatorów.

Teraz masz formułę z kwantyfikatorami q, a twój model zawiera k obiektów, możesz wyrazić formułę, stwierdzając, że istnieje k różnych obiektów, a relację między nimi można wyrazić jako CNF.

Kaveh
źródło