Talk:New Foundations

Ordered pair

Resolved

 – The page has been edited long ago and now correctly points out the significance and possible definitions of type-level ordered pairs.

The statement "ordered pairs [...] in NF and NFU are defined in the usual way" might be misleading since the usual way is not stratified if X and (X,Y) shall be assigned the same type. —Preceding unsigned comment added by Stephan Spahn (talk • contribs) 14:20, 13 May 2011 (UTC)

This entry is a joy to read

It is evident from the writing style alone that the primary author of this entry is Randall Holmes. Thank you very much, Randall, for sharing your knowledge and enthusiasm with the rest of the world. And I can see that your thinking has continued to evolve since you completed your 1998 monograph. You continue to strike me as one of the most philosophically aware mathematicians currently teaching in the USA and Canada. It was by reading you some years ago that I became aware of the extraordinary beauty and power of NFU, which vindicates, I think, Frege's Grundgesetze and Quine's original intuition. I am dismayed at the lack of interest in NFU; in my view, even Tom Forster's monograph does not do it justice. And if it weren't for you, it could truly be said of Quine that, as a mathematician, he would be a prophet without honor in his own country. Nearly all other NFistes are, for some reason, European.

A question. Your 1998 monograph emphasizes a finite axiomatization of NFU, but your entry barely mentions it. Why so reticent? That finite axiomatization banishes once and for all the notion that doing set theory a la Quine style requires a prior commitment to stratification or to some disguised variant of the theory of types. Stratification is, satisfyingly, just an economical way of laying out much of set theory, and requires no ontological commitment of any kind.

Also please discuss briefly McLarty's(1992) negative results on NF and category theory. I am not qualified to say whether McLarty's results are correct, but regardless of their truth status, they deserve mention. The entry should also mention that Saunders MacLane was wrong when he conjectured that Quinean set theory was more hospitable to category theory than ZFC.132.181.160.42 00:03, 10 July 2006 (UTC)

McLarty's results

McLarty's results are correct. The best way to briefly summarize their import is that the set category of all sets and functions in NF or NFU is not really the correct analogue of the category of sets and functions in ZFC: the correct analogue of the category of all sets and functions over ZFC is the category of all strongly cantorian sets and functions in NF(U), which is a proper class category, and which is cartesian closed. McLarty does not say this (or at least I don't think so); he just briefly proves that the set category is not cartesian closed. Randall Holmes 01:24, 3 July 2006 (UTC)

How significant actually is this failure of Cartesian closedness? Is it just a matter of applying some singleton maps to account for the fact that the definition of the naive ${\texttt {curry}}:(A\times B)\to C\quad \to \quad A\to (B\to C)$ is not properly stratified, or is there something deeper to this? Bbbbbbbbba (talk) 09:30, 2 May 2024 (UTC)

Are the quantifiers reversed?

Resolved

 – The problem pointed out has been fixed.

The paragraph about comprehension has this formula:

$\forall x^{n}\exists A^{n+1}[x^{n}\in A^{n+1}\leftrightarrow \phi (x^{n})]$

I read this so that the $A^{n+1}$ can vary for different choices of $x^{n}$, which does not look much like a comprehension. There should be different $A^{n+1}$ for different $\phi$, but for a given $\phi$ and a given n, the formula should say that there exists (at least one set) $A^{n+1}$ which, for each $x^{n}$ contains it if and only if the predicate $\phi$ applies:

$\exists A^{n+1}\forall x^{n}[x^{n}\in A^{n+1}\leftrightarrow \phi (x^{n})]$

Am I missing something?

Now the text leading up to this formula already contains the phrase "the set $A^{n+1}$ exists such that", so perhaps the formula should be only

$\forall x^{n}[x^{n}\in A^{n+1}\leftrightarrow \phi (x^{n})]$

PerezTerron 16:12, 1 January 2007 (UTC)

I tried to fix it. Does it look OK to you now? JRSpriggs 07:29, 2 January 2007 (UTC)

We do not take a position on this?

Could someone please clarify the referent of "we" in the sentence starting "We do not take a position on this..."? This impacts its meaning. If it's the editorial "we" then it's a simple statement of fact about the responsible editor, but if it denotes the readers then it would seem to be more of an advisory of the form "one should not take a position on this." --Vaughan Pratt (talk) 12:12, 12 April 2009 (UTC)

Since taking position on anything would be against the NPOV rule of Wikipedia, an explicit statement of this is redundant and should be removed. --77.13.121.141 (talk) 20:41, 22 July 2012 (UTC)

Even worse, a bit later there are sentences going "(some people say such-and-such, but) We claim that this-and-that". –Henning Makholm (talk) 19:28, 4 September 2012 (UTC)

Much of the article was written by an expert on NF, many years ago (see the page history). It definitely needs to be copyedited to remove most of the uses of "we" and tighten up the sourcing. But at the same time I think it is important to remember it was written in a different period of Wikipedia, and given the authorship there is little reason to be excessively skeptical of the content. — Carl (CBM · talk) 19:46, 4 September 2012 (UTC)

I revised this sentence (already slightly reworded by other editors) to "Given the ambiguity of the concept "standard", this statement is philosophical rather than mathematical.", which hopefully implies "There is no mathematical answer to this." Bbbbbbbbba (talk) 02:29, 10 March 2023 (UTC)

How NF(U) avoids the set-theoretic paradoxes has randomly scrambled sentences

The mentioned paragraph seems to have been edited to trash. I do not know the original work, so I can't correct it. If someone with more knowledge would look through this, it would be helpfull. Rubybrian (talk) 20:34, 15 November 2008 (UTC)

U in NFU

Resolved

 – Now the introduction clarifies that "U" means urelements.

What does the U stand for? --Abdull (talk) 20:30, 6 September 2010 (UTC)

Urelements. --Trovatore (talk) 20:38, 6 September 2010 (UTC)

Summary: what's it for?

It would be nice if this article included, as the second paragraph, a summary of what NF/NFU is "good for" viz, why its interesting and fruitful to pursue (e.g. by hinting at important results). This should come before the definition of TST, and summarize the rather long article that follows. linas (talk) 15:15, 27 July 2011 (UTC)

Choice and Infinity

The article makes numerous references to Choice and Infinity, without defining them. Presumably they refer to the Axiom of choice and Axiom of infinity respectively, and all the editing that needs be done is to make links out of the first occurrencies, but I would be more comfortable if some expert on NF could confirm that these are the correct interpretations. For example, might one need some special care when stating them? The statement given in Axiom of infinity is probably not stratifiable at all! 130.239.234.107 (talk) 15:02, 12 September 2012 (UTC)

I just came here to say the same thing! It is a shame, I guess nobody is reading this page... KarlFrei (talk) 08:49, 1 March 2019 (UTC)

