Countable Sets

Definition

All finite sets are countable sets If the infinite set has the same cardinality as ${\mathbb{Z}}^{+}$, the set is said to be countable, denoted by ${\aleph }_o$ If the infinite set has a different cardinality than ${\mathbb{Z}}^{+}$, then it is uncountable KNOW THAT $\mathbb{R}$ IS UNCOUNTABLE

$|\mathbb{R}|>|{\mathbb{Z}}^{+}|$

$|\mathbb{R}|=|P({\mathbb{Z}}^{+})|=2^{{\aleph }_0}={\aleph }_1$

${\aleph }_0<{\aleph }_1<{\aleph }_2$

No such set $A$ such that ${\aleph }_0<|A|<{\aleph }_1$

Set of programs countable

function $f$ is computable if there exists a computer program that finds the value of $f$ for some input

Examples of Countable Sets

• Odd positive integers $f:{\mathbb{Z}}^{+}\to O^{+}$
• Even positive integers f:
• Even negative integers: \begin{align}1\leftrightarrow -2 \\ 2\leftrightarrow -4\\ \vdots\end{align}