47
$\begingroup$

Suppose I have two sets, $A$ and $B$:

$$A = \{1, 2, 3, 4, 5\} \\ B = \{1, 1, 2, 3, 4\}$$

Set $A$ is valid, but set $B$ isn't because not all of its elements are unique. My question is, why can't sets contain duplicate elements?

$\endgroup$
  • 60
    $\begingroup$ You're on a road trip with three friends, Eiko, Biko, and Shiko. You decide is so much fun that next year you want to go on a trip with Eiko, Eiko, Biko, and Shiko to change things up. Except you don't decide that, because the idea is absurd. $\endgroup$ – Malice Vidrine Sep 17 '14 at 3:17
  • 30
    $\begingroup$ The set B is perfectly valid; it's a set with four items. That's just an extremely strange way to write the set. $\endgroup$ – Eric Lippert Sep 17 '14 at 5:39
  • 9
    $\begingroup$ @Malice the road trip wads only fun because Eiko was so absurd we needed another one of him. $\endgroup$ – corsiKa Sep 17 '14 at 19:49
  • 4
    $\begingroup$ A set is defined to have only distinct abstract objects. You might be interested in multiset and this post: math.stackexchange.com/q/742105/103816 $\endgroup$ – user103816 Sep 19 '14 at 8:05
  • 1
    $\begingroup$ What if I decide to go with both Eiko and Eiko's twin, Eiko? $\endgroup$ – Goldname Dec 9 '16 at 2:01
70
$\begingroup$

The short, perhaps unsatisfying answer is, because that is how they are defined. The long answer is that, in most cases, that is what is useful.

For other cases, there is also a theory built around multisets, which are like sets except they allow multiplicity.

$\endgroup$
  • 2
    $\begingroup$ You can also construe a multiset as a function whose codomain is the natural numbers (telling you how many times the value appears in the multiset). $\endgroup$ – Steve Jessop Sep 17 '14 at 8:19
  • 2
    $\begingroup$ @SteveJessop is it useful to consider multisets which can contain more that finite copies of equal elements? $\endgroup$ – lisyarus Sep 17 '14 at 10:50
  • 2
    $\begingroup$ @lisyarus: I don't know, but good point. By all means use the ordinals instead (restricting to initial ordinals if your idea of "quantity" is any cardinal). You might at some point have to pick a fight with the Axiom of Choice or a weaker variant! $\endgroup$ – Steve Jessop Sep 17 '14 at 12:30
  • $\begingroup$ @Steve: Why would you need to "pick a fight"? A multiset can be seen as a set of constant functions, each of distinct range. The axiom of choice doesn't have to be involved. In either case, it's more natural to use cardinals here, not ordinals, since ordinal model order and cardinals model quantity. Multisets don't have an inherent order, just a notion of multitude of an element. $\endgroup$ – Asaf Karagila Sep 17 '14 at 21:02
  • 2
    $\begingroup$ @Asaf: Cool, thank you. If you want to collapse this conversation into a single comment from you along the lines of "@Steve: you don't need ordinals or the axiom of choice, you just define multiset-equality using the existence of bijections, not equality of the sets involved in the construction", then go right ahead and I'll delete everything back to where you came in :-) $\endgroup$ – Steve Jessop Sep 17 '14 at 21:18
63
$\begingroup$

I'd say that $B$ is valid and equal to $\{1, 2, 3, 4\}$.

The notation $B = \{1, 1, 2, 3, 4\}$ gives $B$ by listing its elements:

$1 \in B$

$1 \in B$

$2 \in B$

$3 \in B$

$4 \in B$

Clearly saying twice that $1 \in B$ is harmless.

This is the axiom of extensionality: two sets are equal iff they have the same elements.