This is a very good question! From my understanding, the "usual" form of Infinity is indeed not stratifiable, but it is also trivially true since the universal set V satisfies it. Even though the existence of $x\cup \{x\}$ is not directly guaranteed by stratified comprehension, the existence of $x\cup \{y\}$ is, and the rules of logic allows substituting x for the free variable y (see Section 8.3 of Holmes' NF book for an example of this kind of technical argument). But such a form of "Infinity" would be pretty much impossible to use effectively in NF, not to mention philosophically meaningless.

The commonly accepted form of Infinity for NF instead uses the form of natural numbers commonly used in NF: The natural number n is defined as the set of sets with n elements (i.e., Frege's definition of the cardinal numbers). The successor operation is well-defined for natural numbers defined this way, but here the danger is that if the universe only has n elements, then n+1 would be the empty set since there is no set with n+1 elements. The Axiom/Theorem of Infinity therefore states that this is not the case for any natural number n, where the concept of "natural number" is rigorously defined as the intersection of all inductive sets (which is defined based on the NF definition of successor).

Still, what does this mean? It would seem that for any "standard" natural number n it cannot be the case that the universe only has n elements, because 0, 1, ..., n are all distinct members of V. And yet there exists models of NFU where Infinity doesn't hold. My current understanding is that there is no guarantee that the intersection of all inductive sets only contain "standard" natural numbers, because there is no a priori guarantee that all "standard" natural numbers form a set. In a model where Infinity doesn't hold, there is no way to distinguish V from externally finite sets. Since the existence of a choice function is a property that could be defined within NF(U) in a stratified way, if the Axiom of Choice doesn't hold, then "the set of all cardinalities such that each set of that cardinality has a choice function" would be an inductive set that doesn't contain the cardinality of V, thus proving Infinity.

I know this is a lot to wrap one's head around, and I'm not sure my understandings are fully correct, but I hope discussion would make things clearer. Bbbbbbbbba (talk) 03:18, 7 March 2023 (UTC)

I added a section trying to rectify this problem. On the statement "NFU + Infinity + Choice proves the existence of a type-level ordered pair": This seems like one just needs to restate the proof of "$|A\times A|=|A|$ for infinite $A$" in terms of Kuratowski pairs, although I'm not certain this could be done in a way so that the final result is correct typewise... Bbbbbbbbba (talk) 04:42, 12 March 2023 (UTC)

Article on NF has to say that it is Non well founded!

How can we have an article on Quines New Foundations which doesn't mention anywhere that it is a non well founded set theory!

I.e. a set theory which permits

…x_n ∈ x_n-1 ∈ …x₃ ∈ x₂ ∈ x₁ .

This should be featured prominently and a whole section devoted to it. I was going to link to this article in something I'm writing (on ET maths) - as the logic sections in wikipedia are generally good - but this is a major omission.

Also it could do with a philosophical section, explanation of the philosophical reasons for focusing on a stratified formula, rather than forcing well foundedness on the sets themselves.

See Quine's New Foundations

I assume this is just an oversight as the article is good otherwise.

I'm not specialist in Quines NF so am a little hesitant about editing the article myself. Especially since it is clearly written by specialists and is otherwise thorough. But you could take the Stanford University account as a starting point. I recommend someone does this.

If nobody else feels up to it, I can do a "stub" type section on this. Robert Walker (talk) 12:57, 15 August 2014 (UTC)

Since this had no reply, I've added an extra para mentioning the well foundedness in the intro. Perhaps someone else would like to write more, as I think it deserves a paragraph on this topic somewhere on the page - on the philosophical motivation of NF as a theory that lets you reason about non well founded sets. Robert Walker (talk) 14:13, 31 August 2014 (UTC)

To be honest, as of now I don't feel like I agree with NF's philosophical motivation. It does admit non-well-founded sets, but actually reasoning about them is difficult since every now and then you'll find yourself restricted to stratified sentences. It is supposed to eliminate the "hall of mirrors effect", and it might do that for "small" sets, but I cannot shake the feeling that large sets like V or Ord are really just "ω types in a trenchcoat": They can be forced to "shed the outermost layer" with the appropriate T operation, and for certain models of NFU they even still believe themselves to be finite because they are "finite at each type". If there is anything I'm currently taking away from my study of NF, it is that TST is cool and NF(U) is the troublesome child. Of course I'm open to the idea that someone with a deeper understanding of NF might change my mind. Bbbbbbbbba (talk) 12:01, 10 March 2023 (UTC)

Consistency of NF

Randall Holmes has announced a consistency proof for NF on his home page. And Murdoch J. Gabbay has a preprint here announcing the same thing. r.e.b. (talk) 21:48, 30 July 2015 (UTC)

"Quine presumably constructed NF with this paradox uppermost in mind"

Resolved

 – The sentence has been edited to assert that Quine did say that, citing the article mentioned by 137.205.100.79.

Yes; Quine actually told us what he had uppermost in mind in a short piece called "The Inception of NF" - chapter XXX in "Selected Logic Papers - Enlarged edition" (Harvard)137.205.100.79 (talk) 08:51, 20 November 2017 (UTC)

Someone edited this sentence, and I added the citation. For the record, next time you might want to clarify that "Chapter XXX" means "Chapter 30" when certain Roman numerals are involved. Bbbbbbbbba (talk) 21:17, 8 March 2023 (UTC)

tone

Hi, the tone in that section where it says it should be easy to prove does not seem to be written in an encyclopedia-like style. — Preceding unsigned comment added by 173.61.129.30 (talk) 12:55, 13 September 2020 (UTC)

"Iterative conception of set" doesn't seem to belong anywhere

Currently the the first paragraph of the section "Models of NFU" talks about the iterative conception of set discussed in Forster 2008, but I don't think the article gives a model of NFU, and I am skeptical that the method could be successfully applied to NFU, because (1) in the Church-Oswald models there is a clear separation of the universe into low sets and co-low sets, while if we use, say, a finite axiomatization for NFU, we will have difficulty determining which sets created by different "wands" are actually equal; (2) if this worked for NFU, why wouldn't this work for NF?

So this citation certainly has something to do with NF(U), but if it doesn't lead to a model of NFU, I think it doesn't belong to this section, and I don't know where else to put it. @Chalst: Since you added this citation, do you have any insight? Bbbbbbbbba (talk) 08:50, 15 March 2023 (UTC)

Proposal: provide weak extensionality axiom

I wasn't confident about what the weak extensionality axiom is until I read somewhere that urelements are empty sets.

In the present article, we have the language "urelements (multiple distinct objects lacking members)", which in retrospect is easily interpreted as "NFU has multiple, unequal empty sets"; however, if a comp sci phd was left unsure, I imagine others will be too.

It's important to have this be crystal clear, since the known consistency of NFU, in contrast to the apparently-not-100%-accepted consistency of NF (or, at best, very difficult to prove consistency), is a fascinating fact.

Weak Extensionality: Two nonempty sets with the same elements are the same set. Imsecretguy (talk) 14:41, 31 August 2023 (UTC)

While that is indeed one way to go about it, from the perspective of ease of use, it makes things much easier to have a "canonical" empty set, if only to make the notation $\{x\mid \phi (x)\}$ uniquely defined. AFAIK this is usually achieved through a sethood predicate (see e.g. Section 2 of [1]). Maybe this page should mention both approaches. Bbbbbbbbba (talk) 10:31, 2 May 2024 (UTC)

Non-well-founded natural numbers as well as ordinals?

In Drake's Set Theory: An Introduction to Large Cardinals (p.19) it is claimed that the natural numbers of any model of NF are non-well-founded. The cited source is (Rosser, Wang, "Non-Standard Models for Formal Logics", 1950), however I do not see the result in this source. Should it be added citing Drake if it is true? C7XWiki (talk) 07:20, 19 January 2024 (UTC)

I couldn't find a copy of Drake's book, but if I'm understanding correctly, it's more that Frage's definition of natural numbers is non-well-founded, e.g. $3\in \{3,33,333\}\in 3$. I'm not sure if this fact is significant enough to be mentioned on this page (instead of maybe on Set-theoretic definition of natural numbers#Frege and Russell). Bbbbbbbbba (talk) 11:32, 2 May 2024 (UTC)

Move NFU

Much of the article is about NFU rather than NF per se. Perhaps it would be better to move the NFU-specific material, such as the section "Strong axioms of infinity", to its own article. Thefringthing (talk) 15:29, 24 April 2024 (UTC)

Hmm... The way I look at it, NFU, as it turns out, is a more intuitive implementation of the NF idea (due to the axiom of choice not failing outright), and possibly a more suitable candidate than NF without urelements to really be used as a "new foundation of mathematics" (although this may change somewhat with the recent verification of the proof of the consistency of NF relative to ZFC), so right now I don't see a good way to separate NFU cleanly from this article.

On the other hand, I don't remember if the section "Strong axioms of infinity" has enough relevance to justify being in this article, so maybe that can be its own article (titled "Strong axioms of infinity in NFU" or similar)? Bbbbbbbbba (talk) 02:30, 27 April 2024 (UTC)

I think Randall Holmes's paper is more detailed than the section, I have just taken the section out and put a ref in the natural numbers + axiom of infinity section. Mathnerd314159 (talk) 03:07, 27 April 2024 (UTC)

What is the consistency of NFU relative to (if anything)?

This article currently states that "In 1969, Jensen showed that adding urelements to NF yields a theory (NFU) that is consistent relative to Peano arithmetic".

Jensen's paper mentions a theory named "elementary number theory (Z)", which seems to me like PA (since its primitives seem to be numbers, addition and multiplication), but I'm not sure right now. Furthermore, Jensen's paper says that Con(NFU) is provable in Z (unconditionally), which is allowed because NFU doesn't prove Inf and thus doesn't interpret Z. It also says that Con(NFU+Inf+AC) follows from Con(TST+Inf+AC) (in other words, NFU+Inf+AC is consistent relative to TST+Inf+AC), the proof of which is formalizable with Z as a metatheory. Jensen's paper also mentions that a weak version (denoted S) of Zermelo set theory is equiconsistent with TST, but I don't see any discussion about how the consistency of the metatheory Z itself factors into the equation. In any case, if NFU or NFU+Inf+AC is consistency relative to PA, then according to my understanding, a stronger theory such as ZF which proves Con(PA) should prove Con(NFU) or Con(NFU+Inf+AC) unconditionally anyway.

How should we actually understand Jensen's result, and should we edit this article to be more accurate? Bbbbbbbbba (talk) 14:13, 4 May 2024 (UTC)