imported>Marc Schroeder at 01:58, 30 May 2025

2025-05-30T01:58:43Z

New page

In [[Intuitionism|intuitionistic mathematics]], a '''choice sequence''' is a [[Constructivism (mathematics)|constructive]] formulation of a [[sequence]]. Since the Intuitionistic school of mathematics, as formulated by [[L. E. J. Brouwer]], rejects the idea of a [[completed infinity]], in order to use a sequence (which is, in classical mathematics, an infinite object), we must have a formulation of a finite, constructible object that can serve the same purpose as a sequence. Thus, Brouwer formulated the choice sequence, which is given as a construction, rather than an abstract, infinite object.{{sfn|Troelstra|1982}}

==Lawlike and lawless sequences==
A distinction is made between ''lawless'' and ''lawlike'' sequences.{{sfn|Linnebo|Shapiro|2020|p=3}} A ''lawlike'' sequence is one that can be described completely—it is a completed construction, that can be fully described. For example, the [[natural numbers]] <math>\mathbb N</math> can be thought of as a lawlike sequence: the sequence can be fully constructively described by the unique element 0 and a [[Primitive recursive function#Definition|successor function]]. Given this formulation, we know that the <math>i</math>th element in the sequence of natural numbers will be the number <math>i-1</math>. Similarly, a [[function (mathematics)|function]] <math> f : \mathbb N \mapsto \mathbb N</math> mapping from the natural numbers into the natural numbers effectively determines the value for any argument it takes, and thus describes a lawlike sequence.

A ''lawless'' (also, ''free'') sequence, on the other hand, is one that is not predetermined. It is to be thought of as a procedure for generating values for the arguments 0, 1, 2, .... That is, a lawless sequence <math>\alpha</math> is a procedure for generating <math>\alpha_0</math>, <math>\alpha_1</math>, ... (the elements of the sequence <math>\alpha</math>) such that:
*At any given moment of construction of the sequence <math>\alpha</math>, only an initial segment of the sequence is known, and no restrictions are placed on the future values of <math>\alpha</math>; and
*One may specify, in advance, an initial segment <math>\langle \alpha_0, \alpha_1, \ldots, \alpha_k \rangle</math> of <math>\alpha</math>.
Note that the first point above is slightly misleading, as we may specify, for example, that the values in a sequence be drawn exclusively from the set of natural numbers—we can specify, [[A priori and a posteriori|a priori]], the range of the sequence.

The canonical example of a lawless sequence is the series of rolls of a [[dice|die]]. We specify which die to use and, optionally, specify in advance the values of the first <math>k</math> rolls (for <math>k\in \mathbb N</math>). Further, we restrict the values of the sequence to be in the set <math>\{1,2,3,4,5,6\}</math>. This specification comprises the procedure for generating the lawless sequence in question. At no point, then, is any particular future value of the sequence known.

==Axiomatization==
There are two [[axiom]]s in particular that we expect to hold of choice sequences as described above. Let <math>\alpha\in n</math> denote the relation "the sequence <math>\alpha</math> begins with the initial sequence <math>n</math>" for choice sequence <math>\alpha</math> and finite segment <math>n</math> (more specifically, <math>n</math> will probably be an integer [[Numbering (computability theory)|encoding]] a finite initial sequence).

We expect the following, called the ''axiom of open data'', to hold of all lawless sequences:
<math display="block">A(\alpha) \rightarrow \exists n[\alpha\in n \,\land\, \forall\beta\in n[A(\beta)]]</math>
where <math>A</math> is a [[one-place predicate]]. The intuitive justification for this axiom is as follows: in intuitionistic mathematics, verification that <math>A</math> holds of the sequence <math>\alpha</math> is given as a [[algorithm|procedure]]; at any point of execution of this procedure, we will have examined only a finite initial segment of the sequence. Intuitively, then, this axiom states that since, at any point of verifying that <math>A</math> holds of <math>\alpha</math>, we will only have verified that <math>A</math> holds for a finite initial sequence of <math>\alpha</math>; thus, it must be the case that <math>A</math> also holds for any lawless sequence <math>\beta</math> sharing this initial sequence. This is so because, at any point in the procedure of verifying <math>A(\alpha)</math>, for any such <math>\beta</math> sharing the initial prefix of <math>\alpha</math> encoded by <math>n</math> that we have already examined, if we run the identical procedure on <math>\beta</math>, we will get the same result. The axiom can be generalized for any predicate taking an arbitrary number of arguments.

Another axiom is required for lawless sequences. The ''axiom of density'', given by:
<math display="block">\forall n \, \exists \alpha [\alpha\in n]</math>
states that, for any finite prefix (encoded by) <math>n</math>, there is some sequence <math>\alpha</math> beginning with that prefix. We require this axiom so as not to have any "holes" in the set of choice sequences. This axiom is the reason we require that arbitrarily long finite initial sequences of lawless choice sequences can be specified in advance; without this requirement, the axiom of density is not necessarily guaranteed.

==See also==
* {{annotated link|Constructivism (philosophy of mathematics)}}

==Notes==
{{Reflist}}

==References==
{{Refbegin}}

*{{cite book
|last= Dummett
|first= Michael
|author-link= Michael Dummett
|title= Elements of Intuitionism
|publisher= Oxford University Press
|year= 1977
}}

*{{cite journal
|last= Fourman
|first= Michael P.
|author-link= Michael Fourman
|title= Notions of Choice Sequence
|journal= Studies in Logic and the Foundations of Mathematics
|url= http://homepages.inf.ed.ac.uk/mfourman/research/publications/pdf/fourman82-notions-of-choice-sequence.pdf
|year= 1982
|volume= 110
|pages= 91–105
|doi = 10.1016/S0049-237X(09)70125-9
|isbn= 9780444864949
}}

*{{cite book
|last= Jacquette
|first= Dale
|author-link= Dale Jacquette
|title= A Companion to Philosophical Logic
|publisher= Blackwell Publishing
|year= 2002
|isbn= 9780631216711
|page= 517
}}

*{{cite journal
|last= Kreisel
|first= Georg
|author-link= Georg Kreisel
|title= A remark on free choice sequences and the topological completeness proofs
|journal= Journal of Symbolic Logic
|year= 1958
|volume= 23
|issue= 4
|pages= 369–388
|doi= 10.2307/2964012
|jstor= 2964012
}}

*{{cite web
|last1= Linnebo
|first1= Øystein
|author-link1= Øystein Linnebo
|last2= Shapiro
|first2= Stewart
|author-link2= Stewart Shapiro
|title= Choice sequences: a modal and classical analysis
|publisher= University of Oslo and Ohio State University
|date= 23 September 2020
|url= https://www.hf.uio.no/ifikk/english/research/projects/cl/events/conferences/slides-potensialism/reals-slides.pdf
|access-date= 14 April 2022
}}

*{{cite book
|last= Troelstra
|first= Anne Sjerp
|author-link= Anne Sjerp Troelstra
|title= Choice Sequences. A Chapter of Intuitionistic Mathematics
|publisher= Clarendon Press
|year= 1977
}}

*{{cite journal
|last= Troelstra
|first= Anne Sjerp
|author-link= Anne Sjerp Troelstra
|title= On the Origin and Development of Brouwer's Concept of Choice Sequence
|journal= Studies in Logic and the Foundations of Mathematics
|year= 1982
|volume= 110
|pages= 465–486
|doi= 10.1016/S0049-237X(09)70145-4
|isbn= 9780444864949
}}

*{{cite journal
|last= Troelstra
|first= Anne Sjerp
|author-link= Anne Sjerp Troelstra
|title= Analysing Choice Sequences
|journal= Journal of Philosophical Logic
|year= 1983
|volume= 12
|issue= 2
|pages= 197–260
|doi= 10.1007/BF00247189
|s2cid= 26373820
}}

*{{cite book
|last1= Troelstra
|first1= Anne Sjerp
|author-link1= Anne Sjerp Troelstra
|last2= Van Dalen
|first2= Dirk
|author-link2= Dirk van Dalen
|title= Constructivism in Mathematics: An Introduction, Volume 1
|publisher= Elsevier Science
|year= 1988a
|isbn= 9780444702661
}}

*{{cite book
|last1= Troelstra
|first1= Anne Sjerp
|author-link1= Anne Sjerp Troelstra
|last2= Van Dalen
|first2= Dirk
|author-link2= Dirk van Dalen
|title= Constructivism in Mathematics: An Introduction, Volume 2
|publisher= Elsevier Science
|year= 1988b
|isbn= 9780444703583
}}

{{Refend}}

[[Category:Constructivism (mathematics)]]

Choice sequence - Revision history

imported>Marc Schroeder at 01:58, 30 May 2025