$\endgroup$
  • 1
    $\begingroup$ -1 on this as it is not how a set is defined (See Clintons answer). If asked to show the members of a set then no member should be seen more than once! $\endgroup$ – Paddy3118 Sep 17 '14 at 15:56
  • $\begingroup$ Clinton's answer doesn't specify how sets are defined. I would interpret this one as offering something of a definition. Although this definition is incomplete (it fails to mention the requirement that B must be a subset of all sets containing the proper elements), it would seem sufficient to answer the particular question asked. Would you prefer another definition? $\endgroup$ – supercat Sep 17 '14 at 16:06
  • $\begingroup$ @Paddy3118: This is concept vs definition. Abstractly, lhf is right. Nominalistically, you are right. Now, come to my school of thought which dictates that we can redefine sets to mean a hippopotamus in a pink unitard. The only meaning anything has is the meaning we give to it. It logically follows that the definition of something in a situation must be useful and relevant to that situation instead of serving as a hindrance to the purpose for which that something was defined. $\endgroup$ – Nick Sep 17 '14 at 18:13
  • 21
    $\begingroup$ @Paddy3118 This answer is correct. Are you actually saying $\{0,1,1\}$ should be considered undefined, rather than simply equal to $\{0,1\}$? Undergraduate and graduate texts widely assert along the lines of $\{0,1,1\}=\{0,1\}$ to introduce or review the concept of extensionality. More important, often we have objects $x,y$ where we don't know if $x=y$, but wish to talk about a set that contains them. I suspect many proofs in published papers would be "wrong" if we prohibited listing the same element of a set more than once. $\forall a \forall b\,\{a\}\cup\{b\}=\{a,b\}$ would be a non-theorem! $\endgroup$ – Eliah Kagan Sep 17 '14 at 19:57
  • $\begingroup$ If the curly bracket notation shows the members of a set then it may be valid, but not useful to show a member of a set more than once. If the notation is of a function taking those items to produce a set then B would be OK, but his question is "why can't sets contain duplicate elements", for which the answer is clearly Clintons - because then it would not be a set - as commonly interpreted rather than some Humpty-Dumpty-esque private meaning of sets such as that from Nick in another comment on this answer. $\endgroup$ – Paddy3118 Sep 18 '14 at 5:43
15
$\begingroup$

Do not think of 1 and 1 as "two elements of the same value". They are the same element really. And an element is either a member of a set or it is not.

$\endgroup$
5
$\begingroup$

Informally, the "set" of members of your household should have a well defined size, and the number of nicknames a person has is unimportant to that set.

It's just agreed by convention that no matter how many labels for the same thing we try to include in a set, the set only contains the things themselves. You refer to 1 twice, but that's just repeating the name of the thing, and by definition, the set only contains the things themselves.

$\endgroup$
4
$\begingroup$

Short Answer:

The axioms of the Set Theory do not allow us to distinguish between two sets like $A = \{1,2\}$ and $B = \{1,1,2\}$. And every sentence valid about sets should be derived in some way from the axioms.

Explained:

The logic of the set theory is extensional, that means that doesn't matter the nature of a set, just its extension. The set $A = \{1,1,2,3,4\}$ could be considered different from $B = \{1,2,3,4\}$ in intension, but they are not different in extension, since $1 = 1$, both sets have the same elements. Even if one instance of the number $1$ precedes the other, the axioms of the set theory do not allow to distinguish between two sets using the order of its elements, because the notion of order is not defined by the axioms of the theory. To do that, the ordered pair is defined as follows: $$\left(a,b\right) \equiv \{\{a\},\{a,b\}\}$$ Thus $\left(a,b\right) \neq \left(b,a\right)$ since $\{\{a\},\{a,b\}\} \neq \{\{b\},\{b,a\}\}$. Thus, the set $A$ can't be distinguished fom B using its order. Moreover, the cardinality of two sets is never used to prove that two sets are different.

What about the ordered pair $\left(1,1\right) \equiv \{\{1\},\{1,1\}\} $? Since $1 = 1$ we have $\{1,1\} \equiv \{1\}$, this pair is a well known structure called singlenton, obtained as a consequence of the axiom of pairing and (as you can see) the axiom of extension. Moreover, since $\{1\}$ is present in $\left(1,1\right)$ two times, $\left(1,1\right) \equiv \{\{1\}\}$ another singlenton. Which is not a problem for the Analysis in $\mathbb{R}^2$, because this pair is different from $\{1\}$, a subset of $\mathbb{R}$, and different from each other pair in $\mathbb{R}^2$. The moral of this story is that you can't distinguish between the first and the second element of $\left(1,1\right)$, and it's ok.

Although the symbol "$\equiv$" is used to introduce syntactic abbreviations instead of semantic equality denoted by "$=$", this difference is just important in the study of Formal Languages, but not really important for this case, since the axiom of extension is what allows us to consider $\{1,1\} \equiv \{1\}$ as $\{1,1\} = \{1\}$. Just read the Section 3 of the book Naive Set Theory of Paul R. Halmos, what introduces the term singlenton in that way, and that's how is used by the specialized literature.

