On a problem of formal logic – Parte III di The Foundation of Mathematics di Frank Ramsey

23 Mag

Schermata 44Propongo la mia traduzione della terza parte delle opere pubblicate di Frank Plumpton Ramsey  raccolte da R. B. Braithwaite sotto il titolo The Foundation of Mathematics.

Questa sezione riguarda la possibilità di trovare una procedura per determinare la verità o la falsità di una qualsiasi formula logica. Non intendo mettere l’accento sulle conseguenze virtuose nell’uso di questa metodologia, ma preferisco sotolineare l’originalità ed il rigore scientifico di questo lavoro se avrete cura di leggere attentamente i procedimenti logici impiegati in larghissima misura originali.

III

Su un problema di logica formale (1928)

Questo documento riguarda principalmente un caso particolare di uno dei problemi principali della logica matematica, il problema di trovare una procedura fissa per determinare la verità o falsità di una determinata formula logica. 1 Ma nel corso di questa indagine , è necessario utilizzare alcuni teoremi sulle combinazioni che hanno un interesse indipendente e sono più opportunamente posti per sé stessi nella parte iniziale.

I

I teoremi che effettivamente ci necessitano riguardano solo le classi finite, ma cominceremo con un teorema simile sulle classi infinite che è più facile da dimostrare e dà un semplice esempio del metodo della discussione.

TEOREMA A. Sia Γ una classe infinita, e μ e r siano degli interi positivi; e posto che tutte quelle sotto – classi di Γ che hanno esattamente r membri, o, come potremmo dire, posto che che tutte le r- combinazioni dei membri di Γ siano suddivisi in qualche modo in μ classi mutuamente esclusive Ci ( i = 1 , 2 , … , μ ), in modo che ogni r- combinazione sia un membro di una e una sola Ci; allora, assumendo l’Assioma delle Selezioni, Γ deve contenere una sottoclasse infinita Δ tale che tutte le r- combinazioni dei membri di Δ appartengono alla stessa Ci.

Consideriamo prima il caso μ = 2. (Se μ = 1 non vi è nulla da dimostrare.) Il teorema è banale quando r è 1, e lo dimostriamo per ogni valore di r per induzione. Supponiamo che, quindi, quando r = ρ -1 e lo deduciamo per r = ρ, che vi siano, dal momento che μ = 2 , solo due classi Ci , cioè C1 e C2.

1 Chiamato in tedesco Entscheidungsproblem ; vedi Hilbert und Ackermann , Grundzüge der Theoretischen Logik, pp 72-81.

Può accadere che Γ contenga un x1 membro e una sotto – classe infinita Γ1, non comprendente x1, tale che le ρ combinazioni, comprensive di x1 insieme a un qualsiasi ρ – 1 membri di Γ1, appartengano tutte a C1. Se è così, Γ1 può parimenti contenere un membro x2 e una sotto- classe infinita Γ2, non comprendente x2, tale che tutte le ρ combinazioni, comprensive di x2 insieme con i membri ρ -1 di Γ2, appartengano a C1. E, ancora, Γ2 può contenere un x3 e un Γ3 con proprietà simili, e così via all’infinito.

Abbiamo così due possibilità: o siamo in grado di selezionare in questo modo due sequenze infinite di membri di Γ (x1 , x2 , … , xn , … ), e di infinite sottoclassi di Γ ( Γ1 , Γ2 , . .. , Γn , … ) , in cui xn è sempre un membro di Γn – 1, e Γn una sotto- classe di Γn – 1 che non include xn , tale che tutti le ρ- combinazioni , comprensive di xn insieme ai ρ – 1 membri di Γn, appartengano a C1; altrimenti il ​​processo di selezione cadrebbe a un certo stadio, diciamo all’n -esimo, perché Γn – 1 (o se n = 1 , Γ stesso) non conterrà nessun membro xn e la sub – classe infinita Γn non comprendente xn così che tutte le ρ combinazioni, comprensive di xn insieme ai ρ – 1 membri di Γn appartengano a C1. Prendiamo a loro volta queste possibilità.

Se il processo va avanti per sempre assumiamo che Δ sia la classe ( x1 , x2 , .. , xn , … ) .Allora tutte queste x sono diverse, in quanto se r > s , xr è un membro di Γr – 1 e così di Γr – 2 , Γr – 3 , . . . , e in ultima analisi di Γs che non contiene xs. Quindi Δ è infinito. Anche tutte le ρ combinazioni dei membri di Δ appartengono a C1; perché se xs è un certo termine di una tale combinazione con almeno un suffisso s, gli altri termini ρ -1 della combinazione appartengono a Γs , e così formano con xs una ρ – combinazione appartenente a C1. Γ quindi contiene una sotto – classe Δ infinita del tipo richiesto.

Supponiamo , invece , che il processo di selezione della x e di Γ fallisca nella fase n -esima, e che y1 sia un qualsiasi membro di Γn – 1. Allora le combinazioni ( ρ -1 ) dei membri Γn – 1 – ( y1 ) possono essere suddivise in due classi mutuamente esclusive C’1 e C’2 secondo le ρ combinazioni formate aggiungendo ad essi y1 che appartiene a C1 o C2, e per il nostro teorema (A), che stiamo assumendo per vero quando r = ρ -1 ( e μ = 2 ), Γn – 1 – ( y1 ) deve contenere una sottoclasse infinita  Δ1, in modo tale che tutte le combinazioni ( ρ – 1 ) dei membri Δ1 appartengono alla stessa C’i; cioè tale che le ρ combinazioni formate unendo y1 ai membri ρ -1 di Δ1 appartengono tutti alla stessa Ci.

Inoltre, questo Ci non può essere C1, o y1 e Δ1 potrebbe essere assunto essere xn e Γn , e il nostro precedente processo di selezione non avrebbe fallito allo stadio n – esimo. Di conseguenza, le ρ combinazioni formate unendo y1 ai ρ -1 membri di Δ1 appartengono tutti a C2. Consideriamo ora Δ1 e sia y2 uno dei suoi membri. Ripetendo il precedente ragionamento Δ1 – ( y2 ) deve contenere una sottoclasse infinita Δ2 così che tutte le ρ combinazioni ottenute unendo y2 ai ρ -1 membri di Δ2 appartengono alla stessa Ci. E , ancora, questa Ci non può essere C1, o, dal momento che y2 è un membro e Δ2 una sotto – classe di Δ1 e così di Γn – 1 che include Δ1 , y2 e Δ2 avrebbe potuto essere scelto come xn e Γn e il processo di selezionare questi non avrebbe fallito nella fase n -esima. Ora sia y3 un qualsiasi membro di Δ2; allora Δ2 – ( y3 ) deve contenere una sottoclasse infinita Δ3 tale che tutte le ρ combinazioni costituite da y3 insieme con i ρ -1  membri di Δ3, appartengono alla stessa Ci, che, come prima, non può essere C1 e deve essere C2. E continuando in questo modo potremo evidentemente trovare due sequenze infinite y1 , y2, . . . , yn, . . . e Δ1 , Δ2 , . . . , Δn , . . . composti rispettivamente da membri delle sottoclassi di Γ , e tali che yn è sempre un membro di Δn-1, Δn una sotto- classe di Δn -1 che non include yn , e tutte le ρ combinazioni formate unendo yn ai ρ – 1 membri di Δn appartengono a C2; e se indichiamo con Δ la classe (y1 , y2, . . . , yn, . . .) abbiamo, dalla dimostrazione precedente, che tutte le ρ combinazioni dei membri del Δ appartengono a C2.

Quindi , in entrambi i casi , Γ contiene una sottoclasse infinita Δ del tipo richiesto, e il Teorema A è dimostrato per tutti i valori di r, purché μ = 2 . Per valori più elevati di μ lo dimostriamo per induzione; supponendolo già provato per μ = 2 e μ = ν -1, si deduce che per μ = ν .

Le r- combinazioni dei membri di Γ sono poi suddivise in ν classi Ci ( i = 1 , 2 , … , ν ) . Definiamo le nuove C’i per i = 1,2 , … , v- 1 con

C’i = Ci ( i = 1 , 2 , … , ν – 2 ) ,

C’ν – 1 = Cν – 1 + Cν

