PROCEEDINGS OF THE 70TH ANNIVERSARY NF MEETING IN CAMBRIDGE

Description

This cahier contains almost all the contributions to the two day meeting, commemorating the 70th year of the publication of Quine's seminal paper “New Foundations for Mathematical Logic”, in which he describes for the first time the remarkable set theory

Sujets

• Sciences humaines et sociales

Informations

• Publié par: L'Harmattan
• Date de parution: 01 juin 2012
• Nombre de lectures: 35
• EAN13: 9782296492356
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

PROCEEDINGS OF THE
TH
70 ANNIVERSARY
NF MEETING IN CAMBRIDGE

D´j` parus

Cahier 1´puis´
Intuitionnisme et th´orie de la d´monstration.
Cahier 2´puis´
Textes de Jean Pieters.
Cahier 3´puis´
J.-L. Moens,Forcing et s´mantique de Kripke–Joyal.
Cahier 4´puis´
La th´orie des ensembles de Quine.
Cahier 5´puis´
T. E. Forster,Quine’s New Foundations.
Cahier 6´puis´
Logique et informatique.
Cahier 7´puis´
L’antifondation en logique et en th´orie des ensembles.
Cahier 8
Ph. de Groote (ed.),The Curry–Howard Isomorphism.
Cahier 9
A. P´try (´d.),M´thodes et analyse non standard.
Cahier 10´puis´
M. R. Holmes,Elementary Set Theory with a Universal Set.
Cahier 11
Chr. Michaux (ed.),Definability in Arithmetics and Computability.
Cahier 12
P. Van Praag,Aspects de la dualit´ en math´matique.
Cahier 13
O. Esser,Une th´orie positive des ensembles.
Cahier 14
K. De Clercq,Logica in communicatie.
Cahier 15
S. Richard,La conception s´mantique de la v´rit´

Une version ´lectronique des volumes ´puis´s sera prochainement
disponible surhttp://www.logic-center.be/cahiers.

/RJ)7

,- 1

/,

"+1

£È

*,"

- " /
/
Çä 6
,-,9

/
,

>ÀVi
, >` />Ã ",-/
, ­i`î

iÌÀi >Ì> `i ,iViÀVià `i }µÕi
>Ì>>
iÌÀÕ ÛÀ >ÛÀÃ}i `i }V>

Ê

" 1 6
1 6

30

Ó ä ä

CAHIERS

DU

CENTRE

DE

LOGIQUE

Directeur de la collection :
M. Crabb´
Comit´ de r´daction :
D. Batens,M. Crabb´, J. De Greef, Ph. de Groote(Nancy),
D. Dzierzgowski, T. E. Forster(Cambridge),R. Hinnion,
M. R. Holmes(Boise),Th. Lucas, J. Meheus,
Chr. Michaux, A. P´try.

Cahier 16 ´dit´ par :
Marcel Crabb´ et Thomas Forster,
Universit´ catholique de Louvain, University of Cambridge.

D/2009/4910/44

Secr´tariat :
D. Servais

Composition :
D. Dzierzgowski

Centre national de recherches de logique
http://www.logic-center.be/cahiers

s.a.c BRUYLANT-ACADEMIA
Grand-Place 29
B–1348 Louvain-la-Neuve

ISBN 978–2–87209–937–5

Tous droits de reproduction, d’adaptation ou de traduction, par quelque proc´d´ que
ce soit, r´serv´s pour tous pays sans l’autorisation de l’´diteur.

Imprim´ en Belgique.

Foreword

This cahier contains almost all the contributions to the two day meeting,
commemorating the 70th year of the publication of Quine’s seminal paper
“New Foundations for Mathematical Logic”, in which he describes for
the first time the remarkable set theory NF. It contains also some other
contributions which were prompted by this meeting.

This meeting follows the 50th meeting held in Oberwolfach in 1987,
organized by M. Boffa and E. Specker in the presence of Quine, and the 60th
anniversary meeting in Cambridge in 1997.
The two first papers : “A permutation method yielding models of the
stratified axioms of Zermelo Fraenkel set theory”, and “Permutation
methods in NF and NFU”, are concerned with permutation techniques and
unstratified formulæ.
In “There is a Forster term model of simple type theory”, M. R. Holmes
shows a model of type theory wherein all elements are the denotations of
closed terms.
In “Ambiguous Cardinals” and “NF and indiscernibles in ZF”, M. Crabb´
and S. Tupailo, show how to export results arising in NF to standard set
theory.
The paper “Combinatorics related to NF consistency”, by A. Tzouvaras,
explores different combinatorial techniques in order to reduce the
consistency problem of NF.
The cahier ends with T. E. Forster’s tutorial on Constructive NF.

