Talk:Set-builder notation
This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
An error
edit" Φ(x) is a formula in predicate logic where the variable x is universally quantified" is wrong - x is free. In this { x : Φ ( x ) } the x is bound, but still not by a universal quantifier. 31.52.255.37 (talk) 15:50, 1 July 2016 (UTC)
- This was not the only error. I have edited the section, and hope that the result is both more formally correct and easier to understand. D.Lazard (talk) 16:56, 1 July 2016 (UTC)
- Unfortunately, one of those edits in the "Formal Set Builder Notation Section" introduces the convention of placing set quantification on the left hand side of the delimiter shortly after the definition is given for the notation explaining that only a variable appears on the left hand side of the delimiter, and shortly before an example of set membership as a proposition being being evaluated - thus leading to two examples, one unexplained, that contradict. However, a little down the page, the same example is shown after the convention is explained. For this reason, I have placed the quantifier to the right of the delimiter, where it was before, which is not an error, for the substantial reason of being consistent with the explanation in that section and the example that follows it. As noted, the other example already appears after the convention is explained. I am also a little confused as to why the editor removed the forward reference to the left hand quantifiers section after the issue was raised, stating only he found errors. My gosh, there was no error in a forward reference. 114.24.25.24 (talk) 23:40, 23 July 2016 (UTC)
Progression in sophistication of notation
editJust a note, some the most recent edits (2016) have changed the progression of the page. The short hand of using domain qualifiers on the left of the delimiter has a section, but now the technique is shown before it is introduced/explained. Russell's paradox has a section, and mention of domain qualification, but similarly the technique is shown before introduced, though this time with a parallel redundant explanation. It is as though the editor didn't read the entire article before making edits. Maybe short hand usage and the Russell's paradox explanation should have links to the relevant sections, .. or would better to be deferred to the sections that are already dedicated to those subjects. 114.24.25.24 (talk) 10:04, 22 July 2016 (UTC)
The notation has been defined at the top of the set builder notation section to have an expression on the left, and a predicate on the right. Further down the section a set inclusion statement is used as a predicate on the left with no explanation. Later in the article there is an explanation given that it is a simply a common convention. It would be less confusing should this convention be used first in the section that is dedicated to its explanation. There certainly is no error in giving the domain quantification as part of the predicate - that edit is not correcting an error, but introducing an inconsistency in the explanation. 114.24.25.24 (talk) 23:08, 23 July 2016 (UTC)
- Putting the domain quantifiers on the left is not "shorthand", and no set theory book I have ever seen would treat as meaning the set . Indeed, in standard set theory the only things that can be elements of sets are sets, not truth values, and there is no set </math>\{true, false\}</math>. Perhaps that is what would happen in a programming language, but set-builder notation is primarily about set theory, not programming. I also note the entire lack of sourcing that set builder notation is ever used that way, and I suspect it is original research to claim that it is used in that way. — Carl (CBM · talk) 23:54, 23 July 2016 (UTC)
- Carl, It is a little difficult to speak for the number of people who had inputs into this article for some years now, but let me share my understanding.
- This is a page on "Set Builder Notation." Set theory has other pages. Often set theory books do not provide a formalism for well formed formulas of a general set builder notation. If you have such a reference, please add it.
- You misconstrue the language being used in the article. The article shows the construction of a set builder notation. It starts with the definition of a triple in braces, and the roles of the members of the triple. Note the word "formal" in the section heading. This was entered at the very start of the article and reviewed by many people over some period of years. It then shows well formed statements according to that definition. No one is saying you can't add domain qualifications -- that is further down in the article. But such statements are not well formed by the definition given in that section. The same goes for expressions.
- Indeed the next section of the article expands the definition by allowing that the variable of the prior section can be an expression. This expanded grammar is unambiguous because the trivial case of an expression is a variable. --No, this explanation is not original synthesis - rather it is given here to explain why the current article layout is consistent and the explanation was clear-- Then in the third section the domain qualifiers are discussed. If only the prior material were under consideration at this point, then the left hand side would be interpreted as an expression should the set builder statements be taken as well formed. Indeed there are mathematical contexts where set inclusion is an operator in expressions. Your books may not have included such contexts, but they do exist. However minor this ambiguity may be in one's opinion, it does exist, and it affects how the grammar can be parsed. To over come this ambiguity requires a convention. This is where I think you are misconstruing the usage of that term and giving it broader connotation than intended. Then by invoking this convention we can define well formed statements in set builder notation that have domain qualifiers and/or expressions on the left of the delimiter. It then makes sense to a reader who scans down the page to see examples that use this.
- If you want to build a set builder notation where the domain qualifications are part of of the original definition, unlike the definition the original authors chose here, then you would change that definition in the section "Formal ... " section which now says the thing on the left of the delimiter is a variable, and say it is a variable or a qualified variable. Hopefully you would then continue the rest of the article in a consistent manner from that somewhat differing choice of set builder notation. You would be changing what a number of editors have put in this article, and I think you would run into some difficulties creating a consistent and correct presentation, but by all means have at it.
- I really don't care which presentation of set builder notation is given, but I do think whatever choice it should be consistent, and it should be possible to those unfamiliar with Set Builder Notation to be able to scan down the page and read the article. It makes absolutely no sense to give examples that have not been explained, even even going so far to delete others edits that give forward references to material that explain them. And then editing those sections when you can't get rid of the reference.
- A final point, using a notation for years, reading the notation in books and papers, does not mean one knows how formally construct it in the general case. I think if you look at the article as it was, you will see that the former editors did a very nice job of it. It certainly appears that way to me.
- 114.24.25.24 (talk) 07:05, 24 July 2016 (UTC)
- Come to think of it, all three descriptions are correct they are not exclusive. Placing the domain qualifier on the left is a short cut, because { x ∈ R | ...} is defined as { x | x ∈ R and ...} i.e. it is a short cut to adding domain qualifiers to the predicate. It is also a convention as described above, and it is standard .. it is standard shortcut convention.
- 114.24.25.24 (talk) 07:05, 24 July 2016 (UTC)
- I pointed out on this talk page in 2014 that (1) the idea that on the left of the vertical bar is ever viewed as a true/false valued function, rather than a domain qualifier, disagrees with numerous set theory texts that I checked at the time, and (2) I know of no set theory text in which would be the set rather than the interval .
- It seems that me that the "former" editors wrote something about what they wished set builder notation could be. But that is not what it actually is in the literature, and that is what Wikipedia articles are meant to reflect. If no set theory books provide a formalism for set builder notation, then we can't do that either - we need to stick to things that we can source. I am OK with simple examples that are in agreement with the literature, even without sources, but the examples I removed are not in agreement with the literature.
- Please find a scholarly source that gives an example in which , or similar, and then we will be able to see what source it actually is. In the meantime, I do believe the article is readable from top to bottom, since the topic of domain quantification is still in its own section. What I removed was just the claim that this is a "shortcut" and the examples that give sets of truth values. — Carl (CBM · talk) 13:16, 24 July 2016 (UTC)
- I agree with CBM. I would add some comments:
- This article, at least its first halve, is not intended for specialists of mathematical logic, but for casual readers who may have encountered the notation in a textbook or an article. This implies that we must emphasize on the most common notation rather than on a notation that is perfectly correct in some logic theory (and may be incorrect in others), and we must avoid technicalities as long as it is possible. This implies that we must prefer to In fact, the latter is more complicated and requires to know what means which is certainly not the case of many readers. Therefore, I am quite sure that most elementary textbooks use the former formula rather than the latter. IMO, formulas containing must be avoided as long as possible.
- The IP user seems consider that is more correct and less sophisticated than As shown above, the former is certainly more sophisticated. It is also less correct, at least in logical theories, which are presently used for formal and computer proofs. In fact, these theories are typed. In such a theory is not a well-formed formula, as is not typed. On the other hand, in the left-hand part of the formula defines the type of
- The heading of § Formal set builder notation as well as a large part of its content suggest that this section is about formal logic. This is much too technical for the second section of the article. I suggest to rename it "Sets defined by a property" and to rewrite it in a less technical style, including my above comments. On the other hand, § Expressions to the left of 'such that' rather than a variable is about shortcuts, which ware considered as abuses of notation by many mathematicians, and are avoided by many authors. Therefore, this section must be moved toward the bottom of the article, with a caveat that the content is often considered as an abuse of notation.
- D.Lazard (talk) 15:50, 24 July 2016 (UTC)
- I agree with CBM. I would add some comments:
- The issue with limiting the domain also comes up in untyped ZFC set theory. Although I doubt there is a source that comes out and says it, the form is more directly applicable to the comprehension axiom in set theory, which says that
- In the usual set-builder notation, the specifier on the left side of the bar gives the set A which is to be substituted for X, and the specifier on the right gives the formula φ, which together allow the axiom of comprehension to be applied. — Carl (CBM · talk) 16:00, 24 July 2016 (UTC)
- The issue with limiting the domain also comes up in untyped ZFC set theory. Although I doubt there is a source that comes out and says it, the form is more directly applicable to the comprehension axiom in set theory, which says that
- Good point: it should be said, somewhere in the article, something like
For any set and any well-formed formula , depending on a free variable , the elements of such that is true form a set, usually denoted . This property, although seeming evident, is independent of the other axioms of set theory, and is called the axiom of comprehension.
— D.Lazard (talk) 22:07, 24 July 2016 (UTC)
- Good point: it should be said, somewhere in the article, something like
- Set membership operators do occur in expressions. I work in discrete domains, where the domains seldom need to be specified as they are understood from context, but set inclusion can be an operator in expressions. To create a simple example, introduce a ternary operator, Q?a|b, which is a if Q is true, otherwise b. Then { x∈Z?1:0 | x∈T } where T is a set of numbers gotten from a proposed algorithm that generates Pythagorean triples, and x is used in another function. This would be a reasonable set to define, and to ask questions about. Richer examples exist of course. Discrete domain questions are becoming more common even in school curriculum. Yet, if you have your way with this article, such simple set definitions would be nonsense. I noticed that someone deleted the set operator in an expression example from the article. What a strange way to make a point. Just delete the counter example from the text. Would it not make sense to add a couple more examples back to that section. Perhaps some with a little more sophistication. Though none of the examples in this article are very sophisticated.
- Also, the set qualifiers are part of the generating predicate independent of where you state them. We know this because we have to put them in before doing proofs or we might get the wrong answers. It would be unfortunate to write an article about the builder notation and not explain that.
- How old is the term "Set Builder Notation"? Carl you mentioned having a reference to a grammar for a general set builder notation, and that it had bearing on edits to this article. Can you post that?
- ... Carl, about your comment of school kids not understanding 'and' .. ah, by the time you introduce sets, the vertical bar, and the concept of predicate rule generators, 'and' has already been repeated many times. But what would mess up a school kid would be to not give him a sufficient explanation before asking him to go do some elementary proofs.
- Carl, about our comment and truth values and sets, truth values absolutely can be placed in sets. Any mathematical object can go in a set. Where on earth did you get an idea like that? In addition, just above I give another example where the item placed in a set is an integer, though set membership appears as an operator in the expression. So as you removed that example based on the false impression that truth values can not go in sets, please put the example back.
- 114.24.25.24 (talk) 01:42, 25 July 2016 (UTC)
- Carl, hmm, unless you come up with a surprising reference showing that truth values are exceptional mathematical objects not fit for sethood, or for that matter, can not even be used in expression while describing sets as shown above with the tertiary operator, it is only appropriate to put back the material you deleted due to this misconception. Specifically the examples in the expression section making use of a set membership proposition, and the discussion about the ambiguity between set membership qualification and set membership as a proposition when appearing on the left hand side of the delimiter.
- 114.24.25.24 (talk) —Preceding undated comment added 04:38, 25 July 2016 (UTC)
- I think you may be conflating my comments and comments by D.Lazard. There are too many different topics in the previous post to respond. Of all the points, which one would you view as the most pressing for the article? That may help focus discussion. — Carl (CBM · talk) 12:38, 25 July 2016 (UTC)
D.Lazard, I have made an attempt to implement your suggestion, which I agree with, to be more explicit about the domain limitation, and to try to avoid some logical syntax. There is more improvement that could still be made, but I need to put it aside for a little while. Please feel free to go through my edits and improve them. — Carl (CBM · talk) 13:26, 25 July 2016 (UTC)
- CBM, D.Lazard did suggest perhaps removing the word 'formal' from the definition section, but your implementation doesn't flow through the rest of the article. Because the description of how set builder notation is built up has been removed, it now becomes awkward to explain how to do even the simplest of proofs. This can be seen in the first paragraph of the set equivalence section, which is now a place holder for the deleted material - one that has the burden of explaining it in reverse, and is awkward as it stands.
- The energy directed to these recent edits appears to have some unstated goal. In examining the talk pages and the edits, it seems this goal is less than mathematical. The edits appear to be driven by a dislike of domain annotation on the left of the delimiter being called a "convention" (as though notation convention can not be standard), a dislike of the statement that domain annotations must be moved to the predicate before poofs are done (all such references have been deleted), and a dislike of the concept of truth values being used in expressions or placed in sets - and thus that untidy ambiguity due to set inclusion as an operator in an expression (CBM states this misconception on these talk pages).
- CBM offered earlier some references to support such dislikes, but none have been produced. As I recall this session started with the hysterical screams of "errors", though one error was pointed out and the fix was valuable, many more errors have been added during the course of these edits, with some now rationalized by dropping the word "formal" from the definition section.
- Due to the lack of new references, the edits based on the incorrect notion of truth values not being allowed in sets, and the unjustified 'dislikes' that have motivated these edits, I suggest that the yesterdays edits be backed out so that the discussion will again flow smoothly and logically, without the reliance on misconceptions. We will keep the other edits. Are there any justified disagreements to this? I.e. can we see the new references, have a different argument than truth values can not be placed in sets, or a reason for deleting references to the fact that domains need to be part of predicates as parts of proofs?
- After that with respect to the goal of showing more examples employing the domain annotations sooner, if that is indeed the goal here, the convention section can be moved up, with examples shifted to it, or duplicated from the prior section. Any discussion of ambiguity in operators would then be in the expressions section.220.137.193.123 (talk) 00:07, 26 July 2016 (UTC)
- I don't support "backing out" the edits. The article has had the same problems since at least 2014, and I think that the recent edits have been improving it steadily; the previous version made various claims that seem to be out of agreement with how set builder notation is actually used in mathematics and in set theory texts.
- Regarding proofs: there is no set builder notation in most formal set theories (actually, I don't know of any well known formal set theory that does involve set builder notation - in the usual formal language of set theory the only terms are variables). To work with formal proofs, set builder notation is eliminated entirely, so there is no issue of which side the domain annotation is on. So the claims about proofs are somewhat confusing. — Carl (CBM · talk) 00:22, 26 July 2016 (UTC)
- Regarding truth values in sets: in informal set theory, it is fine to make the set and this example is in the article. But that set is not made via set builder notation such as . Rather, that notation defines the set of integers, and that is the sense in which the previous version of the article differed from ordinary practice. I have seen no set theory book which suggests that would be a set of truth values. This is related to the fact that, in first-order logic, there is a significant difference between a term such as 2n and a predicate such as . — Carl (CBM · talk) 00:30, 26 July 2016 (UTC)
- Yes I added the example of a set of truth values after you stated that truth values could not be in a set.
- Is it not the case that the only reason a set membership proposition is not part of your concept of set builder notation, is that you have arbitrarily chosen not to allow this. Is it not that case that you do this because you feel it fits what you are accustom to seeing in texts and your work, rather than due to any proof or any reference that you hold. The only justification you offer is "I have never seen this". (But actually you have seen it, I show a ternary operator case above.) Is it not the case that this is an unnecessary constraint? As one follows the constructs that were in the article before, of definition, augmentation with expression, and then introduction of convention, then the constraint is unnecessary. Is it not the case that your recent edits are driven out of dislike for the name "convention" for what you feel is "standard" and that somehow you see those as exclusive concepts?
- Regarding Proofs: quite the contrary, Set Builder Notation is often the precursor to writing a proofs. You can see that in the references provided in the article, you can see that on this very wikipage in the examples of discussing set equivalence, and the discussion of Russel's paradox-provided you don't delete those next, and if you come over to our shop, we can show you more cases. The whole idea of formalizing the rule builder predicate is so it can be used in proofs. Is it not also in your experience that a common error in proofs is the very fact that people do not pay attention to the domains that need to be included in the predicates? -- the very thing you have done here by deleting text noting that the the domains need to be included in the predicates?
- Of course you don't support backing out the last night's edits, as they are yours. But there is a problem with them. This manifests in the section on set equivalence, where it must now be an explanation of why the set builder predicate is not complete, and how to complete it. This explanation and even the concept of an incomplete or partial rule generating predicate was not needed before last nights edits, because the domain qualifiers were explained as a notational equivalence of the conjunction of those same terms on to the predicate, but you have taken that explanation out. Also missing now are any explanation of set membership as a proposition in an expression, and how that would related to domain qualification. Oh, right, you have never seen that before, so .. it doesn't matter?
- If not backing out the edits, how would you propose fixing these things?220.137.193.123 (talk) 01:38, 26 July 2016 (UTC)
- I do not see which specific point you want fixing. However, in case of disagreement between editors, the rule in Wikipedia is trying to reach a WP:consensus. As there are presently two editors who disagree with you, the consensus is certainly not in your favor and, thus, there will things to be fixed only when (or if) several editors will agree with you.
- By the way, WP:Wikipedia is not a textbook, and your concern seems that you want to write this article in a textbook style. In any case, the edit you did yesterday support this point of view: you want to explain how to make proofs on sets defined through set builder notation. Your explanations could be useful for some users, but are certainly confusing for many. Thus, I'll revert it and edit the previous version for clarification. D.Lazard (talk) 08:20, 26 July 2016 (UTC)
- If not backing out the edits, how would you propose fixing these things?220.137.193.123 (talk) 01:38, 26 July 2016 (UTC)
- For what it's worth, I left a message at the math wikiproject yesterday to see if more people are interested in looking at this page. — Carl (CBM · talk) 10:47, 26 July 2016 (UTC)
- We certainly welcome more input, and think that would be helpful.
- Our current understanding is that CBM arrived at this page, hand in hand with D.Lazard with the purpose of removing all reference of the set annotation as a convention, as the article called it, a shorthand convention, for conjucting domain qualifiers on to the rule predicate, and has been trying to do so since 2014. Despite lack of consensus, and lack of rationalization, edits were made to delete all references to moving set domain annotation to the predicate before doing proofs, thus orphaning the first section that discusses proofs, the one on equivalence.
- CBM justified his edits based on having references, which CBM did not site, and quizzically upon misconceptions, for example CBM flatly stated that truth values could not be placed in sets. Though he later backed off that assertion, but not completely, the material he deleted on that basis is still missing. CBM also deleted material while asserting that set builder notation was not a precursor to performing proofs, and has thus deleted all reference to moving set annotation to the rule predicate before performing proofs. It remains a mystery to us as to why he is against explaining this.
- Due to making edits based on misconceptions, even misconceptions backed off from, and certainly not obtaining consensus first, we feel his edits are Vandalism of this article, and thus we request that CBM stop making edits while the deleted material is put back into the article.
- We, and the former editors, are not against describing set annotation on the left of the delimiter that separates the variables from the predicate list -- obviously as there was a section dedicated to exactly that topic in the former article. We would have been happy to move that material up, or to have added more examples. There was no reason to delete the other material, to leave the equivalence discussion orphaned, or to reduce the accuracy and richness of the article. Hence our main concern is one of needless and misleading omissions rather than the additions.
- 220.137.193.123 (talk) 02:41, 27 July 2016 (UTC)
- I did edit the article to remove various claims which were out of line with the usage of set-builder notation in the literature, such as the claim that putting the domain qualifier on the left is somehow inferior to putting it on the right, or the claim that such notation is ambiguous. The purpose of editing the article was to bring it back in line with the literature in various ways. I had pointed out these things years ago on the talk page, but the issue had remained for some time. Eventually, it needed to be fixed.
- The article does discuss the fact that the domain qualifier needs to be considered when proving sets are equal. That does not mean the the domain qualifier needs to be moved "to the right", however, as there are many ways of doing a proof (and, indeed, formal proofs in set theory will not include set builder notation anyway, because this notation is not part of the formal language of set theory.) — Carl (CBM · talk) 10:30, 27 July 2016 (UTC)
Proper bindings yielding issue-free set builder notation
editMost of the aforementioned problems are due to the fact that two basic forms are used for set builder notation (or set comprehension), namely and , where is a logical (Boolean-valued) expression and is any expression. The expression matches both forms, with different meaning. This ambiguity is also mentioned by Leslie Lamport in Specifying Systems, page 289.
These problems can be avoided by maintaining proper distinction between a statement of the form , read " is in " and a binding of the form , read " in ". This is similar to the distinction between use and mention. It is unfortunate that LaTeX uses \in, actually meaning \isin. The basic forms then become and , similar to Z and the notation in Meyer's Introduction to the Theory of Programming Languages. The distinction between (which equals ) and (a set of Boolean values) is then clear. Boute (talk) 09:55, 17 July 2017 (UTC)
Move programming language details and comparison into List comprehension
editCurrently, Set-builder notation#In programming languages includes several details about specific programming languages, including a syntax comparison table, which are not included in the linked List comprehension main article. These details are more closely related to the latter article, whereas Set-builder notation is about the math notation. I suggest moving the detailed info and integrating into List comprehension, and leaving Set-builder notation#In programming languages as just a summary with a few concise examples. 2620:15C:161:107:9977:4897:47AD:5467 (talk) 18:56, 28 December 2023 (UTC)
- It would be great if there exists a "Set comprehension (disambiguation)" page pointing to two distinct pages:
- "Set comprehension (Set theory)", possibly redirecting to "Set-builder notation" which would describe the math notation only;
- "Set comprehension (Programming languages)" which would describe programming languages' aspects.
- Thus the other page, "List comprehension", can be enriched with mutual links to "Set comprehension (Programming languages)" and "Dictionary comprehension", which in turn have much more to describe.
- Andrei Polushin (talk) 09:50, 1 February 2024 (UTC)
- Agreed! There is in fact such an article, called Comparison of programming languages (list comprehension) that already covers this material (though not in tabular form, so this entire section could be removed and a see also link provided at the tail end of the article. Johnnie Bob (talk) 17:31, 10 February 2024 (UTC)
Sets defined by enumeration are not part of set builder notation
editThat is, a set defined entirely by enumerating its members cannot be considered to be expressed using set builder notation. In fact, these two methods for defining sets are mutually exclusive. For example, Rosen[1] (p. 116) states,
There are several ways to describe a set. One way is to list all the members of a set, when this is possible. We use a notation where all members of the set are listed between braces.
He then lists several examples of sets defined using this method, which he calls the roster method and other sources refer to as enumeration, and then states,
Another way to describe a set is to use set builder notation. We characterize all those elements in the set by stating the property or properties they must have to be members.
The article as currently written clearly contradicts this by stating
...set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy...
and then goes into a long discussion of defining sets by enumeration as though this were somehow part of set builder notation.
I propose removing the entire section entitled 'Sets defined by enumeration' and then deleting the heading 'Sets defined by predicate' (but not the text of that section, the text should just continue as paragraphs under the lead paragraph of the article).
Your comments are appreciated.
- ^ Rosen, Kenneth H. (2012). Discrete Mathematics and its Applications (7th ed.). New York, NY: McGraw-Hill. ISBN 978-0-07-338309-5.
Johnnie Bob (talk) 17:23, 10 February 2024 (UTC)
- I agree that the specifications of a set by comprehension and by extension are mutually exclusive. But the set builder notation is a notation commonly used for both sorts of specifications, and, for many sources the use of braces for specifications by extension is a part of set builder notation. I agree that it is possible to consider that Roster notation is not a special case of set builder notation, but, as for most conventions, this is an arbitrary choice. Apparently, the most common convention is to include Roster notation into set builder-notation. So, for removing a large part of the article, you must provide a stronger evidence.
- In any case, this article is about "set notation", and Set notation redirects here. So, I would not oppose to rename this article as Set notation with Set-builder notation redirecting to it. D.Lazard (talk) 18:54, 10 February 2024 (UTC)