4
$\begingroup$

A set is

... is a well-defined collection of distinct objects, considered as an object in its own right. For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2,4,6} (from Wikipedia).

This means that $\{1, 1, 1, 1, 1, 1, ..., 2, 2, 2, 2, 2, 2, ..., 3, 3, 3, 3, 3, 3, ..., ...\}$ is the set $\{1, 2, 3, ...\}$, by definition. But, without the axiom of choice, how can we differentiate between the two?

$\endgroup$
4
  • 3
    $\begingroup$ Those sets are the same, by the principle of extensionality. $\endgroup$
    – Angina Seng
    Jul 23, 2017 at 11:45
  • 1
    $\begingroup$ And, if this isn't already obvious, it's not necessary to "choose" an element to collapse the copies to. Extensionality is already satisfied. $\endgroup$
    – rschwieb
    Jul 23, 2017 at 11:47
  • 3
    $\begingroup$ @Henno: I think the axiom-of-choice tag is justified here -- even though the question is based on a misunderstanding about what AC is and what it is needed for, this fact that such a misunderstanding is central to the question makes it partially a question about AC in my opinion. $\endgroup$
    – hmakholm left over Monica
    Jul 23, 2017 at 11:49
  • 1
    $\begingroup$ This is a valid question that does not merit a down vote. $\endgroup$
    – Ittay Weiss
    Jul 23, 2017 at 11:57

4 Answers 4

Reset to default
11
$\begingroup$

The axiom of choice has nothing to do with the no repetition principle. In mathematics we do not define sets in terms of anything else but rather, when doing things rigorously, we describe the axioms that we want our sets to satisfy. There are different axiomatisations, and things get very delicate very quickly. One axiom, called the axiom of extensionality, expressed the desire for sets to be completely determined just by their elements. This entails that the sets you mentioned are equal. So, it is the axiom of extensionality that is at play here, not the axiom of choice.

The axiom of choice can be stated in several different ways and properly understanding its need and its consequences takes time. One way to think about it is by pretending you are going to be extremely precise about your sets and wonder, if you have lots of non-empty sets, what does it really mean to take one element from each set and form a new set from these elements. Well, if, for instance, all of those sets are sets of natural numbers, then you can simply choose the smallest element from each set. That's it - in a very short sentence I described precisely what that set is. Now, what happens if you don't have any mechanism for choosing an elements from each set? Well, suppose you have a million such sets. Well, you can write a definition consisting of a million lines, namely: choose an arbitrary element from the first set. Choose an arbitrary element from the second set. Choose an arbitrary element from the third set, etc., until you've chosen a million elements which will then form your new set. That is perfectly valid and does not require the axiom of choice. Note though, that it is a very long definition, but still finite. We do demand that our definitions, and our proofs, are all finite. So, what happens if you have infinitely many non-empty sets, and you wish to choose one element from each set and form those into a set? Well, now you have a problem since your 'definition' of this set will have to be infinitely long - and that is not allowed. This is where the axiom of choice comes in. It says that you can shorten this too long of a definition into a single invocation of the axiom of choice. Much like the principle of induction allows you to accept a recipe for infinitely many proofs into a single proof by invoking the principle of induction.

$\endgroup$
9
  • $\begingroup$ Ah! This is what I was looking for, thank you. I was relying too heavily on Wikipedia's example of: "To give an informal example, for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate selection, but for an infinite collection of pairs of socks (assumed to have no distinguishing features), such a selection can be obtained only by invoking the axiom of choice." And thought to myself "Wouldn't this be the same as the set $\{1, 1, 2, 2, 3, 3, 4, 4, ...\}$?" $\endgroup$
    – AmagicalFishy
    Jul 23, 2017 at 12:02
  • 3
    $\begingroup$ @AmagicalFishy: No, a better imagination would be that the set is $\{11,12,21,22,31,32,41,42,\ldots\}$ but somehow we're finding ourselves in a universe where all the sets like $\{11,21,31,41,\ldots\}$ or $\{12,22,32,42,\ldots\}$ or $\{11,22,31,42,\ldots\}$ are missing. $\endgroup$
    – hmakholm left over Monica
    Jul 23, 2017 at 12:06
  • 2
    $\begingroup$ (In actual set theory, of course, we have enough axioms to demand that $\{11,21,31,41,\ldots\}$ always has to exist, so in the "real" examples of models where the axiom of choice fails, the socks are not as simple as integers. A common set-up is that each sock is some infinite set of sets of integers, and it turns out that certain sets of sets of sets of integers can go AWOL without violating the other axioms of set theory). $\endgroup$
    – hmakholm left over Monica
    Jul 23, 2017 at 12:11
  • $\begingroup$ @AmagicalFishy You're welcome. $\endgroup$
    – Ittay Weiss
    Jul 23, 2017 at 12:20
  • 1
    $\begingroup$ @AmagicalFishy: The problem with "examples for failure of choice" is that they all come from beyond the wildest imagination. In order to understand them intuitively without lying to yourself, you should study set theory for a while and do some choiceless work in order to get the hang of it. There is no other way. Anything else is not enough. Of course, for a crude understanding informal examples can do fine, but it's important to remember that it's impossible to "get the details" without actually studying set theory. That is the sad reality of mathematics (as that can be said about anything). $\endgroup$
    – Asaf Karagila ♦
    Jul 23, 2017 at 14:03
5
$\begingroup$

You're being confused by the difference between notation and what the notation stands for.

The ink blots (or pixels or whatever) that make up "$\{1,1,1,\ldots,2,2,2,\ldots, 3,3,3, \ldots\}$" are not what the set is -- they are merely part of a description of a set, and the set itself "doesn't know" how we have chosen to describe it.

What is a set, then?

Most fundamentally, a set is something we can ask, "is such-and-such one of your elements?" for every such-and-such we can think of, and get a "yes" or "no" answer back. Nothing more, nothing less.

The axiom of extensionality asserts that if we're looking at two such things and they agree about what their elements are -- that is if we ask each of them "is such-and-such one of your elements?" about the same such-and-such, then they give the same answers -- then they are really just the same set. We could perhaps imagine that the set has two different phone numbers we can call to ask what its elements are, but unknown to us both numbers lead to the same call center. But (so says the axiom) all other sets do know this, and they will give us the same answer for $\{555,1,2,3,4\}$ as for $\{555,4,3,2,1\}$.

The notation $\{1,2,3\}$ stands for

a set that answers "yes" to "is $x$ one of your elements?" if $x=1$ or $x=2$ or $x=3$, and "no" otherwise.

The notation $\{1,1,\ldots,2,2,\ldots,3,3,\ldots\}$ is informal but would stand for something like

a set that answers "yes" to "is $x$ one of your elements?" if $x=1$ or $x=1$ or $x=1$ or ... or $x=2$ or $x=2$ or $x=2$ ... or $x=3$ or $x=3$ or $x=3$ ..., and "no" otherwise.

For every possible $x$, these two descriptions both demand the same answer, so they describe the same set.

$\endgroup$
3
$\begingroup$

Yes, but not in the way you think it does.

The axiom of choice is not used to prove that $\{1,1,1,\ldots\}=\{1\}$. Only extensionality is used there. So your set is still just $\{1,2,3,\ldots\}$.

The rest of this answer is going to be more technical. And you can ignore it, and just take the naive answer from above: no.

But now, let's talk turkey. Definitions are syntactic and sets are semantic. You can have sets which have one definition in one universe of set theory, and a whole other definition in another. And these definitions can use the axiom of choice. For example, $A=\{x\mid\mathsf{AC}\rightarrow x\neq x\lor\lnot\mathsf{AC}\rightarrow x=\varnothing\}$. In a universe where the axiom of choice fails, $A$ is $\{\varnothing\}$, but in a universe where the axiom of choice holds $A=\varnothing$. The set itself did not change, but the definition of we used to define this set gave us different results. So moving from a universe of $\sf AC$ to a universe of $\lnot\sf AC$ we had to pick a different definition in order to obtain the same set.

$\endgroup$
1
  • 2
    $\begingroup$ Also, what we call a set is influenced by what axioms we have. Without the Axiom of Infinity, say, the class of finite ordinals may not be a set any more. And if we call the same object a set in one framework and a proper class in the other, this clearly means that the very notion of set changes with the axioms $\endgroup$
    – Hagen von Eitzen
    Jul 23, 2017 at 13:36
2
$\begingroup$

The axiom of choice doesn't come into play here. The axiom of extensionality says that "two sets are the same iff they have the same elements".

Your set $\{1,1,1,1,1,\ldots, 2,2,2,2,2,\ldots, 3,3,3,3,3,\ldots \}$ also has as its only elements $1$, $2$ and $3$, so it equals $\{1,2,3\}$; there aren't more "copies" of $1$ "to choose from" (if that is your choice connection..). In this notation, where we enumerate the elements, duplicates are not written, usually.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .