Determining whether elements map to $\aleph_0$

65 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

I think the most instructive way to approach this would be geometrically.

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$.

From basic algebra we know that the solutions to an equation of this shape is a line in the plane. So we're interested in how many integer points in our wedge each of those lines pass through.

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.