Quindi per il teorema per μ = ν – 1 , Γ deve contenere un sottoclasse infinita Δ tale che tutte le r- combinazioni dei membri di Δ appartengono alla stessa C’i . Se, in questa C’i , i ≤ ν – 2 , appartengono tutti alla stessa Ci, che è il risultato da dimostrare; altrimenti appartengono tutti alla C’ν – 1 , cioè o a Cν – 1 o Cν . In questo caso, per il teorema per μ = 2 , Δ deve contenere un infinita sottoclasse Δ’ tale che le r – combinazioni dei membri di Δ’ sia appartengono tutti o a Cν – 1 o appartengono tutti a Cν; e il nostro teorema è dimostrato.

Venendo ora a classi finite ci eviterà problemi il fare alcune convenzioni per la notazione. Lettere minuscole diversa da x e y, o in corsivo o lettere greche (per esempio n , r, μ , m ) , indicheranno sempre cardinali finiti, positivi se non diversamente specificato. Le lettere greche maiuscole (ad esempio Γ , Δ ) indicheranno le classi , e i loro suffissi indicheranno il numero dei loro membri (ad esempio Γm è una classe con m membri). Le lettere x e y rappresenteranno i membri delle classi Γ, Δ, ecc. , e i loro suffissi verranno utilizzati solo per distinguerli. Infine, la lettera C rappresenterà, come in precedenza, classi di combinazioni , e i suoi suffissi non faranno riferimento al numero dei membri, ma servono solo a distinguere le diverse classi di combinazioni considerate.

Corrispondente al Teorema A abbiamo poi

TEOREMA B. Dati qualsiasi r , n , e μ possiamo trovare un m0 tale che , se m ≥ m0 e le r- combinazioni di qualsiasi Γm sono divise in qualche modo in μ classi mutuamente esclusive Ci ( i = 1 . 2 .. μ ) , allora Γm deve contenere una sottoclasse Δn tale che tutte le r- combinazioni dei membri Δn appartengono alla stessa Ci.

Questo è il teorema di cui abbiamo bisogno nelle nostre indagini logiche, e sarebbe allo stesso tempo come avere informazioni su quanto grande deve essere preso m0 per qualsiasi dato r , n , e μ .

Non so come risolvere questo problema, e non ho dubbi che i valori di m0 ottenuti qui sotto sono molto più grandi di quanto sia necessario.

Per dimostrare il teorema cominciamo, come nel Teorema A , supponendo che μ = 2. Prendiamo poi, non il Teorema B in sé , ma l’equivalente:

TEOREMA C. Dati qualsiasi r , n , e k tali che n + k ≥ r, esiste un m0 tale che, se m ≥ m0 e le r- combinazioni di qualsiasi Γm sono divise in due classi mutuamente esclusive C1 e C2 , allora Γm deve contenere due sottoclassi mutualmente esclusive Δn e Λk tali che tutte le combinazioni formate dagli r membri di Δn + Λk che comprendono almeno un membro da Δn appartengono alla stessa Ci.

Che questo è equivalente al teorema B con μ = 2 è evidente dal fatto che, per qualsiasi r dato, il Teorema C, per n e k, asserisce più del Teorema B per n, ma meno del Teorema B per n + k.

La dimostrazione del Teorema C deve essere ottenuta per induzione matematica, e può essere convenientemente che sia presentata come una dimostrazione che è possibile definire ricorsivamente una funzione f (r , n , k) che servirà come m0 nel teorema.

Se r = 1, il teorema è evidentemente vero con m0 pari al maggiore di 2n – 1 e n + k, in modo che possiamo definire

f ( 1 , n , k) = max ( 2n – 1 , n + k) ( n ≥ 1 , k ≥ 0 ) .

Per gli altri valori di r definiamo f ( r , n , k) da formule ricorsive che coinvolgono una funzione ausiliaria g (r , n , k). Supponiamo che f (r – 1 , n , k) sia stata definita per un certo r – 1, e tutte le n, k tali che n + k ≥ r- 1 , allora la definiamo per r ponendo

f ( r,1,k ) = f ( r – 1, k -r + 2, r -2 ) +1       ( k + 1 ≥ r) ,

g ( r, 0, k) = max ( r-1, k ) ,

g (r , n , k) = f { r, 1 , g (r , n – 1 , k) } ( n ≥ 1 ) ,

f ( r , n , k) = f { r , n -1 , g (r , n , k) } ( n > 1 ) .

Si può vedere facilmente che queste formule definiscono f ( r , n , k) per tutti i valori positivi di r , n e k che soddisfano n + k ≥ r , e g ( r , n , k) per tutti i valori di r maggiori di 1, e tutti i valori positivi di n e k; e dimostreremo che il Teorema C è vero quando assumiamo m0 essere questo f ( r , n , k). Sappiamo che questo è così quando r = 1, e noi quindi lo assumeremo che per tutti i valori fino a r – 1 e lo dedurremo per r .

Quando n = 1 , e m ≥ m0 = f ( r – 1 , k – r + 2 , r – 2 ) + 1 , si può prendere qualsiasi membro x di Γm di essere unico membro di Δ1 e ci rimangono almeno f ( r – 1 , k – r + 2 , r – 2 ) membri di Γm – ( x ); le ( r – 1 ) – combinazioni di questi membri di Γm – ( x ) possono essere suddivisi nelle classi C’1 e C’2 in quanto appartengono a C1 o C2 quando x è aggiunto ad esse, e, dal nostro teorema perché r – 1 , Γm – ( x ) devono contenere due classi mutuamente esclusive Δk – r +2 , Λr – 2 tali che ogni combinazione di r -1 termini di ΔK -r +2 + Λr -2 ( in quanto uno dei suoi termini deve provenire da ΔK-r+2 , Λr -2 avendo solo r – 2 membri) appartiene alla stessa C’i . Assumendo che Λk sia questo ΔK – r +2 + Λr – 2 tutte le combinazioni costituite da x , unitamente a r -1 membri di Λk , appartengono alla stessa Ci. Il teorema è quindi vero per r quando n = 1 .

Per altri valori di n lo dimostriamo per induzione, assumendolo per n – 1 e deducendolo per n. Assumendo

m ≥ m0 = f ( r , n , k) = f { r , n – 1 , g (r , n , k ) } ,

Γm . deve , per il teorema per n -1, contenere un Δn – 1 e un Λg ( r,n , k ) tali che ogni combinazione degli r membri di Δn – 1 + Λg ( r, n , k ), almeno un termine dei quali deriva dalla Δn – 1, appartiene alla stessa Ci, ovvero a C1. Se , ora , Λg(r,n , k ) contiene un membro x e una sottoclasse Λk che non include x, tale che una qualsiasi combinazione di x e r-1 membri di Λk appartengono a C1, allora, assumendo che Δn sia Δn – 1 + ( x ) e Λk sia questo Λk , il nostro teorema è vero. Se no, non ci può essere nessun membro di Λg ( r,n , k) che ha una sotto- classe di k membri di Λg ( r,n , k) ad essa connessa in questo modo. Ma dal momento che

g (r , n , k) = f { r , 1 , g (r , n – 1 , k ) } ,

Λg ( r,n , k) deve contenere un membro x1 e una sottoclasse Λg ( r,n – 1 , k) , che non comprende x1, tale che x1 combinato con qualsiasi dei membri r – 1 di Λg ( r,n – 1 , k ) fornisce una combinazione appartenente alla stessa Ci, che non può essere C1, o x1 e qualsiasi k membri di Λg ( r,n – 1 , k) potrebbero essere presi come x andΛk di cui sopra.

Quindi le combinazioni formate da x1 insieme ogni membro r -1 di Λg ( r,n – 1 , k) appartengono tutti alla C2 . Ma adesso

g (r , n – 1 , k) = f { r , 1 , g (r , n – 2 , k ) } ,

e Λg ( r,n – 1 , k) deve contenere un x2 e un Λg ( r,n – 2 , k) , che non includono x2 , tale che le combinazioni formate da x2 e gli r -1 membri di Λg ( r,n – 2 , k) appartengono tutte alla stessa Ci, che deve, come prima, essere C2 , poiché x2 e Λg ( r,n – 2 , k) sono entrambi contenuti in Λg (r , n , k) e g ( r , n – 2 , k) ≥ k.

