The Coq mailing list

[Thorsten Altenkirch <Thorsten.Altenkirch AT nottingham.ac.uk>]

It boils down what we mean by a function. I mean that it should be possible 
in principle to construct an output for every input. It may not be feasible 
but this is very hard to make precise and depends on technological 
development. As a consequence the Boolean semantics of classical logic 
doesn’t work because we cannot not compute a Boolean for formulas in 
predicate logic. However the propositions as types translation works fine.

Sent from my iPhone

> On 4 Jun 2021, at 00:06, Tadeusz Litak <tadeusz.litak AT gmail.com> wrote:
> 
> Hi Emilio (and others),
> 
>> On 3/6/21 8:18 PM, Emilio Jesús Gallego Arias wrote:
>> Another way to look at it is that replacing the axiom scheme from PA by
>> a single, second order induction principle usually rules out
>> non-standard models.
> 
> that depends on one's stance on Henkin-style models.
> 
> Full second-order logic cannot be axiomatized. So even if one states the 
> induction principle with second-order quantification, the kind of 
> (non-standard, Henkin) models that one rules out depends on 
> instantiation/substitution rules postulated for that second-order 
> quantifiers. There is no end to it, as long as one insists that the set of 
> rules/axioms remains decidable.
> 
> Incidentally, there are weak fragments of PA, such as Robinson's Q, which 
> is finitely axiomatizable and yet allows suitable variants of Gödel's 
> incompleteness theorems. I'm not up-to-date: did Robinson arithmetic appear 
> in any relevant Coq formalization?
> 
> 
> Best,
> 
> t.
> 



This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment. 

Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored 
where permitted by law.