When I read https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox#A_sketch_of_the_proof I do not understand this part of the proof:

$$F_2 = \{e\}\cup S(a) \cup S(a^{-1}) \cup S(b) \cup S(b^{-1}) =aS(a^{-1})\cup S(a)$$

where S(a) is the set of all non-forbidden strings starting with a. If I understood it right it has to be a finite string, i.e. the longest allowed string is of length $n\in \mathbb{N}$. If you write the length of the longest allowed string as a superscript, does this actually say

$$ F_2 = \{e\}\cup S^n(a) \cup S^n(a^{-1}) \cup S^n(b) \cup S^n(b^{-1}) =aS^{n+1}(a^{-1})\cup S^{n}(a), n\in\mathbb{N} $$ ? Because otherwise I cannot see how the equality can work.

  • $\begingroup$ All strings are finite, but there are strings of arbitrary length $\endgroup$ – Hagen von Eitzen Sep 21 '16 at 17:29

$S(a)$, for example, is the set of all finite-length non-forbidden strings which begin with $a$. $S(a)=\{a,aa,ab,ab^{-1},aaa,aab,aab^{-1},aba,aba^{-1},abb,ab^{-1}a,ab^{-1}a^{-1},ab^{-1}b^{-1},\cdots\}$. There is no upper bound on the lengths of strings in $S(a)$, but the length of any particular string is finite.

The decomposition of $F_2$ is saying that every non-forbidden string is either the identity, a string beginning with $a$, with $a^{-1}$, with $b$, or with $b^{-1}$. (The Cayley graph of $F_2$ in the Wikipedia article is a useful illustration for this decomposition.)

| cite | improve this answer | |
  • $\begingroup$ So, the cardinality of S(a) is countably infinite? $\endgroup$ – Emil Sep 21 '16 at 17:37
  • $\begingroup$ (If it is I'm not that surprised it is a paradox, playing with infinites seems to be the go to way to end up with weird results :-) ) $\endgroup$ – Emil Sep 21 '16 at 18:00
  • $\begingroup$ @Emil: Yes, the cardinality of $S(a)$ is countably infinite. Your equation at the bottom is correct if you delete the $F_2=$ or make it $F_2^n=$. The equality doesn't work for strings of limited to length $n$ as the $n+1$ subscript on the right shows, but it does work when the length is unlimited. Wagon's book on the subject is excellent. $\endgroup$ – Ross Millikan Sep 21 '16 at 18:48

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.