Continuando in questo modo possiamo trovare n termini distinti x1 , x2 , .. . , xn . e un Λg (r , 0 , k ) tale che ogni combinazione di termini r da (x1 , x2 , .. . , xn) + Λg (r , 0 , k ) appartiene a C2 , a condizione che almeno un termine della combinazione provenga da (x1 , x2 , .. . , xn) . Poiché g (r , 0 , k) ≥ k questo dimostra il nostro teorema, assumendo che Δn sia (x1 , x2 , .. . , xn) e Λk sia qualsiasi termine k di Λg (r , 0 , k) .

Il teorema C è quindi dimostrato per tutti i valori di r, n e k, con m0 pari a f ( r, n , k) . Ne consegue che, se μ = 2 , il Teorema B è vero per tutti i valori di r e n con m0 uguali a f ( r, n – r + 1 , r – 1 ) , che chiameremo anche h (r , n , 2 ) .

Per altri valori di μ dimostriamo il Teorema B per induzione, assumendo che m0 sia h ( r, n , μ ), dove

h (r , n , 2) = f ( r, n – r +1, r – 1 ) ,

h (r , n , μ) = h { r , h ( r, n, μ – 1 ) , 2} ( μ > 2) .

Perché, assumendo il teorema per μ – 1, lo dimostriamo per μ definendo nuove classi di combinazioni

C’1 = C1 ,

Schermata 2014-05-23 alle 19.09.08

Se allora m ≥ h (r , n , μ ) = h { r , h ( r , n , μ -1 ) , 2 } , per il teorema per μ = 2 , Γm deve contenere un Γh (r , n , μ -1 ) le combinazioni dei cui membri r appartengono o tutte a C’1 o tutte a C’2 . Nel primo caso non vi è più nulla da dimostrare, nel secondo dobbiamo solo applicare il teorema per μ – 1 a Γh (r , n , μ – 1 ) .

Nel caso più semplice in cui r = μ = 2 il ragionamento precedente fornisce m0 pari a h ( 2 , n , 2 ), che è facilmente dimostrato essere 2n ( n – 1 ) / 2 . Ma in questo caso vi è una semplice dimostrazione che fornisce il valore molto più basso m0 = n !, E dimostra che il nostro valore h (r , n , μ ) è del tutto eccessivo.

Perché, prendendo in primo luogo il Teorema C, siamo in grado di dimostrare per induzione con riferimento ad n che, per r = 2, possiamo assumere che m0 sia k. ( n + 1 ) ! . ( k è qui supposto maggiore o uguale a 1).

Perché questo è vero quando n = 1, dal momento che, se m ≥ 2k, di m – 1 coppie ottenute combinando un qualunque membro della Γm con gli altri, almeno k devono appartenere alla stessa Ci . Supponendo ciò, quindi, per n – 1, lo dimostriamo per n .

Se m ≥ k. ( n +1 ) ! = k ( n +1) . n ! , Γm deve, per il teorema per n -1, contenere due mutuamente esclusive sottoclassi Δn – 1 e Λk ( n +1), tali che tutte le coppie da Δn – 1 + Λk ( n +1 ), almeno un termine delle quali proviene da Δn – 1 , appartengono alla stessa Ci, ovvero a C1. Consideriamo ora i membri Λk ( n +1), in primo luogo, ci può essere uno di questi, ad esempio x, che è tale che ci sono k altri membri della Λk ( n +1) che, combinati con x danno coppie appartenenti a C1. Se è così , il teorema è vero, assumendo che Δn sia  Δn – 1 + ( x ); altrimenti sia x1 qualsiasi membro ofΛk ( n +1 ). Allora vi sono al più k- 1 altri membri di Λk ( n +1) che, combinati con x1 danno coppie appartenenti a C1, e Λk( n +1 ) – (x1) che devono contenere un Λkn qualsiasi membro del quale fornisce quando combinato con x1 una coppia appartenente a C2 . Sia x2 un qualsiasi membro di Λkn allora, dal momento che x2 e Λkn sono entrambi contenuti in Λk ( n +1), ci sono al massimo k – 1 altri membri della Λkn , che se combinati con x2 danno coppie appartenenti a C1 . Quindi Λkn -( x2 ) contiene un Λk ( n – 1) qualsiasi membro del quale combinato con x2 dà una coppia appartenente a C2. Continuando in questo modo otteniamo x1 , x2 , . . . , xn e Λk , tali che ogni coppia xi , xj e ogni coppia costituita da un xi ed un membro di Λk appartiene a C2.

Il Teorema C è quindi dimostrato.

Il Teorema B per n poi segue , con l’m0 del Teorema C per n – 1 e 1, cioè con m0 pari a n ! 1; ed è un’estensione facile mostrare che , se nel Teorema B r = 2, ma μ ≠ 2 , possiamo assumere che m0 sia n! ! ! . . . . , Dove il processo di prendere il fattoriale si verifica μ -1 volte.

1 Ma questo valore è, credo , ancora troppo elevato. Può essere facilmente abbassato leggermente anche quando seguendo la linea di ragionamento precedente, utilizzando il fatto che se k è pari è impossibile per ogni membro di una classe dispari di avere esattamente k -1 altri con i quali formi una coppia di C1, perché allora due volte il numero di queste coppie sarebbe dispari, possiamo quindi iniziare quando k è pari con un Λk ( n +1) -1 invece di un Λk ( n +1).

II

Ci occuperemo di formule logiche contenenti funzioni proposizionali variabili, ossia predicati o relazioni, che indicheremo con lettere greche φ , X , Ψ , ecc. Queste funzioni hanno come argomenti particolari indicati con x , y , z , ecc. , e ci occuperemo di funzioni con qualsiasi numero finito di termini, cioè di una qualsiasi delle forme

φ ( x ) , Χ ( x , y ) , Ψ ( x , y , z ) . ….

Oltre a queste funzioni variabili avremo una funzione costante di identità

x = y       o     = ( x , y ) .

Agendo sui valori di φ , Χ , Ψ , . . . ,  e l’= le operazioni logiche

~ significa non,

v significa o,

. significa e,

( x ) significa per tutti le x,

∃ x ) significa che c’è una x per la quale,

possiamo costruire espressioni come

[ ( x , y ) { φ ( x , y ) v x = y } ] { v ( ∃ z ) Χ ( z ) }

in cui tutte le variabili particolari sono rese ‘ apparenti ‘ dai prefissi ( x ) o ( ∃ x ), e le sole variabili reali restanti sono le funzioni φ , X , . . . Chiameremo una tale espressione formula di primo ordine.

Se tale la formula è vera per tutte le interpretazioni 1 delle variabili funzionali φ , Χ , Ψ , ecc. , noi la chiameremo valida, e se non è vera per nessuna interpretazione di queste variabili la chiameremo incoerente. Se è vera per alcune interpretazioni (anche se non per tutte) la chiameremo coerente.2

1 Per evitare confusioni noi chiamiamo una funzione costante sostituita ad un φ variabile, non un valore di φ, ma una interpretazione di essa; i valori di φ ( x , y , z) sono ottenuti sostituendo costanti particolari a x , y e z.

2 erfüllbar in tedesco .

L’Entscheidungsproblem (n.d.t.: il problema della decisione cfr. Hilbert) è di trovare un procedimento per determinare se una qualsiasi data formula è valida, o , in alternativa, se una qualsiasi data formula è coerente; perché questi due problemi sono equivalenti, dal momento che la condizione necessaria e sufficiente per una formula per essere coerente è che la sua contraddizione non sarebbe valida. Dovremo trovare più conveniente assumere il problema in questa seconda forma come indagine di coerenza. La coerenza di una formula può, ovviamente , dipendere del numero di particolari nell’universo considerato, e dovremo distinguere tra formule coerenti in ogni universo e quelle che sono coerenti solo in universi con certi particolari numeri di membri .

Ogni volta che l’universo è infinito dovremo assumere l’Assioma delle Selezioni .

Il problema è stato risolto da Behmann 1 per formule che coinvolgono solo le funzioni di una variabile, e da Bernays e Schönfinkel 2 per formule che coinvolgono due sole variabili particolari apparenti. E’ risolto qui sotto nell’ulteriore caso in cui, quando la formula è scritta in ‘ forma normale ‘, esistono un certo numero di prefissi di generalità ( x ) , ma nessuno di esistenza ( ∃ x ) .3 Con ‘ forma normale ‘ 4 qui si intende che tutti i prefissi si trovano all’inizio, con nessuna negazione tra o prima di essi, e hanno ambiti che si estendono fino al termine della formula.

