Determinación de la contabilidad en TOC

Conjunto contable es un conjunto que tiene cardinalidad igual a la de algún subconjunto de N el conjunto de números naturales . Un conjunto numerable es el que es enumerable.

La cardinalidad de un conjunto contable puede ser un número finito. Por ejemplo, B: {1, 5, 4}, |B| = 3, en este caso se denomina contablemente finito o la cardinalidad del conjunto contable puede ser infinita. Por ejemplo, A: {2, 4, 6, 8…}, en este caso se denomina infinito numerable.

Rastros comunes para el conjunto contable:

• Cardinalidad expresada en forma donde , ; m puede o no ser ∞
• Tiene elementos finitos* solo en el caso de conjuntos contablemente finitos.
• Se puede enumerar en términos de forma de tostador* existe una lista exhaustiva que puede incluir todos los elementos al menos una vez, en el caso de una lista infinita numerable, los primeros elementos seguidos de puntos suspensivos de tres puntos (…).

El conjunto de números racionales es contablemente infinito:

Siga la línea roja para construir un juego de tostadores que contenga todos los números racionales. Por lo tanto, se puede construir un conjunto exhaustivo que contenga todos los elementos al menos una vez, por lo tanto, el conjunto de números racionales es contablemente infinito.

Conjuntos incontables:
un conjunto en el que sus elementos no se pueden enumerar o, para decirlo intuitivamente, no existe una secuencia que pueda enumerar todos los elementos del conjunto al menos una vez.

Ejemplo:

R : {set of real numbers is uncountable}
B : {set of all binary sequences of infinite length} 

Rastros comunes para un conjunto incontable:

• Cardinalidad expresada en forma ;
• Es conjunto potencia de conjunto con infinitos elementos.
• Es igual conjunto a R conjunto de números reales
• Es un conjunto igual a Q conjunto de números irracionales
• Es un conjunto no listable.

Referencia rápida de operaciones sindicales:

A	B
Contable	Contable	Contable
Incontable	Incontable	Incontable
Contable	Incontable	Incontable

Ejemplo-1:
Sea N el conjunto de los números naturales. Considere los siguientes conjuntos,

P: Set of Rational numbers (positive and negative)
Q: Set of functions from {0, 1} to N
R: Set of functions from N to {0, 1}
S: Set of finite subsets of N 

¿Cuáles de los conjuntos anteriores son contables?
(A) Solo Q y S
(B) Solo P y S
(C) Solo P y R
(D) Solo P, Q y S

Explicación:
Consulte GATE CS 2018 | Pregunta 58

Ejemplo-2:
Considere los siguientes conjuntos:

S1: Set of all recursively enumerable languages over the alphabet {0, 1}.
S2: Set of all syntactically valid C programs.
S3: Set of all languages over the alphabet {0, 1}.
S4: Set of all non-regular languages over the alphabet {0, 1}. 

¿Cuáles de los conjuntos anteriores son incontables?
(A) S1 y S2
(B) S3 y S4
(C) S1 y S4
(D) S2 y S3

Explicación:
Consulte GATE CS 2019 | Pregunta 43