Fascicule de travaux dirige´s de fondement des mathe´matiques · 2018-09-16 · Fascicule de travaux dirige´s de fondement des mathe´matiques contact: [email protected]

Universite Paris 1 Pantheon-Sorbonne.

Ufr 27 Mathematiques et Informatique

L1 MIASHS 2018-2019

Fascicule de travaux diriges de fondement des mathematiques

contact: [email protected]

1


L1 MIASHS -Fondement des mathematiques

TD 1: Calcul propositionnel

Exercice 1. Soit p la proposition “il fait froid” et q “il pleut.” Donner

l’enonce en language naturel des propositions suivantes.:

1. ¬p

2. p ^ q

3. p _ q

4. p , q

5. p ) ¬q

6. q _ ¬p

7. ¬p ^ ¬q

8. p , ¬q

9. (p ^ ¬q) ) p

Exercice 2. Soit p la proposition “ce chien est petit” et q “ ce chien est

gris.” ecrire chacune des propositions suivantes sous forme symbolique en

utilisant p et q.

1. ce chien est petit et gris

2. Ce chien est grand et gris

3. Il est faux que ce chien soit petit ou gris

4. Ce chien est petit ou il est grand et gris

5. Ce chien n’est ni vetit ni gris.

1

Exercice 3 (D’apres Tristan Bernard) Soit p “il pleut” , q “ il va pleu-

voir” et r “de Deauville on peut voir Le Havre”. Donner un enonce en

language naturel qui traduit la proposition suivante:

(r ) q) ^ (¬r ) p).

Exercice 4. Determiner la valeur de verite des propositions suivantes:

1. Si 3 + 2 = 7 alors 4 + 4 = 8

2. Il est faux que 2 + 2 = 5 si et seulement si 4 + 4 = 10

3. Paris est en Angleterre ou Venise n’est pas en Italie/

4. Il est faux que 1 + 1 = 3 ou 2 + 1 = 3

5. II est faux que si Paris est en Angleterre alors Londres est en France.

Exercice 5. Determiner la negation des propositions suivantes:

1. Il est grand et beau

2. Il n’est ni riche ni heureux

3. Si elle vient elle parlera avec toi.

4. ni Marc ni Eric ne sont joyeux.

5. Si Marc est triste, alors Marie et Jean sont heureux.

6. Marc ou Eric sont elegants et Marie est grande.

Exercice 6. Determiner la table de verite des propositions suivantes puis

determiner leur negation.

1. ¬(p) ^ q

2. ¬(q) ) ¬(p)

3. (p ^ q) ) (p _ q)

4. ¬(p ^ q) _ ¬(p , q)

2

5. (¬(p ^ q) ) r) ) (q ^ r)

Exercice 7 Demontrer que les propositions suivantes sont des tautologies (i.e

qu’elles sont vraies independamment de la valeur de verite des propositions

constituantes):

1. (p ^ q) _ r , (p _ r) ^ (q _ r)

2. (p _ q) ^ r , (p ^ r) _ (q ^ r)

3. ¬(p ^ q) , ¬p _ ¬q

4. ¬(p _ q) , ¬p ^ ¬q

5. ¬(p ) q) , p ^ ¬q

6. p ^ (q ^ r) , (p ^ q) ^ r

7. p _ (q _ r) , (p _ q) _ r

Exercice 8. Demontrer que les propositions suivantes sont des tautologies

(si non demontrees en cours):

1. Raisonnement par contraposee: [p ) q] , [¬q ) ¬p]

2. Raisonnement par l’absurde: [(p ) q) ^ ¬q] ) ¬p

3. Raisonnement par disjonction des cas: [(p_q)^(p ) r)^(q ) r)] ) r

4. Transitivite de l’implication: [(p ) r) ^ (q ) r)] ) [p ) r]

5. Raisonnement par double implication: [(p ) q) ^ (q ) p)] , [p , q]

Exercice 9. Soit P,Q,R des propositions. Indiquer si les propositions

suivantes sont toujours vraies, toujours fausses, ou si leur valeur depend

de celles de P,Q,R.

1. [P _ (Q ^R)] ^ (Q _R).

2. [Q ) P ] ^ ¬(P , Q) ^ (R ^ ¬P ).

3. (¬P ) Q) _ (Q ) P ).

