Révision examen 3 Flashcards
Comment une fonction peut être vu en tant que relation?
On considère deux ensembles, soit A et B. Puis, on considère une relation binaire F de A vers B. Donc F est un sous-ensemble du produit cartésien de A et B. La relation F est une fonction si et seulement si elle satisfait la condition suivante:
Pour tout « a » élément de A, il existe un unique « b » élément de B tel que « a » est en relation avec « b ».
Quels sont les deux critères qu’une relation doit respectée pour qu’elle soit considérée comme une fonction?
- Existence (Pour tout élément « a » de A, il EXISTE un élément « b » tel que « a » est en relation avec « b »)
- Unicité (Il existe qu’un seul élément « b » tel que « a » est en relation avec « b » )
Autre qu’une relation, de quelle manière peut-on voir une fonction?
Une fonction peut être abordé comme une règle d’association.
Comment une fonction peut être traité comme une règle d’association?
Soit A et B, deux ensembles. On appelle fonction de F de A (ensemble de départ) vers B (ensemble d’arrivée) une règle d’association qui, à tout élément de A, fait correspondre exactement un élément de B.
Qu’est-ce qui est considéré comme l’image d’un élément.
Un élément de l’ensemble d’arrivée est appelé image de l’élément de l’ensemble de départ auquel il est associé.
Qu’est-ce que le domaine d’une fonction?
C’est l’ensemble de départ.
Qu’est-ce que le codomaine d’une fonction?
C’est l’ensemble d’arrivée.
Quelle implication découle des critères d’une fonction, soit l’existence et l’unicité?
Quelle est la contraposée de cette implication?
Pour x,y qui appartiennent à l’ensemble A on a l’implication suivante:
f(x) =/ f(y) —> x =/y
La contraposée:
x = y —> f(x) = f(y)
Qu’est-ce qu’on appelle image d’une fonction?
C’est le sous-ensemble de B formé des images des éléments de A.
On le note im(f).
Qu’est-ce que l’image réciproque ou préimage de F?
On considère une fonction qui envoie l’ensemble A sur l’ensemble B où F est un sous-ensemble de B. L’image réciproque de l’ensemble F est le sous-ensemble de A formé de tous les points qui sont préimages aux images de l’ensemble F.
On le note f-1(F).
Qu’est-ce qu’une fonction constante?
C’est une fonction dont tous les éléments de l’ensemble de départ ont tous la même image dans l’ensemble d’arrivée.
Qu’est-ce qu’une fonction identité?
C’est une fonction qui a le même ensemble de départ et d’arrivée, puis chaque préimage à lui-même comme image.
On le note idA(a) = a.
Comme la fonction identité agit dans l’opération de composition de fonctions?
Elle agit comme une sorte d’élément neutre.
Quelle propriété de l’opération fonctionne aussi avec la composition de fonctions?
La composition de fonction est associative.
Donc:
h ° (g ° f) = (h ° g) ° f
Qu’est-ce qu’une fonction itérée?
Soit une fonction de A vers A. Étant donné « k » qui appartient aux naturels non-nul, on appelle fonction itérée d’ordre k de f la fonction f^(k): A —> A.
Cela correspond à ces deux égalités:
f^1 = f et f^(k) = f ° f^(k-1).
En d’autres mots, on répète la fonction f un nombre k de fois.
Quelle est l’idée derrière l’inversion d’une fonction?
On doit se demander s’il est possible d’annuler l’action de f.
Qu’est-ce que l’inverse à gauche d’une fonction?
Soit la fonction f qui envoie A sur B. Si on a une fonction g qui envoie B sur A, on dira que g est l’inverse à gauche de f si :
g ° f = idA (sur le graphique g est à droite)
Qu’est-ce que l’inverse à droite d’une fonction?
Soit la fonction f de A vers B. Une fonction h de B vers A est un inverse à droite de la fonction f si :
f ° h = idB
Comment une fonction peut-elle être inversible?
Une fonction est inversible lorsqu’elle admet un inverse à gauche et un inverse à droite et que ceux-ci sont égaux.
Si une fonction admet à la fois un inverse à gauche et un inverse à droite qu’est-ce que ça signifie?
L’inverse à gauche est unique et l’inverse à droite est aussi unique.
Qu’est-ce qu’une fonction injective?
Chaque élément de l’ensemble d’arrivée qui est une image n’a qu’une seule préimage, donc il sert d’image qu’une seule fois.
Cela revient à dire ceci:
Pour tout x,y qui appartiennent à A, on a
f(x) = f(y) —> x = y
ou par contraposition:
x =/ y —> f(x) =/ f(y)
Soit la fonction injective f de A vers B et la fonction injective g de B vers C, que peut-on affirmer à propos de la composée g ° f de A vers C.
Elle est aussi injective.
Démonstration:
Considérant x, y ∈ A tels que (g ◦ f)(x) = (g ◦ f)(y), il s’agit alors de
montrer que cette supposition mène à l’égalité x = y.
L’hypothèse sur x et y revient au fait que g(f(x)) = g(f(y)). Puisque g est injective, il s’ensuit
que f(x) = f(y). Mais f étant elle aussi injective, on en conclut que x = y, montrant ainsi
que la composée g ◦ f est injective.
Un inverse à gauche admet quel type de fonction?
Si une fonction admet un inverse à gauche alors elle est injective.
Un fonction injective admet un inverse de quel côté?
Elle admet un inverse à gauche.
Qu’est-ce qu’une fonction surjective?
C’est une fonction où tous les éléments de l’ensemble d’arrivée sert d’image.
Cela revient à dire que:
Pour tout « b » élément de B, il existe un élément « a » qui appartient à A tel que f(a) = b
Soit la fonction surjective f de A vers B et la fonction surjective g de B vers C, que peut-on affirmer à propos de la composée g ° f de A vers C.
La composée est aussi une fonction surjective.
Un inverse à droite admet quel type de fonction?
Une fonction qui admet un inverse à droite est surjective.
Si une fonction est surjective elle admet un inverse de quel côté?
Elle admet un inverse du côté droit.
Qu’est-ce qu’une fonction bijective?
C’est une fonction qui est à la fois injective et surjective. Donc, tous les éléments de l’ensemble d’arrivée servent d’image. et ce une seule et unique fois.
Une fonction est bijective si et seulement si…
la fonction est inversible.
Vrai ou faux. Soit une fonction bijective f, l’inverse de f est elle aussi bijective.
Vrai.
Qu’est-ce qu’on veut dire lorsqu’on dit que deux ensembles sont équipotents?
Deux ensembles sont équipotents lorsqu’il existe une bijection entre eux. Cela signifie que les deux ensembles sont de même cardinalité.
À quel moment dit-on qu’un ensemble est fini?
Un ensemble est fini lorsque ce dernier est équipotent à l’ensemble {1,2,…,n}.
Donc, la cardinalité de l’ensemble correspond à n.
Soit deux ensembles finis avec #A = n et #B = m alors combien y’a t’il de fonctions possibles entre A et B.
Il y a m^n possibilités.
Généralement quel calcul doit-on faire pour connaître le nombre de fonctions qu’il y a entre deux ensembles?
Nombre de fonctions = #B^#A
Si #A = n, il y a combien de relations binaires sur A?
il y a 2^(n^2) relations binaires sur A.
Soit deux ensembles finis A et B, où #A = n et #B = m. Comment trouve t-on le nombre de fonctions injectives f de A vers B?
m(m-1)(m-2)…*(m-(n-1)) nous permet de trouver le nombre de fonctions injectives.
Soit A et B, deux ensembles finis de même cardinalité n. Comment trouve t-on le nombre de bijections de A dans B?
n! nous permet de trouver le nombre de bijections de A dans B.
Quand est-ce qu’une ensemble E non vide est dénombrable?
On dit que E est dénombrable si E est équipotent aux naturels.
Si A et B sont deux ensembles dénombrables, qu’en est-il de leur réunion?
A U B est aussi dénombrable.
Si A et B sont deux ensembles dénombrables, qu’en est-il de leur produit cartésien?
Le produit cartésien A x B est aussi dénombrable.
Qu’est-ce qu’une opération n-aire sur A?
C’est une fonction f : A^n —> A
Si n = 1 alors opération unaire et si n = 2 opération binaire.
Soit *, une opération binaire sur un ensemble A. Si elle est associative cela signifie quoi?
Soient a, b, c qui appartiennent à A. * est dite associative si:
(a ∗ b) ∗ c = a ∗ (b ∗ c)
Soit *, une opération binaire sur un ensemble A. Si elle est commutative cela signifie quoi?
a ∗ b = b ∗ a, quels que soient a, b ∈ A
Qu’est-ce qu’un élément neutre pour l’opération binaire *?
e ∈ A est neutre pour ∗ si
e ∗ a = a ∗ e = a, quel que soit a ∈ A.
Quand est-ce qu’un élément est l’inverse d’un autre pour un opération binaire?
Supposons que e est un élément neutre pour ∗ et soit a ∈ A ; alors un élément b ∈ A
est appelé inverse de a pour l’opération ∗ si
a ∗ b = b ∗ a = e
Si on a deux opérations binaires, soit * et sur un ensemble A. Qu’est-ce que ça signifie que l’opération est distributive sur *?
On dit que l’opération est dite distributive par rapport à l’opération ∗ si
a (b ∗ c) = (a b) ∗ (a c), quels que soient a, b, c ∈ A
Qu’est-ce que l’élément neutre de l’opération binaire sur A a de particulier?
L’élément neutre est unique.
Qu’est-ce que l’inverse d’un élément par rapport à une opération binaire sur un ensemble quelconque a de particulier?
L’inverse est unique.
Qu’est-ce que l’associativité dans l’addition?
pour tout a, b, c ∈ Z, (a + b) + c = a + (b + c)
Qu’est-ce que la commutativité dans l’addition?
pour tout a, b ∈ Z, a + b = b + a
Qu’est-ce que l’élément neutre de l’addition? Et que fait-il?
0 est l’élément neutre de l’addition.
l’élément 0 ∈ Z est tel que, pour tout a ∈ Z, a + 0 = 0 + a = a
Qu’est-ce qu’un inverse additif?
pour tout a ∈ Z, il existe ˜a ∈ Z tel que a + ˜a = ˜a + a = 0
Qu’est-ce que l’élément neutre pour la multiplication?
Le chiffre 1 est l’élément neutre de la multiplication.
Qu’est-ce que la distributivité de la multiplication sur l’addition?
pour tout a, b, c ∈ Z, a · (b + c) = a · b + a · c
Qu’est-ce que la simplification de l’égalité pour l’addition?
Soit a, b, c ∈ Z; si a + b = a + c, on a alors b = c.
Quels sont les seuls entiers inversibles?
Il y a -1 et 1.
À quelle condition peut-on dire que deux entiers sont égaux?
on dit que a = b si et seulement si a - b = 0
Qu’est-ce qu’un entier idempotent pour l’addition?
Un entier a tel que a + a = a est dit idempotent pour l’addition.
Pour l’addition quel est le seul entier idempotent?
0 est le seul entier idempotent pour l’addition.
Quel est l’entier absorbant pour la multiplication et que fait-il?
0 est l’absorbant pour la multiplication.
Voici ce que cela signifie:
Soit un entier a. Alors a * 0 = 0
Qu’est-ce que l’opposé d’une somme?
Quels que soient les entiers a et b,
−(a + b) = −a + −b
Qu’est-ce que l’opposé d’une différence?
Quels que soient les entiers a et b,
−(a − b) = −a − −b = b − a
Qu’est-ce que l’opposé d’un produit?
Quels que soient les entiers a et b,
−(a · b) = −a · b = a · −b
Qu’est-ce que l’intégrité des entiers?
Soit deux entiers a et b tels que ab = 0 ; alors a = 0 ou b = 0
Si a|b et a|c que pouvez-vous dire?
a|(xb + yc)
Qu’est-ce que le théorème de la division euclidienne stipule?
Soit a, b ∈ N, avec b 6= 0. Il existe alors des entiers naturels q et r tels que
a = q · b + r, où 0 ≤ r < b
Si « d » est le PGCD de « a » et « b » que peut-on dire à propos de celui-ci?
l’entier positif d satisfaisant aux deux conditions suivantes :
(i) d | a et d | b (d est un diviseur commun de a et b) ;
(ii) c | a et c | b ⇒ c ≤ d (où c ∈ Z∗+)
(et c’est le plus grand des diviseurs communs)
Qu’est-ce que ça veut dire deux entiers qui sont copremiers?
Deux entiers sont copremiers si ceux-ci ont un PGCD égal à 1. On dit aussi qu’ils sont premiers entre eux.
Quel algorithme permet de calculer le PGCD de deux entiers?
L’algorithme d’Euclide. Celui-ci consiste en un enchaînement de divisions euclidiennes.
Qu’est-ce que la relation de Bézout?
Soit a, b ∈ Z, deux entiers (qui ne sont pas tous les deux nuls). Alors il existe x, y ∈ Z tels
que
pgcd(a, b) = xa + yb
Donc, le PGCD(a,b) peut s’écrire comme une combinaison linéaire des deux entiers a et b.
Comment trouve t-on une autre combinaison linéaire du PGCD(a,b)?
pgcd(a, b) = xa + yb
= xa + ab − ab + yb
= (x + b)a + (y − a)b
Qu’est-ce qu’un nombre premier?
C’est un entier naturel ayant exactement deux diviseurs. (donc 1 n’est pas premier)
Soit p et q, deux nombres premiers tels que p|q. Que peut-on dire sur ces deux nombres?
Il s’ensuit que p = q
Soit a un entier et p un nombre premier. Si p ne divise pas a, que peut-on dire sur leur PGCD?
Le PGCD(p,a) = 1.
Qu’est-ce que le théorème fondamental de l’arithmétique stipule?
Tous les entiers peuvent être écrit sous forme d’un produit de nombre premier. (La factorisation première)
-
