Blog Archives

Topic Archive: ZFC

CUNY Logic WorkshopFriday, November 7, 20142:00 pmGC 6417

Stevo Todorcevic

Choice principles and Ramsey theory

University of Toronto

This talk will provide an overview of results of Ramsey theory that have close relationships with constructions of models of ZF that distinguish between various forms of the Axiom of Choice. Some open problems and directions for further research will also be discussed.

CUNY Logic WorkshopFriday, May 10, 20132:00 pmGC 6417

Thomas Johnstone

What is the theory ZFC without power set?

The New York City College of Technology (CityTech), CUNY

The theory ZFC-, consisting of the usual axioms of ZFC but with the power set axiom removed — specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well-ordered — is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context.

For example, there are models of ZFC- in which a countable union of countable sets is not countable. There are models of ZFC- for which the Los ultrapower theorem fails, even for wellfounded ultrapowers on a measurable cardinal. Moreover, the theory ZFC- is not sufficient to establish that the union of Σn and Πn sets is closed under bounded quantification. Lastly, there are models of ZFC- for which the Gaifman theorem fails, in that there exists cofinal embeddings j:M–>N between ZFC- models that are Σ1-elementary, but not fully elementary.

Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory obtained by using collection rather than replacement in the axiomatization above. This is joint work with Joel David Hamkins and Victoria Gitman, and it extends prior work of Andrzej Zarach.

arxiv preprint | post at | post on Victoria Gitman’s blog

Set theory seminarFriday, May 10, 201310:00 amGC 5383

Joel David Hamkins

Algebraicity and implicit definability in set theory

The City University of New York

An element a is definable in a model M if it is the unique object in M satisfying some first-order property.  It is algebraic, in contrast, if it is amongst at most finitely many objects satisfying some first-order property φ, that is, if { b  |  M satisfies φ[b] } is a finite set containing a. In this talk, I aim to consider the situation that arises when one replaces the use of definability in several parts of set theory with the weaker concept of algebraicity. For example, in place of the class HOD of all hereditarily ordinal-definable sets, I should like to consider the class HOA of all hereditarily ordinal algebraic sets. How do these two classes relate? In place of the study of pointwise definable models of set theory, I should like to consider the pointwise algebraic models of set theory. Are these the same? In place of the constructible universe L, I should like to consider the inner model arising from iterating the algebraic (or implicit) power set operation rather than the definable power set operation.  The result is a highly interest new inner model of ZFC, denoted Imp, whose properties are only now coming to light.  Is Imp the same as L?  Is it absolute? I shall answer all these questions at the talk, but many others remain open.

This is joint work with Cole Leahy (MIT).

Abstract on my blog | Related MathOverflow post

CUNY Logic WorkshopFriday, February 15, 201312:00 amGC 6417

Joel David Hamkins

On the axiom of constructibility and Maddy’s conception of restrictive theories

The City University of New York

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible.  Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory.

In this talk, I shall criticize Maddy’s specific proposal.  For example, it turns out that the fairly-interpreted-in relation on theories is not transitive, and similarly the maximizes-over and strongly-maximizes-over relations are not transitive.  Further, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s proposal, although this is not what she had desired.

Ultimately, I argue that the $Vneq L$ via maximize position loses its force on a multiverse conception of set theory, in light of the classical facts that models of set theory can generally be extended to (taller) models of V=L.  In particular, every countable model of set theory is a transitive set inside a model of V=L.  I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.


CUNY Logic WorkshopFriday, May 18, 201212:00 amGC 6417

Joel David Hamkins

The countable models of ZFC, up to isomorphism, are linearly pre-ordered by the submodel relation; indeed, every countable model of ZFC, including every transitive model, is isomorphic to a submodel of its own L

The City University of New York

This will be a talk on some extremely new work. The proof uses finitary digraph combinatorics, including the countable random digraph and higher analogues involving uncountable Fraisse limits, the surreal numbers and the hypnagogic digraph.

The story begins with Ressayre’s remarkable 1983 result that if $M$ is any nonstandard model of PA, with $langletext{HF}^M,{in^M}rangle$ the corresponding nonstandard hereditary finite sets of $M$, then for any consistent computably axiomatized theory $T$ in the language of set theory, with $Tsupset ZF$, there is a submodel $Nsubsetlangletext{HF}^M,{in^M}rangle$ such that $Nmodels T$. In particular, one may find models of ZFC or even ZFC + large cardinals as submodels of $text{HF}^M$, a land where everything is thought to be finite. Incredible! Ressayre’s proof uses partial saturation and resplendency to prove that one can find the submodel of the desired theory $T$.

My new theorem strengthens Ressayre’s theorem, while simplifying the proof, by removing the theory $T$. We need not assume $T$ is computable, and we don’t just get one model of $T$, but rather all models—the fact is that the nonstandard models of set theory are universal for all countable acyclic binary relations. So every model of set theory is a submodel of $langletext{HF}^M,{in^M}rangle$.

Theorem.(JDH) Every countable model of set theory is isomorphic to a submodel of any nonstandard model of finite set theory. Indeed, every nonstandard model of finite set theory is universal for all countable acyclic binary relations.

The proof involves the construction of what I call the countable random $mathbb{Q}$-graded digraph, a countable homogeneous acyclic digraph that is universal for all countable acyclic digraphs, and proving that it is realized as a submodel of the nonstandard model $langle M,in^Mrangle$. Having then realized a universal object as a submodel, it follows that every countable structure with an acyclic binary relation, including every countable model of ZFC, is realized as a submodel of $M$.

Theorem.(JDH) Every countable model $langle M,in^Mrangle$ of ZFC, including the transitive models, is isomorphic to a submodel of its own constructible universe $langle L^M,in^Mrangle$. In other words, there is an embedding $j:Mto L^M$ that is quantifier-free-elementary.

The proof is guided by the idea of finding a universal submodel inside $L^M$. The embedding $j$ is constructed completely externally to $M$.

Corollary.(JDH) The countable models of ZFC are linearly ordered and even well-ordered, up to isomorphism, by the submodel relation. Namely, any two countable models of ZFC with the same well-founded height are bi-embeddable as submodels of each other, and all models embed into any nonstandard model.

The work opens up numerous questions on the extent to which we may expect in ZFC that $V$ might be isomorphic to a subclass of $L$. To what extent can we expect to have or to refute embeddings $j:Vto L$, elementary for quantifier-free assertions?