Préparation à la première SM (La logique)

On a





Donc

f(m.n)=f(m).(n) et f(2)=2 quelque soit m et n e lN²

on a f(m.n)=f(n.m) donc f(m.).n=f(n.).m Poson m =2

on aura

2n=2f(n)

n=f(n)

alors la fonction est f(x)=x

On cherche toutes les fonctions f strictement croissantes définies de IN vers IN qui satisfont la condition:



Puisque f est strictement croissante sur IN, donc f est injective.

Soit P(m,n) l'assertion: f(m.n)=f(m).f(n)

P(1,1)=> f(1.1)=f(1).f(1) => f(1)=f(1)² => f(1)=0 ou f(1)=1

On suppose que f(1)=0, on a donc:

P(m,1)=> f(m.1)=f(m).f(1) => f(m)=f(m).0=0

Donc pour tous entier naturel m on a: f(m)=0, ce qui est contradictoire avec le fait que f est injective.

On conclut que f(1)=1.

De même, on montre que f(0)=0.

Maintenant, montrons par récurrence que: .

Clairement, la relation est vérifiée pour m=0 et m=1.

Hérédité: On suppose que:

Et on montre que: f(n+1)=n+1.

Pour cela, on va faire une petite disjonction de cas:

* Si n est est impair, donc (n+1)/2 est pair, donc:

Puisque n est impair et n>1, on a donc n> 2

=> 2n-n>2 => 2n>n+2 =>

Donc la relation de récurrence est vérifiée pour . On a donc:







.

* Si n est pair, donc n+2 est pair, donc: .

Et puisque n>2 => 2n-n>2 => 2n>n+2 => n>(n+1)/2.

Donc la relation de récurrence est vérifiée pour (n+1)/2.

On a donc:





.

On a f est strictement croissante donc:

f(n+2)>f(n+1) et f(n+1)>f(n).

Et puisque f(n+2)=n+2 et f(n)=n et n+2>n+1>n.

On conclut que f(n+1)=n+1.

Dans les deux cas (n est pair et n est impair) on a: f(n+1)=n+1.

Synthèse de la récurrence:

Pour tous entier naturel n on a: f(n)=n.

Réciproquement, considérons la fonction f: IN ->IN f(n)=n.

On a: * f est strictement croissante sur IN.

* f(m)=m et f(n)=n donc f(m)f(n)=mn et f(mn)=mn d'où: f(m)f(n)=f(mn).

Donc la seule fonction qui satisfait la condition de l'exercice est l'identique sur IN.

Par l'absurde, supposons que pour tout k de A, on a x_{k}-k. Donc:

- x_{1}-1 est impair => x_{1} est pair

- x_{2}-2 est impair => x_{2} est impair

- x_{3}-3 est impair => x_{3} est pair

Et ainsi de suite, jusqu'à:

- x_{n}-n est impair => x_{n} est pair (car n est impair)

Donc l'ensemble {x_{1}, x_{2}, x_{3}, .... , x_{n}}=A contient plus d'éléments pairs que d'éléments impairs.

Et puisque A={1, 2, .... , n} et n est impair, on conclut que l'ensemble A contient plus d'éléments impairs que d'élément pairs.

Donc contradiction, d'où: il existe un élément k de A tel que x_{k}-k soit pair.

Par l'absurde, supposons que pour tout k de A, on a x_{k}-k. Donc:

- x_{1}-1 est impair.

- x_{2}-2 est impair.

- x_{3}-3 est impair.

Et ainsi de suite, jusqu'à:

- x_{n}-n est impair.

On fait la somme, et puisque il y a n nombre impair (et n est impair), donc la somme sera un nombre impair.

Et on a: {x_{1}, x_{2}, x_{3}, .... , x_{n}}=A

Donc:

x_{1}+x_{2}+x_{3}+.....+x_{n}-(1+2+3+.....+n)=0

Donc 0 est impair.

Donc contradiction, d'où: il existe un élément k de A tel que x_{k}-k soit pair.

Sans l'absurde, puisque: {x_{1}, x_{2}, x_{3}, .... , x_{n}}=A

On a:

(x_{1}-1)+(x_{2})+(x_{3}-3)+....+(x_{n}-n)=(x_{1}+x_{2}+x_{3}+.....+x_{n})-(1+2+3+.....+n)=0

Donc la somme des nombres (n nombres avec n impair): x_{1}-1 et x_{2}-2 et x_{3}-3 et ..... et x_{n}-n est un nombre pair.

Donc l'un de ces nombres est nécessairement pair.

D'où: il existe un élément k de A tel que x_{k}-k soit pair.