Newsgroup: it.hobby.enigmi
Titolo: Indecidibile?

 il che e' una contraddizione.
La mia richiesta è: c'è qualcuno che mi chiarisce le idee? Precisamente su
questo passo:
"... se il teorema e' falso, lo si puo' mostrare esplicitamente esibendo una
mappa che non possa esser colorata con quattro colori. Percio' se il teorema
e' indimostrabile deve esser vero."
In pratica si dice:
   teorema falso => dimostrabile che lo è
Quindi, invertendo l'implicazione:
   indimostrabile (indecidibile) => teorema vero
Dovrei aver capito bene? Il problema è che secondo me si sono sbagliate le
implicazioni, che dovrebbero essere:
   teorema falso => falsità mostrabile con un esempio concreto
   falsità non mostrabile con un esempio concreto => teorema vero
Il che dovrebbe essere banale. Sbaglio o quel cosmologo ha preso una
cantonata?
Anche perché poi aggiunge:
"...non possiamo dimostrare che esso e' indimostrabile, in quanto cio'
equivale a dimostrare che esso e' vero, il che e' una contraddizione."
Io questa contraddizione non la vedo, e voi?
MaxArt

Nessuna cantonata.
 L'idea è che esistano affermazioni che non possono essere indimostrabili
per principio, eccone alcune
- P=n^2!!/(n-3)!^(n!-5n)-1   genera solo numeri primi  [ non testatela, sono
lettere a caso]
- il teorema T è indimostrabile [per ogni teorema T]
-il teorema dei 4 colori
consideriamo la prima. Per assurdo sia essa indimostrabile, allora
testandola per i primi 10 n essa genera solo primi, altrimenti avremmo
dimostrato che è falsa, così per i primi 100 n, e 1000 n, e in definitiva
per ogni n, quindi essa è vera. Assurdo.
La seconda. Sia indimostrabile che il teorema T è indimostrabile. Allora
ovviamente non esiste una dimostrazione di T, altrimenti T è dimostrabile,
quindi T è indimostrabile.Assurdo.
La terza. Sia T4C indimostrabile, allora nessuno esibirà mai una cartina non
colorabile con 4 colori, altrimenti il teorema sarebbe falso, quindi il
teorema è vero. assurdo.
Ciao. marc

