49 lines
2.4 KiB
Markdown
49 lines
2.4 KiB
Markdown
---
|
|
up:
|
|
tags:
|
|
aliases:
|
|
---
|
|
|
|
> [!definition] [[fonction partielle]]
|
|
> Une fonction partielle de $\mathbb{N}^{p} \to \mathbb{N}$ est un couple $(A, f)$ où $A \subseteq \mathbb{N}^{p}$ et $f$ est une [[application]] de $A \to \mathbb{N}$.
|
|
> - i $A$ est appelé **domaine de définition** de la fonction
|
|
> - i si $(a_1, a_2,\dots, a_{p}) \notin A$ on dira que la fonction **n'est pas définie** en $(a_1, a_2, \dots, a_{p})$
|
|
> - so Deux fonctions partielles sont égales si elles ont le même domaine de définition, et si elles sont égales sur ce domaine
|
|
^definition
|
|
|
|
- une fonction partielle définie partout est une [[fonction totale]]
|
|
|
|
> [!info] Notations
|
|
> On notera :
|
|
> - $f$ pour désigner, le couple $(A, f)$
|
|
> - $\mathscr{F}^{*}_{p}$ l'ensemble des [[fonction partielle|fonctions partielles]] de $\mathbb{N}^{p} \to \mathbb{N}$
|
|
> - $\mathscr{F}^{*} = \bigcup _{p \geq 0} \mathscr{F}_{p}^{*}$
|
|
>
|
|
> - ! on réservera le mot "fonction" aux [[fonction totale|fonctions totales]]
|
|
>
|
|
^notations
|
|
|
|
# Définitions supplémentaires
|
|
|
|
> [!definition] Composition
|
|
> Soient $f_1, f_2, \dots, f_{n} \in \mathscr{F}_{p}$ et $g \in \mathscr{F}_{n}$
|
|
> La **fonction composée** $h = g(f_1, f_2, \dots, f_{n})$ est l'élément de $\mathscr{F}^{*}_{p}$ défini comme suit :
|
|
> - $h(x_1, x_2, \dots, x_{p})$ n'est pas définie si l'une des $f_{i}(x_1, x_2, \dots, x_{p})$ n'est pas défini ou si, toutes l'étant, $g(f_1(x_1, x_2, \dots, x_{p}), f_2(x_1, x_2, \dots, x_{p}), \dots, f_{n}(x_1, x_2, \dots, x_{p}))$ n'est pas définie
|
|
> - Dans le cas contraire, $h(x_1, x_2, \dots, x_{p}) := g(f_1(x_1, x_2, \dots, x_{p}), f_2(x_1, x_2, \dots, x_{p}), \dots, f_{n}(x_1, x_2, \dots, x_{p}))$
|
|
^composition
|
|
|
|
> [!definition] Récurrence
|
|
> Soient $g \in \mathscr{F}^{*}_{p}$ et $h \in \mathscr{F}^{*}_{p+2}$
|
|
> Il existe une et une seule fonction $f \in \mathscr{F}^{*}_{p+1}$ vérifiant les conditions suivantes :
|
|
> - $\forall (\overline{x}) \in \mathbb{N}^{p},\quad f(\overline{x}, 0) = g(\overline{x})$ (donc, $f(\overline{x}, 0)$ est définie si et seulement si $g(\overline{x})$ l'est, et lui est égale dans ce cas)
|
|
> - $\forall (\overline{x}, y) \in \mathbb{N}^{p+1},\quad f(\overline{x}, y+1) = h (\overline{x}, y, f(\overline{x}, y)$ (même remarque que plus haut)
|
|
> - i on dira que $f$ est **définie par récurrence à partir de $g$ et $h$**
|
|
^recurrence
|
|
|
|
![[schéma mu]]
|
|
|
|
# Propriétés
|
|
|
|
# Exemples
|
|
|