Can anything be said on this issue? I was wondering if one can find a mapping such that the cardinality of two sets of perfect and non-perfect squares can be compared. Not sure if it's a good question or not.
$\begingroup$
$\endgroup$
6
-
$\begingroup$ $\sum \frac 1{n^2}$ converges but $\sum \frac 1n$ diverges. $\endgroup$– luluJun 28, 2016 at 18:26
-
1$\begingroup$ To be clear: the cardinalities are the same (both sets are countable). But if you cap the sample at some large $N$ there are only about $\sqrt N$ squares less than $N$ but about $N-\sqrt N$ non-squares. $\endgroup$– luluJun 28, 2016 at 18:28
-
$\begingroup$ Did my second comment help? Both sets are countably infinite, but as the size $N$ grows the probability that a random natural number $n<N$ is a non-square goes to $1$. $\endgroup$– luluJun 28, 2016 at 18:29
-
$\begingroup$ The relative densities are different, but they are both countably infinite sets, thus have the same cardinality. This is much the same as how the cardinality of the positive even integers is the same as the cardinality of the integers in general. $|\{2,4,6,8,10,\dots\}|=|\{\dots,-2,-1,0,1,2,\dots\}|$ $\endgroup$– JMoravitzJun 28, 2016 at 18:29
-
$\begingroup$ Thanks, I didn't see it. :) $\endgroup$– nullJun 28, 2016 at 18:30
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
4
Let $\mathbb{S}$ denote the set of perfect squares:
$f:\mathbb{S}\to\mathbb{N}$
$f(x)=x$
$g:\mathbb{N}\to\mathbb{S}$
$g(x)=x^2$
Let $\mathbb{T}$ denote the set of non-perfect squares:
$f:\mathbb{T}\to\mathbb{N}$
$f(x)=x$
$g:\mathbb{N}\to\mathbb{T}$
$g(x)=x^2+1$
-
$\begingroup$ how come $g(x) = x^2 + 1$ a bijection from $\mathbb{N}$ to $ \mathbb{T}$? $\endgroup$ Jun 28, 2016 at 20:59
-
$\begingroup$ @vidyarthi: It's not. It is a one-to-one function from $\mathbb{N}$ to $\mathbb{T}$. The other function is a one-to-one function from $\mathbb{T}$ to $\mathbb{N}$. Together they are sufficient for showing that the cardinalities of the two sets are equal (as far as I know). $\endgroup$ Jun 29, 2016 at 7:53
-
$\begingroup$ you mean the cantor-Schroeder Bernstein theorem? $\endgroup$ Jun 29, 2016 at 19:30
-
$\begingroup$ @vidyarthi: Could be, but I was basically using my intuition here. If you have some evidence of this being wrong, then please explain (or show some sort of counterexample), and I will remove the answer. Thanks. $\endgroup$ Jun 29, 2016 at 19:35