hyvin muodostuneita olioita

Jos olioiden (symbolien ja symbolisekvenssien) kokoelmaa on pidettävä ”hyvin muodostuneena”, täytyy olla olemassa algoritmi, joka pysäyttää ”kyllä”-tai ”ei”-vastauksella, onko olio hyvin muodostettu vai ei (matematiikassa wff lyhentää hyvin muodostunutta kaavaa). Äärimmillään tämä algoritmi saattaa vaatia (tai olla) Turingin koneen tai Turingin vastaavan koneen, joka” jäsentää ”symbolijonon sellaisena kuin se esitetään” datana ” nauhallaan; ennen kuin universaali Turingin kone voi suorittaa käskyn nauhallaan, sen täytyy jäsentää symbolit määrittääkseen käskyn ja/tai siihen koodatun datumin tarkan luonteen. Yksinkertaisemmissa tapauksissa äärellinen valtion kone tai pushdown automaatti voi tehdä työtä. Enderton kuvaa ”puiden” käyttöä sen määrittämiseksi, onko jokin logiikkakaava (erityisesti sulkeilla varustettu symbolijono) hyvin muodostettu. Alonzo Church 1934 kuvaa rakentamista ”kaavat” (jälleen: sequences of symbols), joka on kirjoitettu hänen λ-calculus käyttämällä rekursiivinen kuvaus siitä, miten aloittaa kaava ja sitten rakentaa alkaa-symboli käyttäen concatenation ja korvaaminen.

esimerkki: Church määritteli λ-calculuksensa seuraavasti (seuraava on yksinkertaistettu versio jättäen pois käsitteet vapaa – ja sidottu-muuttuja). Tämä esimerkki osoittaa, miten olioteoria alkaa symbolien ja suhteiden objektijärjestelmän määrittelyllä (erityisesti käyttämällä symbolien yhtymäkohtia):

(1) julistetaan symbolit: {,}, (,), λ sekä ääretön määrä muuttujia a, b, c, …, x, … (2) Määrittele kaava: symbolijono (3) Määrittele käsite ”hyvin muodostettu kaava” (wff) rekursiivisesti alkaen ”perusta” (3.i):

• (3.1) (basis) muuttuja x on wff
• (3.2) jos F ja X ovat WFF, niin {F}(X) on wff; jos x esiintyy F: ssä tai X: ssä, sen sanotaan olevan muuttuja {F}(X): ssä.
• (3.3) jos M on hyvin muodostunut ja x esiintyy M: ssä, λx on wff.

(4) Määrittele erilaisia lyhenteitä:

• {F} lyhentää muotoon F (X), Jos F on yksittäinen symboli
• F {\displaystyle {{F}}}
  

  lyhentää muotoon {F}(X,Y) tai F(X, Y), jos F on yksittäinen symboli

• λx1λx2…] lyhentää λx1x2…xn * m
• λab•a(b) lyhentää muotoon 1
• λab•a(A(b)) lyhentää muotoon 2 jne.

(5) Määrittele käsitteen ”substituutio” muuttujalle n koko M (Church 1936)

määrittelemättömät (primitiiviset) objektit

tietyt objektit voivat olla ”määrittelemättömiä” tai ”primitiivisiä” ja saada määritelmän (käyttäytymisensä ehdoilla) aksioomien käyttöönoton kautta.

seuraavassa esimerkissä määrittelemättömät symbolit ovat { ※ ,∫,∫}. Aksioomat kuvaavat heidän käyttäytymistään.

aksioomat

Kleene huomauttaa, että aksioomat koostuvat kahdesta symbolijoukosta: i) määrittelemättömistä eli primitiivisistä olioista ja niistä, jotka ovat aiemmin tunnettuja. Seuraavassa esimerkissä on aiemmin tunnettu seuraavassa järjestelmässä (O,※,∫,∫), että O muodostaa joukon objekteja (”domain”), ※ on objektin objekti, ∫ ja ∫ ovat symboleita objektien välisille suhteille, => tarkoittaa” jos sitten ”loogista operaattoria, ε on symboli, joka ilmaisee” on joukon O elementti”, ja” n ” käytetään osoittamaan mielivaltaista elementtiä joukko-objektien O.

jälkeen (I) määritelmä ”string S”—objekti, joka on symboli ※ tai tiivistetyt symbolit※, ↀ tai∫, ja (ii) määritelmä ”hyvin muodostetuille” kielille — (basis) ※ ja ∫S, ∫S missä S On mikä tahansa merkkijono, tulevat aksioomat:

• ※ ※ =>※, sanoin: ”jos ↀ sovelletaan objekti ※ sitten objekti ※ tulokset.”
• ∫n ε O, sanoin ”jos ∫ sovelletaan mielivaltaiseen objektiin ”n” O: ssa, tämä objekti ∫n on O: n elementti”.
• ↀn ε O, ”jos ↀ käytetään mielivaltaiselle objektille ”n” O: ssa, niin tämä objekti ↀn on O: n elementti”.
• ∫∫n => n, ”jos ↀ sovelletaan objektiin ∫ n, niin objekti n johtaa.”
• ∫∫n => n, ”jos ∫ sovelletaan objektiin ↀn, niin objektin n tulokset.”

mikä siis voisi olla näiden symbolien, määritelmien ja aksioomien (tarkoitettu) tulkinta?

jos määrittelemme ※ on ”0”, ∫ ”seuraaja” ja ↀ ”edeltäjä”, niin※ ※ => ※ tarkoittaa ”oikeaa vähennyslaskua” (joskus merkitään symbolilla ∸, jossa ”edeltäjä” vähentää yksikön luvusta, jolloin 0 ∸1 = 0). Merkkijono ” ∫∫n => n ” osoittaa, että jos seuraajaa sovelletaan ensin mielivaltaiseen kohteeseen n ja sitten edeltäjää ∫ sovelletaan ∫ n, saadaan alkuperäinen n tulos.”

Onko tämä aksioomajoukko ”riittävä”? Oikea vastaus olisi kysymys: ”riittävä kuvaamaan erityisesti mitä?””Aksioomat määräävät, mihin systeemeihin, jotka on määritelty teorian ulkopuolelta, teoria pätee.”(Kleene 1952: 27). Toisin sanoen aksioomat voivat riittää yhdelle järjestelmälle, mutta eivät toiselle.

itse asiassa on helppo nähdä, että tämä aksioomajoukko ei ole kovin hyvä—itse asiassa se on epäjohdonmukainen (toisin sanoen se tuottaa epäjohdonmukaisia tuloksia riippumatta siitä, mikä sen tulkinta on):

esimerkki: määritä ※ as 0, ∫ ※ as 1 ja ↀ1 = 0. Ensimmäisestä aksioomasta lähtien※ ※ = 0, joten ∫ ∫ ※ = ∫0 = 1. Mutta viimeinen aksiooma määrittää, että mille tahansa mielivaltaiselle n: lle, mukaan lukien ※ = 0, ∫∫n => n, joten tämä aksiooma määrää, että ∫∫0 => 0, ei 1.

Huomaa myös, että aksioomajoukko ei määritä, että ∫n ≠ n. Tai, lukuun ottamatta tapausta n = ※, ↀn ≠ n.jos sisällyttäisimme nämä kaksi aksioomaa, meidän olisi kuvattava intuitiiviset käsitteet ”yhtä suuri” symbolisoitu = ja ei-yhtä suuri symbolisoitu≠.