A cyclic proof system, called CLKIDω, gives us another way of representing inductive definitions and efficient proof search. The 2011 paper by Brotherston and Simpson showed that the provability of CLKIDω includes the provability of Martin-Löf’s system of inductive definitions, called LKID, and conjectured the equivalence. Since then, the equivalence has been left an open question. This paper shows that CLKIDω and LKID are indeed not equivalent. This paper considers a statement called 2-Hydra in these two systems with the first-order language formed by 0, the successor, the natural number predicate, and a binary predicate symbol used to express 2-Hydra. This paper shows that the 2-Hydra statement is provable in CLKIDω, but the statement is not provable in LKID, by constructing some Henkin model where the statement is false.

Classical system of Martin-Lof's inductive definitions is not equivalent to cyclic proof system

Berardi, Stefano;
2017-01-01

Abstract

A cyclic proof system, called CLKIDω, gives us another way of representing inductive definitions and efficient proof search. The 2011 paper by Brotherston and Simpson showed that the provability of CLKIDω includes the provability of Martin-Löf’s system of inductive definitions, called LKID, and conjectured the equivalence. Since then, the equivalence has been left an open question. This paper shows that CLKIDω and LKID are indeed not equivalent. This paper considers a statement called 2-Hydra in these two systems with the first-order language formed by 0, the successor, the natural number predicate, and a binary predicate symbol used to express 2-Hydra. This paper shows that the 2-Hydra statement is provable in CLKIDω, but the statement is not provable in LKID, by constructing some Henkin model where the statement is false.
2017
Inglese
Esperti anonimi
10203
301
317
17
http://springerlink.com/content/0302-9743/copyright/2005/
EATCS Award 2017
Theoretical Computer Science; Computer Science (all)
no
2 – prodotto con deroga d’ufficio (SOLO se editore non consente/non ha risposto)
2
info:eu-repo/semantics/conferenceObject
04-CONTRIBUTO IN ATTI DI CONVEGNO::04A-Conference paper in volume
Berardi, Stefano; Tatsuta, Makoto
273
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1658140
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 14
social impact