Théorème de Tarski

D'accord, merci Foys. On évalue la formule récursivement, par exemple $E(\overline{P \wedge Q})= E(\overline{P}) \wedge E( \overline{Q})$, mais on définit $E$ en fonction de $E$ en faisant comme ça ?

On peut procéder comme ça: on définit une fonction $f$ de $\omega$ dans $\{0,1\}$ par récurrence (par $f(\overline{P \wedge Q})=f( \overline{P}) \wedge f(\overline{Q})$ et $f( \overline{\forall x_1, P(x_1)})= \bigwedge_{r\in \N}f(\overline{P(r)})$, etc... On a donc besoin de considérer le graphe de $f$, donc de se placer dans la théorie des ensembles et pas simplement dans l'arithmétique de Peano. Ensuite on définiit $E( \overline{P})=(f( \overline{P})=1)$