Is there any book that explicitly contain the convention that a representation of the set that contain repeated element is the same as the one without repeated elements?

Like $\{1,1,2,3\} = \{1,2,3\}$.

I have looked over a few books and it didn't mention such thing. (Wikipedia has it, but it does not cite source).

In my years learning mathematics in both US and Hungary, this convention is known and applied. However recently I noticed some Chinese students claim they have never seen this before, and I don't remember I saw it in any book either.

I never found a book explicitly says what are the rules in how $\{a_1,a_2,a_3,\ldots,a_n\}$ specify a set. Some people believe it can only specify a set if $a_i\neq a_j \Leftrightarrow i\neq j$. The convention shows that doesn't have to be satisfied.

  • 6
    $\begingroup$ If $A=\{1,1,2,3\}$ and $B=\{1,2,3\}$, then $A\subset B$ (any element you take from $A$ is in $B$) and $B\subset A$ implies $A=B$. A good book that I could recommend for reading for related topics is Paul Halmos; Naive Set Theory. It starts building the axioms of set theory very nicely. $\endgroup$ – T. Eskin Jun 8 '12 at 6:50
  • $\begingroup$ Computer scientists tend to think of sets this way. $\endgroup$ – rotskoff Jun 11 '12 at 23:08

It all ties back into how this specification of sets are defined.

An unordered tuple $\{a_1,a_2,a_3,a_4\dots\}$ is defined as $\{x:x=a_1 \lor x=a_2 \lor x=a_3 \lor x=a_4 \lor\dots\}$.

So, by this convention, $\{1,1\}$ = $\{x:x=1 \lor x=1 \}$

This is equal to $\{ x : x = 1 \}$ by the idempotency of $\lor$, so

$\{1,1\} = \{1\}$

  • $\begingroup$ If there is any book that uses this definition of the specification, then I can accept this as an answer. Although I know it true in convention, but I want to see this explicit definition written down somewhere. $\endgroup$ – Chao Xu Jun 8 '12 at 6:42
  • $\begingroup$ @ChaoXu. Paul Halmos' "Naive Set Theory" covers the axiom of extensionality in section 1, on page 1. $\endgroup$ – in_mathematica_we_trust Jun 8 '12 at 6:50
  • 2
    $\begingroup$ @ChaoXu If you want to learn set theory also try $\textit{Introduction to Set Theory}$ by Hrbacek and Jech. $\endgroup$ – William Jun 8 '12 at 7:00
  • $\begingroup$ Shouldn't it be "an unordered tuple" instead of "an unordered pair"? $\endgroup$ – Vinko Vrsalovic Jun 8 '12 at 9:23
  • $\begingroup$ @VinkoVrsalovic This has been corrected $\endgroup$ – A.S Jun 8 '12 at 15:14

At least in ZFC, there is something called the axiom of extensionality which asserts that if $A$ and $B$ are sets with the same elements, then they are the same set, $A = B$.

In your example, both sets contains only three objects and exactly the same three objects $1, 2, 3$. Hence they are the same set so we may write $\{1,1,2,3\} = \{1, 2, 3\}$.

  • 4
    $\begingroup$ There is a certain viewpoint that to know what some type of thing is, you should ask what it means for two things of that type to be equal. This is a special case of that principle; it's the definition of equality of sets that makes order and repetition irrelevant in set builder notation. $\endgroup$ – Carl Mummert Jun 8 '12 at 11:15
  • $\begingroup$ @CarlMummert I don't think that principle quite works out in that way. I think that for type-2 fuzzy sets {1} and {1, 1} may not work out as equivalent, since the degree of membership of "1" here can come as a fuzzy number. The axiom of extensionality does fail there. $\endgroup$ – Doug Spoonwood Jun 8 '12 at 13:29
  • 3
    $\begingroup$ @Doug Spoonwood: the question then, according to the slogan, is how to tell whether two fuzzy sets are the identical (not equivalent, literally the same). Two ordinary sets are identical (to belabor the point, not just equivalent) if they have the same members, which is why $\{1,1\}$ and $\{1\}$ are identical sets, and why $\{1,2\}$ and $\{2,1\}$ are identical. $\endgroup$ – Carl Mummert Jun 8 '12 at 14:09
  • $\begingroup$ @CarlMummert You can't ever tell when two objects of any sort are literally the same, as no two things are ever literally 100% the same. Even the thought of "1" and "1" differ in space and time and probably other respects, and thus are not literally the same. {1, 1} and {1} come out the same for purposes of set theory. There exists another issue here in that saying {1, 1}={1} and (1+1)=2 don't necessarily use the same notion of equality in that the second equation can get interpreted as involving some sort of computation or evaluation, while the first just involves reasoning from a definition. $\endgroup$ – Doug Spoonwood Jun 8 '12 at 17:55
  • 5
    $\begingroup$ @Doug: Be wary of confusing notation with the thing being notated.... $\endgroup$ – Hurkyl Jul 21 '12 at 16:41