Other reference to understand the difference between intension and extension.

https://plato.stanford.edu/entries/logic-intensional/

$\endgroup$
3
$\begingroup$

To say $2$ sets are equal, show that each set is contained in the other. $\{1,1,2,3,4\} = \{1,2,3,4\}$ since any element on the left can be found on the right and vice-versa.

$\endgroup$
2
$\begingroup$

If we had a 'set' $U$ defined to be $\{1,2,3\}$, could we have another set $V = \{1,1,2,3\}$ where $U\neq V$?

Yes. We can do this, but using this notation makes it ambiguous and nasty.

We need to be careful about what we mean when we say $=$. Let's let $=_S$ denote an equivalence relation on sets, and $=_n$ be the usual equivalence relation of numbers.

It is perfectly consistent to talk about $U,V$, but if we write it down like this we've labeled everything using the weaker relation $=_n$, making it a big mess. I'll show you what I mean:

If $a,b$ are two distinct elements in $V$ where $a=_n 1$ and $b=_n 1$, then $a=_nb$. Furthermore, if we choose the $c \in U$ where $c=_n1$, then $a =_n b =_n c$.

We want $U\neq _S V$, so we must have that $\{a\} \neq_S \{b\}$. We have no idea whether or not $\{c\}=_S \{a\}$ or $\{b\}$. In fact, it might not even be equal (in the set sense) to either of them.

With this knowlege we can re-label the $1$s in our sets: $U=\{1_c, 2, 3\}$, and $V=\{1_a, 1_b, 2, 3\}$. But we still don't have any idea whether or not $1_c$ as a set element is the same as $1_a$ or $1_b$. The same can be said for $U$'s $2$ and $3$ vs $V$'s $2$ and $3$.

Under this notation we have no idea how $=_S$ works comparing elements across sets.


Here's a better way to do it. Instead of worrying about the set relation, define U and V using an index.

To start, clarify that every time you write down $a_i$, $i\in \mathbb{N}$, you are talking about the exact same object $a_i$, in every context. This forces the following property: $\{a_i\} =_S \{a_i\}$.

Now define $a_1 =_n 1\in \mathbb{N}; a_2 =_n 1 \in \mathbb{N}; a_3 =_n 2 \in \mathbb{N}; a_4 =_n 3 \in \mathbb{N}$, and let $U=\{a_1, a_2, a_3, a_4\}, V=\{a_2, a_3, a_4\}$

What we have really done now is make a function from the set $\{1,2,3,4\}\subset \mathbb{N}$ into the set $\{1,2,3\}\subset\mathbb{N}$, and defined $U, V$ in terms of that function. Under this description the $=_S$ relation is well-defined.

$\endgroup$
  • 1
    $\begingroup$ Your second example appears to be defining an ordered tuple of numbers, which do indeed allow duplicate elements, but now also respects order, which is generally considered undesirable in sets: $\{1,2\}\ne_S\{2,1\}$ because $\langle 1,2\rangle\ne\langle 2,1\rangle$. $\endgroup$ – Mario Carneiro Sep 23 '14 at 20:36
0
$\begingroup$

The problem here is one of equating the definition of a set with its representation. The fact that you can kind of represent a set on paper doesn't mean that that representation is the set. So, for example, I can talk about the set that only contains the number we call one, and I can make this concrete by writing it thus: $\{1\}$. If I then wrote $\{1, 2\}$ and said that this is the same set then you would correctly object; but if I wrote $\{1, 1\}$ and said that this was the same set then you should not object because that depiction satisfies the definition.

It's like having the definition of $\pi$ as the ratio of a circle's circumference to its diameter and then writing a number like 3.14159 and saying that the number is $\pi$ - $\pi$ is the definition and the number is what we write to represent $\pi$, and that representation can be imprecise or deficient.

$\endgroup$
0
$\begingroup$

I think there are many way to represent any multiset, using regular set. Doing so, can perhaps be overly descriptive and is not necessary. Also it would seem the notion of a set naturally precedes a multiset in that a set is "simpler" intuitively. Just the same I suppose you could precede sets with multisets but there probably is much use in describing sets in this way? Perhaps they are equivalent, neither one more capable if a set can represent multisets, which then represent sets and vice versa.

But in trying to be formal and rigorously axiomatize theories, sets are probably more efficient, by definition.

$\endgroup$

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.