# Does this prove that there are no infinite sets?

I changed this question so that the socks don't have labels. The labels weren't important.

Suppose we have an infinite number of identical socks $s$. Call this infinite set $S$. Take one of the socks $s$ out of the set $S$ and we still have the original set $S$, since the socks are all identical and there are infinitely many, plus the sock $s$ that we took out, so we have $S \cup \{s\}$. But this new set $S \cup \{s\}$ is really just the same as the old set $S$, since the socks are all the same, so we have $S \cup \{s\}=S$. Subtracting $S$ on both sides, we obtain $\{s\}=\emptyset$, a contradiction. So there can be no infinite sets.

-
No, the labels are actually relevant. Without labels, your set S will have only one element because every socks are identical. So once you remove one sock you removed ALL of them. – Earth Engine Feb 12 '13 at 1:19
You want to have your cake and eat it too. The socks are "identical" apart from the labels (which distinguished them in the original problem), so now you get rid of the labels because they "weren't important." In fact a set cannot contain an item more than once, so if the socks are indeed the same sock repeated infinitely many times, what you describe is not a set. – hardmath Feb 12 '13 at 1:21
You seem to be trying to use a rule like: $A\cup B = A\cup C$ implies $B=C$. But this is just plain false, even for finite sets. – Greg Martin Feb 12 '13 at 1:45
How does subtraction work with multisets when the multiplicity is infinite? If $S$ consists of $s$ with infinite multiplicity (say multiplicity $\omega$) then what does it mean to subtract "one $s$" from $S$? – Trevor Wilson Feb 12 '13 at 1:53
That's like saying $\infty + 1 = \infty \Rightarrow 1 = 0$. – kba Feb 12 '13 at 1:55

Recall that sets ignore both order and repetition of elements, so $\{0,0\}=\{0\}$. So if all the socks are identical then $S$ is really just a singleton. But if we know that the socks are indiscernible from one another, but still different we can still talk about the infinite set of socks.

Once you took out a sock you don't have the same set. If $S$ is all the socks except $s$ then $S\cup\{s\}\neq S$. Now your arguments amounts to cardinality and to the fact that both $S$ and $S\cup\{s\}$ have the same cardinality, and my previously deleted answer applies again:

$\infty+1=\infty-1=\infty$. You can't cancel it out.

$$\Huge\text{Infinity is not a finite number.}$$

You can't apply the rules of finite arithmetics to infinite sets.

-
Yes shouting. "Bro". If I am allowed to shout this at my students, I am certainly allowed to shout this online. – Asaf Karagila Feb 11 '13 at 23:54
@Craig: If all the socks are identical then $S=\{s\}$ and it is a very finite set. – Asaf Karagila Feb 12 '13 at 1:14
There is really no other option. I suggest you strengthen your set theoretical foundations if you want to tackle set theory and infinite sets. – Asaf Karagila Feb 12 '13 at 1:54
@CraigFeinstein: You may have successfully proven that there is not an infinite number of identical socks. What you have certainly not proven is that there are no infinite sets. – ruakh Feb 12 '13 at 1:59
Regardless of how the set is defined, I'm not aware of a definition of "subtracting" an infinite set from both sides of an expression of set equality, which I believe is the important point of Asaf's answer. – Todd Wilcox Feb 12 '13 at 2:29

The sets you're subtracting are not sets of socks, but set of labels of socks. The socks stay the same, but you're explicitly changing the labels, and so have no right to expect the label sets to stay unchanged.

More fundamentally, you cannot prove anything about set theory by reasoning about socks. Socks don't exist in set theory at all, so the properties of (real or imagined) infinite collections of socks have no bearing on whether set theory works or not.

In set theory there are only sets -- the elements of sets are sets too. If you want to construct an argument that set theory is contradictory, your argument needs to work in that formal world. Otherwise the natural conclusion is that something's wrong with your application of set theory to the world of socks, not with set theory itself.

-
This. Any arbitrary sock s will be distinct and unique from any other sock in S, if for no other reason than that you can pull out two socks from S, hold one in each hand, and verify that no matter how identical, they are in fact not the same single unique sock. That makes the set of $S \cup s \neq S$, even though, by our definition, both sets still have an infinite number of socks. Their cardinalities are still equal (countably infinite - $\aleph_0$), because in number-line terms you can trivially create the piecewise bijection $f(x)=\{x \iff x>1, x-1 \iff x\leq 1\}$. – KeithS Feb 12 '13 at 1:36
(Pedantry alert) $S$ isn't necessarily countable. – Eric Stucky Feb 12 '13 at 2:20
I actually would disagree; S is a set of socks, a sock being an atomic indivisible unit, thus ordinable using natural numbers (at least integers), and the set of all natural numbers has cardinality $\aleph_0$. – KeithS Feb 12 '13 at 16:09

The sets of labelled socks before and after are not equal; rather, the re-labelling constitutes a bijection. So what you have shown is that $S \cup \{s\} \approx S$. In fact, the existence of such a bijection is equivalent to $S$ being infinite. It may be counterintuitive, but no one has found a contradiction in the axioms so far.

The reason that what you said isn't a contradiction is that you can subtract a set from both sides of $A = B$ to get $A \setminus C = B \setminus C$, but you can't subtract a set from both sides of $A \approx B$ to get $A \setminus C \approx B \setminus C$, where the "$\approx$" symbol indicates the existence of a bijection (one-to-one correspondence) between sets.

EDIT: Now the problem is, if $S$ is a multiset consisting of a single sock $s$ with infinite multiplicity, how do we subtract some (possibly infinite) number of copies of $s$ from $S$? I suppose this depends on how one defines multiset subtraction, and I suspect that it is not usually defined for infinite multiplicities because there is no good way to do it. In any case, you have to define operations on infinite cardinals before defining operations on multisets with infinite multiplicities, because the multiplicities are cardinals.

However, because infinite sets can be put into one-to-one correspondence with proper subsets of themselves, no subtraction operation with all the properties you expect it to have can be defined for infinite cardinals.

-

we have $S \cup \{s\} = S$ ($= S \cup \varnothing$). Subtracting $S$ on both sides,

Your proof is broken here. You cannot subtract on both sides. $A \cup B = A \cup C$ does not imply $B = C$.

Simplifications like $x \otimes y = x \otimes z \implies y = z$ are not always valid. A common case (not the only one) where this simplification is valid if $\otimes$ is associative and the element $x$ is invertible. A well-known case where such a simplification would be invalid is if $\otimes$ is multiplication of real numbers and $x = 0$: to decude $y = z$ from $x \cdot y = x \cdot z$, you must check that $x \neq 0$.

If you can always simplify by $x$ (i.e. for all $y$ and $z$, $x \otimes y = x \otimes z \implies y = z$), $x$ is sometimes said to be regular. Exercise: prove that for the operation $\cup$ (union on sets), the only regular object is the empty set.

If $A \cup B = A \cup C$, then intuitively speaking:

• Elements that are in $A$ are members of both sides. You cannot say anything interesting about whether they are in $B$ or $C$, because the fact thay they are in $A$ hides any information about their membership in $B$ and $C$.
• If $x \notin A$, then:

• if $x \in B$ then $x \in A \cup B = A \cup C$, but $x \notin A$, so $x \in C$;
• if $x \notin B$ then $x \notin A \cup B = A \cup C$ and therefore $x \notin C$. In other words, from $A \cup B = A \cup C$, you can deduce that $B \setminus A = C \setminus A$. Exercise: write down the proof.

In the original version of your question, there is a second error:

this new set $S \cup \{s\}$ is really just the same as the old set $S$, since the socks are all the same

This error is caused partly by a discrepancy between your mathematical model and the objects you're modeling, and partly because you aren't careful enough around the concept of identical objects, which is more subtle than it looks at first sight.

You have identical socks, but that doesn't make all the same sock. Consider a pair of socks in which the left foot and the right foot are not differentiated. They form a set $P = \{s_1, s_2\}$ that contains two socks (mathematicians call such a set a pair — an unordered pair if there is a risk of confusion with ordered pairs which are a different beast). The two socks in the set $P$ may be identical, in that there is no way to distinguish them, but they are not the same physical object: the sock that I happen to be wearing on my left foot is not the same sock that I happen to be wearing on my right foot.

Thus the set $S \cup \{s\}$ is not identical to the set $S$: it contains an extra sock. Even if that sock is externally indistinguishable from the others, it's a distinct object; you can tell them apart by laying them around and pointing “I mean that sock over there” (which mathematicians write as “let $s_0$ be a sock in $S$”).

In the original version of your question, you put a label on each sock. This is a valid way of distinguishing otherwise-identical socks, and it mirrors very closely what you can do mathematically. Given a mathematical object $\mathfrak{s}$ which is the Platonic idea of a sock, you can create distinct mathematical objects $(\mathfrak{s},1)$, $(\mathfrak{s},2)$, $(\mathfrak{s},3)$, etc. But then your set $S$ is not made of $\mathfrak{s}$: the elements are labeled socks, so $S = \{(\mathfrak{s},1), (\mathfrak{s},2), (\mathfrak{s},3), \ldots\}$. The set $S$ is infinite if you've used infinitely many different labels. It is not the same thing as the set $\{\mathfrak{s}\}$ which contains just the Platonic sock. No matter how many times you add $\mathfrak{s}$ to $\{\mathfrak{s}\}$, it's still the singleton $\{\mathfrak{s}\}$ containing just the Platonic sock.

In a comment, you mention multisets. Multisets are not the same thing as sets, they have different properties. When you add the same element multiple times in a multiset, this puts multiple copies of the same element. While you can have infinite multisets, under the normal definition, there can only be finitely many copies of the same element. If it wasn't for this restriction, then we would indeed run into a paradox like you describe — which is why multisets are defined to have finite multiplicity.

-