Talk:Integer sequence

Merge with sequence?

I think this material should be merged with sequence; integer sequences should be reserved for sequences whose terms are integers. --AxelBoldt

Integer sequences ARE sequences whose terms are integers. (see the first line) — Preceding unsigned comment added by Bubba73 (talk • contribs) 19:26, 10 May 2005‎

Is it really necessary to include a long list of named sequences here, when we have a perfectly good category page with essentially the same information? (And btw, what is the approved method for creating internal links to category pages?) —David Eppstein 18:53, 10 September 2006 (UTC)

Links to the Definition of a Statement?

To me (a non-mathematician), the definitions of definable sequences leaves the term "statement" underdefined, so I would like to understand what a statement is, i..e. is it a finite algorithm definition, must it terminate after a finite number of steps, etc. 198.60.22.24 12:04, 29 July 2007 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Integer sequence/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Does not explain the importance of integer sequence, has an poorly placed list of integer sequences (maybe a template for integer sequences would be better), does not explain major questions or results. shotwell 15:59, 7 October 2006 (UTC)

Last edited at 22:35, 19 April 2007 (UTC). Substituted at 02:14, 5 May 2016 (UTC)

Definable sequences

"The set of computable integer sequences and definable integer sequences are both countable" — Really, both? Or rather the former? "Moreover, there are countable models of ZFC in which all real numbers, all sets of real numbers, functions on the reals, etc. are definable" (quoted from Definable real number#Definability in models of ZFC). (Related to #Links to the Definition of a Statement? above, and to Tarski's undefinability theorem.) (The claim about definable was written at 08:01, 16 November 2004 by 137.111.13.34; see also here: "Notably, in a system of mathematics in which everything is definable, all sets are countable.") Boris Tsirelson (talk) 08:36, 5 February 2018 (UTC)

Whichever definition of "definable" you choose, the formula that defines a definable object is a finite sequence of characters belonging to a finite alphabet. Thus the set of definable objects is definitively countable. I am unable to check whether the quotations are correct. The latter one is highly doubtful, as "everything is decidable" is essentially a non-sense. The former quotation seems reliably sourced. However, the paragraph refers to "countable models of set theory" and "class models". This suggests that some collections of real numbers are not sets or even that one cannot talk about them in the theory (think to Russel's paradox of the set of all sets that do not belong to themselves). This is also related to constructivist logics, where only definable objects define in the theory.

IMO, the section Definable real number#Definability in models of ZFC must be removed or rewritten. I'll tagging it as too technical, as it supposes a good understanding of the logical concept of "model", which most mathematician do not know well. D.Lazard (talk) 11:23, 5 February 2018 (UTC)

I am not exactly sure what this thread is asking, but all of these are correct:

• The set of computable sequences of integers is countable. This is a theorem of ZFC.
• In any model of ZFC, the set of definable sequences of integers (definable in that model) is countable. This is a theorem of ZFC about models of ZFC.
• There are models of ZFC in which the set of sequences of integers is countable when viewed from outside the model (these models themselves are countable). The existence of countable models of ZFC is an elementary fact from the Lowenheim-Skolem theorem. The existence of models in which each element is definable is not as elementary, but is well known, e.g. [1]. These models will still, internally, satisfy the sentence "the set of integer sequences is uncountable".

The third fact is not really relevant to this article. The real issue is that "definable" is not itself expressible from inside a model of ZFC - a model has no access to its own definability relation. This is why in item 2 we can only say that ZFC proves that the set of definable sequences in any model is countable. ZFC cannot prove simply "the set of definable integer sequences is countable" because this cannot be expressed in the language of ZFC.

— Carl (CBM · talk) 11:31, 5 February 2018 (UTC)

(edit conflict) All above quotations refer to non-standard models of set theory. Thus this article is correct, as, unless otherwise stated, all articles of mathematics are supposed to use ZFC as logical foundation. Maybe this should be said in MOS:MATH. D.Lazard (talk) 11:47, 5 February 2018 (UTC)

The first two do not have anything the do with nonstandard models - at best we would say they hold for *all* models. But this article is correct, as is the one on definable real numbers, with one exception: the bare claim here that "almost all integer sequences ... cannot be defined.". The statement "almost all integer sequences cannot be defined" is not a sentence in ZFC, and as such is not provable in ZFC. The issue then becomes more subtle, related to mathematical platonism, and certainly not resolvable within ZFC. Hamkins et al. go into some detail on this issue in the intro of [2]. — Carl (CBM · talk) 12:01, 5 February 2018 (UTC)

As far as I (not expert in logic) understand, Carl is correct, and Lazard should think again. In fact, some time ago I was trapped by this dangerous trap. But now I escaped. Indeed, the statement "almost all integer sequences cannot be defined" is not a sentence in ZFC (!). Accordingly, this article was incorrect before Carl's edit. Boris Tsirelson (talk) 18:31, 5 February 2018 (UTC)

Since Tarski showed that truth is undefinable, I would infer that "there exists some statement P(x) which is true for that integer sequence x and false for all other integer sequences" has no meaning unless it is relativized to some specific set-model. JRSpriggs (talk) 03:08, 6 February 2018 (UTC)

That's certainly the case if we take the "true" literally. It could also be a colloquial way of saying something like "ZFC proves there is a unique sequence satisfying P". For example, this happens if P says "every element of the sequence is zero". Overall this is a standard issue - definability over a model vs. definability over a theory. — Carl (CBM · talk) 16:05, 6 February 2018 (UTC)

Still I think you would need to require that P(x) also be absolute (perhaps provably Δ₁) in order for the 'definition' to actually define anything. JRSpriggs (talk) 04:19, 7 February 2018 (UTC)

There is a flaw in CBM's argument for a 'colloquial' interpretation. You are failing to distinguish between P being a definition and it being a definition of a specific integer sequence x. I agree that we can say that P is a definition, if ZFC proves that $\textstyle \exists x\forall y(y=x\iff P(y))$. But how do we say that x is the thing being defined? You cannot just say that P(x) because P is not a specific formula in the language of set theory, rather it is a variable over Godel numbers for formulas. So you would have to say something like P is true of x.

If you could do that, then what is to stop me from defining a function f as follows: f(k) is zero if k is not the Godel number of a definition; and f(k) = x_k(k)+1 if k is the Godel number of a definition P_k which defines the function x_k. Clearly this would be a contradiction since if n is the Godel number of the definition I just gave for f we get f(n) = x_n(n)+1 = f(n)+1. JRSpriggs (talk) 01:48, 9 February 2018 (UTC)

I'm not really looking to discuss this in detail, because I think it is all well known and standard. A definitional extension only needs a proof of $(\exists !x)\phi (x)$. Of course the properties of the object being defined depend on φ. So φ could say "x is zero sharp if that exists, otherwise x is the constant zero sequence", and we can't prove much about the object defined by that sentence. This is the way it is for definitions over a theory, rather than definitions over a model. — Carl (CBM · talk) 02:05, 9 February 2018 (UTC)

This is not an article about foundations of mathematics, nor about model theory. The present version of the article is thus too technical, as referring to theories that are both unknown by most readers, and not needed for understanding the section. Moreover the present version does not satisfies WP:NPOV, as making too much place to theories that are outside the main stream of mathematics. If one follows what is said in this discussion, we should edit similarly every article that mention uncountable sets, as there are set theories where all sets are countable. For these reasons, I'll restore the old version, and simply add a comment that the existence of non-definable sequences may be not valid in other set theories or other underlying logics. D.Lazard (talk) 14:59, 9 February 2018 (UTC)

Then exclude "definable" at all (in this article). I agree that we'd better stay within ZFC. But, again: existence of non-definable sequences (of integers) is NOT a theorem of ZFC, and moreover, the notion "definable sequence" does not exist within ZFC. Within ZFC you could introduce the notion "a sequence definable under the first strongly inaccesible cardinal if it exists" or something in this spirit. But the definition of "full-blown" definability needs a map from formulas of ZFC to classes (not sets!); this is beyond ZFC. The problem is that quantifiers in ZFC are not bounded. In contrast, we non-logicians mostly use bounded quantifiers ("$\forall x\in X$" rather than "for all x in the class of all sets").Boris Tsirelson (talk) 15:54, 9 February 2018 (UTC)

I disagree: the well-founded statements of ZFC form a countable set (finite words over a finite or countable alphabet). The fact that a statement (element of a well defined set) defines an unique integer sequence is expressible in ZFC (generally not provable nor disprovable). Thus the well-founded statements that define a unique integer sequence form a subset of the well-founded statements, and thus a countable set. Thus the definable sequences form set, a thus a countable set, and this is a theorem of ZFC. However, for a given statement, there is, in general, no proof for deciding whether it defines a unique integer sequence. As defining statements are the unique way for explicitly defining a sequence, it is undecidable whether a sequence is definable. This makes possible that some sequences may be definable in some models and not in other models. Note that the argument for definable sequences is exactly the same as for computable sequences, and thus there is no need of uncountability for proving the existence of undefinable sequences. Also, in the intuitionistic logic that is used in many proof assistants, definable is exactly the same thing as computable. D.Lazard (talk) 17:32, 9 February 2018 (UTC)

I disagree. Yes, the formulas of ZFC form a countable set. Consider the subset of formulas with exactly one free variable (denote it $P(x)$); also a countable set, of course. Given such $P(x)$ you can form the statement $\exists !x\,P(x)$ on the level of syntax. The problem appears when you want to jump from syntax to semantics. Have you a formula $T(P)$ of ZFC that says that the statement "$\exists !x\,P(x)$" is true? (Here "$P(x)$" is treated within ZFC as a word in the appropriate alphabet, and "$\exists !x\,P(x)$" as another word.) No, you have no such formula. Accordingly, you cannot consider "the set of such formulas $P(x)$". Boris Tsirelson (talk) 17:57, 9 February 2018 (UTC)

If anyone checks the reference I have pointed out before [3], theu will find a good summary on pages 9 to 10:

• There is no formula of ZFC so that, in every model, this formula is satisfied by exactly the definable elements.
• In some models, the collection of definable elements is a definable class
• In some models, the collection of definable elements is not a definable class

Also, on page 3, they will see that there are models inside which which every set is definable (without parameters), including every sequence of integers in the model.

Separately, while there are countable models of set theory, there are no models of set theory inside which every set is countable. But there are models of set theory inside which every set is definable. The reason that the argument for definable sequences is different than for computable sequences is that there is a single formula which, in every model of set theory, pulls out the computable sequences of integers. — Carl (CBM · talk) 19:36, 9 February 2018 (UTC)

Line by line explanation

Here is a specific sentence-by-sentence explanation of why the previous version of the article isn't accurate.

The sets of computable integer sequences and of definable integer sequences are both countable, with the computable sequences a proper subset of the definable sequences (in other words, some sequences are definable but not computable).

ZFC cannot prove that the set of definable integer sequences is countable. In some models of ZFC, every integer sequence is definable. But, more importantly, ZFC cannot even express the sentence "every integer sequence is definable"

The set of all integer sequences is uncountable (with cardinality equal to that of the continuum);

This is provable in ZFC

thus, almost all integer sequences are uncomputable and cannot be defined.

The uncomputable claim is provable in ZFC, but not the claim about sequences that cannot be defined

However, there exist non-standard set theories or non-standard underlying logics, where every integer sequence is definable (for example, if all sets are countable).

ZFC proves that "the set of all integer sequences is uncountable", but it is still the case that ZFC cannot prove that the set of definable sequences is countable, because there is no formula of ZFC which holds for exactly the definable sequences. Again, ZFC cannot even express the sentence "every integer sequence is definable". This is not related to nonstandard set theories or to nonclassical logics, it is just a property of ordinary ZFC.

— Carl (CBM · talk) 19:48, 9 February 2018 (UTC)

A set in M

To Carl: Since I am assuming "M is a transitive model of ZFC which is a set and contains all integer sequences", I can prove that the set of all integer sequences definable relative to M is a set and indeed a countable set in M. First, we agree that it is countable. So choose a bijection between ω and the set. Then use the Cantor pairing function to combine the two arguments. This encodes the set as a single integer sequence. Thus it is in M and we can just reverse the encoding to get the bijection and the set in M. JRSpriggs (talk) 20:04, 10 February 2018 (UTC)

I see what you mean, but my next thought about the article was that the entire argument about "contains all integer sequences" ought to be removed, so I was not actually assuming that about M. Perhaps I only made part of the edit I had in mind. The largest challenge is that there is not really a good source for any of this, although it is all pretty elementary. There is sentence from the Hamkins, Linetsky, and Rietz paper that could be used as a source: "The surviving content of the math-tea argument seems to be the observation that in any model with access to a definability map $r\to \psi _{r}$, the definable reals do not exhaust all the reals." I would not mind rephrasing things to use that directly. I am more concerned about having any kind of subtle, unsourceable argument in the article, particularly given the general amount of misunderstanding around this topic. — Carl (CBM · talk) 20:10, 10 February 2018 (UTC)

We could just drop the whole second paragraph as too technical or unsourced, but I personally kind of like it.

We have to make some kind of assumption about the model as I argued above. So I think that assuming a model which is as similar as possible to the universe is desirable. That is why I made it a transitive model of ZFC and included all the things which we are talking about (the integer sequences). Making the model a set is forced on us by the fact that we cannot define truth for a proper class model.

If we left out some integer sequences, then it would create issues about which ones were included versus which were left out. I do not want to deal with those issues. JRSpriggs (talk) 20:25, 10 February 2018 (UTC)

I tried making an edit just now that is sourced, and which still has the essence of what you were talking about. I agree about transitive models - so that the "integer sequences" are actually integer sequences. The main difference is that rather than talking about "all" sequences being included, we can just be explicit: if we have the definability map, we know that not all sequences are definable. In the end, I think the kind of argument you were making is just a different approach to the one that goes via the definability map. — Carl (CBM · talk) 20:30, 10 February 2018 (UTC)