3

Universite Paris 1 Pantheon-Sorbonne.L1 MIASHS -Fondement des mathematiques

TD 2: Calcul des predicats

Exercise 1. Determiner la valeur de verite des propositions suivantes:

1. 9x 2 R x2 � 2x+ 1 = 0

2. 9x 2 R x2 + x+ 1 = 0

3. 9x 2 C x2 + x+ 1 = 0

4. 8x 2 R |x| = x

5. 8x 2 R+ |x| = x

6. 9x 2 R8y 2 R x � y

7. 9x 2 R9y 2 R x � y

8. 8x 2 R9n 2 N n > x 8x 2 R⇤+9n 2 N 1

n < x

Exercise 2. Determiner la negation des propositions precedentes.

Exercise 3. Soit p(x, y, z) un predicat sur R⇥R⇥R, determiner les relationslogiques entre les proposition suivantes:

1. 8x 2 R 8y 2 R 9z 2 R p(x, y, z)

2. 9z 2 R8x 2 R 8y 2 R p(x, y, z)

3. 8y 2 R8x 2 R 9z 2 R p(x, y, z)

4. 8x 2 R 9z 2 R 8y 2 R p(x, y, z)

Exercise 4. Determiner la negation des propositions suivantes.

1. 8x 2 R9y 2 R8z 2 R (x 2 [y, z] or z 2 [x, y])

1

2. 9x 2 R 9n 2 N 8z 2 R (z � n ) x z)

Exercice 5. Ecrire les negations des phrases suivantes (on ne demande pasevidemment de simplement faire preceder la phrase d’un ¬) :

1. 8" > 0, 9` 2 R⇤+, 8a 2 R, 9⌧ 2 [a, a+ `], 8t 2 R, |f(t+ ⌧)� f(t)| ".

2. Tout triangle rectangle possede un angle droit.

3. Pour tout entier x, il existe un entier y tel que pour tout entier z, larelation z < y implique la relation z < x+ 1.

Exercice 6. On associe au nombre reel x 2 R la proposition:

P (x) := 8y 2 R 9n 2 N xn � y

1. Donner un exemple de reel x 2 R tel que P (x) soit vraie (justifier votrereponse).

2. Determiner la negation Q(x) de P (x). Donner un exemple de reel x 2 Rtel que Q(x) soit vraie (justifier votre reponse).

3. Determiner si les proposition suivantes sont vraies ou fausses (justifiervos reponses):

(a) 9x 2 R P (x)

(b) 8x 2 R P (x)

(c) 8x � 1 P (x)

(d) x > 1 ) P (x)

(e) P (x) ) |x| � 12 .

Exercice 7. Montrer que l’assertion :

1. 8" > 0, 9N 2 N⇤, 8n � N, 1n " est vraie.

2. 9N 2 N⇤, 8" > 0, 8n � N, 1n " est fausse.

2


TD 3: Theorie des ensembles

