0

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.

Emil
  • 709

1 Answers1

2

$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.)

Kyle Miller
  • 19,353
  • So, the cardinality of S(a) is countably infinite? – Emil Sep 21 '16 at 17:37
  • (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 :-) ) – Emil Sep 21 '16 at 18:00
  • @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. – Ross Millikan Sep 21 '16 at 18:48