Tra le questioni ancora aperte delle stesso tipo c'è anche la più importante
di tutte, la congettura di Riemann. Essa è certamente dimostrabile.
Resta un quesito:
Se la proposizione P è dimostrabile, allora essa è certamente dimostrabile
da un uomo (\donna)?   [congettura di cip e ciop]
Consideriamo il teorema dell'arresto : non esiste un programma P in grado di
decidere per ogni input N (dove N è un programma) se N si arresta o meno
D'altra parte con argomentazioni analoghe alle precedenti si mostra che per
ogni N, N è decidibile [in breve, se N indecidibile allora non si arresterà,
assurdo!]
Quindi o la congettura di cip e ciop è vera, allora il cervello non è una
Macchina di Turing [ e tra parentesi [infatti ci sono le parentesi [ancora
[...]] saltano tutti i programmi di intelligenza artificiale basati sui
computers] oppure noi siamo MdT, allora la congettura di cip e ciop è falsa
[allora accade che la congettura di Riemann potrebbe essere "umanamente
indimostrabile" pur essendo "dimostrabile in se"]
A naso una dimostrazione non è che una fila finita di caratteri scelti in un
alfabeto finito, si direbbe così che ogni dimostrazione è " umanabile"
(scopribile dall'uomo). Quindi non siamo MdT? La cosa tende al teologico,
io, ateo e  materialista, per il momento mi fermo qui.
Ciao, marc

per ogni n, quindi essa è vera. Assurdo.
Mah, veramente il poco che so (o credo di aver capito) sulle teorie
formali mi dice che "dimostrabile" (sintatticamente) non concide con
"vero" (semanticamente).
Un enunciato può essere semanticamente vero per tutte le
interpretazioni che verificano gli assiomi (tali interpretazioni
diconsi "modelli" della teoria), ma può non esistere una dimostrazione
formale (cioè non è un teorema).
Dunque non riesco a vedere dove sta l'assurdo; cioè non credo vi sia
contraddizione tra "indimostrabile" e "vero".
Per esempio la congettura di Goldbach ("ogni numero pari maggiore di 2
è somma di due numeri primi") potrebbe essere vera ma non
dimostrabile.
--
----------------------------------------------------------------------
Marco Coletti
Network Admin, Webmaster, Tuttologo :)
PGP public key:
http://keys.pgp.com:11371/pks/lookup?op=get&exact=on&search=0x96A79061
Fingerprint: 9F E5 80 61 F6 9F 05 2D  EA 53 6F 2D 82 8B C7 C2
----------------------------------------------------------------------

 > il che e' una contraddizione.
Abbiamo visto che se il teorema e' indimostrabile allora il teorema e'
vero, ma questa non e' una dimostrazione del teorema! E' una
meta-dimostrazione, non una dimostrazione formale (non puo' essere
espressa all'interno del sistema). Il teorema sarebbe vero (perche'
l'abbiamo meta-dimostrato) ma comunque non dimostrabile. E non si
avrebbe nessuna contraddizione.
PS. Non vorrei riaprire una discussione che periodicamente torna su
it.scienza, ma a quanto ne so il teorema dei 4 colori e' stato
dimostrato.
ciao,
	Em.

 dimostrabile.
L'assurdo sta nel fatto che il fatto di essere indimostrabile implicherebbe
che č vera,
e quindi, dimostrata !!!...
Il fatto che si possa dimostrare che una proposizione č indimostrabile,
significa proprio
che PUO' essere sia vera che falsa, ma che non si puň dimostrare né l'una né
l'altra
ipotesi.
--
Er Roscio.

 wrote:
: > Dunque non riesco a vedere dove sta l'assurdo; cioč non credo vi sia
: > contraddizione tra "indimostrabile" e "vero".
: > Per esempio la congettura di Goldbach ("ogni numero pari maggiore di 2
: > č somma di due numeri primi") potrebbe essere vera ma non
: > dimostrabile.
: 
: L'assurdo sta nel fatto che il fatto di essere indimostrabile implicherebbe
: che č vera, e quindi, dimostrata !!!...
Non credo comunque che una congettura come quella di Goldbach (che si puo`
"dimostrare" con una quantita` "semplicemente" numerabile di esempi) possa
essere indimostrabile. Ma lascio la parola ai logici matematici.
ciao, .mau.

 essere indimostrabile. Ma lascio la parola ai logici matematici.
Scusa, ma non ti seguo... non mi sembra proprio che la congettura di
Goldbach
si possa dimostrare verificando TUTTI i numeri naturali pari... caso mai se
ne può
dimostrare la falsità non appena si trova un numero che non può essere
espresso
come somma di due numeri primi. E' un po' quello che è successo col teorema
della
mappa a quattro colori che, se non erro, qualche anno fa è stato confutato
da una
mappa "incolorabile"...
--
Er Roscio.

 wrote:
: > Non credo comunque che una congettura come quella di Goldbach (che si puo`
: > "dimostrare" con una quantita` "semplicemente" numerabile di esempi) possa
: > essere indimostrabile. Ma lascio la parola ai logici matematici.
: 
: Scusa, ma non ti seguo... non mi sembra proprio che la congettura di
: Goldbach si possa dimostrare verificando TUTTI i numeri naturali pari... 
Non ho scritto `dimostrare' ma `"dimostrare"' :-)
Quello che intendevo dire era che visto che il numero di operazioni da fare
e` numerabile e gli assiomi di Peano accettano in pratica il numerabile al
loro interno, mi sembrerebbe strano che una simile proposizione fosse
indecidibile. Se ci pensi, l'ipotesi del continuo *supera* la
numerabilita`.
: E' un po' quello che è successo col teorema della
: mappa a quattro colori che, se non erro, qualche anno fa è stato confutato
: da una mappa "incolorabile"...
???? Questo l'hai sognato.
ciao, .mau.

 wrote:
: : E' un po' quello che è successo col teorema della
: : mappa a quattro colori che, se non erro, qualche anno fa è stato confutato
: : da una mappa "incolorabile"...
: ???? Questo l'hai sognato.
   Forse era il famoso pesce d'aprile di Martin Gardner, che in un
articolo parlo` di presunte scoperte scientifiche immeritatamente
ignorate, tra cui questa, una confutazione della relativita`, l'invenzione
dello sciacquone da parte di Leonardo e altre...
Ciao,
							Daniele

equivale a dimostrare che esso e' vero, il che e' una contraddizione."


 wrote:
: : : E' un po' quello che è successo col teorema della
: : : mappa a quattro colori che, se non erro, qualche anno fa è stato confutato
: : : da una mappa "incolorabile"...
: 
: : ???? Questo l'hai sognato.
: 
:    Forse era il famoso pesce d'aprile di Martin Gardner
Ah si`, adesso lo ricordo :-)
ciao, .mau.

 ciao, .mau.
AZZ... Davvero?... E io che credevo che ci fossimo tolti un "problema"
davanti...
:-))))))))))))))))))))))))))
--
Er Roscio.

 wrote:
: > :    Forse era il famoso pesce d'aprile di Martin Gardner
: >
: > Ah si`, adesso lo ricordo :-)
: 
: AZZ... Davvero?... E io che credevo che ci fossimo tolti un "problema"
: davanti...
Perche`? il teorema dei 4 colori e` stato regolarmente dimostrato.
E chi si lamenta del tipo di dimostrazione (enumerativa, dopo avere
ovviamente dimostrato che ogni mappa puo` essere ridotta a una che fa parte
di un numero finito di configurazioni) deve anche lamentarsi della
dimostrazione che non esistono quadrati greco-latini di ordine 6.
.mau.

essere indimostrabile.
La cardinalita' degli esempi non c'entra. La famosa proposizione
indimostrabile ma vera di Goedel e' appunto verificata semanticamente
da tutti i numeri naturali nell'interpretazione standard (quindi ben
piu' "dimostrata" della congettura di Goldbach) ma non per questo e'
dimostrabile sintatticamente. Ciao

 comune utilità.
Scusate, ma evidentemente il cosmologo parlava quando ancora il teorema dei
4 colori non era stato ancora dimostrato.
Solo un precisazione.
MaxArt

 wrote in message
8dgd3j$9jf$1...@pegasus.tiscalinet.it...

Si', infatti la sua lettera risale al 1960.
Per ISM voglio ripostare la risposta di Martin Gardner:
***
    La situazione e' un po' meno tragica quando ci rendiamo conto che un
teorema indecidibile secondo Godel entro un dato sistema deduttivo puo'
sempre esser deciso metamatematicamente ampliando il sistema. Se il
teorema dei quattro colori venisse riscontrato esser indecidibile
secondo Godel entro un sistema basato su certi postulati di topologia e
teoria degli insiemi, esso diverrebbe automaticamente *vero* (come
Sciama chiarisce), ma *vero* nel senso metamatematico di esser
decidibile in un sistema ampliato, magari un sistema in cui lo stesso
teorema della mappa sarebbe un nuovo postulato.
***
Dennis Sciama e' il cosmologo inglese in questione.
Non aggiungo altro perche' non sarei in grado :-(...
Ciao ciao
Claudio
--
*Nessuno sa che quest'affermazione e' vera!*
da *Impossibilita'* di John D. Barrow