User talk:RJGray/Sandboxcantor1
Handling of some clarify comments
[edit]I'm carefully working through your excellent clarify comments. I mention the clarifies that cause me to modify the article in my Edit summaries, but I need a way to communicate about the other clarifies, which is what I've decided to do on my Talk page. Here are three of those clarifies.
The Lead
Clarify: The name 'NBG' could be understood to refer to a collaborate effort of N., B., and G. However, from your description it seems that they never e.g. met to a discussion session, but that they worked independently, one reading and incorporating papers of the other(s). Maybe it's worth stating their (non-)relation explicitly?
Reply: Excellent point about the (non-)relation! However, I've only been able to recently discover the Bernays/Gödel connection. So far, I have found nothing on the von Neumann/Bernays connection. I've just started reading Hao Wang's A Logical Journey: From Gödel to Philosophy, and learned that Gödel and Bernays kept in contact for many years. I suspect that Bernays may have been dealing with von Neumann's articles, but he could have had contact with von Neumann around 1929, the year that von Neumann's 1929 axiom system was published and the year that Bernays' started lecturing on his work on sets and classes. Some historical research may give insight into whether they discussed set theory together. While working on this article, I did discover that Gödel learned of Bernays' theory in a 1931 letter. This clarified a major confusion of mine—I knew that together Bernays' articles of 1937 and 1941 contain his axioms, but Gödel lectured on his system, which is a modification of Bernays' system, in 1938! I was happy to learn about the 1931 letter. Anyway, I mention the 1931 letter in the History section and refrain from speculating about the von Neumann/Bernays connection. These details (and more) are covered in History section. (I misread MOS:LEAD, so I took that quote out.) Anyway, the Gödel/Bernays connection as I currently understand it is one letter (there are letters after Gödel's 1938 lectures but they are not relevant to Gödel's development of his axiom system). Also, I currently know nothing about the von Neumann/Bernays connection, so I really don't want to discuss the relations or non-relations in the lead.
J.'s Reply: Ok, I see that the full details of history are complicated and not completely uncovered yet. (Btw: I very much like your interest in history and your appreciation of original papers.) Would it at least be possible to indicate that there wasn't a common paper of von Neumann, Bernays, and Gödel (like Artin.Tate.1951 for the Artin–Tate lemma), but instead the situation was more like for the Artin–Rees lemma (own paper Rees.1956, and independently an Artin paper which I couldn't find out yet)? - I'm not familiar with any of both lemmas; I just took them from Category:Lemmas as an example for you about what I mean; none of them should be mentioned in the NBG article itself. I guess, the phrase "independent work" from the lead of Artin–Rees lemma doesn't really apply to NBG? If it would, it could be used for a brief characterization in the lead. If it doesn't, things are probably too complicated for the lead.
Reply #2: I'm glad to hear that you like my interest in history and original papers. I'm very curious how people come up with ideas and I find that I get a better sense of where ideas come from by learning the history and the original approach to problems. I think that NBG is really a case of 3 mathematicians building on the work of the earlier mathematicians (probably mostly through publication in von Neumann->Bernays, and publication in von Neumann->Gödel and the 1931 letter in Bernays->Gödel). I think that this comes across a bit in the current lead and more so in the History section. Your diagram captures this, too. By the way, thinking about your diagram, I realized that it may be good to keep Zermelo with "Elementary sets", add "Ordered pairs" to von Neumann's two axiom systems, and keep "Pairing" for Bernays and Gödel. I think we have several options here, but this particular axiom isn't as important as the other ones. For now, I think it's best to keep the lead as is. However, I will revisit the lead later and will keep your thoughts in mind. (After I'm done with an article, I always revisit the lead.)
Class existence axioms and axiom of regularity
Clarify: Maybe, a sentence that concludes the example is helpful, e.g.: Provided all four axioms are present, the above arguments can be used to prove that is a class whenever both F and G are.
Reply: I started implementing this suggestion, but realized some subtleties get in the way. For example, the axioms are not enough to produce the unique set of ordered pairs because the permutation axioms do not produce unique classes. You only get uniqueness after defining and intersecting the class produced by the axioms with . The intersection with is an important detail that is covered later. Anyway, this example is just to give the reader an idea of what kinds of axioms are needed and how they will be used.
J.'s Reply: Ok; I wasn't aware of these subtleties.
Clarify: For readers wondering about an equality-handling axiom, here may be the best place to announce that (=) will be reduced to (in) by extensionality. On the other hand, having too many announcements in the article isn't a good idea; so I'm not sure.
Reply: I prefer not to make the announcement. Most readers who are astute enough to wonder about an equality-handling axiom may realize on their own that extensionality may play a role here. Also, this article is making enough demands on the reader, so I want to keep to a minimum announcements about future developments.
J.'s Reply: Ok; I wasn't sure myself.
Thanks for all your clarifies, RJGray (talk) 17:04, 16 September 2017 (UTC)
Handling of clarify comment about quantified formulas being expanded
[edit]Hi Jochen, I thought it'd be a good idea to use this Talk page for discussing the article.
Clarify: Since the exact structure of the formula is important here, the issue of section 'Definitions and axioms of extensionality and pairing' should be remembered here. In particular, univ.quant. abbreviation is expanded into implication, which has to be transformed away. When you keep the abbreviated notation for convenience, make plausible why this can't cause any harm. Possibly, inserting an 'abbreviation expansion' transformation step between 2 and 3 would do.
Reply: Good point! The reason the proof works is that quantifiers are handled by and the domain axiom states:
So it also uses an abbreviated expression, which is why the proof works. If you do expand the expression for in the definition of , you also need to expand the expression when is used. Here are the details in the part of Case 3 of the inductive proof that handles:
The inductive hypothesis implies that there is a unique class of -tuples such that:
By the axioms of domain and extensionality, is the unique class of -tuples such that:
If you change to you need to change it in the definition of and in Note: I use rather than because the latter quantifies over classes, which we must avoid, and the two are equivalent. Changing to
Obviously, I don't want to go into a long explanation like this in the article. As long as one consistently uses abbreviated expressions or longer expressions, there are no problems. I'm not sure if readers will even see a problem since I do handle expressions consistently. Perhaps you can make some suggestions here. Thanks, RJGray (talk) 18:41, 17 September 2017 (UTC)
- I understand that these (unexpectedly many) technicalities shouldn't be explained in detail in the article. What about a footnote to tell the reader that this issue had been thought of and doesn't cause problems? E.g. "Strictly formally, quantification over lower case set variables is transformed to , and accordingly transformed versions of the axioms of domain and extensionality are used [in inductive step case 3]." If the footnote is placed within that case, the bracket contents can be omitted of course. - I think, a computer programmer (I'm 1/2 math + 1/2 cs) might wonder which kinds of nodes could appear in a formula tree when implementing your algorithm, and then will appreciate the footnote's hint. - Jochen Burghardt (talk) 09:51, 27 September 2017 (UTC)
Handling of "Class existence theorem" comments
[edit]First part of proof. Renamed: Proof of the class existence theorem: Transforming the given formula; Expansion lemma
Clarify: Apparently, P must also contain *all* pairs satisfying R, since Q contains all such tuples.
Reply: I'm not sure what you mean by "all pairs". For example, if is , does "all pairs" refer to ? The terminology I consistently use is "a class whose ordered pairs satisfy ." The term "whose ordered pairs" distinguishes the ordered pairs of from the other elements may contain. So it naturally refers to all the ordered pairs of . The reader has earlier experienced this terminology along with the formal statement for it. For example, in the axiom:
- Membership. There exists a class whose ordered pairs are such that the first component is a member of the second component.
- Membership. There exists a class whose ordered pairs are such that the first component is a member of the second component.
J.'s Reply: I read your phrasing "a class whose ordered pairs satisfy " formally as "". I think you'd need also the direction "R(x_i,x_j) ⇒ (x_i, x_j)∈P". So yes, in case that R is (=), my "all pairs" should refer to ; in contrast, for this R e.g. P = { (∅,∅) } would be a "class whose ordered pairs satisfy ", from this P you can't get , by embedding.
Reply #2: Excellent catch! My phrasing is completely misleading! It all started with my membership axiom wording (see above). It now reads:
- Membership. There exists a class containing all the ordered pairs whose first component is a member of the second component.
- Membership. There exists a class containing all the ordered pairs whose first component is a member of the second component.
My problem was that I used "whose ordered pairs" to mean "iff", which I realized when you read it as "implies", which is what it really means. So I fixed the membership axiom to use "containing all the ordered pairs". I looked at all the occurrences of "whose" in the article and the only ones that were valid are found in the circular permutation and transposition axioms. This caused quite a cleanup job for me and I made a few other improvements while doing this work. Thanks again for noticing the problem.
Second part of proof. Renamed: Proof of the class existence theorem for transformed formulas
Clarify: This is 'only' the proof of the 'heart' theorem (stated below), which shouldn't be confused with the whole class existence theorem (as stated above). I'm not sure whether to call the former a 'theorem' at all, since it isn't in the 'export interface' (to abuse a software-engineering notion for mathematics) of this article; it might be called 'lemma' therefor.
Clarify: Clearly distinguishing the two theorems will avoid confusion (like 'why does he restrict the class existence theorem now?') here.
Reply to both clarifies: Excellent clarifies! I've been having trouble naming the parts of the theorem and your comments have clarified things for me. I realized now that it's more than a lemma, it's a special case of the theorem. So I have changed the name of this part of the proof to "Class existence theorem for transformed formulas" since what is being proved is a special case of the theorem, which handles the entire theorem because of the first part of the proof handles the transformation of the formula. This is a standard proof technique used in some proofs, so readers may have come across it before (if they haven't, this will introduce this proof technique to them).
J.'s Reply: You are right; I didn't notice before that the induction actually proves a special case of the class existence theorem.
Reply #2: You are not alone in not noticing this. It took me quite a bit of time to realize that it was a special case—this is the 2nd time I've rewritten parts of this section.
Remaining clarify comments from "Class existence theorem" section
[edit]Proof of the class existence theorem for transformed formulas
Clarify: I think, you might well end up here [Case 2c () for ] with n>1, e.g. from a case 2 inductive step on a formula in 2 free var.s. Also, you don't really need n=1.
Reply: I'm a bit confused. I don't see how I'll end up in Case 2c with n > 1. The 3 cases are all distinct from each other and the case does occur. Here's a sample of the 3 cases with their outputs:
is where Example: Class:
is where Example: Class:
is where Example: Class:
J.'s Reply: Oops, my fault. When reading case 2b, I didn't fully realize its meaning (I must have been sleeping). My 'clarify' intended to suggest to add just that case (2b). - Sorry for the confusion! I now realize that case 2a,b,c together completely cover i<=n AND n>=1, as expected. You need the distinction 2b,c since the former case needs embedding, but the latter doesn't.
Clarify: (Case 3 of inductive step) Similar to base case 2c, I'm afraid you can have x sub k with k>n arbitrary as the quantified variable. --- After reading your Pascal program and re-reading the bounded renaming rule, I think k can't deviate from n+1. I nevertheless keep this (clarify) so you can confirm that.
Reply: Yes, you figured it out. The bound variable renaming rule guarantees that k = n + 1.
Handling of clarify comments: Set axioms
[edit]Axiom of infinity. There exists a nonempty set such that for all in , there exists a in such that is a proper subset of .
Clarify: Perhaps easier to comprehend: 'for each x in a, some proper superset y of x is in a, too.'
Reply: I agree it's perhaps easier to comprehend, but I'm reluctant to change the statement of an axiom (unless there are strong reasons to change it).
The axioms of infinity and replacement prove the existence of the empty set.
Clarify: While I had no problems understanding this, a first-time reader might overlook the class/set distinction. Maybe you can italicize these words? And using a colon ':' rather than a period '.' after the 1st sentence would indicate that a justification (rather than a new issue) follows.
Reply: I rearranged the second sentence, and followed it with "Proof that is a set: …" This lets the reader know immediately what is happening (proving that the empty class is a set) instead of putting it at the end of the paragraph.
Handling of clarify comments: The uses of classes
[edit]Clarify: A sentence might be added to explain the difference to ZFC's axiom, e.g. (needing improvement): While ZFC's axiom of choice ensures that for every family M of nonempty sets a choice function f exists with (forall x in M. f(x) in x), NBG's axiom of global choice additionally ensures that all possible choice functions can agree.
Reply: I have mixed feelings about getting into why this is stronger because it's covered well in "Axiom of global choice" in the "Set axioms" section. However, I did add: "This is stronger than ZFC's axiom of choice that states: For every set of nonempty sets, there exists a choice function defined on such that for all " I also added a reference: "[[#Axiom of global choice]] explains why it is provably stronger." So I give the reader some idea of why it probably is stronger, then refer them to the place I cover it in more detail. Please give me feedback on this.
J.'s reply: I think, your explanation in User:RJGray/Sandboxcantor1#Axiom of global choice is fine, and the footnote at User:RJGray/Sandboxcantor1#The uses of classes is ok, too.
Handling of clarify comments: Extending the class existence theorem
[edit]2nd clarify: "they can be replaced by free variables ": This completes my confusion about the role of the (C sub k). I have to think it over by myself, also considering the distinction between variables in the theory and meta-variables. I may need some time to come up at least with a question about what precisely I don't understand.
Reply to 2nd clarify: I've unfortunately confused you here. What I should have said is that we can go from the formula with arbitrary constants:
to the universally quantified formula:
This is valid by universal generalization: If has been proved for arbitrary , then follows. Paul Cohen says the following about this (Set Theory and the Continuum Hypothesis, p. 10):
Often in arguments we say "let c be an arbitrary but fixed integer". We then proceed to reason about c and come to a certain conclusion A(c). We can then deduce that ∀x A(x) since we used no special properties of c. In reality, we have treated c as a variable, even though we called it a constant. This is because our valid statements will be true in every interpretation of the constant and relation symbols. (I'm not sure what he's trying to say in this last sentence.)
1st clarify: "class term": Aren't the (C sub k) in the un-generalized class existence theorem allowed to be class terms, too? Looking at the above core proof, the relevant case is 2c in the induction base; there, an arbitrary term denoting a class will do. All other base case steps deal with permutations/embeddings; a class term would't hurt there either. Consequently, I wonder if tfm. step 3 below can be omitted. (E.g. if we already *know* that (C1 cap C2) is a class, we don't need to know how it is defined; we just return that class term in base step 2c.) - In any case, it might be a good idea to state explicitly whether (C sub k) means a constant or an arbitrary term in the above un-generalized theorem.
Reply to 1st clarify: This is a complex issue. I know I've went from calling them parameters to classes. Here's how Gödel handles them: he calls the 's "symbols for special classes" before his M1 (his first class existence metatheorem) on page 8, but he doesn't define "special class" until after the proof of M1 on page 12. Here he states that "a special class A is introduced by a defining postulate φ(A), where φ is a propositional function containing only previously defined symbols, and it has to be proved first that there is exactly one class A such that φ(A).
This is very unusual for Gödel, defining something after it is used. I've looked into this further and realized that, before M1, he calls them "symbols for special classes" so they are different than the "special classes" introduced on page 12. Hence, they seem to be individual constants, or more precisely, individual class constants. I guess we can call them "class constants".
Unfortunately, Wikipedia does not have a good definition for "individual constant". They are mentioned at Non-logical symbol, but when you click on the link for individual constant, it sends you to the current page (a circular link!). So if I introduce class constants, I'm going to have to define what they are on the Non-logical symbol page or some other page.
But perhaps Mendelson's approach is better. He doesn't use "symbols for special classes", instead he uses class variables from the start. Here's how the class existence theorem appears with this approach:
Class existence theorem. Let be a formula that quantifies only over sets and contains no free variables other than (not necessarily all of these). Then there exists a unique class of -tuples such that: The class is denoted by
The proof just uses the 's instead of the 's. Also, it may be good to use Mendelson's instead of Gödel's
So which do you think is better: Gödel's approach of starting with class constants and later switching to class variables or Mendelson's approach of only using class variables?
- J.s reply: Thank you for your elaborate explanations; and please apologize my confusion; it's a problem of mine, not of your presentation. Your explanations helped me to get some (feeling of) clarity.
- I now think I first should become clear about the following questions: "When using the class existence theorem, what kind of expressions am I allowed to insert for ?", and, conversely, "When proving it, what kind of expressions do I have to deal with?" I guess the answer to both questions is "anything that denotes a class", examples being (I'd call this a class constant), (I'd call this a class expression), or just some (I'd call this a class variable) that was introduced somewhere before by "let be a class [such that ...]". - I guess you would agree with that, except possibly for my namings in parantheses, wouldn't you?
- Provided my above understanding is acceptable, I'd prefer Mendelson's approach. Calling the (or ) variables would indicate to me that the theorem can be used for arbitrary instances of them, and that inside the proof nothing can is known about them except that they are classes. - My point in the 1st clarify was that the class existence theorem doesn't need to be extended in order to allow e.g. to be substituted for some in an application of the theorem. However, now I think you might still need for class expressions (a.k.a. class terms) that originate from , rather than from some ; as an example, I came up with , the expression around can't be understood to be an instance of some , therefore you need the New transformation rules to cope with . In contrast, you wouldn't need them to cope with , for some given classes (admittedly a poor example). - As a resulting suggestion, maybe just giving an example (a better one than mine above) of a </math>\phi</math> that needs the New transformation rules could be helpful; it could easily be presented before Example 3 and 4. - Jochen Burghardt (talk) 11:35, 27 September 2017 (UTC)
Clarify: A formula of the form 'forall X exists A (A=T(X))' looks unusual to me, as it is trivially true. The non-trivial part is that T(X), i.e. the class comprehension, is defined at all, i.e. exists and is unique. However, this is not *expressed* by the formula, but *presupposed* by it.
Reply: I admit it looks unusual and thus confusing. I think I'm using the set-builder notation in a way that's not normally done. So I'm taking it out, but I'll show you that it does make sense. To see this, I'll transform using extensionality and then the definition of the set-builder notation.
So is the class of -tuples satisfying .
J.'s reply: My point is the the first formula, (*), of your demonstration is trivially true (abbreviating the class comprehension by ""):
Hence, the achievement of the class existence theorem is not the validity of the latter formula, but the well-definedness of the expression in it. As an analogy, after constructing integer numbers from natural numbers, one may conclude "We have shown that , hence the expression is always well-defined and we can use it from now on"; but it doesn't make sense to write instead "We have shown that ". Extending the analogy, one could argue that is equivalent to , but the issue of well-definedness remained. - Jochen Burghardt (talk) 12:08, 27 September 2017 (UTC)
Rewrite of Class existence theorem and Extending the class existence theorem
[edit]Hi Jochen, Thanks for all your clarify comments. I have rewritten the class existence theorem using free class variables. Also, I figured out why you found "Extending the class existence theorem" confusing. It's because I didn't do a good job writing it. In fact, I diverted too far from Gödel's proof. He doesn't transform a formula as far as I do—he only transforms it so that it satisfies the hypothesis of the class existence theorem. So I completely rewrote it. I also redid Example 4 so it shows how a set variable can interact with a class variable in an operation. I came up with this example because of one of your insightful clarifies. This example can't be handled through class variables alone and thus shows the need for extending the class existence theorem. RJGray (talk) 20:39, 8 October 2017 (UTC)
Done with rewrite of NBG article; also planning to add a section to "Function (mathematics)"
[edit]Hi Jochen, I think that I'm finally done with my rewrite of the article. Mostly it's a rewrite of the two sections "Class existence theorem" and "Extending the class existence theorem" (the latter section has been completely rewritten to handle your excellent comments). Because you had earlier confusion on the function definition I used, I'm planning to add a section to the Wikipedia article "Function (mathematics)", which will follow the current "Definition" section. The current article only emphasizes one definition of function so I can't reference their article from my article without confusing readers. The new section is below. Thanks for all your help, RJGray (talk) 18:26, 14 October 2017 (UTC)
Proofs are now hidden
[edit]Hi Jochen, A while ago, you mentioned having the proofs come up hidden. I didn't want to do that at the time because in the computer program I use classes that are defined in the proof. I've finally realized that I can define these classes in the comments and make the program independent of the proofs. I would like your opinion on this. Particularly, my explanation of the program being independent of the proof that appears just before the program. Thanks, RJGray (talk) 20:39, 17 October 2017 (UTC)
- Hi Robert, sorry for the delay. This weekend, I'll have time to read the article in one piece. I'd prefer to give my impression about hiding / not hiding the proofs after that, when I have recalled the contents as a whole. Best regards - Jochen Burghardt (talk) 17:08, 19 October 2017 (UTC)
Hi Jochen, no need to apologize for the delay—it's given me time to improve it a bit more. Thank you for telling me that you are planning to look at it this weekend. This motivated me to look over my recently changed intro to the computer program. I have rewritten and improved it. Looking forward to your comments, RJGray (talk) 16:24, 20 October 2017 (UTC)
- Hi Robert, I started reading, but was interrupted by my neighbors playing load German pop songs. So I stopped reading, and added the few remarks that came to my mind. — I just arrived before the now-hidden proof boxes; my feeling is that after that much preparatory explanations, I'd like to see the proofs in any case; that is, I'd prefer the boxes coming up expanded. The title of the first box is too wide on my (16 cm wide) tablet, the "[hide]" appears overlayed on the "lemma" there. On my laptop, the browser window is sufficiently wide so it looks fine. However, I can't copy-and-paste from the headings, probably since you set them in <math>. I believe to remember you did this in order to have the heading, the "Proof", "Case 1", etc. in an appropriate size, so probably it shouldn't be changed. — When reading the lead section, I wondered if you could give (in the "NBG, ZFC, and MK" section) examples for collections that are definable
- in MK, but not in NBG (I guess, some exist),
- in NBG, but not in ZFC (e.g. just refer to introduced before),
- in NBG, but not in MK (if some exist),
- in none of ZFC, NBG, MK (this would require an understandable informal description, maybe, "class of all classes" could be an example?)
- I'll read the second half of the article tomorrow. Best regards - Jochen Burghardt (talk) 19:54, 21 October 2017 (UTC)
Concerning "The axiom of regularity" in "Von Neumann's 1925 axiom system", I did a little searching by myself, and found that von Neumann (1925) on p.230 critizes Fraenkel's "Beschränktheitsaxiom" (literally: "axiom of boundedness"). The only article he cites from Fraenkel is:
- Abraham Fraenkel (1922). "Zu den Grundlage der Cantor-Zermeloschen Mengenlehre". Math. Annalen. 86: 230–237.
{{cite journal}}
: Cite has empty unknown parameter:|month=
(help)
In this article, Fraenkel mentions a Beschränktheitsaxiom on p.234 (=p.6 in the PDF), and refers in fn.7-->fn.3 (p.231=p.3 in the PDF) to another publication for details:
- Abraham Fraenkel (1922). "Axiomatische Begründung der transfiniten Kardinalzahlen I — Herrn K. Hensel zum sechzigsten Geburtstag". Mathematische Zeitschrift. 13: 153–188.
There on p.163 (=p.12 in the PDF), I found his "axiom X", which translates "There are no cardinal numbers ['KZ' is explained on p.153=p.2 as 'Kardinalzahl'] except for those that exist due to axiom I to IX". — I don't know whether any of this is useful for the article (the relations between the citations are probably too difficult to explain them there), but you might be interested in the references nevertheless. I'll also add them to the Abraham Fraenkel article. - Jochen Burghardt (talk) 13:44, 22 October 2017 (UTC)
It seems that section "Models" hasn't be written by you, as it is hard to understand, lacking many explanations. I wonder if the "Von Neumann universe V" there is the same as your class of sets V. At least, both Vk and Lk should be explained. "Mendelson's version of NBG" should be explained, too, and be related to your history section. Concerning the "Category theory" section (also probably not authored by you?), it says nothing than a repetition of your paradoxes section, applied to categories rather than sets. I doubt whether NBG is mentioned in any of its two references; I'd suggest to just delete it. In contrast, the text of "Models" appears to be of some value, although I can't understand it. — Trying to remember the actual state of the history diagram, I think your remarks of 6+7 Aug on User_talk:RJGray#New History section are the latest. Or did I (forget and) miss something? If not, I'll implement your suggestions there (concerning pairing) in the next days. Best regards - Jochen Burghardt (talk) 15:37, 22 October 2017 (UTC)
- Concerning your history diagram, you haven't missed anything—my latest suggestion was about pairing. As for the category theory section, I'm reluctant to delete it since it does show an application of NBG's classes. Also, I don't like to remove work of others who in good faith added it because they found the information to be of value. Looking forward to your diagram, it will be a great addition to the History section, RJGray (talk) 00:39, 27 October 2017 (UTC)
Thanks for your feedback + need some advice
[edit]Hi Jochen, Thanks for all your excellent clarifies. As you've probably noticed, I've started working through them. I want to complement you on your excellence in English. I seldom make grammar errors in my writing, so I'm impressed when someone corrects me. Here's the sentence (subsection "The uses of classes"):
This is stronger than ZFC's axiom of choice that[clarify] states: For every set of nonempty sets, there exists a choice function defined on such that for all [clarify]
On your first clarify, you are correct "which" should be used rather than "that". In American English, "which" is used to introduce a non-restrictive clause and "that" is used to introduce a restrictive clause. The clause "states: For every set ..." is obviously non-restrictive since "ZFC's axiom of choice" completely identifies what is being talked about. In British English, "which" can also be used to introduce restrictive clauses. So I still made an error in British English since "that" is never used for non-restrictive clauses. So I should have used ", which states:". However, I then realized that this is not even needed—the colon is enough by itself.
On your second clarify, I was bothered by all the symbols running together, but figured the comma helped. Your solution is far better.
Concerning the "Class existence theorem" section: On the issue of when to have a proof come up hidden: There seem to be no rules on this. I tend to have them come up hidden if they are not central to the article or if they are central but long. The French seem to have them come up hidden all the time (at least in some articles). For example, in their article "Filter (mathematics)", all the proofs come up hidden, even a one-line proof!
As you can see, I've merged the two proof sections and have it come up hidden. Because the proof is so long, I find it more user-friendly to have it come up hidden. Sometimes, I just want to read a bit of the article and I find it annoying to have to page through a long proof that I've already read. I merged the two proof sections because the Expansion Lemma is really an essential part of the proof. Also, I find it annoying to have to "show" twice when I just wanted to read through the whole proof.
I changed from the "math proof" template to a wikitable because the "hide/show" wasn't working correctly when I shrunk the window—it would overwrite some of the title. The "math proof" template originally came from the French Wikipédia, but it's functionality is different for some reason (their Démonstration template correctly handles "hide/show").
Your problems with long math lines on a tablet: Since I don't have a tablet, I can't check things out. However, there are several possibilities. We could go back to my original: However, there would still be the problem of a long line in the proof, which your clarify mentions.
Another solution that may work (you can tell me how it works on your table): Abbreviate the list of class variables by , so a formula—such as —can be written as I've implemented this only for Case 2 so you can test it and tell me how it looks.
Concerning your clarify in subsection "Set axioms":
Definition. [clarify] is a function if
I plan to add the following section (it appears as a subsection on this Talk page) after the "Definition" section of Function (mathematics). I've included the notes and references that I'm adding. Then I'll add a link to this new section. I appreciate your feedback on this. I feel that the "Function (mathematics)" article should describe the definitions used in set theory so these definitions can be linked to.
Definitions used in set theory
[edit]Set theory provides three definitions of function depending on what has been specified: neither domain nor codomain, only the domain, or both the domain and codomain. The function, domain, and codomain can be sets or classes.[1]
- F is a function if F is a set or class of ordered pairs such that for all x, y, and z: If (x, y) ∈ F and (x, z) ∈ F, then y = z.
- F is a function on X if F is a function and X is the domain of F.
- F is a function from X to Y if F is a function, X is the domain of F, and F[X] ⊆ Y where F[X] is the image of F.
The first definition allows the use of functions without specifying their domain or codomain. For example, this definition is used to state the replacement axiom of von Neumann-Bernays-Gödel set theory: For all classes F and for all sets X, if F is a function, then F[X] is a set.
The second definition can be used to define a set or class of functions without specifying a codomain. For example, the class of functions on the ordinal α. Also, an infinite sequence can be defined as a function on ω, the set of finite ordinals.
The third definition, which specifies the function's domain and codomain, was discussed in the last section.
Notes
[edit]- ^ Gödel 1940, p. 16; Jech 2003, p. 11; Cunningham 2016, p. 57. Gödel gives definitions 1 and 2 (in definition 2, he uses "over X " instead of "on X " ). Jech gives all three definitions. Cunningham gives definitions 1 and 3.
References
[edit]- Cunningham, Daniel W. (2016). Set theory: A First Course. Cambridge University Press. ISBN 978-1107120327.
{{cite book}}
: Invalid|ref=harv
(help) - Gödel, Kurt (1940). The Consistency of the Continuum Hypothesis. Princeton University Press. ISBN 978-0691079271.
{{cite book}}
: Invalid|ref=harv
(help) - Jech, Thomas (2003). Set theory (Third Millennium ed.). Springer-Verlag. ISBN 3-540-44085-2.
{{cite book}}
: Invalid|ref=harv
(help)
I enjoy working with you on this article, RJGray (talk) 17:13, 26 October 2017 (UTC)
Clarify comments in "Classes and sets"
[edit]Hi Jochen,
Concerning Gödel's use of and : Gödel was writing in English. In his Fraktur usage, the only exception to not using English that I currently know (I haven't checked all his Fraktur usage) is his use of for "Menge". For example, he uses for "X is well-ordered by Y" instead of the German Maybe he used because he wanted some German in his article and this is the most important concept in set theory, or maybe he thought the Fraktur S, which would give , would be too confusing since it doesn't look like an S (or maybe it was a little of both). By the way, the word "Menge" seems to have first showed up on the first page of Cantor's 1879 article Ueber unendliche, lineare Punktmannichfaltigkeiten. 1.:
- "... wir nennen sie lineare Punktmannichfaltigkeiten oder kürzer lineare Punktmengen, ..."
The reason I use for Mendelson's defined set predicate is because this is what Mendelson used. Also, using Gödel's Fraktur predicate would be confusing since Gödel's predicate is a primitive predicate and not a defined predicate.
On the "more natural" clarify: I wrote it this way on purpose. I wanted "may appear more natural at first" in the text because not everyone reads the footnotes. Also, the footnote states "The historical development suggests that the two-sorted approach does appear more natural at first." I purposely changed "may appear more natural at first" to "does appear more natural at first". It's a subtle difference, especially with the "suggests" but I think it captures what the historical evidence points to. Also, I don't mind the possible repetition in a footnote.
I enjoy working through your clarifies. It makes me think more deeply on why I wrote things the way I did, and this time, it motivated me to look up the first occurrence of "Menge" in Cantor's articles. Probably, the only other articles it could have appeared earlier in are those of Dedekind and Riemann (I believe "Mannichfaltigkeit" came from Riemann). --RJGray (talk) 17:06, 27 October 2017 (UTC)
- Hi Robert, I uploaded a new version of the diagram to File:NBG Evolution.pdf and File:NBG Evolution svg.svg.
- I realized some of my clarifies didn't make sense; please apologize; I probably wasn't fully concentrated when writing them.
- About "that" vs. "which" I wasn't quite sure; thanks for your explanations. Btw.: I think I often use just the wrong preposition in a sentence (similar for other word categories), if you gave me corrections in some cases (just "use 'foo' instead of 'bar'" would suffice) I'd appreciate that very much.
- The "hide/show" overwriting the title you experienced was exactly the problem I had on my tablet; it appears to be solved by your change of template. I think looks nice; it avoids all line overflows (both on tablet and laptop). Since you don't need to access a particular component in the inductive step, it doesn't affect understandibility. In the Basis step, I think I'd prefer to keep it expanded as .
- As for the function definition and your extension "Definitions used in set theory" for function (mathematics), I think it is a good idea. As I said in my clarify, from the extension I learnt to distinguish the conventions about functions used set theory from those used in (say) calculus. Since you ask, I'd like to have an explicit footnote in addition (since I think many readers will unfamiliar with the set theoretic notion of function); but of course it is up to you to decide.
- Also thanks for your explanations on the Fraktur Cls and M. The origins of the word "Menge" appears noteworthy to me, it should probably go the the set (mathematics) article. Your remark on Gödel writing in English inspired me to read the personal-life details of his wikipedia biography more carefully. I hadn't fully realized before that he emigrated to Princeton soon after the 1938 Nazi occupation ("Anschluss") of Austria.
- You are right, a slight repetition in a footnote isn't really a problem.
- Best regards - Jochen Burghardt (talk) 19:46, 29 October 2017 (UTC)
Done with rewrite of NBG article
[edit]History diagram
[edit]Hi Jochen. I'm very impressed with your history diagram—it's an excellent visual summary of the history section. I've been carefully rereading the original articles to make sure your diagram for the history section accurately portrays the axiom systems. My suggestions are:
Zermelo set theory: I think it's more accurate to have "Elementary sets" instead of "Pairing (unordered)" because "Elementary sets" was the name of his axiom and it covers more than just Pairing (unordered) {See: Zermelo set theory}. I realized that I'm the one who first suggested replacing "Elementary sets" with "Pairing (unordered)", but I'm definitely having second thoughts about this.
To the left of Von Neumann 1925, 1928:
Replace: Limitation of size With: Limitation of size
(Implies Replacement) (Implies Replacement, Choice)
This is better since von Neumann points out that Limitation of size implies both Replacement and Choice. Also, this explains how he could remove both Replacement (stated by Fraenkel and Skolem) and Choice (from Zermelo set theory). At this historic point, all we need to know is that Limitation of size implies Choice. Of course, it implies the stronger von Neumann choice and Global choice, but that comes later in the history.
- Jochen's reply: I uploaded a new version at File:NBG Evolution svg.svg and File:NBG Evolution.pdf, the former being used at User:Jochen Burghardt/sandbox. For some strange reason, I needed to increase the width by 1 mm: although "Elementary sets" occupies less width than "Pairing (unordered)", TeX's paragraph layout algorithm uses an additional (third) line after replacing the longer by the shorter text; this is avoided by increasing the width. Also, I added an empty line in the "Fraenkel / Skolem 1922" box to align its height with that of its right neighbor, and to emphasize that some primitive (corresponding to "Sets") is missing. Another 1 mm width increase was needed to fit the "(implies Replacement, Choice)" into the left column.
- Bob's reply: The new version looks great! However, there is a small error. You replaced "Pairing (unordered)" by "Elementary sets" in the "Zermelo 1908" box, but on the left of the "von Neumann 1925, 1928" box, you remove "Pairing (unordered)" rather than "Elementary sets". Your diagram is an excellent addition to the History section and will greatly help readers who would otherwise get lost with all the changes that occurred in the evolution of NBG. The evolution of ZF → ZFC was far simpler: just the addition of replacement and regularity. I'm glad you suggested it and implemented it. So when do you want to put it in? Now or wait until I publish the article (then you get credit on the History page)?
- Jochen's reply: I fixed the remaining error, and tried it out on your page User:RJGray/Sandboxcantor1#History. - Jochen Burghardt (talk) 16:36, 19 November 2017 (UTC)
- Bob's reply: It's a great addition to the History section. Only one small suggestion: You label it "History of approaches that lead to NBG". Since we are talking about history, the present tense "lead" should be changed to the past tense "led". You may be getting them confused because the chemical element "lead" is pronounced "led". (Sometimes, I think that English pronunciation was designed to confuse people.) RJGray (talk) 21:43, 19 November 2017 (UTC)
Clarify comments
[edit]I've went through all the clarifies and I give my comments on most of them below. I skipped writing up the ones that are either simple changes or changes I've already explained. Going through your clarifies has really helped the article. Thanks for all your help. --RJGray (talk) 20:35, 15 November 2017 (UTC)
Axiom schema versus class existence theorem
[edit]Clarifies: I restructured and rewrote it to deal with your clarifies. Hopefully, now it's clear what I'm saying.
Class existence axioms and axiom of regularity
[edit]Clarify: Class existence axioms and axiom (Should be 'the axiom') of regularity
Reply: Two items to think about: (1) The idea of the title is to keep it short and "the" is commonly left out. For example, in "Definitions and axioms of extensionality and pairing" and in "Axiom of global choice". (2) Do we want to be consistent and either add "the" to all 3 titles or leave "the" out here? (I checked with my daughter who writes a lot: She says if it was in a sentence, the "the" is necessary, but in a title, it's not needed.) So I'm leaving it the same and leaving it for future readers to change if it bothers them.
- Jochen's reply: Ok, I see. Thanks for explaining this.
Clarify: Trying to open the following link in a new browser tab doesn't work on my laptop and my tablet. Maybe, you better use the ((efn)) pendant to ((ref name=Modifications))?}}
Reply: I now state that Bernays' axiom will simplify the proof of the class existence theorem. The forward link was a bad idea because it throws the reader into a later footnote giving a detailed discussion of the theorem's proof, which they haven't yet been prepared for. At this point, it's better just to say why Bernays' axiom is being used without going into details.
Clarify: Gödel's proofs of the first three statements of the tuple lemma are given. The proof of the fourth statement, which is Gödel's redundant axiom B6, is from Mendelson. I found this footnote difficult to understand. Maybe, it is sufficient if you just talk about the different axiom versions here, and postpone talking about of proof authorships?}}
Reply: You are right—it's confusing. I've rewrote it.
Clarify: Complement (negation). For any class , there is a class consisting precisely of the sets not belonging to . You might add a footnote here, saying something like: this is a kind of 'absolute' complement, while ZFC only admits relative complements.
Reply: Actually, all complements are relative, but I guess that's why you are saying this is a kind of 'absolute' complement. NBG supports complements relative to classes, while ZFC requires that complements be relative to sets. One problem in adding a footnote is that NBG and ZFC use different axioms to justify complements. NBG uses the complement axiom, while ZFC justifies relative complements through the axiom schema of separation. I really don't want to bring in separation here. The reason they use different axioms is that NBG needs the class complement to prove the class existence theorem. I did explore the possibility of adding a footnote saying that this is a feature that distinguishes NBG from ZFC and give the example that is a proper class for all sets , but to prove this requires the axiom of union, which doesn't appear until later. Since I've followed the French Wikipédia article in emphasizing and getting to the class existence theorem as soon as possible, I'm unable to write some footnotes, which isn't a bad thing since I already have 25 efn's.
Class existence theorem
[edit]Clarify: If you have published your proof version, you could cite it here, in order to prevent the accusation of WP:SYNTH.
Reply: I went back to an earlier (and more accurate) way of describing the proof, which comes from Gödel's proofs of M1, M3, and M4. I also point out the goal of getting to Gödel's M4. I find Mendelson a bit confusing because he never seems to state and prove Gödel's M4. Also, part of his proof seems to be in his exercises. So the proof in this article is really a modification of Gödel's proof that is more accessible to Wikipedia readers, which is similar to what I did with Cantor's original proof in Cantor's first set theory article. Of course, Cantor's proof was simpler to start with so my modifications were smaller. (One modification was: "We simplify Cantor's proof by using open intervals.") But in both cases, I have tried to remain true to the original proofs. In fact, I hope that readers will get interested in the original proofs and read them for themselves. My proofs will prepare them for the original proofs. The current article NBG set theory has a proof sketch that is quite different from Gödel's proof: see NBG set theory#Replacing Class Comprehension with finite instances thereof.
Clarify: It looks nicer if all examples are typeset similarly. I'm not sure whether to suggest to put all of them in boxes or none. Maybe, boxes should be used only to emphasize the main theorems of NBG theory?
Reply: Good idea! I've done it and it does look nicer.
Clarify: In order to reduce nesting of indices, you could use 'D_{i,k,n}' rather than 'E_{i,Y_k,n}'.
Reply: The Y_k is important because we will need to substitute a class for Y_k. For example, let Using the program Class, we get . If I call the program with , then can be thought of as an abbreviation of but never has anything substituted for it. Since only the position is important, I just use the By the way, is used because the membership axiom states that there exists a class . I suspect Gödel used because "epsilon" starts with E.
Clarify: Should be '\complement_{V^n}'.
Reply: Don't know what you mean here: \complement_{V^n} = , which already appears. What means is the complement of restricted to . An equivalent way to write it is:
- Jochen's reply: I think on the left-hand side, using (TeX source: "\complement_{V_n}") is a typo; shouldn't that be (TeX source:"\complement_{V^n}") instead?
- Bob's reply: Yes, it's a typo. I missed seeing it twice! Once, when I made it, and the second time, when you tried to correct it the first time. Things like this lead me to be patient when I find typos in published mathematical articles. Math has such a concise notation that typos like this tend to creep in. RJGray (talk) 17:12, 16 November 2017 (UTC)
- Bob's latest change: I just rewrote part of this section. I was bothered by the fact that it took applying both the transformation rules and the bound variable renaming rule to produce a "transformed formula". So I renamed the bound variable renaming rule—it's now rule #4 of the transformation rules. This unified my explanations and application of the transformation rules. I also state why the first 3 rules must be applied before the fourth rule. RJGray (talk) 16:11, 20 November 2017 (UTC)
- Bob's latest change #2: Another partial rewrite of the class existence theorem being a metatheorem. Tried to make the paragraph clearer. Also, I'm wondering if I should just remove this short paragraph. It's really not necessary. What's your opinion of this paragraph? Thanks, RJGray (talk) 00:13, 27 November 2017 (UTC)
- Jochen's reply: I found it elucidating to read that the CET is a metatheorem (rather than a consequence of the conjunction of all NBG axioms). Also, isn't this paragraph the introduction to your Pascal program? I'd suggest to keep the paragraph; I find it pretty understandable. - Jochen Burghardt (talk) 20:01, 28 November 2017 (UTC)
Extending the class existence theorem
[edit]Clarify: Suggest to append 'for transformed forms' [to class existence theorem], since the original theorem doesn't have an easy-to-recognize hypothesis.
Reply: I think that I may have confused you because I originally reduced it down to "transformed formulas". Now I just reduce it to formulas that quantify only over sets and have no free variables other than the ones specified, which is the hypothesis of the class existence theorem.
Clarify: The justifications could be added as another column in the previous 'alignat'. The subclauses of rule 2 could be named '2a' and '2b', to shorten references; e.g. just '& \mbox{ by 2b}' needed to be appended in the first line.
Reply: Excellent idea! I've added the column and named the subclasses.
- Bob's latest change: I just rewrote the parts of this section that deal with special classes. I reread Gödel's proof and he handles their definition similar to the way he handles operations. So I now give a more unified treatment by defining them by formulas that is similar to the way that operations are defined. This also simplifies and shortens the section a bit. RJGray (talk) 19:48, 22 November 2017 (UTC)
Set axioms
[edit]Clarify: From your explanation on the talk page I understood why left-totality isn't essential for the notion of function, while right-uniqueness is. To convey this idea, what about adding a footnote like: 'F may be partial on V; the above axiom of domain ensures the existence of a class D on which F is total'?
Reply: I've added the link function, which brings up the section containing the definitions of function used in set theory that I told you about. I added this section to "Function (mathematics)" and redirected "Function (set theory)" to it.
Clarify: If possible, I'd like to see additionally the short forms of the first three axioms, using the above introduced class operators; replacement: '\forall F [F \text{ is a function} \implies \forall a \exists b b=F[a]]', union: '\forall a \exists b \cup a \subseteq b', power: '\forall a \exists b \mathcal{P}(a) \subseteq b'.
Reply: Good idea! It reinforces the approach that is used to introduce the axioms. I'm using the short forms in the verbal description of the axioms. I prefer to keep the symbolic form the same since this is what appears in books, such as Gödel's.
Axiom of global choice
[edit]Clarify: This article is very general and doesn't define 'model'. What about linking to Structure (mathematical logic) instead? It also has a redirect Model (mathematical logic), which is a more appropriate link text.
Reply: I switched the link; thanks for giving me the redirect.
Von Neumann's 1925 axiom system
[edit]Clarify: "Fraenkel introduced an axiom to exclude these sets." If you have a reference, append it here, so the reader can evaluate von Neumann's judgement on Fraenkel's original paper.
Reply: It would be nice to do this, but your research indicates that Fraenkel's articles on this are all in German, which presents a problem in English Wikipedia. I'll look into some history of set theory books to see if anyone mentions Fraenkel's approach.
Gödel's axiom system (NBG)
[edit]Clarify: 'V_\alpha' in the following formula should be explained.
Reply: Added "where is the set of all sets having rank less than "
NBG, ZFC, and MK
[edit]Clarify: Replace by ', due to', in order to avoid the unintended reading as 'it cannot be proven in NBG using Gödel's second incompleteness theorem'.
Reply: Glad you caught this. I rewrote it: MK is a stronger theory than NBG because MK proves the consistency of NBG, while Gödel's second incompleteness theorem implies that the consistency of NBG is not provable in NBG.
Models
[edit]I remember your mentioning the first sentence of this section at some point. I now have them describable in terms of the hierarchies and not the universes, which is more accurate.
ZFC, NBG, and MK have models describable in terms of the cumulative hierarchy Vα and the constructible hierarchy Lα .
Thanks again for all your help on this article. It's probably the most complex article I've worked on. --RJGray (talk) 20:35, 15 November 2017 (UTC)
- Jochen's reply: I'm glad that I could contribute to the article, although I didn't have much knowledge in set theory beyond, say, Halmos' "Naive set theory" book. Many thanks for all your patient explanations; I have learned a lot new things during reading the article. I think you should publish it now. - Jochen Burghardt (talk) 22:01, 15 November 2017 (UTC)
- Bob's reply: I'm very impressed that you were able to contribute so much to this article starting with your background not much beyond Halmos' "Naive set theory" book. NBG is probably one of the most (if not the most) complex axiomatic set theories. You obviously have strong mathematical abilities. I'm happy to hear that you learned a lot of new things. Working on this article, I've also learned a lot. The reason I'm good at patient explanations is that I'm always challenging myself to learn more complex math. To do this, I had to become patient with my sometimes very slow understanding. Hence, I'm patient with others when helping them through math that is complex to them. I'm glad to see that you think I should publish now. I have some final checks that I always do before publishing an article. I used to publish quicker, but when I did this, I would spend days making changes on the published article. I'm planning on publishing it after our upcoming Thanksgiving weekend (the weekend after this). Thanks again for all your help, RJGray (talk) 18:00, 16 November 2017 (UTC)
Almost ready to publish!
[edit]Hi Jochen, Finally, I'm almost ready to publish the article. Two items I would like you to look over. The sections "Metatheorem" and "Rewrite of NBG article" that follow this section. "Metatheorem" is just my latest rewrite of the paragraph that follows the proof of the class existence theorem. The "Rewrite" section, I will be adding to NBG's Talk page. As for your diagram: you have the option of having it removed, having me publish the article, and then you adding the diagram. Thanks again for all your help and your patience—it does take me quite a while to publish an article—I'm a bit of a perfectionist. RJGray (talk) 17:24, 30 November 2017 (UTC)
- Hi Robert,
- I can't comment on the section "Rewrite of NBG article" since you wrote it very concisely for NBG set theory experts and for editors familiar with the page history; the single exception is the appraisal paragraph, for which I wish to thank you. - As for the diagram, I think the easiest way is that you keep it included in the article when moving. I intend to upload the diagram to commons, I'll appear as the uploader there. Anything except the diagram's layout is your work, anyway. - I'm looking forward to see your article at Von Neumann–Bernays–Gödel set theory. Best regards - Jochen Burghardt (talk) 14:08, 1 December 2017 (UTC)
Metatheorem
[edit]Gödel pointed out that the class existence theorem "is a metatheorem, that is, a theorem about the system [NBG], not in the system …"[1] It is a theorem about NBG because it is proved in the metatheory by induction on NBG formulas. Also, its proof—instead of invoking finitely many NBG axioms—inductively describes how to use NBG axioms to construct a class satisfying a given formula. For every formula, this description can be turned into a constructive existence proof that is in NBG. Therefore, this metatheorem can generate infinitely many NBG proofs.
- ^ Gödel 1940, p. 11.
- Jochen's comment: While I feel I know the difference between a metatheorem and a theorem "in the system", I find it difficult to explain in a few words. Probably, your paragraph is close to the best possible explanation; in particular, I think "induction on ... formulas" is a good characterization of the meta level. -
- As a minor point, I'd hestiate to say that a proof consists of axioms (this would make it easy to find proofs automatically, while it remains a hard problem after dozens of years of research). On the other hand, replacing your version by, say, "instead of using NBG axioms" would make the difference less clear, since "use" would appear in the characterization of an in-system theorem proof and a metatheorem proof. -
- Maybe, your (continuation of) example 2 (after your Pascal program) can be used to illustrate the difference by way of an example. What about "For example, applying the class existence [meta]theorem to the formula from example 2 yields a proof that (definition shown #here) is a class and that is a consequence of the NBG axioms" ? - Jochen Burghardt (talk) 13:44, 1 December 2017 (UTC)
- Bob's comment: It's nice to hear that you also find it difficult to explain in a few words—I've rewritten this paragraph about 10 times. I changed the 3rd sentence to read "instead of consisting of NBG axioms" to "instead of consisting of finitely many NBG axioms". This alone might be enough, but I decided to try one more sentence to distinguish the metatheorem from NBG theorems. Hopefully, this last sentence clarifies the situation more rather than confusing readers. RJGray (talk) 17:15, 1 December 2017 (UTC)
- Jochen's comment: The last sentence is fine, except that it uses "NBG class existence theorem" to denote theorems in the system, while at all other places "class existence theorem" denotes the meta theorem. I'm not sure that the reader will note that the "NBG" prefix makes the essential difference here. What about "this metatheorem generates infinitely many theorems in/within/inside/of the NBG system about the existence of classes."? This would avoid the pattern "class existence theorem", and make the connection to Gödel's phrase "in the system". - As another point, I just glanced at the target articles of your links metatheorem and metatheory, and found them very unspecific, probably written by non-logicians. Maybe Metamathematics is more specific about mathematical logic and its treatment of mathematical (object) theories. There is also an article object theory, but at least it's lead doesn't explain that term to be the opposite of metatheory. - Jochen Burghardt (talk) 21:35, 1 December 2017 (UTC)
- Bob's comment: It's great to get feedback on my latest rewrite of this paragraph. I agree that using "NBG class existence theorems" is a mistake. I've rewritten the last two sentences to emphasize the NBG proofs that the metatheorem generates. I'm trying to emphasize the differences between "in NBG" and what the metatheorem does. For example, I also state that the metatheorem's proof does not consist of finitely many axioms, and later I state that it generates infinitely many NBG proofs. As to Metamathematics vs. Metatheorem: The former is mostly about the large developments in metamathematics such as Frege's work, Gödel's incompleteness theorem, Tarski's definition of model-theoretic satisfaction, and the impossibility of the Entscheidungsproblem. This article does not deal with an isolated metatheorem, which is what we have here. The first paragraph in Metatheorem, which defines "metatheorem", seems accurate enough to me and is probably the best description of an isolated metatheorem that Wikipedia has right now. Of course, it could be written a bit better. For example, both the terms "formal system" and "object theory" are used, but it's not pointed out that they are equivalent terms (according to Object theory#Informal theory, object theory, and metatheory, these terms are equivalent). Also, this article is a bit short and has no citations. Perhaps one of us should consider rewriting it someday. --RJGray (talk) 20:11, 2 December 2017 (UTC)
- Jochen's comment: I agree. As for improving the Metatheorem article, I can do some improvements, but I lack sufficient sources and knowledge to achieve a profound rewriting. - Jochen Burghardt (talk) 19:55, 4 December 2017 (UTC)
- Bob's comment: We can work on it together. You can write something down, then I can go over it and make revisions, And we can go back and forth, revising each other's work. I can handle the sources after I see what is being written. --RJGray (talk) 01:46, 5 December 2017 (UTC)
Rewrite of NBG article
[edit]Four and a half years ago, in the last paragraph of #Two sorted theory, I wrote: "We are still left with the question of why this Wikipedia article is giving an exposition of NBG in two-sorted logic. As Carl points out, Mendelson's book, which is referenced by this article, treats NBG with a single sort. Personally, I would like to see an exposition that is closer to Gödel's and Mendelson's. I think it would be a more accurate representation of NBG and would be simpler for readers not familiar with many-sorted logic. Also, we can then remove Rp(A,a) ("set a represents class A"), which is only mentioned once in the Ontology section, and also remove the abuse of notation a=A, which means the same as Rp(A,a) and which is only used three times in the Axiomatizating NBG section."
Since a rewrite has not appeared, I decided to do one. Before I go into details, I would like to thank Jochen Burghardt for all his help on the rewrite. He read through a couple of editions of this rewrite and made many excellent suggestions (including the extension lemma used in the proof of the class existence theoem). He also pointed out some errors. His work not only led to a more accurate article, but also to a more readable, comprehensive, and visually appealing article. He also suggested and implemented the diagram on the History page that gives the history of the approaches that led to NBG. This diagram is a compact representation of the evolution of NBG.
My approach to writing the article was to not only look at Gödel's 1940 monograph and the original Wikipedia article, but also the French Wikipédia article (fr:Théorie des ensembles de von Neumann-Bernays-Gödel) and the German Wikipedia article (de:Neumann-Bernays-Gödel-Mengenlehre). Both the French and German articles use a single sort. The German article is short and follows Mendelson. The French one is much longer and references both Gödel and Mendelson. Also, it has a proof of what Mendelson calls the class existence theorem, which shows how to build classes for any given formula. The French proof is nearly complete as far as atomic formulas are concerned, but it just mentions the axioms used for the inductive part of the proof. I have given the details.
What I like best about the original Wikipedia article is that the editor(s) gave a proof of the very important class existence theorem. However, concerning the axiomatization, the article states: "The finite axiomatization presented below does not necessarily resemble exactly any NBG axiomatization in print."
I believe that it's best to follow Gödel's axiomatization and proof closely enough so that readers who get interested in the original proof will find that the proof in the Wikipedia article prepares them to read the original proof. I made three small modifications that simplify Gödel's proof for Wikipedia readers.
The first modification is a small change to one of Gödel's axioms. (I've converted Gödel's axiom to use the standard definition of n-tuples with new components on the right rather than his definition with new components on left):
In words: If is a class, there is a class whose ordered pairs have the property that their first component is a member of Gödel's axiom only specifies the ordered pairs of It may contain members that are not ordered pairs. So the first modification is to go back to the axiom of Bernays that Gödel modified:
In words: If is a class, then is also a class. Bernays' axiom is stronger because it specifies all the members of It allows the proof of the class existence theorem to produce unique classes at the end of the basis and inductive steps of the class existence theorem's proof. In a footnote, I explain the difference between the proof in the rewritten article and Gödel's proof, and I point out how his approach allows him to use his weaker axiom.
Using Bernays' axiom along with a second modification—proving the theorem immediately for class variables rather than for "symbols for special classes"—reduces Gödel's four-theorem approach to his theorem M4 (he proves theorems M1, M2, M3, and M4) down to proving two theorems.
The third modification concerns bound variables. In the case of the existential quantifier, I found Gödel's inductive proof somewhat hard to explain because he introduces a non-subscripted variable in the formula for the inductive hypothesis. This formula does not have the form expected by the induction hypothesis since the class existence theorem is stated for subscripted variables. To get formulas with subscripted variables, just replace the bound variables by subscripted variables that continue the numbering of the free set variables through the nested quantifiers. Since bound variables are free for part of the induction, this guarantees that, when they are free, they are treated the same as the original free variables.
These modifications lead to a short computer program that succinctly captures what is happening for readers who know some elementary programming. Output from this program illustrates how the construction of a class mirrors the construction of the formula defining the class. I included this output because the original article states: "An appealing but somewhat mysterious feature of NBG is that its axiom schema of Class Comprehension is equivalent to the conjunction of a finite number of its instances." So I'm attempting to lift some of this mystery; readers can tell me whether I succeeded.
The subsections Axiom schema versus class existence theorem and Classes and sets contain material borrowed from the French article. The History section comes from the original article (I added some material here and also Jochen's diagram has been added). The ZFC, NBG, and MK section contains material from the original article's Discussion section together with material from the French article (I also added to this material). The Models subsection comes from the original article's Model theory section with a couple of additions. The Category theory section comes from the original article's Category theory section with a little rewording.
I used Gödel's definition of the formulas used in the class existence theorem—namely, those formulas that quantify only over sets. I avoid the term "predicative" for two reasons: (1) Gödel's definition is simpler and (2) the formulas are not completely predicative but only predicative for proper classes, so the reference to Wikipedia's Impredicativity article is confusing. The Wikipedia reference says: "Roughly speaking, a definition is said to be impredicative if it invokes (mentions or quantifies over) the set being defined." When a formula that quantifies only over sets is used by class comprehension to produce a class that is a set, this set is impredicatively defined because the formula quantifies over all the sets including the set being defined. NBG has to allow this since ZFC allows impredicative definition of sets. So quantifying only over sets only means that proper classes are defined predicatively. By the way, the Impredicativity article states "There is no generally accepted precise definition of what it means to be predicative or impredicative: many different authors have given different but related definitions of what the words mean."
In the Models subsection, I use the term "model" rather than "intended model." For Peano arithmetic, an intended model exists, but it's hard to justify this term for models of set theory. When Zermelo and von Neumann wrote down their axioms, they intended that their axioms would characterize the universe of sets. Of course, their axiom systems only approximately characterize the universe of sets since, for example, they don't decide the continuum hypothesis.
In 1930, Zermelo was the first to build the models for strongly inaccessible (see Zermelo's models and the axiom of limitation of size). He didn't consider these models as "intended models" of set theory. Instead, he used this sequence of models to explain that the paradoxes "depend solely on confusing set theory itself … with individual models representing it. What appears as an 'ultrafinite non- or super-set' in one model is, in the succeeding model, a perfectly good, valid set with both a cardinal number and an ordinal type, and is itself a foundation stone for the construction of a new domain [model]."
I hope that readers will find the rewrite informative and interesting.
Some rewriting of Set axioms section
[edit]Hi Jochen, I'm hoping to publish the article on Monday or Tuesday. I've made a few changes to the section "Set axioms". I remembered that you had some trouble with the definition of function because the definition used in set theory is different from the one used in other parts of math. I figure that if you had trouble, others may also have trouble. I now state that the definition used in set theory does not require that a domain or codomain be given. I also point out that in the definition of "image" the set whose image is being taken is not required to be a subclass of the function's domain. Also, I realized that I did not prove that the union and power set of a set are themselves sets. So I added a proof of this. I now feel that the article is done. Thanks for all your help. --RJGray (talk) 19:19, 9 December 2017 (UTC)