Question induction structurelle

[Archytas]

Est-ce que tout ensemble défini par induction structurelle est dénombrable ?

[Doraki]

c'est quoi un ensemble défini par induction structurelle ?

[Archytas]

Un objet de base (par exemple pour les entiers 0). Et des opérateurs (sur le même exemple l'outil s qui désigne le successeur) en extrémement simplifié. Il y a aussi les listes avec [] comme objet de base et l'opérateur de consage... Enfin tu dois savoir ce que c'est étant donné ton niveau. Tu as une idée de la réponse ?

[Doraki]

Donc si on prend un objet de base non dénombrable ça répond à ta question ?

[Archytas]

Comment c'est possible ? Un objet de base en lui même est de cardinal 1, non ?

[Doraki]

Ben ça dépend de tes définitions.
Ou alors tu parles peut-être de l'ensemble des trucs que tu peux construire ?

[Archytas]

Ben ça dépend de tes définitions.
Ou alors tu parles peut-être de l'ensemble des trucs que tu peux construire ?

Oui, c'est ça. Il me semblait que c'était la définition.
Je sais que c'est pas les bons termes mais c'est l'ensemble "engendré" par les objets de bases grâce aux constructeurs.
En fait initialement je me demander s'il était possible en théorie de construire les réels par induction structurelle.

[Skullkid]

Bonjour, si j'ai pas compris la définition de travers, l'ensemble des objets que tu peux construire s'injecte dans l'ensemble des "mots" que tu peux faire à partir des symboles que sont l'élément de base et tes opérateurs. Autrement dit ton ensemble est plus petit que l'ensemble des suites finies à valeurs dans un ensemble fini, donc il est dénombrable.

[Archytas]

Salut,
Je n'ai pas bien compris, pourquoi "à valeur dans un ensemble fini" ? Par exemple pour le successeur d'un entier je veux bien que tout nombre soit obtenu par une suite finie (pour l'opérateur successeur succ) on a 4 = succ(succ(succ(succ(0)))). Mais l'ensemble d'arriver n'est pas fini.
Ou alors j'ai rien compris...

[Skullkid]

L'ensemble fini c'est ton alphabet, par exemple pour les entiers c'est {0,succ}. Si E est l'ensemble construit par induction structurelle à partir de l'alphabet fini A, on injecte E dans les suites finies à valeurs dans A en associant à chaque élément de E une de ses écritures en tant que mot dont les lettres sont dans A.

[Doraki]

Et si t'as une infinité non dénombrable de constructeurs ou d'objets de base, ça te donne un ensemble non dénombrable à l'arrivée.

[Archytas]

D'accord, je comprends le principe ça répond à mes questions !
Merci !