Article about Fractal Image Compression

[Jules Ruis]

For an article about Fractal Image Compression goto:

http://einstein.informatik.uni-oldenburg.de/rechnernetze/fraktal.htm

[Charleswehner]

For an article about Fractal Image Compression goto:

http://einstein.informatik.uni-oldenburg.de/rechnernetze/fraktal.htm

That is a very good example of degrading image compression, similar to JPEG but with slightly different characteristics.

I myself researched data compression, looking for the Shannon P_i Log(P_i), and found it.

Due to an oversight in the design of GIF, it violates Russell's Rule that a set cannot contain itself. It TRIES to put sets F and R into set R. But R cannot contain R.

I avoided this pitfall, and found the fundamental algorithm. Sets F and R are put into set G:

I then explored all manner of variants on the theme - discovering that as this is the bedrock level of non-degrading compression, Nature itself must use it in human and animal brains. How else can one store a lifetime of data in one-and-a-half kilos of grey matter (3 pounds, 5 ounces)?

There is more on the subject at http://wehner.org/compress

A subject I have not yet explored is the subject of differation - as I call it (new science needs new jargon) - in TWO dimensions.

The visual cortex, for example, is a two-dimensional plane, and the brain beneath it is a parallel-running super-computer. So with a Pentium or other CPU, these things are tricky. For Nature - which it seems got there first, it is a doddle to differate in two dimensions.

Charles

[bh]

Due to an oversight in the design of GIF, it violates Russell's Rule that a set cannot contain itself. It TRIES to put sets F and R into set R. But R cannot contain R.

I have not found anything about "Russell's Rule" on the web. I am wondering if you are not confusing with Russell's Paradox, which states that the "set of all sets that do not contain themselves as members" cannot exist? There is an axiom in Zermelo-Fraenkel set theory that does prevent sets from containing themselves, it is the axiom of regularity; but I have not seen it called Russell's Rule. Furthermore, this only holds in Zermelo-Fraenkel set theory, and there are other set theories that might allow such sets.

Axiomatic theories of sets, or Russell's Paradox in particular, are things so abstract that I am surprised to see you write about them alongside with so concrete things as data compression. Yes, we are dealing with "sets" in both cases, but the firsts are monsters that are a matter of formal play, whereas yours are finite, or at worst countable sets.

I don't understand at all why the creators of LZW would have violated "Russell's Rule". I understand that we have on one side sets of uncompressed data and on the other side sets of compressed data. But how are you going to identify "data" with "sets of data"? It seems to me that when you write about set A containing set B (as a member), you are in fact trying to find an injection from B to A, which is a different thing.

[Charleswehner]

Due to an oversight in the design of GIF, it violates Russell's Rule that a set cannot contain itself. It TRIES to put sets F and R into set R. But R cannot contain R.

I have not found anything about "Russell's Rule" on the web.

Yes - it is identically the same as Russell's Paradox.

The paradox is about the Set of all sets that does not contain itself. I wrote "This is the set of all jokes that does contain itself". I told a friend in England, and he told me that in twenty years' time, somebody will break out laughing.

Set theory is one of those mathematical abstractions like bounded systems, countable numbers, decidability and so forth that are central to mathematics and so affect everything.

Russell stated that a set cannot contain itself. Nothing can contain itself. So there is no set of all sets.

Surprisingly, there is a joke that does contain itself.

Any attempt at putting a set into itself is doomed to failure. Gottlob Frege was trying to define all logic and mathematics by using the set of logical and mathematical procedures. That was where Russell wrote to him, and explained that he was trying to violate a law of nature. Perhaps it is not formally known as Russell's Rule, but Frege accepted the rule and stopped his researches.

There is a lot about the Russell-Frege correspondence on the Internet.

Charles

[bh]

Any attempt at putting a set into itself is doomed to failure. Gottlob Frege was trying to define all logic and mathematics by using the set of logical and mathematical procedures. That was where Russell wrote to him, and explained that he was trying to violate a law of nature. Perhaps it is not formally known as Russell's Rule, but Frege accepted the rule and stopped his researches.

