Es el conjunto de submonoids de $(\Bbb N,+)$ contables?

Question

Tener la monoid $(\Bbb N,+)$, me pregunto si no son contables muchos submonoids. Obviamente, hay infinitamente muchos desde $S_n = \{kn \mid k \in \Bbb N\}$ es un submonoid para cualquier $n \in \Bbb N$.

Mi conjetura es que el conjunto de todos los submonoids es contable, porque creo que las siguientes afirmaciones (que yo no había probado hasta ahora), mantenga pulsado para cualquier submonoid $S$$(\Bbb N,+)$:

• hay un elemento extraño en $S$ $\Rightarrow \exists e \forall f: (f \ge e \rightarrow f \in S)$ $\Rightarrow \Bbb N \setminus S$ es finito

• todos los elementos de a $S$ son incluso $\Rightarrow \exists e \forall f: (2f \ge e \rightarrow 2f \in S)$ $\Rightarrow \Bbb N \setminus (S \cup \{1,3,5,...\})$ es finito

En ambos casos podemos identificar la submonoid por un conjunto finito de números que no son elementos de la submonoid. Por lo tanto, sólo tenemos contables muchas posibilidades.

Se puede completar este enfoque o proporcionar una mejor?

Answer 1

Todos numérico monoids tiene un número finito de generadores (llamada la dimensión de embedding), y el conjunto de los subconjuntos finitos de $\mathbb{N}$ es contable.

Answer 2

Deje $A$ ser un submonoid de $(\mathbb{N}, +)$. Deje $d$ ser el MCD de todos los elementos de a $A$. Dividiendo por $d$, obtenemos un isomorfo submonoid $A'$ con MCD $1$. Así, existen elementos $a_1, a_2, \ldots, a_k \in A'$$\gcd(a_1, \ldots, a_k) = 1$.

Es fácil demostrar que para cualquier conjunto de enteros positivos con MCD 1, hay sólo un número finito de enteros positivos que no se pueden escribir como una suma finita de elementos del conjunto. Esto se deduce de la Generalizada la identidad de Bezout con un poco de trabajo; el caso con un conjunto de dos enteros primos relativos $a,b$ es bien conocido, con el mayor entero que no puede ser escrito como suma de un número finito de ser $ab - a - b$. Esto se conoce a veces como el Chicken McNugget Teorema; en general, encontrar el entero más grande que no puede ser escrito como una suma finita es más difícil, y es conocido como el problema de Monedas.

Todo esto es para mostrar que $A'$ es generado por el conjunto finito $\{a_1, a_2, \ldots, a_k, b_1, b_2, \ldots, b_m$ donde $b_1, b_2, \ldots, b_m$ son un número finito de enteros que no puede ser expresado como una suma finita de la $a_i$s. Por lo $A'$ es finitely generado, por el isomorfismo así es $A$.

A pesar de que el conjunto finito de generadores puede no ser única, mediante la selección de algunas conjunto de generadores para cada submonoid obtener una inyección de un conjunto de submonoids de $(\mathbb{N}, +)$ en el conjunto de los subconjuntos finitos de $\mathbb{N}$, lo que demuestra countability, y como se reivindica en Vadim la respuesta.