1

Recently I had a thought about some sets with special properties that are constructed from a starting set $A$ and successively removing elements from it. I am not an expert in set theory but perhaps someone who is can enlighten me. To be more precise I am thinking of three examples:

1) The prime numbers. We can start with $A=\mathbb{N}$ and first delete 1 from it. Then keep 2 but delete all multiples of it. Keep 3 but delete all multiples of it. Keep 5 but delete all multiples of it. When we complete this process at infinitum we are left with the primes, which is kind of a peculiar set. In some ways they appear to be random but in other ways they appear having a definite structure.

2) The Cantor middle thirds set: Start with the unit interval $A=[0,1]$ and remove the middle third, $[1/3,2/3]$. In the two remaining pieces remove the middle third. Do that in the $4$ remaining pieces and so on. This is actually the set of numbers in $A$ that have only $0$ and $2$ in their base-$3$ representation. This is a disconnected set, uncountable but with measure zero. Not sure if it's dense or not, but surely one of the "funny" sets. If we start looking at base-$3$ numbers $x$, if we encounter a 1 we know for sure that it's not in the set but in order to prove that $x$ is in the set we have to check the entire sequence which is an infinite process.

3) The computer scientist's favorite set, the Mandelbrot set $\mathbb{M}$. Start with the complex plane $A=\mathbb{C}$ and remove all the points $z$ for which the composition $f^{(n)}(z)\to\infty$, where $f(z)=z^2+1$. This is a fractal set: If we zoom in on a point $z\in\mathbb{M}$ we see the same pattern as the whole. I think it's connected, it's boundary is kind of funny and I don't know about it's Housdorff dimension, it could be strictly between $1$ and $2$.

In all three examples it's easy to show that an element is not in the set but hard to show that it's actually in the set. Are there any other sets like that? Is it the process of removing elements that makes them so peculiar?

Help from anyone? I appreciate.

Asaf Karagila
  • 393,674
Georgy
  • 1,467

1 Answers1

0

In some sense every set is specified in this way: if you define $A$ via $A = \{ x \mid P(x) \}$ for some property $P$ it is the same as saying "take $A$ to be everything but those points $x$ for which $\neg P(x)$". One notable example is the Vitali set which is formed by removing everything from $[0,1]$ which isn't an element of one of infinitely many equivalence classes.

Another example is the set of squares of integers $\{1,4,9,16,\ldots \}$.

Also, you mentioned the Mandlebrot set as a fractal, but the Cantor set is one too!

user139388
  • 3,449
  • Checking if $P(x)$ or $\not P(x)$ can be entirely different things. Suppose you want to show that two numbers $x$ and $y$ in the unit interval differ. You check if they have the same digits. If $x$ differs from $y$ then the algorithm stops after a finite number of steps, at the first position $k$ for which $x_k$ differs from $y_k$. Suppose now you want to show that $x=y$. You have checked so far that the first $N$ digits agree. However you still are uncertain of the result, and in fact you never will never. Roger Penrose has extensively worked and talked talked about these issues. – Georgy Apr 07 '14 at 09:55
  • You are very correct. This is why I wrote "in some sense" not meaning, of course, the practical sense. The set of squares example does satisfy the property that in finite time the status of any candidate can be ascertained. Many famous sequences such as the Fibonacci numbers do too. I'll try to think of something more exotic and come back if I succeed :) – user139388 Apr 07 '14 at 14:07