I took a quick look through some of the likelier candidates on my shelves. The following introductory discrete math texts all explicitly point out, with at least one example, that neither the order of listing nor the number of times an element is listed makes any difference to the identity of a set:

  • Winfried K. Grassman & Jean-Paul Tremblay, Logic and Discrete Mathematics: A Computer Science Perspective
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 4th ed.
  • Richard Johnsonbaugh, Discrete Mathematics, 4th ed.
  • Bernard Kolman, Robert C. Busby, & Sharon Ross, Discrete Mathematical Structures for Computer Science, 3rd ed.
  • Edward Scheinerman, Mathematics: A Discrete Introduction, 2nd ed.
  • 1
    $\begingroup$ @Doug: Presumably they make a point of saying it for the same reason that I did when I taught any course in which sets were introduced: because they’ve found that students often don’t pick up on it if it isn’t pointed out. In any case, I answered the question that was actually asked; others have already dealt adequately with the underlying reason for saying that $\{1,1,2,3\}=\{2,1,3,1\}$. $\endgroup$ – Brian M. Scott Jun 8 '12 at 20:09
  • $\begingroup$ Yes, you did. I misread the question. My error, I'd change my vote if I could now. $\endgroup$ – Doug Spoonwood Jun 8 '12 at 20:23

You asked

Is there any book that explicitly contain the convention that a representation of the set that contain repeated element is the same as the one without repeated elements?

Set Theory and the Continuum Problem by Smullyan and Fitting contains, on page 19:

For any sets $a$ and $b$ (whether the same or different) by $\{a,b\}$ we mean the class whose only elements are $a$ and $b$—or equivalently the class of all $x$ such that $x=a$ or $x=b$. … Note that if $a$ and $b$ happen to be the same, then $\{a,b\} = \{a\}$—stated otherwise, $\{a,a\}=\{a\}$.

Here is one of many examples that I found by searching in Google Books for set theory ordered pair. It appears on page 23 of Naive Set Theory by Paul Halmos. This well-known book says:

The ordered pair of a and b… is the set $(a, b)$ defined by: $$(a, b) = \{\{a\}, \{a,b\}\}.$$ … We note first that if $a$ and $b$ happen to be equal, then the ordered pair $(a, b)$ is the same as the singleton $\{\{a\}\}$.

  • $\begingroup$ @Doug: Because if $a=b$ then by the definition, $(a,b) = \{\{a\}, \{a,a\}\}$, and Halmos explicitly says that this set is "the same as" $\{\{a\}\}$; he has first eliminated the repeated element $a$ from the inner set, and then the repeated element $\{a\}$ from the outer set. I think that is an example of exactly what OP was asking for in the first paragraph of the question: "a representation of the set that contain repeated element is the same as the one without repeated elements". Do you think I should include this explicitly in my answer? $\endgroup$ – MJD Jun 8 '12 at 13:36
  • 2
    $\begingroup$ The question asked "Is there any book that explicitly contain the convention…I have looked over a few books and it didn't mention such thing." It does not ask for an explanation of how $\{a,a\}=a$. I'm sorry that you don't like the question, but I answered the question that was asked. $\endgroup$ – MJD Jun 8 '12 at 13:58
  • $\begingroup$ You're right I did misread the question. My mistake. You have a typo in your comment there. $\endgroup$ – Doug Spoonwood Jun 8 '12 at 17:41

For variety, I'll note that both magma and python have a set constructor using a comma-separated list surrounded by curly braces, and they both allow repeated entries. For example, in python:

>>> {1,1,2,3}
{1, 2, 3}
>>> {3,2,1} == {1,1,2,3}

Mathematica, on the other hand, uses curly braces to construct lists rather than sets, so it would behave differently. Array initializers in C also use curly braces -- but again you're creating lists, not sets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.