Bonsoir,
Un ensemble X inclu dans U est dénombrable s'il est fini, ou il existe une fonction f: N -> U telle que f(N) = U.
N est l'ensemble des entiers naturels.
Est-ce que l'ensemble des formules booléennes propositionnelles en forme normale conjonctive est dénombrable? Exemple d'une telle formule : (x1 v -x3 v -x5) ^ (-x1 v x2 v x3) ^ (x2 v x5)
v : ou
^ : et
- : non
Merci d'avance.
Ça dépend de si l'ensemble de tes variables V est dénombrable ou pas
Si cet ensemble n'est pas dénombrable, alors trivialement l'ensemble des formules booléennes propositionnelles n'est pas dénombrable.
Si cet ensemble est dénombrable, alors pour tout entier naturel n, l'ensemble des formules de longueur n est dénombrable, en effet, il est compris dans E^n ou E est dénombrable et
L'ensemble de toutes les formules est alors dénombrable comme réunion dénombrable d'ensemble dénombrable
Cela me semble logique, merci!
De même l'ensemble des graphes orientés finis est une union dénombrable d'ensemble dénombrables, donc l'ensemble est dénombrable.
Mais qu'en est-il des graphes orientés infinis ? Je veux dire comment justifier que cet ensemble est dénombrable (ou non) ?
L'ensemble des graphes orientés infini n'est pas dénombrable.
En effet, un de ses sous ensemble n'est pas dénombrable : L'ensemble des graphes dont les seuls arcs vont du sommet 0 à un autre sommet.
Cet ensemble est en bijection avec l'ensemble des suites de N -> {0,1} (a un graphe G on associe la suite g telle que g(n) = 1 si il y a un arc qui va de 0 à n, 0 sinon) donc en bijection avec {0,1}^N , ensemble qui a la puissance du continu.
Donc le fait que ce sous-ensemble ne soit pas en bijection avec N (mais avec {0,1}^N) implique que l'ensemble des graphes orientés infini n'est pas dénombrable ?
Oui, puisque {0,1}^N n'est pas dénombrable. Ça se montre grâce à l'argument de la diagonale de Cantor, et c'est une démonstration absolument fondamentale. Si tu ne l'as jamais faite en cours (comment montrer que l'ensemble des réels n'est pas dénombrable), je te suggère de lire la page wikipédia sur le sujet :
http://en.wikipedia.org/wiki/Cantor%...gonal_argument
L'ensemble des sous-parties de N est-il dénombrable ?
MERCI D'AVANCE.
L'ensemble des parties d'un ensemble n'est jamais en bijection avec cet ensemble.
Dans le cas particulier de IN, il a déjà été dit ici quen'est pas dénombrable, or cet ensemble est clairement en bijection avec les parties de IN.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
y a t- il différence entre sous-parties de N et sous-parties finies de N ???
Je crois que pour le cas d'ensemble de sous parties finies de N est dénombrable!!!
Merci d'avance !!
Bien sur puisque toutes les parties de IN ne sont pas finies, il y en a même "beaucoup plus".Envoyé par DjMatematica
D'une façon générale si E est un ensemble de cardinal
Dernière modification par Médiat ; 24/11/2011 à 17h40.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
