¿Hay tal cosa como un sistema contable con un subconjunto incontable?

Question

¿Hay tal cosa como un sistema contable con un subconjunto incontable?

Realmente yo sé la respuesta. Bueno, creo que sé la respuesta, que es NO. Por desgracia, el profesor en una clase de teoría de computación dijo que sí, hay tal subconjunto.

Esto es para resolver una discusión con los compañeros. Una discusión que se va a ninguna parte así que nos vamos a las internets para un veredicto.

Gracias de antemano por peso esta cuestión.

Answer 1

Por supuesto, es fácil ver que cualquier subconjunto de una contables conjunto es contable. Al enumerar el conjunto más grande, acaba de saltar sobre cualquiera de los elementos que no están en el subconjunto, y una enumeración de las subconjunto.

Sin embargo, ya que usted menciona que estaban en la teoría de la computabilidad supuesto, hay un par de computabilidad como sentidos en los que algo como una respuesta positiva a la pregunta es posible.

• Cada infinita computably conjunto enumerable tiene numerosas subconjuntos que no son computably enumerable. Esto es simplemente debido a que cada conjunto infinito tiene una cantidad no numerable de subconjuntos, y la mayoría de estos no se computably enumerable, ya que sólo hay countably muchas c.e. los conjuntos. Pero desde una perspectiva de la computabilidad, computably enumerable es a menudo el derecho análogo de contables, ya que esos son los conjuntos con una computable función de enumeración, y este es un muy razonable sentido en el que la demanda es casi cierto.

• No puede ser c.e. conjuntos cuyo complemento es infinito, pero que no contiene infinitas c.e. subconjunto. Por lo tanto, usted puede enumerar el conjunto $S$, y la infinita cantidad de números que no están en $S$, pero no es computable para enumerar un conjunto infinito de números que no están en $S$. Estos son conocidos como el simple conjuntos, y se estudió a partir de la hora de Publicar.

• Sin AC, que es coherente que usted puede tener un conjunto $A$ con una relación de equivalencia $\sim$, que el número de clases de equivalencia de a $\sim$ $A$ es estrictamente mayor que la cardinalidad de a $A$. Por ejemplo, podemos hacer una relación de equivalencia $\sim$ tener exactamente $\mathbb{R}+\omega_1$ muchas clases de equivalencia, diciendo que dos reales son equivalentes si son iguales, o de lo que tanto el código como las relaciones en $\omega$ que están bien las órdenes de la misma longitud. Pero bajo el Axioma de Determinación, no es $\omega_1$-secuencia de los distintos números reales, por lo que esta cardinalidad es estrictamente mayor que $\mathbb{R}$.

Answer 2

Un conjunto es infinito numerable si existe una función inyectiva de ella a los números naturales.

Supongamos que $A$ es contable y $f\colon A \to \omega$ es una inyección testigos, entonces si $B\subseteq A$ la restricción de $f$ $B$ es una función inyectiva de $B$ a los números naturales, por lo tanto $B$ es contable.

Una nota es que hay conjuntos infinitos sin un subconjunto contable sin el axioma de elección. Es una cantidad otra.

Answer 3

Si el curso era un curso de TCS, entonces tal vez tu profesor mezcla sistemas contables con sistemas enumerables. (Esto sucede a veces, especialmente en las áreas de lengua alemana, donde es "abzählbar" vs "aufzählbar).

Cada subconjunto de un sistema contable es contable o finito (o vacío). Sin embargo, no todo subconjunto de un conjunto enumerable es enumerable.

Por ejemplo, $\mathbb{N}$ es trivial enumerable. Pero el codomain de la función ocupada bever, que es un subconjunto de $\mathbb{N}$, no es.

Answer 4

Considere un conjunto que contiene un contable de la colección de innumerables conjuntos.

Un ejemplo sería el conjunto cuyo $m^{th}$ (a pesar de que no tienen un orden) es el conjunto de los números reales entre el$m$$m+1$.

Entonces puedo decir que un conjunto tiene una contables subconjunto, y que cada uno de estos subconjuntos contiene un incontable número de elementos.

Sin embargo, yo no podía decir que este conjunto contiene un incontable subconjunto de una contables subconjunto de los números reales, simplemente que contiene una contables subconjunto de (innumerables) conjuntos.