my intuition tells me that C,D,E and F all the cardinality of the continuum and A and B have cardinality aleph null. Is this correct? I wouldn't know how to show it though and that's what I'm interested in. Here is the question:

Consider the following sets:

A = set of all infinite arithmetic progressions in $\mathbb{Z}$,

B = set of all infinite arithmetic progressions in $\mathbb{Q}$,

C = set of all infinite arithmetic progressions in $\mathbb{R}$,

D = set of all infinite sequences in $\mathbb{R}$,

E = set of all subsets of $\mathbb{R}$,

F = set of all closed balls in $\mathbb{R^2}$.

For each pair of these sets determine which one has larger cardinality or if they have equal cardinality.

PS: I have tried looking through the set theory section but couldn't find a similar Q and A.

  • $\begingroup$ Are you aware that there are cardinalities strictly greater than the cardinality of the continuum? Have you seen the result that $x<2^x$ even for infinite cardinal numbers? $\endgroup$ – JMoravitz Apr 26 at 13:37

First, recall that for infinite sets you have $X$ is the same cardinality as $X^n$ for any positive integer $n$. Here I will be using $\simeq$ to denote "has the same cardinality as."

Arithmetic progressions can be uniquely determined by two pieces of information: the starting value and the common difference.

We see then:

  • $A\simeq \Bbb Z^2\simeq \Bbb N$
  • $B\simeq \Bbb Q^2\simeq \Bbb N$
  • $C\simeq \Bbb R^2\simeq \Bbb R$

Next, the set of infinite sequences in $\Bbb R$ can be a little tricky, but the answers to this question show

  • $D\simeq \{f~\mid~f~:\Bbb N\times \Bbb N \to \{0,1\}\}\simeq \Bbb R$

Now, the set of all subsets of $\Bbb R$ is the Power Set of $\Bbb R$ and by Cantor's theorem we know that the power set of any set is of strictly greater cardinality.

  • $E = \mathcal{P}(\Bbb R)$

Finally, the set of all closed balls in $\Bbb R^2$ can be described using three pieces of information. The $x$-coordinate of the center of the ball, the $y$-coordinate of the center of the ball, and the radius of the ball. We see then that

  • $F \simeq \Bbb R^3\simeq \Bbb R$

Or, if you prefer, these can be written as having cardinality $\aleph_0,\mathfrak{c}, 2^{\mathfrak{c}}$ respectively

  • $\begingroup$ Thank you great answer. This will help me a lot. $\endgroup$ – TommySmith97 Apr 26 at 14:01
  • $\begingroup$ I have one question about D: in the answers linked what does the notation {𝑓𝑛}𝑛 mean? It's been a while. $\endgroup$ – TommySmith97 Apr 26 at 14:05
  • $\begingroup$ @TommySmith97 a technique called currying lets you redescribe a function which takes multiple arguments and gives an output instead as a function which takes one argument and returns a function which is then evaluated with the second argument giving the final output. It can be applied in reverse as well, a function which takes input and returns a function which later takes other input and returns a value can be thought of as a single concise function that takes both arguments as input. $\endgroup$ – JMoravitz Apr 26 at 14:10
  • $\begingroup$ Ah thank you I think I understand. $\endgroup$ – TommySmith97 Apr 26 at 14:11
  • $\begingroup$ @TommySmith97 as for what $\{f_n\}_n$ means, it is a sequence of functions. $(f_1,f_2,f_3,\dots)$. In this case, each function itself represents a real number and this is a sequence of real numbers, i.e. a sequence of functions. Each function is itself a function from $\Bbb N\to\{0,1\}$. $\endgroup$ – JMoravitz Apr 26 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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