The Editors

Contents

V. H. Dang and Z. McKenzie
A permutation method yielding models of the stratified axioms
of Zermelo Fraenkel set theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

T. E. Forster and M. R. Holmes
Permutation methods in NF and NFU .. . . . . . . . . . . . . . . . . . . . . . . . . . .33

M. R. Holmes
There is a Forster term model of Simple Type Theory. . . . . . . . . . . . . 77

M. Crabb´
Ambiguous cardinals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

S. Tupailo
NF and indiscernibles in ZF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

A. Tzouvaras
Combinatorics related to NF consistency. . . . . . . . . . . . . . . . . . . . . . . . . 109

T. E. Forster
A tutorial on Constructive NF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Cahiers du Centre de logique
Volume 16

1.

A permutation method yielding
models of the stratified axioms of
Zermelo Fraenkel set theory

by

V. H. DangandZ. McKenzie
University of Cambridge

Introduction

This paper endeavours to survey some of the recent work investigating
models of the stratified axioms of Zermelo-Fraenkel Set Theory (ZF).
Specifically we will focus on a hybridisation of the
Fraenkel-MostowskiSpecker and Rieger-Bernays permutation techniques developed by Thomas
Forster to produce models of the stratified fragment of ZF refuting certain
unstratified axioms.The major motivation is the hope that models of
fragments of stratified comprehension will shed some light on the consistency
strength of Quine’s “New Foundations” (NF). The job of completely
understanding and exploring generalisations of Forster’s technique is nowhere
near completion, by any stretch of the imagination.We will paint the
partial picture representing our present understanding as an overture to
discussing some of the important and interesting open problems in this
research. Anyresults discussed in the paper that are attributed to an
individual, but not referenced to a published text, have emerged in
discussions on this subject held at Cambridge University.

10

2.

V. H.D A N GANDZ. MC K E N Z I E

Forster's Hereditarily Symmetric Sets

In [4] Thomas Forster builds an inner model by inductively collecting
sets fixed by the action of a group of finitely supported permutations of
VωHe demonstrates that this class modelsacting at some level down.
the stratified axioms of Zermelo-Fraenkel set theory, axiomatised with
replacement, while refuting the axiom of choice.It is important to note
that when we restrict our attention to the stratified axioms of ZF set theory
we need to be explicit about exactly which axiomatisation of this theory we
are considering.While, in the presence of foundation and separation, full
replacement is equivalent to collection, the restriction of our attention to
stratified formulae renders the collection scheme strictly stronger than the
replacement scheme.This can be seen by considering Zermelo set theory
(Z). An old result of Coret’s [2] demonstrates that Z proves every instance
of stratified replacement, while Adrian Mathias [9] has observed that it
is easy to find models of this theory in which stratified collection fails —
consider for example a model that contains no infinite set of infinite sets
each of different cardinality.In the other direction a simple application of
stratified comprehension to the stratified collection schema yields stratified
replacement. Laterin this paper we will appeal to stratified collection in
order to show that Forster’s model interprets ZF set theory.For this
reason we will prove that the models we are considering satisfy stratified
collection wherever it is possible.In order to review Forster’s construction
and further examine some of the features of this model, we first need to
recall some basic definitions.These definitions will be familiar to the
reader acquainted with NF.

Definition 1.We useιto denote the operation of taking the singleton of
a set, i.e.ιx={x}.

For a setxwe also defineP1(x) ={ιy|y∈x}.

Definition 2.Ifφis a formula in the language of set theory, then
astratificationforφis an assignment of natural numbers to variables such
that ifxandyare variables andx∈yoccurs inφthenxis assigned
the natural numbernif and only ifyis assigned the natural number
n+ 1, and ifx=yoccurs inφthenxis assigned the natural number
nif and only ifyis assigned the natural numbern.

A sentence or formula,φ, in the language of set theory, that admits a
stratification is said to bestratified.

A

P E R M U T A T I O N

M E T H O D

1