I admit I have trouble understanding Russell's terminology:

There is just one point where I have encountered a difficulty. You state that a function, too, can act as the indeterminate element. This I formerly believed, but now this view seems doubtful to me because of the following contradiction. Let w be the predicate: to be a predicate that cannot be predicated of itself. Can w be predicated of itself? From each answer its opposite follows. Therefore we must conclude that w is not a predicate. Likewise there is no class (as a totality) of those classes which, each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection does not form a totality.

What is true is that we can't have a set containing all sets. Indeed, from the Axiom schema of specification of Zermelo-Fraenkel set theory, we would then be able to build the set of all sets that do not contain themselves, and then invoke Russell's paradox. This does not prevent a set from containing itself. I know what you think of Wikipedia, but I'm still citing excerpts from http://en.wikipedia.org/wiki/Axiom_of_regularity:

Two results which follow from the axiom are that "no set is an element of itself", [...]
The axiom of regularity is arguably the least useful ingredient of Zermelo-Fraenkel set theory, since virtually all results in the branches of mathematics based on set theory hold even in the absence of regularity (see Chapter III of [Kunen 1980]). In addition to omitting the axiom of regularity, non-standard set theories have indeed postulated the existence of sets that are elements of themselves. See "Well-foundedness and hypersets" in the article Axiomatic set theory.
[...] It is natural to ask whether the presence of the axiom of regularity in Zermelo-Fraenkel set theory (ZF) resolves Russell's paradox in this setting. It does not; if the ZF axioms without the axiom of regularity were already inconsistent, then adding the axiom of regularity could not make them consistent.

[Charleswehner]

My answer to things containing themselves generally involves a bottle that contains itself.

The outside of the glass is therefore inside the glass. Therefore, the thickness of the glass is at the very least nil, or at worst less than nil. If there is no glass, there is no bottle. "What about a plastic bottle, har, har har"?  I'm glad we've got that behind us.

I once interpreted for the Great Eastern Writer, the Great Khatib. At least, he told everybody he was a Great Eastern Writer. As I sat with him, he held his writings up, and recited what he had written. When I asked him to repeat what he had read, he would always "read" it again totally differently.

Follow me quick and flit across the page
Fly left and zigzag down at every stage
Shifty-eyed reader, I toy with your brain
These words will give you nothing but eyestrain!

It slowly dawned upon me that the Great Khatib was not a Great Eastern Reader. He could not read in any language. He could not read what he himself had written. His eyes never zigzagged, but remained glazed and focused on the middle-distance.

He would often be seen in Hampstead cafs, holding up a book by Doskovesky or by Andrew Guide. It took time to explain to him that the names are Dostoyevski and Andr Gide. He had not made it past the cover.

On the strength of his self-acclaim he was given the task of reviewing the book Shama by a rival author Salman Rushdie. He decided that as Shamanism is haram, Salman Rushdie is anti-Islam. However, the book was a political, not a religious, commentary. It was called Shame. The Great Khatib had again failed to get past the cover. His own works were reviewed by a highly literate Pakistani, and were declared to be written in poor Urdu.

In the story I translated from his broken English ("I have only been in England for thirty years, and don't speak the language - you must translate for me") he introduced a character. She said ^{opening quote}I was talking to my friend who said  ^{opening quote}My family say  ^{opening quote}We say  ^{opening quote}Everybody says  ^{opening quote}.......

The day arrived when he suddenly shrieked "DONE"! I said that it was difficult to round off the Magnum Opus because he had opened 147 layers of nested quotes, and had not closed a single one. What should I do? Should I finish off with a paragraph of closing quotes?

THIS is the set of all jokes that DOES contain itself.

Lord Russell was right. Try it.

This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}

But then I realised that we keep trying to substitute itself by the joke. It is true that itself cannot contain the joke, but the joke can contain itself. You just put it in:

This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain ^{opening quote}This is the set of all jokes that does contain itself

 ^{closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote  closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote  closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote   closing quote}


We managed to close all the quotes, even though it required a separate paragraph (in the style of the Great Khatib).

So the quotes are closed, the set is closed, the joke is closed and the subject is closed.

Charles

[David Makin]

The question about a set containing itself reminded me of a similar question:

If the universe is truly infinite, then how many copies of itself can it contain ?

(substitute "existence" for "the universe" if you like)

[rloldershaw]

I think the question about whether an infinite Universe can contain copies of itself has the same answer as the sets problem.

The *parts* of an infinite Universe can be present in infinite numbers (exact copies or similar copies).

On the other hand, by definition there can only be *one* whole infinite Universe.

If we are talking about multiple copies, then we are talking about a group of "universes" or a group of parts of the ultimate Universe.

Regarding existence, Spinoza gave the definitive first approximation answer to the whole qiestion of life, existence and nature.
The book: "Spinoza and Spinozism" by Stuart Hampshire is an excellent introduction to Spinoza's ideas (avoid the original writings at first).

Rob

[Nahee_Enterprises]

David Makin wrote:
>
>    The question about a set containing itself reminded me of a similar question:
>    If the universe is truly infinite, then how many copies of itself can it contain ?
>    (substitute "existence" for "the universe" if you like)

There is no limit to the number, they are infinite.  But which one is the "original" that contains the copies??  And are there copies of the copies??

Actually, each one is its own unique universe, they are just alternate universes existing within the same time and space.

[Sockratease]

David Makin wrote:
>
>    The question about a set containing itself reminded me of a similar question:
>    If the universe is truly infinite, then how many copies of itself can it contain ?
>    (substitute "existence" for "the universe" if you like)

There is no limit to the number, they are infinite.  But which one is the "original" that contains the copies??  And are there copies of the copies??

Actually, each one is its own unique universe, they are just alternate universes existing within the same time and space.

The "copies" of the universe would need to be incomplete by virtue of the fact that they can not contain their own copies too!

So there would still be only one Universe regardless.

Infinity never struck me as plausible.

I like to think of it as a Mathematical Construct with no counterpart in Reality whatsoever.

I firmly believe that ALL is finite.  Even fractal math is limited in it's iterations by the available time of the existence of the Universe (which I believe must also be finite!).

I prefer to think Infinity is one of those things we invented to help make sense of the weirdness we observe.

My disbelief in it Increases Without Bound!

Purely from Philosophy and Logic Study, not from any advanced Math study...  YET!

[Charleswehner]

Sets are central to the whole idea of Fractals. They are based on the paradox that you can try to make a thing contain itself, but Nature will try to wriggle out of the situation.

Recursion, whether it is a joke that must contain "a joke that must contain &c. or Z f(Z), is the trick that tries to force Nature to put something inside itself.

The Mandelbrot set is a set of patterns. If the attractors are painted black, one will find huge numbers of spots of black. Each one seems to be the complete Mandelbrot set, but Nature has distorted it - to avoid the set being inside itself. So each one is uniquely different. This is how endless variety evolves.

The sticking point with Russell's paradox - which he described many times in many different ways - is infinity. If the set that contains itself is infinitely large, it might yet contain itself. That is like a bottle with a finite thickness of glass but with infinite volume. The thickness of the glass tends to zero in its relationship to the volume of the bottle.

So as you enlarge the Mandelbrot set, you find an infinite collection of black dots which iff infinitely enlarged will each be a perfect Mandelbrot set.

Iff is a recent bit of mathematical jargon, for "If and only if".

Infinite magnification is impossible.

So the Mandelbrot set only contains the Mandelbrot set under some theoretical conditions where real-world axioms no longer apply.

Charles

[heneganj]

This is exactly the ringside seat I was hoping for when I created Fractal Forums.

Pure gold.

Continue.

[rloldershaw]

Hi Charles,

I have two comments relating to the issues of infinity, self-similarity, and the set of all sets.

