Ehrenfeucht's lemma in set theory

DOI10.1215/00294527-2018-0007zbMATH Open1455.03065arXiv1501.01918OpenAlexW1576970471WikidataQ124967791 ScholiaQ124967791MaRDI QIDQ1782238FDOQ1782238

Authors: Gunter Fuchs, Victoria Gitman, Joel David Hamkins 

Publication date: 19 September 2018

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Abstract: Ehrenfeucht's lemma (1973) asserts that whenever one element of a model of Peano arithmetic is definable from another, then 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 can fail, however, in models of set theory with $VeqHOD$, and it necessarily fails in the forcing extension to add a generic Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht's lemma, namely, the principles of the form $EL(A,P,Q)$, which asserts that whenever an object $b$ is definable from some $ainA$ using parameters in $P$, with $beqa$, then the types of $a$ and $b$ over $Q$ are different. 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$ (as in Hamkins, Leahy arXiv:1305.5953). Ehrenfeucht's lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using similar analysis, we answer two open questions posed by Hamkins and Leahy, by showing that (i) algebraicity and definability need not coincide in models of set theory and (ii) the internal and external notions of being ordinal algebraic need not coincide.

Full work available at URL: https://arxiv.org/abs/1501.01918

Recommendations

• Algebraicity and implicit definability in set theory
• Pointwise definable models of set theory
• When does every definable nonempty set have a definable element?
• Undefinable Classes and Definable Elements in Models of Set Theory and Arithmetic
• Extendible Sets in Peano Arithmetic

zbMATH Keywords

algebraicityordinal definabilityEhrenfeucht's lemmaLeibniz-Mycielski axiom

Mathematics Subject Classification ID

Set-theoretic model theory (03C55) Models of arithmetic and set theory (03C62) Inner models, including constructibility, ordinal definability, and core models (03E45) Other notions of set-theoretic definability (03E47)

Cites Work

• Powers of regular cardinals
• Algebraicity and implicit definability in set theory
• Pointwise definable models of set theory
• Title not available (Why is that?)
• Finite groups of OD-conjugates
• On the Leibniz–Mycielski axiom in set theory
• Discernible elements in models for Peano arithmetic
• Leibnizian models of set theory
• Models and types of Peano's arithmetic
• Title not available (Why is that?)

Cited In (4)

• On Russell typicality in set theory
• Algebraicity and implicit definability in set theory
• On the ‘definability of definable’ problem of Alfred Tarski, Part II
• An unpublished theorem of Solovay on OD partitions of reals into two non-OD parts, revisited

Uses Software

• MathOverflow

This page was built for publication: Ehrenfeucht's lemma in set theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1782238)