Cardinality of decreasing functions from N to N

[CGandC]

Problem: Find the cardinality of the set $A = \{f \in \Bbb N \to \Bbb N. \forall n\leq m .f(n) \geq f (m) \}$.

I know that $A \subseteq P(\Bbb N \times \Bbb N)$ implies $|A| \leq |P(\Bbb N \times \Bbb N)| = | P(\Bbb N) | = \aleph$. So I have a feeling that $\aleph \leq |A|$ and this is what I want to show by finding an injective function from a set whose cardinality is $\aleph$ to set $A$ and then I'll use Cantor-Schroder-Bernstein in order to deduce that $|A| = \aleph$.

Attempt 1:
Define $F : P( \Bbb N ) \to A$ as $F(\tau)(n) = \sum \limits_{a \in \tau} a ~~~~~~~ , \forall \tau \in P( \Bbb N ), \forall n \in \Bbb N$
Attempt 2:
Define $F : P( \Bbb N ) \to A$ as $F(\tau)(n) = \begin{cases} \sum \limits_{a \in \tau \setminus\{n\}} a &n\in \tau \\\sum \limits_{a \in \tau \cup \{n\}} a &n\notin \tau \end{cases} ~~~~~~~ , \forall \tau \in P( \Bbb N ), \forall n \in \Bbb N$

However, Attempt #1 is bad since it's not injective $( F({3,5,7})(n) = F({15})(n) = 15 , \forall n \in \Bbb N)$ and I don't even know if attempt #2 is ok or not I tried checking but couldn't get to results. Do you have any ideas as to what the injective function should be? Maybe $A$ is actually countable?

 

[Office_Shredder]

Have you tried just writing down some examples of functions to see what they look like?

In particular, how many degrees of freedom do you have to make these as arbitrarily as possible?

 

[CGandC]

I think these functions are a constant from some point. So I think I have finite degrees of freedom to make each such function arbitrary as possible.
If so then each such function can be represented as a finite sequence.
So then, $A$ is a set of sequences. But what can I do with this info?

 

[Office_Shredder]

I actually think you cannot represent each function as a single sequence, or at least not naturally. I still recommend you actually fully write down like, three of these functions, and not trivial examples.

 

[CGandC]

We have $f(n) \geq f(n+1) \forall n \in \Bbb N$, hence $f$ is monotonically decreasing and is bounded below by $0$ ( Since $f: \Bbb N \to \Bbb N$ ). Hence $f$ converges ( Not necessarily to $0$ though ). So I think $A$ is the set of all functions from naturals to naturals that are monotonically decreasing and converging. How you'd continue from here?

 

[Office_Shredder]

Ok, here's one example of a function:
f(n)= 2 if n<5
f(n)=1 otherwise.

Can you write down a couple more? Try making at least one that's complicated. This isn't me just being pedantic, writing down example objects is a healthy practice and once you do it the simple description of the functions is much easier to see for me as least.

 

[mathman]

You wrote $\aleph$. Did you mean $\aleph_0$.?

 

[SSequence]

Shouldn't the answer be $\aleph_0$ (that is, countable). We are just talking about finite sequences/lists of natural numbers here (and adding some suitable restrictions upon them).

 

[CGandC]

Ok, here's one example of a function:
f(n)= 2 if n<5
f(n)=1 otherwise.

Ok sorry, here's another example:

$f(n) = c ~~~ ,\forall n \in \Bbb N$, where $c$ is some natural constant.

I don't think there are many more options, besides variants of what you wrote like
$f(n) = c_1 , ~~ if~~ n<N$
$f(n) = c_2 , ~~ otherwise$
and $c_1 > c_2$, where $c_1 , c_2 , N$ are naturals.

You wrote $\aleph$. Did you mean $\aleph_0$.?

I don't know the answer.

Shouldn't the answer be $\aleph_0$ (that is, countable). We are just talking about finite sequences/lists of natural numbers here (and adding some suitable restrictions upon them).