1. It seems to me that nature and mathematics are two different things. My definitions are that nature is actual objects and their motions, while mathematics involves artificial constructions which can be used to generate approximate models of nature, or can be explored and enjoyed for their intrinsic properties as an exercise in pure abstraction. But this is an area of much contention among philosophers and scientists.

2. If one has a structure with discrete self-similarity, then the copies at different hierarchical levels can only be exactly self-similar if the the discrete self-similar hierarchy is at least countably infinite in the "small" "direction".

The proof of this involves a matching procedure, not unlike G. Cantor's diagonal proofs. In order for copies at two different levels to be exactly self-similar, their number of internal levels of substructure must be equal and capable of a one-for-one matching. Only for infinite sets is this possible. For finite sets, the copy that is "higher" in the hierarchy will have more levels of substructure.

I still do not understand exactly what causes the Mandelbrot Set to generate an infinite hierarchy of self-similar copies of itself, and the usual explanation that recursive systems tend to do that does not fully answer the question. It is curious that the copies are highly self-similar, but all deformed in some way (according to conventional wisdom). But I think it has to be the mathematics that does this, rather than nature, if my distinction between nature and math is correct.

Rob

[lycium]

1. It seems to me that nature and mathematics are two different things. My definitions are that nature is actual objects and their motions, while mathematics involves artificial constructions which can be used to generate approximate models of nature, or can be explored and enjoyed for their intrinsic properties as an exercise in pure abstraction. But this is an area of much contention among philosophers and scientists.

an excellent recent book by roger penrose, "the road to reality", covers this topic extremely well in chapter 1. he factorises our existence into 3 seperate "worlds":

the platonic mathematical world
the physical world
the mental world

which are cyclic subsets! i can't summarise the chapter unfortunately - interestingly he uses the mandelbrot set as an example a number of times, it's one of the first pictures in the book - due to present time constraints.

2. If one has a structure with discrete self-similarity, then the copies at different hierarchical levels can only be exactly self-similar if the the discrete self-similar hierarchy is at least countably infinite in the "small" "direction".

agreed; no matter how complex the results of a finite experiment may appear to be, its information content must too be finite. that the forms we see in the mandelbrot set not "everywhere unique" but rather "everywhere changed" seals the deal for me - i don't have any formal axiomatic justification for this, but it seems right on so many levels (not just intuitively, but as some manner of "information conservation" or entropy issue).

I still do not understand exactly what causes the Mandelbrot Set to generate an infinite hierarchy of self-similar copies of itself, and the usual explanation that recursive systems tend to do that does not fully answer the question. It is curious that the copies are highly self-similar, but all deformed in some way (according to conventional wisdom). But I think it has to be the mathematics that does this, rather than nature, if my distinction between nature and math is correct.

it certainly must be a property of mathematics; it's everywhere/anytime repeatable, just like putting N stones in one bag, M stones in another, and finding N+M stones if you empty one bag into the other. nature does not seem to like such certainties (with the usual exceptions of death and taxes

i don't think anyone can truly know the mandelbrot sense in its full existence, but the laws that govern it are incredibly simple and that simply must tame the complexity at least a little. the same is true for many other, perhaps more "real" things: global economic activity and a city's traffic are other complex systems that obey simple rules and exhibit emergent behaviour (inflation/crashes, congestion). to understand the rules of a game is unfortunately not always enough to determine its outcome, but at least we can gain microscopic understanding...

[Charleswehner]

One of the original explanations of Russell's Paradox came from Lord Russell himself. It might have been the one he sent to Frege.

He considered a librarian making a catalogue of all the books on the shelves. As he/she is completing the catalogue, he/she starts writing "cat", but cannot continue. He/she realises that he/she is writing a lie, because the catalogue is (1) incomplete, and (2) not yet on the shelf.

There was an American librarian who was writing a catalogue. Then he put "catalog" into the list, but found he had to stop before he had completed the word. That is how the Americans got their spelling.

Charles