Premium
Relatively Recursively Enumerable Versus Relatively Σ 1 in Models of Peano Arithmetic
Author(s) -
Michalski Grzegorz
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410408
Subject(s) - peano axioms , mathematics , recursively enumerable language , countable set , extension (predicate logic) , recursively enumerable set , discrete mathematics , arithmetic , combinatorics , computer science , programming language
We show that that every countable model of PA has a conservative extension M with a subset Y such that a certain Σ 1 ( Y )‐formula defines in M a subset which is not r. e. relative to Y .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom