Set vs Multi-set in specific examples

Question

I'm not a set theorist, but I feel like I've been taught all my life that I can write sets with repeating elements but those repeats are sort of degenerate and not counted as separate. So $\{a, b, a\} = \{a, b\}$. This always fit nicely with the fact that I could only check if two sets are equal by asking if they are subsets of one another. But a (computer science with math background) colleague of mine got into a long debate with me on whether I'm ever allowed to do this without referring to some multiset. For a moment I said, OK, maybe I've just not been careful. But now I'm seeing this issue pop up everywhere. Below is a recent example from notes I was writing for my students.

Can anyone help me with a reference to the fact that $\{a, b, a\} = \{a, b\}$ is definitely OK or not OK??

Example: For a group $G$ and an element $a \in G$, define $$\langle a \rangle := \{ a^n \in G \vert n \in \mathbb{Z} \}$$

Of course if the group is finite then for some $n \ne m$ we have $a^n = a^m$ and I feel like this is used a lot to describe this fairly reasonable set. In some sense it has repeating elements but if you take the approach above it's not an issue at all. What am I missing?

Answer 1

I believe the best reference would include the reason why duplicate elements are extraneous.

It's due to the Axiom of Extentionality.

From Kunen's, Set Theory: An Introduction to Independence Proofs

Axiom of Extentionality

$$\forall x\forall y[\forall z(z\in x\iff z\in y) \iff x=y]$$

In English, two sets are equal if and only if they have the same elements.

So, $\{a,b,c\}= \{a,a,b,b,c,c\}$ by the Axiom.

On page 12, you see the explicit example that $\{x,x\} = \{x\}$.

To see why this generalizes (from a different perspective)

Notice that by the Axiom of Extentionality,

$$\forall x(z\in x\Rightarrow x\cup\{z\} =x)$$

So, adding elements to a set, that are already in it- doesn't change the set.

Answer 2

Michael Carey has explained why, on classical set theory, $\{a,b,a\}= \{a,b\}$. It is due to the axiom of extensionnality.

Now, if you want, you can give a sense to the notion of "multiset" in classical set theory. Basically $\{a,b,a\}$ is the set $\{a,b\}$ where you count $a$ $2$ times and $b$ $1$ time. So we will say, by definition, that $\{a,b,a\}$ is a function $f : \{a,b\} \to \mathbb{N}$ such that $f(a)=2$ and $f(b)=1$.

More generally, starting from a set $S$, you can define all the multisets generated by $S$ as all the possible functions $f : S \to \mathbb{N}.$

Answer 3

let's call the classification proposed by CS colleague a two-fold way : there are sets, and there are multi-sets.

The most known classification that places sets and multi-sets in a larger context is the so called Twelve-fold Rota way : https://en.wikipedia.org/wiki/Twelvefold_way#Intuitive_meaning_of_the_chart_using_Balls_and_Boxes_scenario

There is also a Bogart twenty fold way https://en.wikipedia.org/wiki/Twelvefold_way#The_twentyfold_way

In introductory texbooks there is also a simple classification, a 4-fold way, that consider only lists and sets, with or without repetitions.

A 30-fold way of placing in context sets and multisets is here (extending Rota way) https://arxiv.org/ftp/math/papers/0606/0606404.pdf (this one can be completed to a 40-fold ways).

I would ask the C.S. collegue "how many empty sets do you consider in C.S. ?" given that in Combinatorics invoked here we have different empty boxes, any amount, for free, not defined by extensionality but by color, position or other qualities (intensionality).