1

Is the set of all sequences of positive integers of unlimited length denoted $\Bbb N^\infty$?

I think that's most probably not right as it seems to imply the set of infinitely long sequences of integers but it's all I can come up with. I want the set $X$ of sequences of integers of unlimited length, satisfying:

$(1,1,1)\in X$

$(1,2,3,6,4)\in X$

but $(1_n:n\in\Bbb N)\notin X$

it's a hire car baby
  • 9,243

3 Answers3

3

From what I understand by looking at your examples, you are looking for the set $$\bigcup_{k=1}^\infty \Bbb N^k$$

Surb
  • 55,662
3

In set theory, the set of finite strings of natural numbers is denoted $$\omega^{<\omega}.$$ I've also seen "$\mathbb{N}^{<\mathbb{N}}$" used for the set of finite strings of naturals, outside of set theory. (I think variations like "$\mathbb{N}^{<\infty}$" and "$\mathbb{N}^{<\omega}$" would also be understood, but I would prefer the previous two, and I personally cringe at "$\mathbb{N}^{<\infty}$" although that reflects my own set-theoretic biases.)

However, I would certainly understand "$\mathbb{N}^\infty$" to refer to the set of infinite strings of naturals (not even "infinite-or-finite!"), and I think that's not peculiar to me. Ultimately any notation is "permitted" as long as you define it carefully, but I would view this as very confusing.

