« Introduction aux mathématiques/Rudiments de logique » : différence entre les versions
Contenu supprimé Contenu ajouté
Ligne 702 :
==Somme, produit et division euclidienne dans <math>\mathbb{N}</math>==
===Définitions de la somme et du produit dans <math>\N</math>===
On a bien sur reconnu en <math>\N</math> notre ensemble usuel pour compter, ceci fera l'objet du prochain chapitre, mais avant cela il nous faut donner un sens à l''''addition''' et la '''multiplication'''. Faisons le proprement ici : Pour un élément <math>m\in\N</math>, on définit la suite suivante par récurrence : <math>\begin{cases}s^m_0=m \\ s^m_{\sigma(n)}=\sigma(s^m_n), \forall n\geq 1\end{cases}</math>. On note alors <math>m+n:=s^m_n</math>.
{{Théorème|titre=Proposition|contenu=
<math>\forall m\in\N,\, m+0=0+m=m</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
Que <math>m+o=m</math> résulte de la définition.<br />
On montre l'autre égalité par récurrence sur <math>m</math>. L'initialisation est encore la définition de la somme. Supposant que <math>0+m=m</math>, on en déduit <math>0+\sigma(m)=s^0_{\sigma(m)}=\sigma(s^0_m)=\sigma(0+m)=\sigma(m)</math>. Ceci étant valable pour tout <math>m\in\N</math>, on conclut grâce au théorème de récurrence.
}}
On remarque alors que <math>\forall n\in\N,\, \sigma(n)=\sigma(n+0)=\sigma(s^n_0)=s^n_{\sigma(0)}=n+\sigma(0)=n+1</math>. Dorénavan, on utilisera volontiers cette égalité.
Exercice : Montrer qu'on à également <math>\forall n\in\N,\, \sigma(n)=1+n</math>
{{Théorème|titre=Proposition|contenu=
<math>\forall m,n,p\in\N,\, (m+n)+p=m+(n+p)</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On récure sur <math>p\in\N</math> :
* La proposition précédente donne l'initialisation : <math>\forall m,n\in\N,\, (m+n)+0=m+n=m+(n+0)</math>.
* Pour l'hérédité on suppose <math>(m+n)+p=m+(n+p)</math>, alors <math>(m+n)+\sigma(p)=s^{m+n}_{\sigma(p)}=\sigma(s^{m+n}_p)=\sigma((m+n)+p)=\sigma(m+(n+p))=\sigma(s^m_{n+p})=s^m_{\sigma(n+p)}=m+\sigma(s^n_p)=m+(n+\sigma(p))</math>, et de conclure.
}}
{{Théorème|titre=Proposition|contenu=
<math>\forall m,n\in\N,\, m+n=n+m</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
On récure (avec l'éponge, oui oui) sur <math>\forall m\in\N</math> en posant <math>\mathcal{P}(n)=\forall m\in\N,\, m+n=n+m</math>.<br />
* Initialisation : c'est la première proposition.
* Hérédité : On suppose donc que <math>\forall m\in\N,\, m+n=n+m</math>, et on constate que <math>m+\sigma(n)=m+(n+1)=(m+n)+1=(n+m)+1=n+(m+1)=n+(1+m)=(n+1)+m=\sigma(n)+m</math>. On conclut comme précédemment.
}}
Remarque : On résumera bientôt c'est trois propositions en disant que <math>(\N,+)</math> est un monoïde commutatif.
Exercice :
# En lisant les preuves, bien justifier (dans sa tête, ça suffit) chaque égalité, par exemple quand a-t-on utilisé l'exercice précédent ?
# A titre d'entraînement faire les preuves des propositions suivantes concerant la multiplication.
On définit maintenant à <math>m</math> fixé dans <math>\N</math>, la suite <math>\begin{cases}p^m_0=0 \\ p^m_{\sigma(n)}=p^m_n +m, \forall n\geq 1\end{cases}</math>, et on note bien sur <math>m\times n:=p^m_n, \forall m,n\in\N</math>, bien qu'on omette souvent le signe <math>\times</math> ou qu'on le remplace par <math>\cdot</math>.
{{Théorème|titre=Proposition|contenu=
<math>\forall m\in\N,\, m\times 1=1\times m=m</math>.<br />
<math>\forall m,n,p\in\N,\, (mn)p=n(mp)</math>.<br />
<math>\forall m,n\in\N,\, mn=nm</math>.
}}
===Liens avec l'ordre, division euclidienne===
{{Théorème|titre=Théorème|contenu=
Soit <math>(a,b)\in\N\times\N^*</math>. ( où <math>\N^*:=\N\setminus\{0\}</math>).<br />
Alors <math>\exists!(q,r)\in\N^2/ a=bq+r \text{ et } 0\eq q <r</math>.<br />
<math>q</math> (resp: <math>r</math>) est appelé le '''quotient''' (resp: le '''reste''') de la division euclidienne de <math>a</math> par <math>b</math>.
}}
{{boîte déroulante|align=left|alignT=center|titre=Preuve|contenu=
}}
=Rudiments de combinatoire=
| |||