[MPSI] Injection et cardinal fini

Discussions générales concernant les mathématiques.
[participation réservée aux membres inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
acid24

[MPSI] Injection et cardinal fini

Message non lu par acid24 »

Bonjour à tous,
une petite question-débat:
Soient $E,F$ deux ensembles finis, $Card(E)=n,~Card(F)=p$
peut on considerer que l'affirmation :
$\exists f $ injective $E \rightarrow F \ \Rightarrow Card(F) \ge Card(E)$
soit "intuitive" (lu dans un livre de cours de math ! ? ) ? la démonstration par récurrence(sur $n$ ? là est ma question en fait) est nécessaire/utile ou on "enfonce les portes ouvertes" ?

merci, bonne journée a tous :)
martini_bird

Re: [MPSI] Injection et cardinal fini

Message non lu par martini_bird »

Salut,

pourquoi une démonstration par récurrence ? L'image de f contient au moins n éléments (sinon elle ne serait pas injective) et donc comme $f(E)\subset F$, c'est fini...

Cordialement.
acid24

Message non lu par acid24 »

oui cela semble juste ... en fait la question d'origine est démontrer

$[|1,n|] $ equipotent $[|1,p|] \Leftrightarrow n=p$

cela semble intuitif, mais j'ai vu une démo par récurrence un peu complexe ....
vos avis ??
kilébo
Modérateur honoraire
Modérateur honoraire
Messages : 1059
Inscription : samedi 22 avril 2006, 12:08
Localisation : Région Parisienne

Message non lu par kilébo »

Ta question est vraiment difficile à répondre sauf sur un point : non cela n'a rien d'intuitif, il faut le démontrer.

Là où c'est difficile c'est qu'il faut éviter soigneusement de ne pas introduire de cercle vicieux dans les différents théorèmes à démontrer.

Quant à l'utilisation de la récurence, cela me parait être la méthode naturelle pour ce genre de démonstration.
acid24

Message non lu par acid24 »

