6
$\begingroup$

I have become somewhat overwhelmed with a problem I am working on I had a friend tell me that my proof was wrong. I would be grateful if someone could explain why I am wrong, and possibly offer a alternate solution.

Problem: A function $f\colon \mathbb{N} \to \mathbb{N}$ is zero almost everywhere iff $f(n)=0$ for all except a finite number of arguments. It can be shown that the set of functions that are zero almost everywhere is enumerable.

Attempt: Let $E=\{f\colon \mathbb{N} \to \mathbb{N}\mid f \text{ is zero almost everywhere}\}$. Let $Q\colon \mathbb{N}\to E$ such that $Q(n)=f_n$ where we define $f_n(x)=0$ for all but $n\in\mathbb{N}$ values.

Fix $f\in E$, then we need show that there exists some integer $n\in N $ such that $f=f_n$, but by defnition $f$ is zero almost everywhere, so $f(x)=0$ for all but a finite $r\in\mathbb{N}$ values. Choose $n=r$.

I realize that this is a incorrect proof, but I'm not really sure where. I also never used a hint I was given which says to use the fact that a countable union of countable sets is countable.

Thank you.

$\endgroup$
5
  • $\begingroup$ Two different functions can be nonzero for exactly $r$ values, so $Q$ is not well defined. $\endgroup$
    – Pedro M.
    Feb 19, 2015 at 23:11
  • $\begingroup$ To expand @Pedro’s comment, your $f_n$ is not well-defined. For each $k$ and $\ell$ in $\Bbb N$ let $g_{k,\ell}\Bbb N\to\Bbb N$ be $0$ except at $k$, and let $g_{k,\ell}(k)=\ell$. Then your $f_n$ could be any one of these functions $g_{k,\ell}$. $\endgroup$ Feb 19, 2015 at 23:16
  • $\begingroup$ Your $Q$ is a correspondence $1$-to-many. Your proof could be completed and use the hint if you show that each $Q(n)$ is countable. $\endgroup$
    – Tom
    Feb 19, 2015 at 23:16
  • $\begingroup$ This question says that using "if" in definitions is an established convention. How come your definition uses "iff"? $\endgroup$
    – user26486
    Feb 20, 2015 at 5:24
  • $\begingroup$ Because this was the way I typed it. $\endgroup$
    – Valentino
    Feb 20, 2015 at 5:38

5 Answers 5

5
$\begingroup$

We will find an explicit bijection from $E$ to $\mathbb{N}\setminus\{0\}$. Getting an explicit bijection from $E$ to $\mathbb{N}$ (or in the other direction) is then easy.

Let $p_0,p_1,p_2,\dots$ be the primes in their natural order. If $f$ is a function which is $0$ almost everywhere, map $f$ to $$p_0^{f(0)}p_1^{f(1)}p_2^{f(2)}p_3^{f(3)}\cdots.\tag{1}$$ The product in (1) is a finite product. By the Fundamental Theorem of Arithmetic, the mapping we have just defined is a bijection from $E$ to $\mathbb{N}\setminus\{0\}$.

$\endgroup$
3
$\begingroup$

$Q$ is not correctly defined. You say that $Q(n)$ is a function that is not zero for exactly $n$ values, but there are (infinitely) many functions that satisfy this property.

If you specify which is that function (or use the Axiom of Choice), then $Q$ will be certainly not surjective.

How about the following? Define $E_k$ as the set of functions that are $0$ for $n>k$ (for $n\le k$ may be zero or not). Then $E_k$ is finite. Now use the hint you mentioned.