Noah Schweber
  • 245,398
  • Thank-you. With your $\omega^{<\omega}$ you've thrown me into uncertainty now, whether $\bigcup_{k\in\Bbb N}\Bbb N^k\to \Bbb N$ imposes a $\omega^\omega$ or an $\epsilon_0$ order type on $\Bbb N$ – it's a hire car baby Jul 15 '18 at 08:16
  • @RobertFrost I don't understand what you're asking - how does a map $\bigcup_{k\in\mathbb{N}}\mathbb{N}^k\rightarrow\mathbb{N}$ impose any sort of ordering on $\mathbb{N}$ at all? It is true that there is a natural ordering of $\bigcup_{k\in\mathbb{N}}\mathbb{N}^k$, of ordertype $\omega^\omega$, and pushing that ordering through the map gives an ordering of $\mathbb{N}$ of type $\omega^\omega$; is that all you mean? – Noah Schweber Jul 15 '18 at 14:23
  • Yes, that's all I mean but it doesn't sit well with something I previously believed, $\Bbb N^{<\omega}$ can pick out any vertex on an infinitely tall, rooted, regular, $\infty$-ary tree which I thought had a natural association with an $\epsilon_0$ ordering of the integers so I'm just sketching it out to decide if this is because of two different ways of translating the ordering through the map to $\Bbb N$, or whether I was under a misconception before about the $\epsilon_0$ ordering. – it's a hire car baby Jul 15 '18 at 17:18
  • @RobertFrost I'm not sure what "$\mathbb{N}^{<\omega}$ can pick out any vertex on an infinitely tall, rooted, regular, $\infty$-ary tree" means. Are you just saying that any infinitely tall, rooted, regular, countably-branching tree can be thought of as a subtree of $\mathbb{N}^{<\omega}$? If so, that's correct but irrelevant. – Noah Schweber Jul 15 '18 at 17:22
  • Incidentally, it's easy to construct an ordering of $\mathbb{N}$ of type $\epsilon_0$; it's hard to show that it is well-ordered. That is, the construction isn't the hard part, it's the analysis. – Noah Schweber Jul 15 '18 at 17:25
  • If we say $k$ in $\bigcup_{k\in\Bbb N}\Bbb N^k$ identifies distance from the root of the tree, then make each integer $n_k$ in a sequence drawn from $\Bbb N^{<\omega}$ an end-extension which picks out the $n_k^{th}$ child of its parent $n_{k-1}$ then every element of $\bigcup_{k\in\Bbb N}\Bbb N^k$ picks out a unique vertex of the graph. A map $\bigcup_{k\in\Bbb N}\Bbb N^k\to \Bbb N$ means we can label the same graph with integers. The Collatz graph is such a labelling (assuming the conjecture is true) so that's the relevance to me. But I accept it may not be relevant to you. – it's a hire car baby Jul 15 '18 at 17:47
  • ...if you can construct some natural $\epsilon_0$ ordering of $\Bbb N$ then I'd speculate there's a small but not insignificant chance that $(3x+2^{\nu_2(x)})\lvert3x+2^{\nu_2(x)}\rvert_2\preceq x$ in the order. – it's a hire car baby Jul 15 '18 at 17:51
  • This is isomorphic to a Prufer p-group, but has exponent $\omega$ rather than $p$. I'd love to know how far the analogy goes and whether it has a Pontryagin dual of $\omega$-adic integers but this is way beyond me and I digress a long way from the original question! – it's a hire car baby Jul 15 '18 at 17:57
  • @RobertFrost Natural $\epsilon_0$-orderings have nothing to do with the Collatz conjecture. If you already have, for each $i\in\mathbb{N}$, an ordering $\triangleleft_i$ of $\mathbb{N}$ of ordertype $\alpha_i:=\omega^{\omega^{...}}$ ($i$ times), you can "paste them together" to get an $\epsilon_0$-ordering: fixing a bijection $\langle\cdot,\cdot\rangle:\mathbb{N}^2\rightarrow\mathbb{N}$ (say, the Cantor pairing function), we set $x\triangleleft y$ iff $a<c$ or $a=c$ and $b\triangleleft_a d$, where $x=\langle a, b\rangle$ and $y=\langle c, d\rangle$. (cont'd) – Noah Schweber Jul 15 '18 at 18:01
  • 1
    @RobertFrost How can a graph be isomorphic to a group? What is exactly is the Prufer $\omega$-group? What are the $\omega$-adic integers? Can you give exact definitions of the concepts you're using here? Until you do that, I can't really address any of your perceived connections in a serious way - besides saying that I don't see what you're getting at. (It is true of course that the Collatz conjecture is equivalent to the statement that a certain well-ordering is well-founded (once we cut out the "trivial loops"), and hence has an ordinal rank, but a priori $\epsilon_0$ is irrelevant.) – Noah Schweber Jul 15 '18 at 18:08
  • Every Prufer p-group is isomorphic to the infinite, p-ary, rooted tree (labelled). Elements of any given exponent are the same number of vertices from $0$ as each other. Raising any element to the power of $p$ goes to its parent in the tree. So e.g. in the 2-group $\frac14$ and $\frac34$ are of the same order and share the same parent which is $\frac12$. Then raising either to the power of $2$ (groupwise): $\frac14+\frac14=\frac12$ and $\frac34+\frac34=\frac12$ – it's a hire car baby Jul 15 '18 at 18:13
  • 1
    @RobertFrost "Every Prufer p-group is isomorphic to the infinite, p-ary, rooted tree" No, that's not true. No group can be isomorphic to a graph. What you have is a situation where there is a graph associated to a group, with certain nice properties. That's not an isomorphism. – Noah Schweber Jul 15 '18 at 18:29
  • sorry, my bad. This graph is isomorphic to the graph of a Prufer p-group, except having exponent ω rather than p. I'd love to know how far the analogy goes and whether it has a Pontryagin dual of ω-adic integers but this is way beyond me and I digress a long way from the original question! – it's a hire car baby Jul 15 '18 at 19:06
  • 1
    @RobertFrost OK, now you just need to precisely define the group you want to associate to this graph, prove that it is locally compact, and precisely define the "$\omega$-adic integers," and you'll have a precise claim which can be true or false. My point is that the connections you're trying to make are not nearly as well-defined (not even getting to the question of whether they are real or not) as you think, and that you really need to make your basic concepts precise before anything interesting can actually be done. – Noah Schweber Jul 15 '18 at 19:10
  • I today learnt that the Baire Space is the precisely defined structure and I repeat my claim with a little more precision that in the category of Prufer p-groups, we can send $p\to\omega$ and consider the Baire space to be the Prufer $\omega$-group. I can't give a precise definition of the group operation yet but it would seem likely that it's something like addition modulo shifting the coefficients in Cantor normal form to the right. – it's a hire car baby Jul 19 '18 at 08:16
2

Notation means whatever the author intends. Most commonly (infinite) sequences are thought of as functions from $\Bbb N$ to the set of possible entries. A finite sequence on the other hand can be thought of as a function from $\{1,2,\dots,n\}$ to the set of possible entries.

There is precedent for denoting the set of functions from $A$ to $B$ as

$$\{f~:~f~\text{is a function }A\to B\}=B^A$$

Some of the justification behind this notation is for the convenient identity for finite sets then that $|B^A|=|B|^{|A|}$. You will also as a result commonly see instead of the power set of $A$ notated as $\mathcal{P}(A)$ to instead see it notated as $2^A$ or as $\{0,1\}^A$.

Using this notation as a base and using the interpretation that you want all finite or infinite length sequences of positive integers, the set you describe could be written then as:

$$\Bbb N^\Bbb N\cup \left(\bigcup\limits_{n=1}^\infty \Bbb N^{[n]}\right)$$

where $[n]=\{1,2,3,\dots,n\}$ (or if you prefer $\{0,1,2,\dots,n-1\}$). If you wish to include the empty-sequence, you may adjust the lowerbound to $n=0$ instead of $n=1$.

JMoravitz
  • 79,518
  • 1
    The OP doesn't seem to want infinite length sequences. – Adayah Jul 14 '18 at 18:54
  • 3
    If the infinite-length sequences are to be excluded, just omit the $\Bbb N^\Bbb N$ at the beginning. – JMoravitz Jul 14 '18 at 18:55
  • 1
    It is worth mentioning as well, that the square brackets could potentially be omitted too, as the usual interpretation of $\Bbb N^k$ is the set of all ordered $k$-tuples of natural numbers, which are then usually defined as functions from $[k]$ to $\Bbb N$. – JMoravitz Jul 14 '18 at 18:59
  • Thank-you. It would seem more natural initially to think of $(1,2,5)\in\Bbb N^3$ but do I understand correctly you're giving a richer notation in which $(1,2,5)\in\Bbb N^{{1,2,3}}$? – it's a hire car baby Jul 14 '18 at 19:07