merci de vos réponses, kilébo ta réponse était pour mon premier message ou pour le second ?(désolé c'est maintenant pas très clair comme fil)
Bruno

Message non lu par Bruno »

Bonjour.

Kilebo a parfaitement raison, il faut savoir exactement ce que l'on fait pour démontrer ce résultat.

Ceci dit, puisque l'on parle de cardinaux, on fait de la théorie des ensembles et on connaît les ordinaux. Or il y a un théorème qui assure que si l'on considère deux ordinaux, l'un d'eux est un segment initial de l'autre ce qui permet de démontrer le résultat recherché par Acid24. Pour plus de détails, regarder dans Krivine, par exemple.
la main gauche

Message non lu par la main gauche »

Si tu parles du permier POST, le théorème des préfixes montre l'implication réciproque. Pour son deuxième POST, la direction que tu indiques nous amène vers le théorème de Cantor-Bernstein, mais il s'agit d'un cours de MPSI, et ces dernières considérations sont peut-être un peu élaborées, non?

Peut-être que qcid24 pourrait nous aider en nous donnant les définitions de Cardinal, Cardinal fini, de N (entiers naturels) et de p >= q pour des cardinaux, comme elles sont dans le cours. Il y a plusieurs façons de présenter les coses, plus ou moins adaptées aux considérations plus ou moins rudimentaires que l'on souhaite développer.
acid24

Message non lu par acid24 »

ensemble fini par définition un ensemble en bijection avec $[|1,p|], p\in \N$
son cardinal est $p$ , et $p \le n $ est une inégalité d'entier,

le théoreme de Cantor Bernstein est hors programme en Sup (je pense, même si mon prof me l'avait enseigné, corrigez-moi si vous pensez le contraire), la cardinalité d'ensembles infinis HP aussi, bref , ma question se place dans un cadre élémentaire , mais strict.

je dois donner une colle sur ces sujets (ensembles, injection/surjection/bijection, récurrence ...) et la question de mon 2ème post fait partie des questions de cours possibles, et j'en cherche la démo, ou plutôt je me demande s'il n'y a pas une démo plus simple que celle de mon bouquin de cours de référence, qui est par récurrence et me semble "lourde",

quel est ce "théorème des préfixes" ?
merci, a plus :)

PS: merci à celui qui a déplacé ce post, c'est vrai que j'ai hésité aussi .... finalement on pourrait même le mettre dans gdt_profs ....
la main gauche

Message non lu par la main gauche »

acid24 a écrit : quel est ce "théorème des préfixes" ?
Je voulais parler du théorème que cite Bruno (préfixe et segment commençant sont pour moi synonymes).

Je propose la preuve suivante pour la première question, avec une récurrence mais facile: l'idée de départ et que si $f: [1,p] \to [1,n]$ est injective, on peut trier ses images, i.e. composer avec une bijection de $[1,n]$ pour que $f$ soit juste l'injection canonique du permeir segment dans le second. Comme un tri est (la plupart du temps) une opération récursive, on fait une récurrence, sur p, genre "pour tout n entier si il existe f tq ... n >= p".

* pour p = 1, ...
* induction: on compose f avec la permutation de 1 et de f(1) dans [1,n], on obtient une fonction f' voisine (injective) de la précédente qui applique 1 sur 1; en effaçant 1 on est ramené au cas p-1.
michelll

Message non lu par michelll »

L'explication de martini_bird me semble correcte et compréhensible surtout pour les gens ne connaissant pas la theorie des ordinaus et cardinaux... De plus l explication de martini montre que l'on a compris ce qu'est une injection.... alors ne parlez pas du théorème de Cantor Bernstein s'il vous plait... ou de démonstration par récurrence... N'avez vous pas pensé aussi de construire les entiers avant de faire une récurrence ??
acid24

Message non lu par acid24 »

efectivement , je me suis embrouillé ,
c'est bien ce théorème qui se montre par récurrence :
acid24 a écrit : $[|1,n|] $ equipotent $[|1,p|] \Leftrightarrow n=p$
la première propriété est une consequence de la définition d'injectivité,
si l'on parle de cardinal d'ensemble fini , c'est qu'on a construit ou admis les entiers... non ??

quand à Cantor Bernstein, je n'en parlais que pour répondre à la main gauche, j'evite au maximum ce théorème que je trouve délicat

les mathématiques sont l'école de la rigueur, et j'ai beaucoup a apprendre, mais est-ce que cela merite un commentaire si acerbe ?
MB
Administrateur
Administrateur
Messages : 7538
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Message non lu par MB »

acid24 a écrit :les mathématiques sont l'école de la rigueur, et j'ai beaucoup a apprendre, mais est-ce que cela merite un commentaire si acerbe ?
Je crois que c'est simplement le style de michelll ...
MB. (rejoignez pCloud afin d'obtenir 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
michelll

Message non lu par michelll »

Mon avis est le suivant :

Je pense que l'intention de l' Exo comme il est posé n'est pas de redémontrer des choses de base du type [1,n] en bijection avec ... si et seulement si n=p ce qui aurait fait l'objet d'une question préliminaire...
Ensuite une injection est une bijection sur son image qui elle contient moins de points que l'espace d'arrivé. Et comme par def 2 ensembles ont le meme cardinal s'il existe une bijection entre eux, c'est FINI.

Ce théorème d'équipotence dont vous parliez ([1,n] en bijection avec ... si et seulement si n=p) montre que le cardinal est une notion bien défini, ce qui (je pense) n'est pas l'objet de cet exo.

Désolé pour mon style à la michelll.

PS : pour les interesses des ordinaux et cardinaux, je vous conseille ce livre, très agréable à lire :
Halmos, P.R., Naive Set Theory, D. Van Nostrand Company, Princeton, NJ, 1960. Reprinted, Springer-Verlag, New York, NY, 1974.