Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The continuum hypothesis states that there is no set whose cardinality is strictly between that of the integers and the real numbers. However, it seems that it is possible to construct sets that consists of integers and some irrational numbers with cardinality lying in between the two. Here is an example.

If we define a set $\{f|(\exists x_1 \in \mathbb{Z}$ (set of integers)) $\wedge$ ($\exists x_2 \in \mathbb{Z^+}$ (set of positive integers)) $\wedge$ $ (f=x_1.\sqrt{x_2})\}$, then the members of the set can be obtained by writing the $x_1$'s and $x_2$'s along the vertical and the horizontal direction as follows:

   1   2   3   4 

1 $\ \sqrt{1}$, $\sqrt{2}$, $\sqrt{3}$, $\sqrt{4}$...

2 $\ 2\sqrt{1}$, 2$\sqrt{2}$, 2$\sqrt{3}$, 2$\sqrt{4}$...

3 $\ 3\sqrt{1}$, 3$\sqrt{2}$, 3$\sqrt{3}$, 3$\sqrt{4}$...

4 $\ 4\sqrt{1}$, 4$\sqrt{2}$, 4$\sqrt{3}$, 4$\sqrt{4}$... .

Now, the above set consists of all the integers along with some irrational numbers. There are two possible arguments here:

Argument 1: If, we map all the integers to the set of integers then there are still remaining irrational numbers which are not mapped to any elements in the set of the integers. Using this argument, can we state that the above mentioned set has a cardinality that is at least greater than that of the set of integers? This argument as it seems might not be mathematically sound.

Argument 2: If we traverse the set (skipping any repeated elements) to show a one-to-one correspondence with the set of integers, can we say that this set also has the same cardinality as that of the set of integers. Does, this imply that any set that can be expressed exhaustively using integers (finite in number) has the cardinality same as that of the set of integers? Does this also hold for sets that can be expressed using countably infinite integers?

Note: The original argument of George Cantor regarding the cardinality of rational numbers can be obtained by defining a similar set of two variables $\{f|(\exists x_1, x_2 \in \mathbb{Z}$ (set of integers)) $\wedge$ $ (f\neq 0 \wedge f.x_2=x_1)\}$. He also showed that the cardinality of the set of rational numbers is same as that of natural numbers using a similar approach.

The above mentioned argument can be extended to sets constructed using more variables with increasingly complex expressions as follows:

$\{f|(\exists x_1,x_2 \in \mathbb{Z}$) $\wedge$ ($\exists x_3 \in \mathbb{Z^+}$) $\wedge$ $ (f=x_1.e^{x_2}\sqrt{x_3})\}$

$\{f|(\exists x_1,x_2,x_3 \in \mathbb{Z}$) $\wedge$ ($\exists x_4 \in \mathbb{Z^+}$) $\wedge$ $ (f=x_1.\pi^{x_2}.e^{x_3}\sqrt{x_4})\}$


$\{f|(\exists x_1,x_2,x_3,...,x_{\infty} \in \mathbb{Z}$) $\wedge$ $ (f=\phi(x_1,x_2,...,x_{\infty}))=\mathbb{R}\}$ (set of real numbers expressed with an infinitely complex function $\phi(x_1,x_2,...,x_{\infty})$)

Is it possible to say that the set of real numbers can be obtained by a function of infinite complexity expressed using finite or countably infinite number of variables? Does, this imply that the set of real numbers also has the same cardinality as that of the set of integers which is in contradiction with the original proposition of Cantor that the set of real numbers has a larger cardinality than the set of integers. If this seems to be a contradiction then does that mean that all sets constructed using functions of increasing complexity with finite or countable infinite number of variables do not necessary have the same cardinality as that of the set of integers?

Is there any notion of complexity of a function on the basis of what portion of the set of real numbers does it capture in its range?

share|cite|improve this question

closed as off-topic by Andrés E. Caicedo, Pedro Tamaroff, Sanath K. Devalapurkar, mookid, Alexander Gruber Mar 30 '14 at 3:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – Andrés E. Caicedo, Pedro Tamaroff, Sanath K. Devalapurkar, mookid, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.

Argument 1 is not sound. You can map $\mathbb{Z}$ to $\mathbb{Z}$ by $x \mapsto 2x$, but just because it's not surjective, doesn't mean that $|\mathbb{Z}|$ is strictly greater than $|\mathbb{Z}|$. But Argument 2 is right: $\mathbb{Z}^n$ for any positive integer $n$ has the same cardinality as $\mathbb{Z}$. It doesn't hold for countably infinite: $\mathbb{Z}^\mathbb{N}$ has the same cardinality as $\mathbb{R}$. – Henry Swanson Mar 30 '14 at 2:32
up vote 8 down vote accepted

For any finite $n$, the set $\mathbb Z^n$ of all $n$-tuples of integers is countable, and therefore so is any set that can be obtained by applying some function to all the members of $\mathbb Z^n$. That includes the first three of the four sets described in your question.

On the other hand, the set $\mathbb Z^\omega$ of infinite sequences of integers is uncountable; it has the cardinality of the continuum. A set obtained by applying a function to all elements of $\mathbb Z^\omega$ is likely to be uncountable, but it might be countable if the function mapped lots of elements of $\mathbb Z^\omega$ to the same element. So, without knowing what function is being applied to the infinite sequences, one cannot reach a definite conclusion about the cardinality of the resulting set.

share|cite|improve this answer

Whatever function you define with domain an countable set, i.e., with cardinality $\aleph_0$, the cardinality of its image couldn't be greater than $\aleph_0$. So your set is still countable.

On the other hand, your $\phi$ function is actually $\mathbb{Z}^\omega\to\mathbb{R}$, i.e., the domain of which is sequences, so its image could be uncountable.

However, it was proved that CH is independent with respect to ZFC, so you cannot say it's true or false. Assuming ZFC is consistent, both ZFC+CH and ZFC+not CH are consistent.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.