Dobře-tvořil objectsEdit

kolekce objektů (symbolů a symbol-sekvence) je třeba považovat za „dobře-tvořil“, algoritmus musí existovat pro určení, zastavení s „ano“ nebo „ne“ odpověď, zda je či není objekt je dobře-tvořil (v matematice a wff, abbreviates dobře-tvořil vzorec). Tento algoritmus, v krajním případě, může vyžadovat (nebo být) Turingův stroj nebo Turingův ekvivalentní stroj, který „analyzuje“ řetězec symbolů tak, jak je prezentován jako „data“ na jeho pásce; předtím, než univerzální Turingův stroj může provést instrukci na své pásce, musí analyzovat symboly, aby určil přesnou povahu instrukce a / nebo datum kódované tam. V jednodušších případech konečný stav stroj nebo pushdown automat může dělat svou práci. Enderton popisuje použití „stromů“ k určení, zda je logický vzorec (zejména řetězec symbolů se závorkami) dobře vytvořen. Kostel Alonzo 1934 popisuje stavbu „vzorců“ (opět: sekvence symbolů), jak je napsáno v jeho λ-kalkulu pomocí rekurzivního popisu toho, jak začít vzorec a pak stavět na počátečním symbolu pomocí zřetězení a substituce.

příklad: Church specifikoval svůj λ-kalkul následovně (následuje zjednodušená verze vynechávající pojmy volné a vázané proměnné). Tento příklad ukazuje, jak objekt, teorie začíná specifikaci objektu systém symbolů a vztahů (zejména pomocí zřetězení symbolů):

(1) Prohlásí symbolů: {, }, (, ), λ, plus nekonečné množství proměnných a, b, c, …, x, … (2) Definujte vzorec: posloupnost symbolů (3)definuje pojem“ dobře formovaný vzorec „(wff) rekurzivně počínaje „základem“ (3.i):

• (3.1) (basis) proměnná x je wff
• (3.2) pokud F A X jsou WFF, pak {F}(X) je wff; pokud se x vyskytuje ve F nebo X, pak se říká, že je proměnná v {F}(X).
• (3.3) pokud je M dobře tvarováno a x se vyskytuje v M, pak λx je wff.

(4) Definujte různé zkratky:

• {F} abbreviates k F(X), pokud F je jeden symbol
• F {\displaystyle {{F}}}
  

  abbreviates {F}(X,Y) nebo F(X,Y), jestliže F je jeden symbol

• λx1λx2…] zkracuje na λx1x2…xn * M
• λab * a (b) zkracuje na 1
• λab•a(a (b)) zkracuje na 2 atd.

(5) Definovat pojem „náhrada“ vzorce N proměnné x po M (Kostel 1936)

Nedefinovaný (primitivní) objectsEdit

Některé objekty mohou být „nedefinované“ nebo „primitivní“ a získat definice (ve smyslu jejich chování) zavedení axiomů.

V dalším příkladu budou nedefinované symboly { ※ ,ↀ,}}. Axiomy budou popisovat jejich chování.

AxiomsEdit

Kleene poznamenává, že axiomy se skládají ze dvou sad symbolů: (i) nedefinovaných nebo primitivních objektů a těch, které jsou dříve známé. V následujícím příkladu, je již dříve známo, že v následující systém ( O, ※, ↀ, ∫ ) O představuje soubor objektů („domény“), ※ je objekt v doméně, ↀ a ∫ jsou symboly pro vztahy mezi objekty, => označuje „JESTLI PAK“ logický operátor, ε je symbol, který označuje „je prvkem množiny O“, a „n“ bude použito pro označení libovolný prvek množiny z objektů O.

Po (i) definici „řetězec S“—objekt, který je symbolem ※ nebo spojeny symboly ※, ↀ nebo ∫ a (ii) definice „dobře-tvořil“ nitky … (základ) ※ a ↀS, ∫S, kde S je libovolný řetězec, pojď axiomy:

• ↀ※ => ※, slovy: „POKUD ↀ je aplikován na objekt ※ PAK objekt ※ výsledky.“
• ∫n ε O, slovy „pokud ∫ je aplikován na libovolný objekt“ n „v O, pak tento objekt ∫n je prvek O“.
• ↀn ε O, „pokud ↀ je aplikován na libovolný objekt“ n „v O, pak tento objekt ↀn je prvek O“.
• n n = > n, „pokud ↀ je aplikován na objekt ∫ n pak objekt n výsledky.“
• ∫ ↀn = > n, „Je-li ∫ aplikován na objekt ↀn, pak objekt n výsledky.“

jaká by tedy mohla být (zamýšlená) interpretace těchto symbolů, definic a axiomů?

Pokud definujeme ※ jako „0“, ∫ jako „nástupce“, a ↀ jako „předchůdce“ pak ↀ ※ => ※ indikuje „správné odčítání“ (někdy označeny symbolem ∸, kde „předchůdce“ odečte jednotka z řady, tedy 0 ∸1 = 0). Řetězec “ ↀ∫n => n “ znamená, že pokud první nástupce je aplikovat na libovolný objekt n a pak předchůdce ↀ je aplikován na ∫n původní n výsledky.“

je tato sada axiomů „adekvátní“? Správnou odpovědí by byla otázka: „adekvátní k popisu toho, co konkrétně?““Axiomy určují, na které systémy, definované zvenčí teorie, se teorie vztahuje.“(Kleene 1952: 27). Jinými slovy, axiomy mohou být dostatečné pro jeden systém, ale ne pro jiný.

Ve skutečnosti, to je snadné vidět, že tento axiom set není velmi dobrý—ve skutečnosti, to je v rozporu (to znamená, že výnosy nekonzistentní výsledky, bez ohledu na to, co jeho výklad):

Příklad: Definovat ※ jako 0, ∫※ jako 1, a ↀ1 = 0. Od prvního axiomu,※ ※ = 0, takže ※ ※ = 0 0 = 1. Ale poslední axiom udává, že pro libovolné n včetně ※ = 0, ∫ↀn => n, takže tento axiom stanoví, že ∫ↀ0 => 0, ne 1.

Všimněte si také, že sada axiomů neurčuje, že ∫n n n. Nebo, s výjimkou případu n = ※, ↀn ≠ n. Pokud bychom měli zahrnout tyto dva axiomy, musíme popsat intuitivní pojmy „rovná se“ symbolizované = a ne-rovná symbolizované ≠.