11
$\begingroup$

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.

  • 0
    Computer scientists tend to think of sets this way.2012-06-11

5 Answers 5

1

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} True 

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.

22

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\}$.

10

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\}$

  • 0
    @VinkoVrsalovic This has been corrected2012-06-08
9

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.
  • 0
    Yes, you did. I misread the question. My error, I'd change my vote if I could now.2012-06-08
3

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\}\}$.

  • 0
    You're right I did misread the question. My mistake. You have$a$typo in your comment there.2012-06-08