Exercice 1.Soient A = {1, 2, 3, 4}, B = {2, 4, 6, 8}, et C = {3, 4, 5, 6}. Determiner A[B,A [ C, B [ C et A [ A

Exercice 2.Soient A = {1, 2, 3, 4}, B = {2, 4, 6, 8}, et C = {3, 4, 5, 6}.

1. Determiner A \ B, A \ C, B \ C andA \ A

2. Determiner (A \ B) \ C and A \ (B \ C).

Exercice 3.

1. {1, 2, 3, 4} \ {x 2 N | 9y 2 N x = 2y} = ?

2. {x 2 N | x 40} \ ({x 2 N | 9y 2 N x = 3y} \ {x 2 N | 9y 2 N x =4y}) = ?

Exercice 4. Dire si les a�rmations ont un sens et sont justes, et si non, lescorriger de sortes qu’elles le deviennent :

1. 1 2 {1; 2}.

2. 1 ⇢ {1; 2}.

3. 1 2 {{1}, 2}.

4. L’ensemble ; a zero element.

5. ; = {;}.

6. L’ensemble {;, ;} a un element.

1

Exercice 5. Soit ⌦ un ensemble et A, B et C trois sous-ensembles de ⌦.

1. Demontrer que si A [B ⇢ A alors B ⇢ A.

2. Demontrer que si A [ B = A \ C alors B ⇢ A ⇢ C.

3. Demontrer que si A [ B = A [ C et si A \B = A \ C alors B = C.

Exercice 6. Demontrer les proprietes suivantes (sauf celles deja demontreesen cours)

• Idempotence:

A [ A = A A \ A = A

• Associativite:

(A[B)[C = A[(B[C) (A\B)\C = A\(B\C)

• Commutativite:

A [B = B [ A A \ B = B \ A

• Distributivite

A[(B\C) = (A[B)\(A[C) A\(B[C) = (A\B)[(A\C)

• Element neutre

A [ ; = A A \ U = A

• Element absorbant

A [ U = U A \ ; = ;

• Lois du complementaire

A [ Ac = U A \ Ac = ;

(Ac)c = A U c = ;

2

• Lois de Morgan

(A[B)c = Ac\Bc (A\B)c = Ac[Bc

Exercice 7. On suppose que U est l’ensemble de tous les ensembles et onpose

A = {x 2 U | x 62 x}.

1. Montrer qu’on ne peut avoir A 2 A.

2. Montrer qu’on ne peut avoir A 62 A.

3. Qu’en deduisez-vous sur l’ensemble de tous les ensembles ?

3



TD 4: Theorie des ensembles (suite)

Exercice 1.Soient A = {1, 2, 3, 4}, B = {2, 4, 6, 8}, et C = {3, 4, 5, 6}. Determiner A/B,A/C, B/C andA/A

Exercice 2. Soient A et B deux ensembles. Demontrer que:

1. (A� B) \ B = ;

2. (A� B) \ (B � A) = ;

3. (A� B) \ (A \ B) = ;

4. (A� B) = (B � A) if and only if A = B

Exercice 3 Soient U = {1, 2, 3, 4, 5, 6, 7, 8, 9} et A = {1, 2, 3, 4}, B =

{2, 4, 6, 8}, and C = {3, 4, 5, 6}. Determiner les complementaires dans Usuivants: Ac Bc Cc

(A [B)cand (A \ C)

c

Exercice 4Quel est le complementaire de l’ensemble des entiers positifs pairs

dans l’ensemble des entiers positifs ? Dans l’ensemble des entiers relatifs ?

Exercice 5 Soient A et B deux ensembles. Montrer que

Ac � Bc= B � A

Exercice 6 Soient A et B deux ensembles tels que A \B = ;.Montrer que:

A [Bc= Bc

Exercice 7.

1

1. Soit A = {0, 1}. Determiner P(A)

2. Soit B = {x 2 R | x2= 0}. Determiner P(B)

3. Determiner P(;), P(P(;)), P(P(P(;))).

Exercice 8 Soit E un ensemble tel que CardE = n, ou n 2 N. Demontrer

par recurrence sur n que CardP(E) = 2n.

Exercice 9Soit E un ensemble et Q un sous-ensemble de P(E). Montrer que les trois

proprietes suivantes sont equivalentes.

1. 8(A,B) 2 Q2, (A�B 2 Q, A \B 2 Q)

2. 8(A,B) 2 Q2, (A�B 2 Q, A [B 2 Q)

3. 8(A,B) 2 Q2, (A/B 2 Q, A [ B 2 Q)

N.B: A/B est la di↵erence ensembliste et A�B la di↵erence symetrique de

A et B : A�B := (A/B) [ (B/A).

Exercice 10. Soient A = {a, b}, B = {2, 3}, C = {3, 4}. Determiner:

1. A⇥ (B [ C)

2. (A⇥ B) [ (A⇥ C)

3. A⇥ (B \ C)

4. (A⇥ B) \ (A⇥ C)

Exercice 11. Representer dans un repere cartesien l’ensemble:

{x 2 R | 1 x 4}⇥ {x 2 R | �2 x 3}

Exercice 12. Demontrer que: A⇥ (B \ C) = (A⇥ B) \ (A⇥ C)

Exercice 13. Donner un exemple de sous-ensemble de R2qui ne soit pas de

la forme A⇥ B ou A et B sont des sous-ensembles de R.

2


TD 5: Fonctions

Exercice 1 On definit deux fonctions f, g : [0, 1] ! [0, 1] par:

• f(x) =

(3x si x 2 [0,

1

3]

1 sinon

• g(x) =

(0 si x 2 [0,

2

3]

3x� 2 sinon

Determiner f � g et g � f.

Exercice 2Determiner si les applications suivantes sont injectives, bijectives,surjectives.

• f : N ! N, n 7! n+ 1

• g : Z ! Z, n 7! n� 1

• h : R2 ! R2, (x, y) 7! (x+ y, x� y)

Exercice 3. Soit f : Z ! Z definie par f(n) = n2 pour tout n 2 Z.

1. Determiner f�1({1}), f�1({1, 2}), f�1({1, 2, 3, 4}).

2. f est-elle injective ? surjective ? bijective ?

Exercice 4. Soit g : Z ! N definie par f(n) = n2 pour tout n 2 Z.

1. Determiner g�1({1}), g�1({1, 2}), g�1({1, 2, 3, 4}).

2. g est-elle injective ? surjective ? bijective ?

Exercice 5. Soit h : R ! R definie par f(x) = x2� 4x+3 pour tout x 2 R.

1. Determiner h�1({0}), h�1(R).

1

2. h est-elle injective ? surjective ? bijective ?

Exercice 6. On considere l’application f : R2 ! R definie par f(x, y) =x2 + y.

1. Montrer que f n’est pas injective. En deduire qu’il n’existe pas defonction g : R ! R2 telle que g � f = IdR2 .

2. Montrer que f est surjective, et que l’application h : R2 ! R2 definiepar h(x, y) = (x, x2 + y) est une bijection.

3. Trouver une application g : R ! R2 telle que f � g = IdR.

Exercice 7 Soit f : A ! B et g : B ! C des applications. Montrer que

• g � f injective implique f injective.

• g � f surjective implique g surjective.

2


TD 6: Fonctions (suite)

Exercice 1 Soit f : N2 ! N⇤, (n, p) 7! 2n(2p + 1). Montrer que f est unebijection.

Exercice 2 Soit f : X ! Y . Montrer que les conditions suivantes sontequivalentes :

1. f est injective.

2. Pour tous A,B 2 P(X), on a f(A \B) = f(A) \ f(B)

Exercice 3 Soient E un ensemble,et A et B deux parties de E. On pose:

f : : P(E) ! : P(A)⇥ : P(B)X 7! (X \ A,X \ B)

1. Montrer que f est injective si et seulement si A [ B = E.

2. Montrer que f est surjective si et seulement si A \ B = ;.

3. Donner une condition necessaire et su�sante sur A et B pour que fsoit bijective. Donner dans ce cas la bijection reciproque.

Exercice 4 Determiner toutes les applications h de E = {0, 1, 2, 3, 4} danslui-meme telles que pour tout x, y dans E on ait h(x+ y) = h(x) + h(y).

Exercice 5. Donner des exemples de familles d’ensembles indicees par N,Z, R.

1

Exercise 6. Soit (Dn)n2N la famille d’ensembles indicee par N definie parDn =]0, n[. Determiner:

1. D3 [D7

2. [i2NDi

3. D3 \D20

4. \i2NDi

2



TD 7: Relations

Exercice 1

1. Dessiner le graphe des relations suivantes dans R : �,, >,< .

2. De quell relation binaire dans R la droite y = x est-elle le graphe ?

3. Graphiquement, quelle propriete a le graphe d’une relationbinaire dans

R qui est which is reflexive ? symetrique? anti-symetrique ?

Exercice 2 Soit X = {1, 2, 3, 4}. Sur X on considere la relation dont le

graphe est l’ensembleG suivant : G = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (3, 4), (4, 2), (4, 3), (4, 4)}.Cette relation est-elle reflexive ? symetrique ? anti-symetrique ? transitive

?

Exercice 3

1. Donner un exemple de relation a la fois symetrique et anti-symetrique.

2. Soit E un ensemble fini ayant n elements. Combien y a-t-il de relations

sur E qui soient a la fois symetriques et anti-symetriques ?

Exercise 4. Les relations suivantes sont elles reflexive? transitive? symetrique?

anti-symetrique ?

1. Dans N, aRb si et seulement si a divise b

2. Dans P(E), la relation d’inclusion.

3. Dans R, la relation xR si et seulement si |x| = |y|

4. Dans P(E), la relationARB si et seulement si A \B = ;

1

5. Dans R, the relation xRy si et seulement si u(x) > u(y) ou u : R ! R.

6. Dans R, the relation xRysi et seulement si u(x) � u(y) ou u : R ! R.

7. Dans R, the relation xRysi et seulement si u(x) � u(y) ou u : R ! Rest une fonction croissante.

8. Dans Z⇥N� {0}, la relation (a, b)R(c, d)si et seulement si ad� bc = 0

Exercise 5. Les relations precedentes sont-elles des relations d’equivalence

? Des relations d’ordre ?

Exercice 6 Determiner lorsque cela est possible les bornes inferieures et

superieures, ainsi que les maxima et minima des sous-ensembles de R suiv-

ants :

A1 = [�1, 3]; A2 =]� 12,�3] [ {1}; A3 =

⇢1

n+ (�1)

n, n 2 N⇤�

Exercise 7. Soient R et S deux relations d’ordre totales sur E telles que

8(x, y) 2 E ⇥ E xRy ) xSy

Montrer que 8(x, y) 2 E ⇥ E xRy , xSy

Exercise 8. Soit ⇡(E) l’ensemble des partitions de E et R la relation dans

⇡(E) definie par

⇡1R⇡2 , 8P1 2 ⇡19P2 2 ⇡2, P1 ⇢ P2.

Montrer que R est une relation d’ordre. Quels sont les elements minimaux

et maximaux de R?

Exercise 9. Les ensembles suivants ont-ils un minimum ? un maximum ?

une borne superieure ? une borne inferieure ?

• Subsets of R :

1. ]0, 1[

2

2. [n2N{�n}3. [0, 1]

4. { 1n}n2N�{0}

5. { 1x}x2R�{0}

• Subsets of Q

1. {x 2 Q | x > 0}2. {x 2 Q | x > ⇡}

Exercise 10. Soit A une partie non vide de R, on pose B = �A := {b 2 R |9a 2 A, b = �a}, c’est-a-dire b 2 B si et seulement si �b 2 A.

• Montrer que A est majore si et seulement si B est minore. Montrer

que A est minore si et seulement si B est majore.

• Montrer que � est un minorant de A si et seulement si �� est un

majorant de B.

Exercise 11. Soit E un ensemble ordonne tel que tout sous ensemble majore

de E admet une borne superieure. Montrer que tout ensemble minore de Eadmet une borne inferieure.

3


TD 8: Nombres entiers

On rappelle les axiomes de Peano:

Axiome: 1 (de Peano) Il existe un ensemble appele ensemble des entiersnaturels est note N, un element 0 2 N appele zero et une application s : N !N appelee successeur, verifiant les proprietes suivantes:

1. 0 62 s(N) (0 n’est le successeur d’aucun entier).

2. s est injective (deux entiers ayant le meme successeur sont egaux)

3. Si A ⇢ N est telle que 0 2 A et 8n 2 A s(n) 2 A alors A = N (principede recurrence).

Exercice 1 Quels axiomes de Peano l’ensemble {0, 1, 2, 3}, muni de la fonc-tion successeur s definie par s(0) = 1, s(1) = 2, s(2) = 3 et s(3) = 0 neverifie-t-il pas ?

Exercice 2Donner un exemple d’ensemble muni d’une fonction successeur qui verifietous les axiomes de Peano sauf l’axiome de recurrence.

Exercice 3 Monter que tout entier est pair ou impair, i.e que

8n 2 N 9p 2 N (n = 2 ⇤ p _ n = 2 ⇤ p+ 1)

Exercice 4 Soit a, b, d des entiers. on suppose que d divise a. Montrer qued divise a+ b si et seulement si d divise b.

Exercice 5

1

1. En considerant l’ensemble des entiers multiples de a � 1 et b � 1,montrer que ppcm(a, b) existe

2. Demontrer que ppcm(a, b) est unique.

Exercice 5 Montrer qu’il existe une infinite de nombre de premiers.N.B on pourra considerer P ! + 1 si P est le plus grand nombre premier.

Exercice 7 Soient a = 2088 et b = 504, donner la decomposition en facteurspremiers de a et b puis leur pgcd et ppcm.

Exercice 8 Soit n � 1,. Determiner le reste dans la division euclidienne parn de la somme des n premiers entiers.

Exercice 9Demontrer que la somme de trois cubes consecutifs est toujours divisible par9.

2


TD 9: Nombres reels

Exercice 1Determiner l’ecriture decimale de la fraction 2/7 et verifier qu’elle devientperiodique.

Exercice 2 Determiner la fraction correspond au developpement decimal22, 75 358 358 358....

Exercice 3

1. Montrer que pour tout reel x et pour tout rationnel y, x est rationnelsi et seulement si x+ y est rationnel.

2. En deduire que l’ensemble {y +p2, y 2 Q} est infini.

3. En deduire que l’ensemble des irrationnels est infini.

Exercice 4 Determiner lorsque cela est possible les bornes inferieures etsuperieures, ainsi que les maxima et minima des sous-ensembles de R suiv-ants :

A1 = [�1, 3]; A2 =]�12,�3][{1}; A3 =

⇢1

n+ (�1)n, n 2 N⇤

�et A4 =

⇢ln(x)

x, x > 0

�.

Exercice 5 Soit A une partie non vide de R, on pose B = �A := {b 2 R |9a 2 A, b = �a}, c’est-a-dire b 2 B si et seulement si �b 2 A.

• Montrer que A est majore si et seulement si B est minore. Montrerque A est minore si et seulement si B est majore.

• Montrer que � est un minorant de A si et seulement si �� est unmajorant de B.

1

• En deduire (en se basant sur l’axiome de la borne superieure) que siA est minore, l’ensemble des minorants de A possEde un plus grandelement qui sera note inf(A). Montrer que inf A = � supB.

Exercice 6 Soit A une partie non vide de R, dont la borne inf vaut ↵. Onsuppose que ↵ /2 A, montrer que A ne possede pas de plus petit element.

Exercice 7

1. Donner un exemple de sous-ensemble borne de R n’ayant pas de plusgrand element.

2. Existe-t-il des sous-ensembles finis de R n’ayant pas de borne inferieure?

3. Donner un exemple de sous-ensemble infini et denombrable de R n’ayantpas de borne inferieure.

4. Donner un exemple de sous-ensemble infini et denombrable de R ayantune borne inferieure.

5. Donner un exemple de sous-ensemble infini et denombrable de R ayantun plus petit et un plus grand element

2


TD 10: Nombres reels (suite)

Exercice 1 Soit A et B deux parties non vides de R telles que : 8(a, b) 2A⇥ B, a b. Demontrer que supA et inf B existent et que supA inf B.

Exercice 2 Soit A et B deux parties majorees et non vides de R. On definitA + B = {a + b, (a, b) 2 A ⇥ B}. Montrer que A, B, A + B admettent desbornes superieures dans R et que

sup(A+B) = sup(A) + sup(B).

Exercice 4

1. Soit f : R+ ! R+ definie pour tout x 2 R par f(x) =x

x+ 1,

determiner infR+ f et supR+f.

2. Soit g : R/{�2} ! R definie pour tout x 2 R par f(x) =x

x+ 2,

determiner infR g et supR g.

3. Soit h : R ! R definie pour tout x 2 R par h(x) = sin(ex), determinerinfR h et supR h.

4. Soit k : R ! R definie pour tout x 2 R par k(x) = tan(x2), determinerinfR k et supR k.

Exercice 4 Soit X un ensemble non vide et f et g deux applications borneesde X dans R. Comparer supX(f+g) et supX f+supX g. Donner un exempleou l’inegalite est stricte. Montrer que supX(f�g) � supX f�supX g. A-t-onsupX(f � g) � | supX f � supX g|

1

Exercice 5 Soit A, B et C trois ensembles de reels, non vides et bornes, etsoit f et g des applications bijectives telles que f : A ! B et g : B ! C.Determiner sup g � f en fonction de sup f et sup g.

Exercice 6 Soient x, y 2 R, Demontrer les inegalites suivantes:

1. |x|+ |y| |x+ y|+ |x� y|

2. 1 + |xy � 1| (1 + |x� 1|)(1 + |y � 1|)

3. |x+y|1+|x+y|

|x|1+|x| +

|y|1+|y|

2

Documents

Fascicule de travaux dirige´s de fondement des mathe´matiques · 2018-09-16 · Fascicule de travaux dirige´s de fondement des mathe´matiques contact: [email protected]