3
$\begingroup$

No subset of the real numbers is countable. True or false.

In looking at the wikipedia article for real numbers, I'm not really clear on the answer to this. They use the words computable and countable, and I'm not sure of the difference. Also, I dont think I fully understand the term countable. The definition states that a set is countable if it has the same cardinality as some subset of the natural numbers, but I'm not sure what that means.

  • 4
    Take a finite subset of $\mathbb{R}$ or consider $\mathbb{N} \subset \mathbb{R}$.2010-11-27

2 Answers 2

5

A set is said to be countable if there is bijection between a subset of natural numbers (or even integers) and that set.

http://en.wikipedia.org/wiki/Countable_set

Cantor's diagonalization argument shows that the set of reals is uncountable. So, there are uncountably many subsets of real numbers that are countable. For example the set consisting of any single real number.

Computability has nothing to do with counting the number of elements in a set. This is related to the idea of computable functions.

http://en.wikipedia.org/wiki/Computable_function

A real number is computable if there is finite algorithm that can yield it's digits to any desired level of accuracy.

  • 4
    Cantor's diagonalisation argument shows that the reals are uncountable and it is certainly not suited to showing that anything is countable. One proves the countability of the rationals by explicitly establishing a bijection between $\mathbb{Q}$ and $\mathbb{N}$.2010-11-27
  • 0
    Sorry, my bad. i have edited that part.2010-11-27
  • 0
    @Alex So the reals are uncountable, but there is a subset of the reals that is countable, correct? So for a set to be countable, does it have to be finite? Is the set of all natural numbers countable?2010-11-27
  • 1
    @fprime From wikipedia: "A set S is called countable if there exists an injective function f from S to the natural numbers". The identity is an injective function from $\mathbb{N}$ to themselves, so yes, the natural numbers are countable.2010-11-27
  • 0
    The use of "bijection" in the answer above is incorrect. It should be "injective function".2017-06-30
  • 0
    @MarcusAnderson: It does not matter whether one speaks of a "bijection with a subset of $\mathbb N$" or "injection into (a subset of) $\mathbb N$". The two definitions obviously define the same concept, and there is no reason to edit the answer here to change to a different-but-equivalent definition from the one the answer was originally using.2017-06-30
  • 0
    Bijection is "one to one". Injection is "none or one to one". If f (x) = 10*N then f (x) is injective (0,1 to 1) and is definitely not bijective (1 to 1). Surjective is different again. There are three terms because each term has different meaning.2017-07-01
5

It is false, because you can always pick a countable subset of your choice (e.g. {1, 2}). A set is countable if it can be put into one-to-one correspondence with the set of Natural numbers or some subset of Natural numbers. Since Natural numbers are contained in Real numbers, you can always pick a subset (like the one mentioned above) that would be countable.