From 5a5b5798211665f9c24753c9151050cec8351c55 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 30 Oct 2023 08:05:38 +0100
Subject: A remark on arity.

---
 transp-inf110-01-calc.tex | 53 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 050ee4f..15f5e79 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -1400,6 +1400,59 @@ fonctions générales récursives.
 Les manipulations de programmes sont typiquement p.r. (même si les
 programmes manipulés sont des fonctions générales récursives).
 
+\end{frame}
+%
+\begin{frame}
+\frametitle{Arité et encodage des tuples}
+
+{\footnotesize\textcolor{gray}{Remarque qui aurait dû être faite
+    avant ?}\par}
+
+\bigskip
+
+Pour tout $k \geq q$, les fonctions
+\[
+\left\{
+\begin{array}{l}
+\mathbb{N}^k \to \mathbb{N}\\
+(x_1,\ldots,x_k) \mapsto \dbllangle x_1,\ldots,x_k\dblrangle
+\end{array}
+\right.
+\quad\text{~et~}\quad
+\left\{
+\begin{array}{l}
+\mathbb{N} \to \mathbb{N}\\
+\dbllangle x_1,\ldots,x_k\dblrangle \mapsto x_i
+\end{array}
+\right.
+\]
+sont p.r.  Par conséquent,
+\[
+f\colon\mathbb{N}^k \dasharrow \mathbb{N}\text{~récursive}
+\;\Longleftrightarrow\;
+\left\{
+\begin{array}{l}
+\mathring f\colon\mathbb{N} \dasharrow \mathbb{N}\\
+\hphantom{f\colon}
+\dbllangle x_1,\ldots,x_k\dblrangle \mapsto f(x_1,\ldots,x_k)
+\end{array}
+\right.\text{~récursive}
+\]
+et de plus, un numéro $e$ de $f$ (i.e., $f = \varphi^{(k)}_e$) se
+calcule de façon p.r. à partir d'un numéro $e'$ de $\mathring f$
+(i.e., $\mathring f = \varphi^{(1)}_{e'}$) et vice versa.
+
+\medskip
+
+Ceci justifie d'omettre parfois abusivement l'arité
+
+(par défaut, « $\varphi_e$ » désigne « $\varphi^{(1)}_e$ »).
+
+\bigskip
+
+{\footnotesize Même chose, \textit{mutatis mutandis} (avec $\psi$)
+  pour les fonctions p.r.\par}
+
 \end{frame}
 %
 \begin{frame}
-- 
cgit v1.2.3