1 H. Behmann , ” Beiträge zur Algebra der Logik , insbesondere zum Entscheidungsproblem, ” Math. Annalen , 86 (1922), pp 163-229 .

2 P. Bernays und M. Schönfinkel , “Zum Entscheidungsproblem der mathematiscen logik, “Math. Annalen, 99 (1928), pp. 342-372. Questi autori, tuttavia, non includono l’identità nelle formule che considerano.

3 Più avanti estendo la nostra soluzione al caso in cui ci siano anche prefissi di esistenza purché tutti questi precedano i prefissi di generalità.

4 Hilbert und Ackermann, op. cit., 63-64.

Le formule da considerare sono pertanto nella forma

(x1,x2, …, xn) F(ϕ,Χ,Ψ, …, = x1,x2, …, xn)

Dove la matrice F è una funzione verità dei valori delle funzioni ϕ,Χ,Ψ, ecc., e = per gli argomenti tratti da x1,x2, …, xn

Questo tipo di formula è interessante come il tipo generale di un sistema di assiomi interamente costituito da ‘ leggi generali ‘. 1

Gli assiomi per ordine, nello stare in relazione , e ordine ciclico sono tutti di questa natura , e noi stiamo tentando così una teoria generale della coerenza dei sistemi di assiomi di un tipo comune, se molto semplice.

Se l’identità non si verifica in F il problema è banale, poiché in questo caso se la formula è coerente o non può essere dimostrato che sia indipendente dal numero di particolari nell’universo, e abbiamo solo il facile compito di provarlo per un universo con un solo membro. 2

Ma quando si introduce l’identità il problema diventa molto più difficile, perché anche se è abbastanza evidente che, se la formula è coerente nell’universo U deve essere coerente in ogni universo con un minor numero di membri di U, ma può facilmente essere coerente in un più piccolo universo ma non in universo più ampio .

Per esempio ,

( x1 , x2 ) [ x1 = x2 v { φ ( x1 ) . ~ Φ ( x2 ) } ]

è coerente in un universo con un solo membro ma non in qualsiasi altro.

Iniziamo la nostra indagine esprimendo F in una forma particolare. F è una funzione verità dei valori di φ , Χ , Ψ , … e = per gli argomenti tratti da x1,x2, …, xn. Se φ è una funzione di r variabili ci saranno nr3 valori di φ che possono verificarsi in F e F sarà una verità funzione dei valori Σnr di φ , Χ , Ψ , … e = , che chiameremo proposizioni atomiche .

1 C.H. Langford , ” la completezza analitica degli insiemi postulati “, Proc. London Math. Soc. ( 2 ) , 25 ( 1926) , pp. 115-116 .

2 Bernays und Schönfinkel , op . cit . , p. 359 . Noi ignoriamo del tutto universi senza membri .

3 Qui e altrove i numeri sono riportati non in quanto sono rilevanti per l’argomento , ma per consentire al lettore di verificare che egli ha in mente la stessa classe di entità dell’autore.

Con riferimento a queste proposizioni atomiche Σnr ci sono 2Σnr possibilità di verità e falsità che chiameremo alternative, essendo ogni alternativa una congiunzione di Σnr proposizioni che sono o proposizioni atomiche o le loro contraddizioni. Nel costruire le alternative tutte le proposizioni atomiche Σnr devono essere utilizzate sia che si verifichino in F o meno. F può quindi essere espresso come una disgiunzione di alcune di queste alternative, cioè quelle con cui è compatibile.

