# Determining whether elements map to $\aleph_0$

Consider the infinite sequences

$$A=\left\{\begin{array}{lcr} 1,\\2,2,\\3,3,3,\\4,4,4,4,\\\vdots\end{array}\right\}\qquad B=\left\{\begin{array}{lcr} 1,\\2,3,\\3,4,5,\\4,5,6,7,\\\vdots\end{array}\right\} \qquad C=\left\{\begin{array}{lcr} 1,\\2,1,\\3,2,1,\\4,3,2,1,\\\vdots\end{array}\right\}$$

$A$ is constructed by adding $n$ copies of $n$.

$B$ is constructed by counting up from $n$ to $2n-1$.

$C$ is constructed by counting down from $n$ to $1$.

It's immediately clear that all three sequences have the same number of elements, namely infinitely many. However, if you ask how many times some $x$ appears in a sequence, you get different results: $x$ for $A$, $\left\lceil{x/2}\right\rceil$ for $B$, and infinitely many for $C$.

In one sense, I understand why this is; it's pretty clear from inspection that $C$'s elements will show up in each consecutive row, while the other two sequences' elements fizzle out.

What I'm curious about is if there's a more satisfying explanation for what's happening here, or a rule that covers this behavior. Based on only a description to the effect of "$A$ stays constant, $B$ counts up, $C$ counts down," I would never expect one of them to have such wildly different properties from the other two.

• If you have three different sequences, it's surely no surprise that some number occurs a different number of times in each. Commented Aug 18, 2018 at 15:38
• Sure... what surprises me is that every element in $A$ and $B$ only occurs a finite number of times, and every element in $C$ occurs infinitely many times. Commented Aug 18, 2018 at 15:40
• It's not really that $B$ counts up while $C$ counts down -- you would get the same behavior if you reversed each "row" of $B$ and $C$ separately. Commented Aug 18, 2018 at 15:44
• John von Neumann, one of the great mathematicians of the 20th century, advised a student thusly: "Young man, in mathematics, one does not understand things. One merely gets used to them." Commented Aug 19, 2018 at 1:58

You have three functions on $\mathbb Z\times \mathbb Z$: $$A(x,y) = y \qquad B(x,y) = -x+y \qquad C(x,y) = x+y$$ and now you're restricting each of them to the "wedge" $\{ (x,y)\mid 0\le x<y \}$. You then ask about the number of solutions to $f(x,y)=k$ within this wedge, for different $k$.
We can find the direction of the solution lines easily from the coefficients: For $A$ they are horizontal; for $B$ they slant $45^\circ$ upwards (upwards because our $y$ coordinate grows downwards), and for $C$ they slant downwards.
Geometrically we can see that the lines in $A$ and $B$ intersect both sides of the wedge, so each line has a finite length within the wedge and can only have finitely many integer points.
However, the lines in $C$ are parallel to one of the sides of the wedge, and so if any point on the line is within the wedge, an entire infinite ray will be. Since the slope is rational, this means that every integer point on this ray will have an infinite sequence of integer points further down the ray.