From 2e5991760ea27bc61a51f2497036e08bec3a3c17 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 22 Nov 2023 11:13:01 +0100 Subject: A few clarifications on stability of decidable and semidecidable sets. --- transp-inf110-01-calc.tex | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 6dc00b7..269df80 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -2566,7 +2566,9 @@ Les ensembles \textbf{décidables} sont stables par : \item intersections finies, \item complémentaire, \item \alert{mais pas par} projection $\mathbb{N}^k \to - \mathbb{N}^{k'}$ (où $k'\leq k$ ; cf. transp. précédent). + \mathbb{N}^{k'}$ (où $k'\leq k$).\\ {\footnotesize (Le problème de + l'arrêt est une projection d'un ensemble décidable, + cf. transp. précédent.)} \end{itemize} \bigskip @@ -2575,8 +2577,10 @@ Les ensembles \textbf{semi-décidables} sont stables par : \begin{itemize} \item réunions finies (par lancement en parallèle !), \item intersections finies, -\item projection $\mathbb{N}^k \to \mathbb{N}^{k'}$ (où $k'\leq k$ ; - cf. transp. précédent), +\item projection $\mathbb{N}^k \to \mathbb{N}^{k'}$ (où $k'\leq + k$),\\ {\footnotesize (Les ensembles semi-décidables sont + projections d'ensembles décidables donc sont eux-mêmes stables par + projections, cf. transp. précédent et idées proches.)} \item \alert{mais pas par complémentaire}. \end{itemize} -- cgit v1.2.3