E’ ben noto che tale espressione è possibile; anzi è il duale di quello Hilbert e Ackermann chiamano ‘ ausgezeichnete konjunktive Normalform (eccellente forma normale congiuntiva‘ , 1 ed è fondamentale anche nella logica di Wittgenstein. L’unica eccezione è quando F è una funzione di verità auto – contraddittoria, nel qual caso la nostra formula non è certamente coerente .

F essendo stato quindi espresso come una disgiunzione di alternative (nel nostro speciale significato della parola ), il nostro compito successivo è quello di mostrare che alcune di queste alternative possono essere in grado di essere eliminate senza incidere sulla coerenza o incoerenza della formula. Se tutte le alternative possono essere rimosse in questo modo la formula sarà incoerente; altrimenti dovremo ancora considerare le alternative che rimangono .

In primo luogo una alternativa può violare le leggi di identità contenendo parti di una qualsiasi delle seguenti forme : –

xi ≠ xi2

xi = xj.xj ≠ xi ( i ≠ j )

xi = xj.xj = xk . xi ≠ xk ( i ≠ , j ≠ k, k ≠ i) ,

o contenendo xi = xj ( i ≠ j ) e i valori di una funzione φ ed è contraddittoria ~ φ per un insieme di argomenti che diventano gli stessi quando xi è sostituito da xj [ad esempio x1 = x2 . φ ( x1 , x2 , x3) . ~ φ ( x1 , x2 , x3 ) ] .

1 op. cit . , p . 16 .

2 Noi scriviamo x ≠ y per ~ ( x = y) .

Qualsiasi alternativa che violi queste leggi deve essere sempre falsa e può evidentemente essere scartata senza compromettere la coerenza della formula. Le alternative rimanenti possono essere classificate in base al numero di x che rendono diverse, che può essere qualsiasi, da 1 fino a n.

Supponiamo che per un determinato alternativa questo numero è ν , allora possiamo trarre da questo ciò che chiameremo la corrispondente y alternativa dal seguente processo: –

Per x1, ovunque si manifesti nella data alternativa, si scrive y1; poi, se in alternativa a x2 = x1, per x2 si scrive di nuovo y1, se non si scrive y2 per x2. In generale, se xi è la data alternativa identica con qualsiasi xj con j minore di i, scrivo per xi la y precedentemente scritta per xj; altrimenti si scrive per xi , yk +1, dove k è il numero di y già introdotto. L’espressione che risulta contiene ν di y tutte diverse invece delle x di n, alcune delle quali sono identiche, e noi le chiameremo y alternative che corrispondono alla data x alternativa .

Così all’alternativa

φ ( x1 ) . ~ Φ (x2) . φ ( x3 ) . ~ φ (x4) . x1 = x3.x2 = x4.x1 ≠ x2 1

corrisponde l’alternativa y

φ ( y1 ) . ~ Φ ( y2 ) . y1 ≠ y2

Chiamiamo le due y alternative simili se contengono lo stesso numero di y e possono essere derivate l’una dall’altra permutando queste y, e noi chiamiamo due x alternative equivalenti se corrispondono a simili (o identiche) alternative y.

Così

φ ( x1 ) . ~ Φ (x2) . φ ( x3 ) . ~ φ ( x4 ) . x1 = x3.x2 = x4.x1 ≠ x2 ( α )

è equivalente a

~ Φ ( x1) . φ ( x2 ) . φ ( x3 ) . φ ( x4 ) . x1 ≠ x2.x2 = x3 = x4 ( β )

1 Prendiamo una funzione di una variabile solo per semplicità; anche per risparmiare spazio omettiamo espressioni che possono essere adottate per certe come x1 = x1 , x1 ≠ x4

in quanto corrispondono alle alternative y simili

φ ( y1 ) . ~ Φ ( y2 ) . y1 ≠ y2

~ Φ (y1) . φ ( y2 ) . y1 ≠ y2

derivabili una dall’altra scambiando y1 e y2 sebbene ( α ) e ( β ) non siano nello stesso modo derivabili permutando le x.

Ora vediamo che possiamo scartare ogni alternativa contenuta in F, qualora F contenga anche tutte le alternative equivalenti ad essa; ad esempio se F contiene ( α ) ma non ( β ), ( α ) può essere eliminata da questa. Perché omettendo le alternative chiaramente non può rendere la formula coerente se non lo era così prima; e possiamo facilmente dimostrare che, se fosse stata coerente prima, omettere queste alternative non potrebbero renderla incoerente.

Perché supponiamo che la formula sia coerente, cioè che per qualche particolare interpretazione di φ , Χ , Ψ , . . . F è vero per ogni insieme di x, e sia p un’alternativa contenuta in F, q un’alternativa equivalente a p, ma non contenuta in F.

Allora per ogni insieme di x una e una sola alternativa in F sarà (con questa interpretazione di φ , Χ , Ψ , ….) quella vera, e questa alternativa non può mai essere p. Perché se fosse p, la corrispondente alternativa y sarebbe vera per alcuni insiemi di y, e la simile alternativa y corrispondente a q sarebbe vera per qualche insieme di y ottenuto permutando questo ultimo insieme. Dando opportuni valori di x in termini di y di, q allora sarebbe vera per un certo insieme di x e F sarebbe falsa per di queste x in contrasto con le ipotesi. Quindi p non è mai la vera alternativa, e può essere omessa senza influenzare la coerenza della formula.

Quando abbiamo scartato tutte queste alternative di F, il resto cadrà in insiemi ciascuno dei quali è l’insieme completo di tutte le alternative equivalenti a una data alternativa. Ad un tale insieme di alternative x corrisponderà una serie completa di alternative y simili, e la disgiunzione di un insieme completo di alternative y simili (cioè di tutte le permutazioni di una data alternativa y ) chiameremo una forma. 1 Indicheremo una forma contenente ν di y con una maiuscola corsiva con suffisso ν, ad esempio, Aν Bν

La forza di una formula può essere rappresentata dalla seguente congiunzione, che chiameremo P:

Schermata 2014-02-05 alle 19.00.41 traduzione

dove Aν Bν 2 , ecc., sono le forme corrispondenti alle x alternative ancora rimaste in F. Se per qualsiasi ν ≤ n non ci sono tali forme, cioè se non esistono alternative a ν diversi x rimangono in F, la nostra formula implica che non vi sono oggetti come ν particolari distinti, e quindi non può essere coerente in un mondo ν o più membri.

1 Cf . Langford , op . cit . , 116-20 .

2 La notazione è parzialmente fuorviante , dal momento che Aν non ha una più stretta relazione con a Aμ rispetto a Bμ .

Ora dobbiamo definire cosa si intende dicendo che una forma è coinvolta in un’altra. Si consideri una forma Aν e prendiamo una delle alternative y in essa contenuta . Questo y alternativa è un insieme di valori di φ , Χ , Ψ , . . . e le loro contraddittorie per gli argomenti tratti dalla y1 , y2 , . . . , yν (potremmo lasciare fuori i valori di identità e differenza, dal momento che è dato per scontato che le y sono sempre differenti.) Se μ < ν possiamo selezionare un μ di questi y in qualche modo e lasciare fuori dall’alternativa tutte i termini in essa che contengono qualsiasi y non selezionati di ν-μ. Abbiamo lasciato una alternativa y in μ che possiamo rinumerare y1 , y2 , . . . yμ e possiamo descrivere la forma Eμ a cui questa nuova alternativa appartiene come coinvolta nella Aν da cui abbiamo iniziato. Partendo da un particolare y alternativo in Aν possiamo ottenere un gran numero di differenti Eμ scegliendo in modo diverso la μ di y che selezioniamo per riservarla; e da qualsiasi y alternativo in Aν cominciamo, l’Eμ che troviamo essere coinvolto in Aν sarà lo stesso .

Per esempio ,

{ φ ( y1 , y1 ) . φ ( y1 , y2 ) . φ ( y2 , y1 ) . ~ Φ ( y2.y2 ) } v { ~ Φ ( y1 , y1 ) . φ ( y1 , y2 ) . φ ( y2 , y1 ) . Φ ( y2 ,y2 ) }

è una forma A2 che coinvolge le due E1 di

φ ( y1 , y1 ) ,

~ Φ ( y1 , y1 ) .

E ‘chiaro che se per qualche insieme distinto di ν di y una forma Aν è vera, allora ogni forma Eμ coinvolta in Aν sarà vera per alcuni distinti insiemi di μ di y contenuti nel ν.

Siamo ora in grado di risolvere la coerenza o l’ incoerenza della nostra formula quando N, il numero di particolari nell’universo, è inferiore o uguale a n, il numero di x nella nostra formula. Infatti , se N ≤ n , è necessario e sufficiente per la coerenza della formula che P deve contenere una forma AN insieme con tutte le forme Eμ coinvolte in esso per ogni μ minore di N.

Questa condizione è evidentemente necessaria, dal momento che gli individui N nell’universo lo devono, assunto che y1 , y2 , . . . yN, abbiano una qualche forma AN rispetto a qualsiasi φ , Χ , Ψ , . . . ; e tutte le forme coinvolte in questo AN devono essere vere per le diverse selezioni di y, e così contenute in P se P deve essere vera per queste φ , Χ , Ψ , . . ..

Viceversa, supponiamo che P contenga una forma AN insieme a tutte le forme coinvolte in AN; allora chiamando gli N particolari nell’universo y1, y2 , . . . yN, possiamo definire che le funzioni φ , Χ , Ψ , . . . che rendono qualsiasi assegnata alternativa y in AN vera; perché ogni permutazione di questi N di y sarà un’altra alternativa in AN vera, e per qualunque sottoinsieme di y qualche alternativa y è una forma coinvolto in AN. Poiché tutte queste alternative y sono per ipotesi contenuta in P, P sarà vera per questi φ , Χ , Ψ , . . . , e la nostra formula coerente.

Quando, tuttavia, N > n il problema non è così semplice, anche se dipende chiaramente dalle AN in P tale che tutte le forme coinvolte in essa sono contenute anche in P. Possiamo definire queste  An come completamente contenute in P, e se non ci sono tali An una dimostrazione simile a quella utilizzata quando N ≤ n mostrerà che la formula è incoerente. Ma l’argomento opposto, che se c’è una AN completamente contenuta in P la formula deve essere coerente, non può essere sostenuta bene; e per procedere oltre dobbiamo introdurre una nuova concezione , la concezione di una forma che sia seriale.

Ma prima di procedere a spiegare questa idea è meglio semplificare la questione con l’introduzione di nuove funzioni. Sia φ essere una delle funzioni variabili nella nostra formula, con, ad esempio, r termini. Allora se r < n , φ si presenta in P , con tutti i suoi diversi argomenti [ad esempio φ ( y1 , y2 , … , yr )] e anche con alcuni di questi uguali [ad esempio φ ( y1 , y2 , … , yr – 1 , y1 )]; ma possiamo opportunamente eliminare i valori del secondo tipo con l’introduzione di nuove funzioni con meno argomenti di r, che, quando tutti i loro termini sono diversi, assumono i valori equivalenti a quelli di φ con alcuni dei suoi argomenti identici .

Ad esempio possiamo mettere

φ1 ( y1 , y2 , … , yr – 1 ) = φ ( y1, y2, … , yr – 1 , y1) .

In questo modo φ dà luogo ad un grande numero di funzioni con un numero minore di argomenti; noi definiamo ciascuna di queste funzioni solo per il caso in cui tutti gli argomenti sono diversi, come è garantito da questi argomenti essendo differenti i suffissi di y.

Se r > n , non vi è alcuna differenza, tranne che φ non può mai verificarsi con tutti i suoi argomenti diversi , e così è interamente sostituita dalle nuove funzioni.

Se facciamo questo per tutte le funzioni φ , Χ , Ψ , . . . , e le sostituiamo con le nuove funzioni ovunque si verifichino in P con alcuni dei loro argomenti della stessa, P conterrà una nuova serie di funzioni variabili (compresi tutte le vecchie che non hanno più di n argomenti), e questi non si presenteranno mai in P con lo stesso argomento ripetuto.

È facile vedere che questa trasformazione non influisce sulla coerenza della formula, perché, se era coerente prima, deve essere coerente in seguito, poiché le nuove funzioni devono semplicemente essere sostituite dalle loro definizioni. E se è coerente dopo deve essere state così prima, dal momento che a qualsiasi funzione del vecchio insieme deve solo essere dato per qualsiasi insieme di termini il valore dell’opportuna funzione del nuovo insieme. 1

In considerazione di questo fatto troveremo più conveniente prendere P nella sua nuova forma , e indicare il nuovo insieme di funzioni con φ0 , Χ0 , Ψ0 , . . .

1 Per esempio , se φ ( y1 , y2 , y3 ) è una funzione del vecchio insieme, abbiamo cinque nuove funzioni

φ0 ( y1 , y2 , y3) = φ ( y1 , y2 , y3 )

Χ0 ( y1 , y2 ) = φ ( y1 , y1 , y2 )

Ψ0 ( y1 , y2 ) = φ ( y1 , y2 , y1 )

π0 ( y1 , y2 ) = φ ( y2 , y1 , y1 )

ρ0 (y1) = φ ( y1 , y1 , y1 )

e ogni valore di φ è equivalente ad un valore di una, e solo una , delle nuove funzioni. Va ricordato che le nuove funzioni sono usate solo con tutti i loro argomenti diversi; perché altrimenti non sarebbero indipendenti, dal momento che dovremmo avere , per esempio, Χ0 ( y1 , y1 ) equivalente a ρ0 ( y1 ) . Ma Χ0 ( y1 , y1 ) non si verifica mai, e φ ( y1 , y1 , y1 ) è equivalente non a qualsiasi valore di Χ0 ma solo a ρ0 ( y1 ) .

Supponiamo, poi, che φ0 sia funzione di r variabili; ci saranno

n ( n – 1 ) , .. ( n -r +1 )

valori di φ0 con r diversi argomenti tratti dalla y1 , y2 , . . . , yn e ogni y alternativa deve contenere ciascuno di questi valori o suoi contrari. r ! di questi valori avrà come argomenti le permutazioni di y1 , y2 , . . . , yr . Qualsiasi altra serie di r di y può essere organizzata secondo l’ordine dei loro suffissi come yS1 , yS2 . . . , ySr , s1 < s2 < s3 . , . . . < sr e può accadere che una data un’alternativa contenga i valori di φ0 per quelle e solo quelle permutazioni di yS1 , yS2 , . . . , ySr che corrispondono (in modo ovvio ) alle permutazioni di y1 , y2 , . . . , yr , per le quali (l’alternativa) contiene i valori di φ0; ad esempio se l’alternativa contiene φ0 ( y1 , y2 , … , yr ) e φ0 ( yr , yr – 1 , … , y1 ), ma per ogni altra permutazione di y1 , y2 , . . . , yr , contiene il valore corrispondente di ~ φ0 , allora può accadere che l’alternativa contenga φ0 (yS1 ,yS2 , … ,ySr ) e φ0 ( ysr , ysr – 1 , … , yS1 ), ma per ogni altra permutazione di yS1 , yS2 , . . . , ySr , contenga il valore corrispondente di ~ φ0.

Se questo accade, non importa come venga scelto l’insieme di r di y , yS1 , yS2 , . . . , ysr, da y1 , y2 , . . . , yn , allora diciamo che l’alternativa è seriale in φ0 , 1 e se un alternativa è seriale in ogni funzione del nuovo insieme la chiameremo semplicemente seriale .

1 Così , se φ0 è un . funzione di n variabili , tutte le alternative sono seriali in φ0.

Si consideri, per esempio , la seguente alternativa, in cui possiamo immaginare φ0 e Ψ0 che derivino da una ‘vecchia’ funzione φ con le definizioni

φ0 ( yi , yk ) = φ ( yi , yk ) .

Ψ0 ( yi ) = φ ( yi , yi ).

φ0 ( y1 , y2 ) . ~ Φ0 ( y2 , y1 ) . φ0 ( y1 , y3 ) . ~ Φ0 ( y3 , y1 ) . φ0 ( y2 , y3 ) . ~ Φ0 ( y3 , y2 ) ,

Ψ0 ( y1 ) . ~ Ψ0 ( y2 ) . Ψ0 ( y3 ) .

Questa è seriale in φ0, dal momento che abbiamo sempre φ0 (yS1 ,yS2 ) . ~ Φ0 (yS2 ,yS1 ); ma non in Ψ0 , dal momento che a volte abbiamo Ψ0 (yS1 ), ma a volte ~ Ψ0 (yS1 ). Quindi non è un’alternativa seriale .

Chiamiamo una forma seriale quando contiene almeno una alternativa seriale, e ora possiamo affermare il nostro risultato principale come segue.

TEOREMA – Dato un numero finito m, dipendente da n, il numero di funzioni φ , Χ , Ψ , . . . , e il numero dei loro termini, in modo tale che la condizione necessaria e sufficiente per la nostra formula di essere coerente in un universo con m o più membri è che ci dovrebbe essere una forma seriale An completamente contenuta in P. Per coerenza in un universo con un numero di membri inferiore ad m questa condizione è sufficiente ma non necessaria .

Noi in primo luogo dimostreremo che, qualunque sia il numero N di particolari nell’universo, la condizione è sufficiente per la coerenza della formula. Se N ≤ n, questa è una conseguenza del risultato precedente, poiché , se An è contenuto totalmente in P, allora qualunque AN è coinvolto in An.

Se N > n , noi supponiamo l’universo ordinato in una serie da una relazione R. ( Se N è infinito questo richiede l’Assioma delle Selezioni.) Sia q qualsiasi alternativa seriale contenuta in An.

Se φ0 è una funzione di r termini, q conterrà i valori o di φ0 o ~ φ0 ( ma non entrambi ) per ogni permutazione di y1 , y2 , . . . , yr. Qualsiasi di tali permutazioni possono essere scritte yρ1 , yρ2 , . . . , yρr , dove ρ1 , ρ2 , . . . , ρr sono 1 , 2 , . . . , r riordinati. Facciamo un elenco di tutte quelle permutazioni ( ρ1 , ρ2 , … , ρr ) in cui q contiene i valori di φ0, e chiamiamo questo elenco Σ. Diamo ora a φ0 la costante interpretazione che φ0 (z1, z2 … , zr ) deve essere vero se e solo se l’ordine dei termini z1, z2 … , zr  nella serie R è dato da una delle permutazioni (ρ1 , ρ2 , … , ρr) contenute in Σ , nel senso che, per ogni i , zi è l’ ρi– esimo di z1, z2 … , zr, in quanto sono ordinati per R.

Supponiamo ora che y1 , y2 , . . . , yn . siano numerati nell’ordine in cui si verificano in R , cioè che nella serie R y1 è il primo di essi , y2 il secondo , e così via. Allora vedremo che, se a φ0 viene data l’interpretazione costante sopra definita, tutti i valori di φ0 e ~ φ0 in q saranno veri. Infatti , per i valori cui argomenti sono ottenuti permutando  y1 , y2 , . . . , yr ciò segue subito dal modo in cui φ0 è stato definito. Perché φ0 ( yσ1 , yσ2 , … , yσr ) è vero se e solo se l’ordine di yσ1 , yσ2 , … , yσr nella serie R è dato da una permutazione ( ρ1 , ρ2 , … , ρr) contenuta in Σ. Ma l’ordine nella serie di yσ1 , yσ2 , … , yσr è infatti dato (in base alla nostra ipotesi presente che l’ordine della y è y1 , y2 , … , yr ) da ( σ1 , σ2 , … , σr ) , che è contenuto in Σ se e solo se φ0 ( yσ1 , yσ2 , … , yσr) è contenuto in q. Quindi i valori di φ0 per gli argomenti consistenti nei primi r di y sono veri quando sono contenuti in q e falsi in caso contrario, cioè quando i corrispondenti valori di ~ φ0 sono contenuti in q.

Per l’insieme di argomenti non contenuti nei primi y di r il nostro risultato deriva dal fatto che q è seriale, vale a dire che se s1 < s2 < . . . < sr così che yS1 , yS2 , . . . , ysr sono nell’ordine dato dalla serie R, q contiene i valori di φ0 proprio per quelle permutazioni di yS1 , yS2 , . . . , ysr che corrispondono alle permutazioni di y1 , y2 , . . . , yr per cui contiene i valori di φ0, ossia nella definizione di φ0 e per l’argomento precedente, proprio per quelle permutazioni di yS1 , yS2 , . . . , ysr, che rendono φ0 vero.

Quindi tutti i valori di φ0 e ~ φ0 in q sono vere quando y1 , y2 , . . . , yn sono nell’ordine dato dalla serie R.

Se, poi, definiamo analoghe interpretazioni costanti per Χ0 , Ψ0 , ecc , e combiniamo queste con la nostra interpretazione di φ0, l’insieme di q sarà vero ammettendo che y1 , y2 , . . . , yn sono nell’ordine dato dalla serie R, e se y1 , y2 , . . . , yn sono in qualsiasi altro ordine l’alternativa vera verrà ottenuta da q opportunamente permutando le y, cioè sarà un’alternativa simile a q e contenuta nella stessa forma An. Quindi An è vero per qualsiasi insieme distinto di y1 , y2 , . . . , yn. Inoltre, per ogni insieme di distinto y1 , y2 , . . . , yn , ( ν < n) la forma vera sarà una forma coinvolta in An, e dal momento che An e tutte le forme coinvolte in esso sono contenute in P, P sarà vero per queste interpretazioni di φ0 , Χ0 , Ψ0 , . . . , e la nostra formula deve essere coerente.

Avendo così dimostrato la nostra condizione di coerenza sufficiente in qualsiasi universo, dobbiamo ora dimostrare la necessità, in ogni universo infinito o finito sufficientemente grande, e per questo dobbiamo usare il Teorema B dimostrato nella prima parte del documento .

La nostra linea di ragionamento è la seguente: dobbiamo dimostrare che, qualunque φ0 , Χ0 , Ψ0 , . . . , prendiamo , P sarà falso a meno che contenga completamente un An seriale. Per questo è sufficiente dimostrare che, dati qualsiasi φ0 , Χ0 , Ψ0 , . . . , ci deve essere un insieme di n di y per cui la forma vera è seriale 1 o , poiché una forma seriale è quella che contiene un’alternativa seriale, che ci deve essere un insieme di valori di y1 , y2 , . . . , yn per cui l’alternativa vera è seriale.

Supponiamo che tra le nostre funzioni φ0 , Χ0 , Ψ0 , . . . esistano a1 funzioni di una variabile, a2 di due variabili , . . . , e an di n variabili, e che ordiniamo l’universo con una relazione seriale R.

Gli N termini nell’universo sono divisi dalle funzioni a1 di una variabile in 2a1 classi a seconda che rendano queste funzioni vere o false, e se N ≥ 2a1k1 , possiamo trovare k1 termini che appartengono tutti alla stessa classe, vale a dire che si accordano a quelle funzioni di a1 che le rendono vere e a quelle che le rendono false, dove k1 è un numero intero positivo da assegnare successivamente.

Chiamiamo questo insieme di individui k1 Γk1 .

1Perché allora P può essere vero solo per φ0 , Χ0 , Ψ0 , . . . nel contenere completamente tale forma seriale vera.

Ora consideriamo qualsiasi due membri distinti di Γk1 , diciamo z1 e z2, e poniamo che z1 precede z2 nella serie R . Allora in relazione a qualsiasi delle funzioni a2 di due variabili, diciamo φ0, ci sono quattro possibilità . Possiamo avere

( 1 ) φ0 ( z1 , z2 ) . φ0 ( z2 , z1 ) ,

o ( 2 ) φ0 ( z1 , z2 ) . ~ φ0 ( z2 , z1 ) ,

o ( 3 ) ~ φ0 ( z1 , z2 ) . φ0 ( z2 , z1 ) ,

o ( 4 ) ~ φ0 ( z1 , z2 ) . ~ φ0 ( z2 , z1 ) .

φ0 divide così le combinazioni a due a due dei membri di Γk1 in quattro classi distinte in base a quale di queste quattro possibilità si verifica a seconda di quali di queste quattro possibilità si verifica quando si assume la combinazione come z1, z2 nell’ordine in cui i suoi termini si verificano nella serie R; e l’intero insieme delle funzioni a2 di due variabili divide le combinazioni a due a due dei membri di Γk1 in 4a2 classi, essendo le combinazioni in ciascuna classe in accordo nella possibilità che esse soddisfino con riferimento a ciascuna funzione a2. Quindi , per il Teorema B , se k1 = h ( 2 , k2 , 4a2 ), Γk1 deve contenere una sottoclasse Γk2 di k2 membri tale che tutte le coppie di Γk2 concordano nelle possibilità che soddisfino in relazione a ciascuna funzione di due variabili a2.

Continuiamo a ragionare nello stesso modo secondo la seguente forma generale: –

1 Se ar = 0 si interpretano h (r , kr , 1) come kr e rendono identici Γkr -1 e Γkr.

Consideriamo qualsiasi r distinti membri di Γkr -1; supponiamo che nella serie R essi abbiano l’ordine z1 , z2 , . . . , zr. Allora con riferimento a qualsiasi funzione di r variabili esistono 2r! possibilità in riferimento a z1 , z2 , . . . , zr, e le ar funzioni di r variabili dividono le combinazioni r ad alla volta dei membri del Γkr – 1 in 2r!ar classi. Per il Teorema B , se kr- 1 = h (r , kr, 2r!ar ) , 1 Γkr – 1 deve contenere una sottoclasse Γkr , di kr membri tale che tutte le combinazioni r alla volta dei membri del Γkr concordano nelle possibilità che esse concordino rispetto a ciascuna delle ar funzioni di r variabili.

Si procede in questo modo fino a raggiungere Γkr – 1 , tutte le combinazioni n – 1 alla volta dei cui membri concordano nelle possibilità che soddisfino in relazione a ciascuna delle an- 1 funzioni di n – 1 variabili. Noi allora stabiliamo che kn – 1 deve essere uguale a n, che determina kn -2 come h ( n – 1 , n , 2 ( n – 1 ), an – 1 ) e così via indietro fino a k1 , ogni kr – 1 essendo definito da kr .

Se, dunque , N ≥ 2a1k1 , l’universo deve contenere una classe Γkn – 1 o Γn ( dal momento che kn – 1 = n ) di n elementi che sono contenuti nella Γkr per ogni r ( r = 1 , 2 , … , n -1 ). Siano i suoi n membri, nell’ordine dato loro da R , y1 , y2 , . . . , yn . Allora per ogni r minore di n , y1 , y2 , . . . , yn sono contenuti in Γkr e tutte le r combinazioni di queste concordano nelle possibilità che soddisfino con riferimento a ciascuna funzione di r variabili. Siano ys1, ys2, …,ysr ( s1 < s2 < … < sr ) una tale combinazione , e Χ0 una funzione di r variabili. Allora ys1, ys2, …,ysr sono nell’ordine dato loro da R, e così sono y1 , y2 , . . . , yr; di conseguenza il fatto che queste due combinazioni concordano nelle possibilità che esse realizzano rispetto a Χ0 significa che Χ0 è vero per le stesse permutazioni di ys1, ys2, …,ysr come è di y1 , y2 , . . . , yr. La alternativa vera per y1 , y2 , . . . , yn è quindi seriale in Χ0, e allo stesso modo è seriale in ogni altra funzione di qualsiasi numero di variabili r 1; ed è pertanto un’alternativa seriale .

1 Abbiamo dimostrato questo, quando r < n , possiamo anche avere r = n , ma allora non c’è nulla da dimostrare in quanto in una funzione di n variabili ogni alternativa è seriale.

La nostra condizione è , dunque, dimostrata essere necessaria in qualsiasi universo di almeno 2a1k1, membri dove k1 è dato da

Schermata 2014-02-07 alle 08.12.49 traduzione

Per universi compresi tra n e 2a1k1 non abbiamo trovato una condizione necessaria e sufficiente per la coerenza della formula, ma è evidentemente possibile determinarla per tentativi se una data formula è coerente in uno qualsiasi di tali universi.

III

Considereremo ora come diventano i nostri risultati quando la nostra formula

( x1 , x2 , … , xn ) F ( φ , X , Ψ , … , = , x1 , x2 , … , xn)

contiene oltre all’identità una sola funzione φ di due variabili .

In questo caso abbiamo due funzioni φ0 , Ψ0 date da

φ0 ( yi , yk ) = φ ( yi , yk ) ( i ≠ k) ,

Χ0 ( yi ) = φ ( yi , yi ) ,

così che a1 = 1 , a2 = 1 , ar = 0 quando r > 2 . Di conseguenza,

k2 = k3 = … = kn- 1 = n e k1 = h (2, n , 4) ;

ma l’argomento alla fine della parte prima mostra che possiamo prendere invece k1 = n ! ! ! , e la nostra condizione necessaria e sufficiente per la coerenza si applica a qualsiasi universo con almeno 2 . n ! ! ! particolari.

In questo semplice caso possiamo presentare la nostra condizione in una forma più evidente come segue.

È necessario e sufficiente per la coerenza della formula che sia vera quando φ è sostituito da almeno uno dei seguenti tipi di funzioni: –

( 1 ) La funzione universale x = x . y = y .

( 2 ) La funzione nulla x ≠ x . y ≠ y .

( 3 ) Identità x = y .

( 4 ) Differenza x ≠ y .

( 5 ) Una funzione seriale che ordini l’intero universo in una serie ,ossia che soddisfa

( a) ( x ) ~ φ ( x, x ) .

( b ) ( x , y ) [ x = y v { φ ( x , y ) . ~ Φ ( x, y ) } v { φ ( x, y. ) . ~ φ ( x , y ) } ] .

( c ) ( x , y . z ) { ~ φ ( x, y ) v ~ φ ( y, z ) v φ ( x , z ) } .

( 6 ) Una funzione che ordini l’intero universo in una serie, ma che contenga anche tra gli altri membri sé stessa, cioè che soddisfi

(a ‘ ) ( x ) φ ( x , x )

e ( b ) e ( c ) come in ( 5 ) .

I tipi da ( 1 ) a ( 4) comprendono una sola funzione ciascuno; per quanto riguarda i tipi ( 5 ) e ( 6) , è irrilevante il tipo di funzione che assumiamo, dato che se si soddisfa la formula così, possiamo vedere che soddisfa tutte le altre.1

1 Un risultato ottenuto in precedenza per il tipo ( 5 ) da Langford , op. cit.

Dobbiamo dimostrare questa nuova forma della nostra condizione, mostrando che P conterrà completamente un seriale An se e solo se è soddisfatto dalle funzioni di almeno uno dei nostri sei tipi. Ora un’alternativa in  n di y è seriale in Χ0 se contiene

Schermata 2014-02-07 alle 09.22.00 traduzione

ma non altrimenti , e sarà seriale in φ0 se contiene

Schermata 2014-02-07 alle 09.22.08 traduzione

Ci sono quindi complessivamente otto alternative seriali sia per φ0 e Χ0 ottenute combinando uno di ( i) , ( ii ) con qualsiasi di ( a) , ( b ) , ( c) , ( d ); ma queste alternative seriali otto danno origine solo a sei forme seriali, poiché le alternative ( i) (b) e ( i) ( c ) possono essere ottenute l’una dall’altra invertendo l’ordine della y e quindi appartengono alla stessa forma, e così accade per le alternative ( ii ) ( b ) e ( ii ) ( c ).

E’ anche facile vedere che qualsiasi formula contenente esclusivamente una di queste sei forme seriali verrà soddisfatta da tutte le funzioni di uno dei sei tipi secondo lo schema

forma                 ( i) ( a)       (i ) ( b e c )         (i ) ( d )      ( ii ) ( a)        ( ii ) ( b e c)        ( ii ) ( d )

Tipo di funzione    1                6                         3                 4                 5                         2

e che viceversa una formula soddisfatta da una funzione di uno dei sei tipi devono contenere esclusivamente la forma corrispondente. Per esempio , una funzione del tipo 6 soddisferà l’alternativa ( i) ( b ) quando y1 , y2 , . . . , yn sono nel loro ordine nella serie determinata dalla funzione, e quando y1 , y2 , . . . , yn sono in qualsiasi altro ordine che la funzione soddisferà un’alternativa della stessa forma.

Nel linguaggio della teoria dei sistemi postulato possiamo interpretare il nostro universo come una classe K, e concludere che un sistema postulato su una base ( K , R ) costituita esclusivamente da leggi generali che coinvolgono al massimo n elementi sarà compatibile con K avente tanti  membri  quanti 2 . n ! membri se e solo se può essere soddisfatta da una R di uno dei sei tipi .

IV

In conclusione , indichiamo brevemente come estendere il nostro metodo per determinare la coerenza o l’incoerenza delle formule del tipo più generale

( ∃ z1, z2 , … , zm ) ( x1 , x2 , … , xn ) F ( φ , Χ , Ψ , … , = , z1, z2 , … , zm , x1 , x2 , … , xn)

che hanno nella forma normale entrambi i tipi di prefisso, ma soddisfano la condizione che tutti i prefissi di esistenza precedono tutti quelli di generalità .

Come prima , possiamo supporre F rappresentato come una disgiunzione di alternative e scartare quelle che violano le leggi di identità. Possiamo raggruppare quelle rimaste in base ai valori di identità e differenza per argomenti tratti completamente dalle z . Possiamo definiamo tale insieme di valori di identità e differenza con Hi ( = , z1, z2 , … , zm ) , e F può essere messo nella forma

( H1 . F1 ) v ( H2 . F2 ) v ( H3 . F3 ) v … ,

e l’intera formula è equivalente a una disgiunzione di formule.

( ∃ z1, z2 , … , zm ) { H1 ( = , z1, z2 , … , zm ) . ( x1 , x2 , … , xn ) F1 ( φ , … , = z1 , … , zm , x1 , … , xn ) } v ( ∃ z1, z2 , … , zm ) { H2 ( = , z1 , … , zm ) . ( x1 , x2 , … , xn ) F2 ( φ , …. , = , z1 , … , zm , x1 , … , xn) } v ecc

Dal momento che se una qualsiasi di queste formule è coerente è coerente la sua disgiunzione, e se la sua disgiunzione è una coerente, almeno uno dei suoi termini deve essere coerente, è sufficiente per noi di mostrare come determinare la coerenza di uno di essi, diciamo il primo.

In questo H1 ( = , z1, z2 , … , zm ) è un insieme coerente di valori di identità e differenza per ogni coppia di z. Rinumeriamo le z z1 , z2 , …. , zμ utilizzando lo stesso suffisso per ogni insieme di z che sono identici in H1, e la nostra formula diventa

( ∃ z1, z2 , … , zμ ) ( x1 , x2 , … , xn ) F1 ( φ , Χ … , = z1, z2 , … , zμ , x1 ,.. , xn ) , (i )

in cui si comprende che due di z con differenti suffissi sono sempre diverse.

Ora, supponendo che l’universo abbia almeno μ + n elementi, consideriamo le diverse possibilità per quanto riguarda le x di essere identiche alle z, e riscriviamo la nostra formula

Schermata 2014-02-07 alle 09.48.06

in cui ⊃ significa ‘ se , allora’ e

G ( φ , … , xn) = Π F1 ( φ , Χ , … , = , z1 , … zμ , θ1 , θ2 , …. θn ) ,

il prodotto essendo assunto da

θ1 = x1 , z1, z2 , . . . , zμ ,

θ2 = x2 , z1, z2 , . . . , zμ ,

……. ….

θn = xn , z1, z2 , . . . , zμ ,

e in G qualsiasi termine xi = zj è sostituito da una falsità (ad esempio xi ≠ xi ) che non comprende nessun z .

Quindi modifichiamo G introducendo nuove funzioni. In G si verificano i valori di, ad esempio φ , con argomenti alcuni dei quali alcuni sono z e alcuni x; da questi si definiscono le funzioni delle x solo semplicemente considerando le z come costanti, e chiamiamo queste nuove funzioni φ0 , Χ0 , . . .. Sostituiamo i valori di φ , Χ , Ψ , . . . , che non comprendono nessuna x tra i loro argomenti, con le proposizioni costanti p , q , . . . Gli unici valori di identità in G sono nella forma xi = xj e lasciamo solo questi. Supponiamo che da questo processo G diventi

L ( φ , Χ , Ψ , … , φ0 , Χ0 , …. , p , q , … , = , x1 , x2 , … , xn) .

Allora la coerenza della formula ( i) in un universo di N termini è evidentemente equivalente alla coerenza in un universo di N – μ termini della formula

( x1 , x2 , … , xn ) L ( φ , Χ , Ψ , … , φ0 , Χ0 , …. , p , q , … , = , x1 , x2 , … , xn)

Ma questa è una formula del tipo precedentemente affrontato, ad eccezione delle proposizioni variabili p , q , . . . , che sono facilmente eliminate considerando i diversi casi della loro verità e falsità, essendo la formula coerente se è coerente in uno di questi casi .

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: