Montrer la propriete

[newton]

bonjour

je suis coincé par cette recurrence

a) Montrer que la propriété P(n) définie par :
"Il existe une fonction surjective de [1..n] dans [1..n+1]"
est héréditaire

b) Que pensez vous de cette propriété ?

merci de m éclairer j ai un ds demain :briques:

[arnaud32]

tu as la condition n>=2 je suppose

qie designes tu par [1..n], l'intervalle rel [1,n] ou l'enesmble {1,...,n} ?

[newton]

effectivement

[1..n] est l ensemble des entiers de 1 à n

[arnaud32]

1) pour ce qui estd e l'heredite
tu as
{1, ... ,n+1} = {1, ... ,n} U {n+1}
{1, ... ,n+2} = {1, ... ,n+1} U {n+2}
tu as une fonction f de {1, ... ,n} dans {1, ... ,n+1} surjective.
tu dois fabriquer g de {1, ... ,n+1} dans {1, ... ,n+2} surjective
tu peux le faire avec g(k)=f(k) si k dans {1, ... ,n} et g(n+1) = n+2
verifie que g est bien definie et surjective.

2) a ton avis la propriete est-elle vraie?

[newton]

merci

pour moi
j en conclue aussi qu elle injective voir aussi bijective donc est ce que je peux dire que la propriété est vraie....???

[arnaud32]

pour que ta propriete soit vraie il te faut un point initiale
as tu une surjection de {1} dans {1,2}?

[newton]

pour moi oui
mais je suis un peu perdu pour demontrer

[arnaud32]

c'est faux.
car si f de {1} -> {1,2} est surjective, il existe x et y dans {1} tels que f(x)=1 et f(y)=2
or {1} est un singletion donc x=y=1.
et 1=f(1)=f(1)=2, et 1=2 est absurde.

donc tu as une propriete qui est hereditaire mais dont le point de depart est faux.

tu ne peux donc pas prouver sa veracite par recurence.

[Sylviel]

Pour compléter : si tu as une surjection de A dans B ça veut dire que A est "plus gros" que B (ben oui, pour chaque point de B tu as au moins un point de A)
si tu as une injection de A dans B, A est "plus petit" que B (ben oui, pour chaque point de A tu as au moins un point de B)
si tu as une bijection : il sont de "même taille" !

(le sens de plus gros / moins gros / même taille doit pour le moment être compris intuitivement exclusivement)

[beagle]

oui, mais si une propriété est fausse,
et qu'elle restera tout le temps fausse,
a-t-elle une hérédité?
Une tare peut ètre héréditaire, non?

[beagle]

je réessaye:
si la propriété avait été vraie dès le départ et qu'alors elle serait restée toujours vraie,
c'est bien le fait qu'elle soit fausse au départ qui la rend fausse de façon héréditaire.

par contre si le fait d'ètre vraie au départ ne l'empèche pas d'ètre fausse pour des ordres plus élevés, alors elle n'est pas fausse par hérédité.

c'est possible ça?

[arnaud32]

Ce que tu as prouve c'est qu'elle est hereditaire.
Ce que je t'ai montre c'est que n=1 n'est pas un point de depart.
tu ne peux donc rien conclure

pour prouver que c'est vrai tu dois avoir [ P(0) vraie ] et [ P(n) vraie implique P(n+1) vraie]
pour prouver que c'est faux, tu dois prouver que [P(0) faux ] et [P(n) faux implique P(n+1) faux ]

Ceci dit ici ta proposition est fausse et herediatire
fausse car s'il existe une surjection f de {1, .. , n} dans {1, .. , n+1} il existe x(1) ... x(n+1) dans {1, .. , n} tels que f(x(k)) = k.
s'il existe p et q tels que x(p)=x(q) alors p=f(x(p))=f(x(q))=q, ce qui implique que les x(p) sont distincs. donc {x(p) | p=1, .., n+1} C {1, .., n} et leurs cardinaux verifient:

n+1 = Card({x(p) | p=1, .., n+1}) =< Card({1, .., n}) = n
ce qui est absurde.

[beagle]

Ce que tu as prouve c'est qu'elle est hereditaire.
.

alors il a bon à la première question.

et à la deuxième il dit que c'est faux.

c'est fini, il peut aller faire de l'anglais maintenant.