Notre Dame Journal of Formal Logic 59 (3):355-370 (2018)

Authors
Joel David Hamkins
Oxford University
Abstract
Ehrenfeucht’s lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, they satisfy different types. We consider here the analogue of Ehrenfeucht’s lemma for models of set theory. The original argument applies directly to the ordinal-definable elements of any model of set theory, and, in particular, Ehrenfeucht’s lemma holds fully for models of set theory satisfying V=HOD. We show that the lemma fails in the forcing extension of the universe by adding a Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht’s lemma, namely, the principles of the form EL, which asserts that P-definability from A implies Q-discernibility. We also consider various analogues of Ehrenfeucht’s lemma obtained by using algebraicity in place of definability, where a set b is algebraic in a if it is a member of a finite set definable from a. Ehrenfeucht’s lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using a similar analysis, we answer two open questions posed earlier by the third author and C. Leahy, showing that algebraicity and definability need not coincide in models of set theory and the internal and external notions of being ordinal algebraic need not coincide.
Keywords Leibniz–Mycielski axiom   algebraicity   ordinal definability  Ehrenfeucht’s lemma
Categories (categorize this paper)
DOI 10.1215/00294527-2018-0007
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,307
Through your library

References found in this work BETA

Models and Types of Peano's Arithmetic.Haim Gaifman - 1976 - Annals of Mathematical Logic 9 (3):223-306.
Pointwise Definable Models of Set Theory.Joel David Hamkins, David Linetsky & Jonas Reitz - 2013 - Journal of Symbolic Logic 78 (1):139-156.
Algebraicity and Implicit Definability in Set Theory.Joel David Hamkins & Cole Leahy - 2016 - Notre Dame Journal of Formal Logic 57 (3):431-439.
Powers of Regular Cardinals.William B. Easton - 1970 - Annals of Mathematical Logic 1 (2):139.
Discernible Elements in Models for Peano Arithmetic.Andrzej Ehrenfeucht - 1973 - Journal of Symbolic Logic 38 (2):291-292.

View all 6 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Algebraicity and Implicit Definability in Set Theory.Joel David Hamkins & Cole Leahy - 2016 - Notre Dame Journal of Formal Logic 57 (3):431-439.
On the Hamkins Approximation Property.William J. Mitchell - 2006 - Annals of Pure and Applied Logic 144 (1-3):126-129.
Ehrenfeucht Games and Ordinal Addition.Françoise Maurin - 1997 - Annals of Pure and Applied Logic 89 (1):53-73.
Variations of Rado's Lemma.Paul Howard - 1993 - Mathematical Logic Quarterly 39 (1):353-356.
Dickson's Lemma and Higman's Lemma Are Equivalent.Berger Josef - 2016 - SOUTH AMERICAN JOURNAL OF LOGIC 2 (1):35-39.
On Ehrenfeucht-Fraïssé Equivalence of Linear Orderings.Juha Oikkonen - 1990 - Journal of Symbolic Logic 55 (1):65-73.
Some Consequences of Rado’s Selection Lemma.Marianne Morillon - 2012 - Archive for Mathematical Logic 51 (7-8):739-749.
Ramsey’s Theorem and König’s Lemma.T. E. Forster & J. K. Truss - 2007 - Archive for Mathematical Logic 46 (1):37-42.

Analytics

Added to PP index
2018-06-20

Total views
11 ( #852,788 of 2,507,867 )

Recent downloads (6 months)
1 ( #416,715 of 2,507,867 )

How can I increase my downloads?

Downloads

My notes