$\endgroup$
8
  • 1
    $\begingroup$ Of course. It is not zero for at most $k$ values, so it is zero almost everywhere. $\endgroup$
    – ajotatxe
    Feb 19, 2015 at 23:32
  • 1
    $\begingroup$ Perhaps I misunderstood, but it seems that $E_k$ is countable, not finite. $\endgroup$
    – dtldarek
    Feb 20, 2015 at 0:10
  • 1
    $\begingroup$ @Valentino $E_k \subset E$, but $E_k \notin E$. $\endgroup$
    – dtldarek
    Feb 20, 2015 at 0:13
  • 1
    $\begingroup$ @Valentino That can be fixed by assuming that elements of $E_k$ have values at most $k$. Then such sets are finite and their union still covers everything. Or you can define $E_k = \{f \mid f \leq g_k\}$ with $g_k$ taken from my answer to your previous question. $\endgroup$
    – dtldarek
    Feb 20, 2015 at 0:19
  • 1
    $\begingroup$ @Valentino By that phrase I meant $E_k = \{f : \mathbb{N}\to\mathbb{N} \mid \forall n\leq k.\ f(n)\leq k, \forall n > k. f(n)=0\}$. $\endgroup$
    – dtldarek
    Feb 20, 2015 at 7:35
3
$\begingroup$

Hint: Count your functions as follows. Let $A_N$ be the set of all functions which are non-zero only for $n \leq N$ and all non-zero values of the function are less than or equal to $N$. Clearly your set is $\cup_N A_N$. But each $A_N$ is finite, so if you know that a countable union of finite sets is at most countable, then you are done.

$\endgroup$
2
  • $\begingroup$ Why is our set clearly $\bigcup _N A_N$? $\endgroup$
    – Valentino
    Feb 20, 2015 at 1:01
  • $\begingroup$ @Valentino Because for any almost everywhere zero function, there is a maximum $n$ (call it $N_1$) where the function $f(n)$ is non-zero, and there is a finite maximum (call it $N_2$) for the function values $f(n)$ where the function is non-zero. Then just put $N = \max(N_1,N_2)$ and your function will be in $A_N$. $\endgroup$ Feb 20, 2015 at 20:24
2
$\begingroup$

A common way to prove a set is enumerable is to use the following fact (also the hint you provided):

A union of at most countably many enumerable sets is enumerable.

The proof of this statement goes exactly like the usual proof that the rationals are enumerable.

With this, can you decompose your set $E$ into a union of countable many enumerable sets?

(Hint: How many elements of $E$ have exactly $1$ nonzero element? How many with exactly $2$? How many...)

$\endgroup$
9
  • $\begingroup$ Ahhhh the answer to the hint is countably infinitely many right? Or did I miss something? $\endgroup$
    – Valentino
    Feb 19, 2015 at 23:32
  • 1
    $\begingroup$ It is, but do you see why? $\endgroup$ Feb 19, 2015 at 23:37
  • 1
    $\begingroup$ That's basically right, although I assume you meant "countably infinitely many." What might help you visualize this: a function $f:\mathbb{N}\to\mathbb{N}$ is the same thing as a sequence $(a_1,a_2,\ldots)$ with $a_i\in\mathbb{N}$. Now, can you reason out the case when there are exactly $2$ nonzero terms of the sequence? $\endgroup$ Feb 19, 2015 at 23:55
  • 1
    $\begingroup$ Yes, but can you prove it? If you can then you're basically done. $\endgroup$ Feb 20, 2015 at 0:17
  • 1
    $\begingroup$ Try doing it for $k=2$. If you can do this you will see all the others. What choices do you need to make to construct a sequence of natural numbers $(a_n)$ that only has $2$ nonzero terms? (Hint: you can get away with making at most $4$ choices. What are they?) $\endgroup$ Feb 20, 2015 at 0:48
1
$\begingroup$

Each $\Bbb N\to\Bbb N$ function is a natural sequence. Let's define a 'portrait' of an almost-everywhere zero function as a finite sequence of all arguments, for which the function has non-zero value, interleaved with those values. For example $f=(0, 0, 15, 0, 27, 0,...)$ has a portrait $P(f)=(3, 15, 5, 27)$. Of course the portrait is unique: each function has its own portait. Let's also define a natural 'size' of a function $f$ as a sum of portrait's terms $S(f)=\sum_{n\in\Bbb N}P(f)_n$. The example function above has size $3+15+5+27=50$.

All functions can be ordered by an increasing size. There is of course many, but always finitely many functions of the same size. All functions of the same size can be ordered lexicographically by their portrait.
This way we define a sequence of all almost-everywhere zero natural sequences, which estabilishes their enumerability.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .