3
$\begingroup$

So there is such a visual way to show that set of integers has the same cardinality as the set of natural numbers. $$0,1,-1,2,-2,3,-3,4,-4,5,-5...$$ But I think it is not really rigorous proof (and I think it does not pretend to be so) of the fact that integers and natural numbers are equipotent, because it doesn't really show the bijective function between $\mathbb{Z}$ and $\mathbb{N}$ . So I tried to find such a function which will represent the sequence above. So what I found was this: $$f(n)=\sum_{i=0}^{n-1} i\cdot(-1)^{i+1}$$ The domain of course is $\mathbb{N}$. And although this function associates some integer to every natural number, I do not know how to show that for any integer $b$ I can find some $m$ such that $f(m)=b$. So to do this I need to find the inverse function of $f$ or at least show that this inverse exists, but can this inverse function be expressed in closed form? If not, is it possible to prove the inverse exists?

$\endgroup$
  • 1
    $\begingroup$ By induction on $n\in \Bbb Z^+,$ if $f(2n-1)=n$ then $f(2n)=-n$ and $f(2(n+1)-1)=n+1.$ $\endgroup$ – DanielWainfleet Jun 27 '18 at 11:04
  • 5
    $\begingroup$ In what sense is this not adequately rigorous? It is a somewhat trivial lemma that if a repetition-free sequence $x_1, x_2, x_3, ...$ enumerates a set $A$ then that set is countably infinite with the map $f: \mathbb{N} \rightarrow A$ given by $f(i) = x_i$ a bijection. Asking for an explicit formula for the inverse makes it seem more complicated than it is. $\endgroup$ – John Coleman Jun 27 '18 at 13:49
  • $\begingroup$ I second @JohnColeman 's comment. As an instructor I would much rather see the equicardinality proved by your sequence than by any cooked up formula.and its inverse. $\endgroup$ – Ethan Bolker Jun 27 '18 at 14:06
  • $\begingroup$ @JohnColeman Because you need to define the sequence somehow and prove it is repetition-free. Because of that I was trying to find this function to define this sequence. $\endgroup$ – Юрій Ярош Jun 27 '18 at 14:49
  • 3
    $\begingroup$ The point is that a description like "zero, and then each natural number followed by its negative in increasing order of size" is perfectly precise, and you can easily argue that it contains every integer exactly once. You don't need to be able to express it as a formula or give an explicit inverse to make those arguments. $\endgroup$ – Ben Millwood Jun 27 '18 at 15:43
10
$\begingroup$

$f^{-1}(n) = |2n - \frac{1}{2}| + \frac{1}{2}$

$\endgroup$
5
$\begingroup$

I am not sure what you consider to be a closed form, but I would consider a simpler version of the function $f$ to be: $$ f(n)=-\lfloor n/2\rfloor\cdot(-1)^n $$ and the inverse could be expressed as: $$ f^{-1}(n)= \begin{cases} 2n & \text{if }n>0\\ -2n+1 & \text{otherwise} \end{cases} $$

$\endgroup$
  • $\begingroup$ By closed form I mean expression in terms of polynomials, exponents, logarithms, trigonometric functions. $\endgroup$ – Юрій Ярош Jun 27 '18 at 10:00
  • $\begingroup$ @ЮрійЯрош: But in that sense your suggested form of $f$ is not a closed form, since it has a variable number of terms. What I mean by that is that summation still involves something similar to dividing into cases, since checking the condition $i\leq n-1$ is some sort of if-statement. $\endgroup$ – String Jun 27 '18 at 10:01
  • $\begingroup$ Yes, but I was asking about the inverse. Of course it's hard to imagine closed form of the inverse of the function which itself has no closed form. $\endgroup$ – Юрій Ярош Jun 27 '18 at 10:06
  • $\begingroup$ If you plug in $2n$ for positive $n$ in $f$ you get $-n$, but you should get $n$. $\endgroup$ – Юрій Ярош Jun 27 '18 at 10:24

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.