¿Cada lengua es regular?

Question

Podría alguien decirme el error en mi razonamiento:

1. El conjunto de cadenas de caracteres de un alfabeto es una contables conjunto.
2. Cada cadena puede ser determinado por un lenguaje regular.
3. La unión de los dos idiomas es de nuevo de manera regular.
4. Por lo tanto: por tomarse una contables de la unión de regular idiomas, podemos formar cualquier idioma, y como este lenguaje es la unión de regular los idiomas, debe ser así.

Obviamente esto no es cierto, pero no veo mi error.

Answer 1

La respuesta ya fue dada por Florian, pero voy a elaborar un poco: Este es un caso de una confusión general en Matemáticas: Algo que es cierto/definibles por dos elementos, puede extenderse a cualquier número finito de elementos si se cumple alguna de asociatividad requisito, pero no a un número infinito.

Por ejemplo, además: usted sabe cómo sumar dos números, y se puede extender a cualquier número finito de sumandos, pero esto no implica que sepa cómo la suma de un número infinito de sumandos (y de hecho, lo que se suma infinito número de sumandos puede resultar en un indefinido o infinito resultado aunque para cualquier número finito de sumandos, el resultado es definido y finito). Otro ejemplo es el resultado topológico/definición que la intersección de dos conjuntos es de nuevo un conjunto abierto - este es extender fácilmente a la intersección de cualquier número finito de abrir sets, pero no es el adecuado para un infinito intersección.

Este error puede deberse a un error de interpretación de la inducción matemática; por inducción que por lo general muestran que algunos son el resultado se cumple para cualquier número natural $n$; de lo que no implica que el resultado se cumple para un número infinito. Así que en nuestro caso es fácil deducir, a partir de 3 por inducción que la unión de $n$ regular idiomas es regular, pero no se puede inferir que la unión de un número infinito de regular idiomas es regular.

Answer 2

La Unión de dos idiomas regulares es regular implica que finito sindicatos vuelven a ser regulares, pero no puede concluir que la Unión de infinitamente muchos idiomas es regular (y de hecho esto no es cierto).