sal a écrit :
Je crois que vous voulez dire la logique de premier ordre, n'est-ce
pas? Dans la logique de premier ordre on ne peut pas quantifier sur
les ensembles, et, par consequent, on ne peut pas exprimer le concept
"dénombrable".
On peut quantifier sur les ensembles en logique du premier ordre: ZF est une théorie du premier ordre.
En revanche, le logique du second ordre est plus fort,
et on peut exprimer le concept "dénombrable" la-bas, bien sûr.
Inutile de sortir le bazooka pour écraser une mouche: l'arithmétique du second ordre est suffisante pour formaliser les réels; d'ailleurs on l'appelle l'«analyse» à cause de cela.
Très joli! L'ensemble des machines de Turing, il es dénombrable;
l'ensemble de machines que ne boucle pas, il es dénombrable aussi;
mais, l'ensemble de machines que boucle, il n'est pas dénombrable!
Merci; trés chouette.
Notez que la formule «il existe une bijection entre les entiers et les machines de Turing qui bouclent» n'est pas contradictoire, tout comme «il existe un cardinal inaccessible» ou «il existe une méthode pour multiplier les lingots d'or à l'infini».
--
Joe Cool