So each function could be represented by a finite sequence, so $A$ will be a set of finite sequences , but what makes $A$ be countable?

 

[SSequence]

So each function could be represented by a finite sequence, so $A$ will be a set of finite sequences , but what makes $A$ be countable?

For example, let $B$ be the set of all finite sequences of natural numbers. The point here is that there is a bijection between:
---- each function in the collection $A$
---- an appropriately selected subset of $B$ (let's call it $C$)

Now because $C \subset B$ and $B$ is countable, we must have $C$ as countable. And now, because there is a bijection between $A$ and $C$, we must have $A$ as countable.

 

[CGandC]

Ok so since $A \subseteq B$, and since $B$ is countable, then since $A$ is infinite set ( this is seen since we have constant functions of the form $\forall n,c \in \Bbb N . f(n) = c$ that belong to it and there are infinite of those ) then $A$ is also countable.
I didn't know that the set of all finite sequences is countable, I looked it up now on wiki, thanks.

 

[SSequence]

Ok so since $A \subseteq B$, and since $B$ is countable, then since $A$ is infinite set ( this is seen since we have constant functions of the form $\forall n,c \in \Bbb N . f(n) = c$ that belong to it and there are infinite of those ) then $A$ is also countable.
I didn't know that the set of all finite sequences is countable, I looked it up now on wiki, thanks.

Yes, the idea is right. But writing $A \subseteq B$ might not be strictly correct. I think a better way is to say that there is a bijection between $A$ and some subset of $B$. (rest of the logic is last two sentences of post#10)

 

[Office_Shredder]

You cannot easily biject these functions into the set of finite sequences.

For your example, there are three numbers specified here, $c_1,c_2,N$. Does the order matter? If I just gave you the same list in a different order, could you construct uniquely the same function, or are there other functions that can use the same set of numbers in different places?

This is why writing down example is a healthy practice, if you wrote a bunch of them down you would notice you are picking both what values the function has, and also where it changes value.

 

[SSequence]

Considering the example described in post#9:
$f(n) = c_1 , ~~ if~~ n<N$
$f(n) = c_2 , ~~ otherwise$
and $c_1 > c_2$, where $c_1 , c_2 , N$ are naturals.

What's wrong with the following (ordered) list:
$c_1,c_1,c_1,...,c_1,c_2$ (essentially $N$ number of $c_1$'s)

Doesn't this uniquely identify the given function?

============

Also, not all finite lists will necessarily identify some function (in the set $A$). That's why I mentioned subset of $B$ (the set of all finite lists) in post#10.

 

[CGandC]

Another example:
$f(n) = n ~~~ if ~ n<100$
$f(n) = 0 ~~~ else$

I think there are no functions that can use same set of values in different indexes ( if we represent them aslists ), because by doing so the monotonicity will break since one value will have to be larger than the other so the index at which the monotonicity breaks will change.

 

[SSequence]

I think (given the preceding discussion) it is useful to clarify some distinctions when we say "finite lists of natural numbers". For example, we might mean:
(1) Finite ordered lists with repetitions allowed (we could call these finite sequences of natural numbers)
(2) Finite ordered lists without repetitions
(3) Finite unordered lists without repetitions (basically sets of natural numbers with finite cardinality)

All of these are countable. In post#10, I was referring to (1) since this is the most common usage of the term I have seen [i.e. by default] and also because in the given context it makes the question easier.

If we use (2) or (3) then we would need to do more tricky encoding [though (2) is only slightly more difficult than (1)].

===============================================
===============================================

Another example:
$f(n) = n ~~~ if ~ n<100$
$f(n) = 0 ~~~ else$

I didn't quite understand what you meant to say. However, I think what office shredder was saying in post#13 (it seems) was roughly along the following lines.

If we use the option-(1) which I mentioned above then we can encode this function $f$ via the following list:
(n,n,...,n,0) ------ list of length 101

But if we are using option-(2) then we also need to record the positions at which the function values decrease. For example, if we try to encode the function $f$ via the following list:
(n,0)
it is clearly insufficient for a bijection because we could have another function say $g$ (with the same encoding) such that $f \neq g$. For example:
$g(n) = n ~~~ if ~ n<50$
$g(n) = 0 ~~~ else$

So the encoding for option-(2) will be slightly more complicated.

 

[stevendaryl]

I haven't read all these responses, but clearly, the set $A$ has the same cardinality as the integers.

If $f$ is a nonincreasing function from $N$ to $N$, then we can characterize $f$ completely by giving the first $n$ values: $f(0), f(1), ..., f(n)$, where $n$ is chosen so that $f(x+n) = f(n)$ for all $x \ge 0$.

Then you have to prove (or cite) the fact that the set of all finite sequences are countable.

 

[CGandC]

Proof: for every $f \in A$ define the set $A_{\alpha} = \{ f(n) | n \in \Bbb N \}.$ Denote $\alpha = min A_{\alpha }$. Define the set $A_{\beta} = \{ n \in \Bbb N | f(n) = \alpha \}$. Denote $\beta = min A_{\beta}$. Notice that $\forall n \geq \beta . f(n) = \alpha$. Hence, we can express $f$ as a finite sequence up-to index $\beta$ ( after which the values just repeat themselves ) $< f(0),f(1),...,f(\beta)>$ hence $A$ is a set of finite sequences of naturals and since every set of finite sequences of naturals is countable then $A$ is countable.

Question: What I want to know is, when I wrote " we can express $f$ as a finite sequence up-to index $\beta$ ( after which the values just repeat themselves ) $< f(0),f(1),...,f(\beta)>$ " , is it valid to do such a thing - take an infinite sequence and make it finite ? after all, $f$ is the same after index $\beta$ but it is still infinite.

 

[SSequence]

It looks OK because it is fairly understandable. One small point to mention though:

... hence $A$ is a set of finite sequences of naturals and since every set of finite sequences of naturals is countable then $A$ is countable.

It would probably be suitable to change the wording a bit here. Let $B$ denote the set of all finite sequences of natural numbers. Instead of saying "$A$ is a set of finite sequences of naturals", one might consider writing:
"$A$ is in bijection with some subset of $B$. Since every subset of $B$ is countable (because $B$ is countable), we have $A$ as countable too."

==========================================

Here is how I would write the same thing (maybe it will help answer the question you asked). This is kind of a repeat of post#10 though.

==========================================

For every $f \in A$, define a set $X \subseteq \mathbb{N}$ as $X=range(f)=\{f(n)|n \in \mathbb{N}\}$. Note that $X \subseteq \mathbb{N}$ and hence has a minimum element (w.r.t. comparison relation for natural numbers). Now define $\alpha=\min (X)$. Now define a set $Y \subseteq \mathbb{N}$ as $Y=\{n \in \mathbb{N}|f(n)=\alpha\}$. Now we write $\beta=\min (Y)$.

Now let $B$ be the set of all finite sequences of natural numbers. We want to define a 1-1 function $G:A \rightarrow B$. For a given $f \in A$, we want to describe how to calculate $G(f)$. We define $G(f)$ to be:
$G(f)=<f(0),f(1),f(2),...,f(\beta)>$
Observe that this function $G$ is necessarily 1-1. Now because $range(G)=\{G(F)|F \in A\} \subseteq B$, and $B$ is countable, we get $A$ as countable.


Edit:
There is one small (but somewhat annoying) point here. We showed that $A$ is countable. However, note that $A$ is "countably infinite" and not "countably finite". If we are being quite formal here, there seem to be two options here it seems.

(i) We could proceed as above and in the end note that because $A$ has infinite number of elements it is countably infinite.

(ii) Another way would be to change the wording of the argument and use "countably infinite" instead of "countable" at several places. At number of points we would also need to change "subset" with "infinite subset". This makes the argument more verbose but also neater in a way.

 

[CGandC]

Ok I understand, thank you very much!