Welcome to Fractal Forums

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

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 (http://en.wikipedia.org/wiki/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.

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

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 (http://en.wikipedia.org/wiki/Axiom_of_separation) 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 (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.

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

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)

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

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!

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 (http://wehner.org/tools/fractals/arrowl.gif) 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

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

Pure gold.

Continue.

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

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.


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


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

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

I tend to think of the Universe/Existence as a limitation of an infinite mathematical construct.
Most seem to consider things the other way round  :)

Also copies can contain copies can contain copies - at least mathematically speaking - just zoom into the Harter-Heighway Dragon for example.

Also - on the question of a set containing everything.

Would it be true to say "everything" can only truly be defined as two sets: a set of everything except nothing and an empty set ?
(I confess my formal education on such ended with Venn diagrams)

Thanks Lycium for your thoughtful and interesting response to my comments on infinite sets.

Someday someone is going to explain exactly why the M-set generates the recurive copies-within-copies structure wherein the copies are self-similar versions of the whole M-set, rather than little pictures of Richard M. Nixon or a discrete hierarchy of completely different shapes. The mystery of self-similarity is a very fundamental one, I think, and its explanation will involve a big step forward in human understanding of mathematics and nature.

Anybody got any ideas?

Here's one off-the-wall idea. If the M-set were reformulated in a version wherein the hierarchy were not capped at the top, i.e., the M-set continues without bound in the "larger scale direction", as it does in the "smaller scale direction", then maybe the discrete self-similarity would be exact at all levels.  So the fact that the copies are are all slightly deformed, would be a result of artificially capping off the hierarchy. Unfortunately I do not have the math skills to check this out.

Rob

btw,


am i the only calculus student that feels downright violated by that remark? :-\

Unfortunately I don't know much serious maths about the Mandelbrot set, but I think your problem is something really well understood. Here is what I can scratch as a beginning of explanation.

Take the largest minibrot at the left of the main part. You will find its center is at about c = -1.7548. In fact, this value is one of the four roots of the polynomial (c²+c)²+c. The roots are the values of c for which 0 makes a cycle of order 3 (question: where are the other three roots? It's not too difficult).

We call c₀ this root and set c = c₀ + d. Since 0 makes a cycle of order 3, we consider in place of f(z) = z²+c the function:

g(z) = f(f(f(z)))
       = ((z²+c₀+d)²+c₀+d)²+c₀+d

It is some trouble to expand, but only the general form is important. We can assume that d is small. We can also assume that z is small, because to draw the mandelbrot set we want to iterate the value 0, and for d=0 we have g(0)=0. We also make use of the fact that (c₀²+c₀)²+c₀ = 0. Keeping only the smallest powers of z and d (because the others are negligible) we get something like:

g(z) = a z² + d

for a constant a, which makes a nearly standard mandelbrot set.

A complete proof would certainly need to control exactly how those d and z keep being small. But it's a math theorem, not a philosophy theorem.

Obvious generalizations for higher order cycles: the eight roots of ((c²+c)²+c)²+c ...

Can someone point to a reference where this would be explained in length?

Charles took my virginity some time ago, and this one doesn't really bother me.

May I beg everyone to clearly distinguish several ways that a set can "contain" another?

• Set B can be an element of set A (like the set {1,{3,4},{2,7,8},{0,{0}}} "contains" the set {2,7,8})
• Set B can be a subset of set A (like the set {1,{3,4},{2,7,8},{0,{0}}} "contains" the set {1,{2,7,8}}, and in this sense it is worth noting that every set contains itself)
• The image f(B) of set B by an injective function can be a subset of set A (like the Sierpinsky triangle "contains" multiple copies of itself via similarity transformations, or the set of even integers "contains" the set of integers via f(n)=2n)
  

and please only try to invoke Russell's paradox in the first case?

Many thanks for that - it certainly clarifies the situation for me (having next to no education on set theory).

Firstly, there is a very superficial individual who continues to fight a flame war against me. His commentaries are ill-considered, and uninformative. He is peeved because I would not accept his lectures. He seems determined to score "points" off me.

So when you are guided by someone who has an ulterior motive - other than truth itself - you get led astray.

In this case, for example, bh has been misled (1) into thinking I am as flippant as my detractor, and (2) into believing that set theory is small-talk.

Think again.

From first principles, Russell's Paradox considers only a set containing itself.

The first case cited by bh was of a set containing another set - which has nothing to do with the paradox.

I had hoped that there would be friendly discussion here, amongst people interested in Fractals. Personal attacks and ego-trips have no place. I was obliged to say before that life is not war. I repeat it. People like bh are being distracted by side-issues caused by the rancour of another.

Charles

Can we get back on topic please?

The symbolic logic that is at the heart of this set inclusion difficulty is what most people including myself are not familiar with. This is simply because i am familiar with a more natural collection of relations which the symbolic logic of the past never set out to model. Nevertheless whatit has produced is a model of certain systematic relations among defined and ill defined entities. Russel in setting out his paradox or rule set it out in many complementary systems, but the most telling is in the formal definition of a logical statement: the predicate. Again the predicate is ill defined and custom and usage among philosophers of logic linguistics and symbolic logic fail to appreciate the iterative nature of some of the concepts that seem so hard and fixed. After iterating through many written expressions of a statement the defined parts resolve into entities not on paper or in the statement structure but in our perception faculty. The referent for predicate is a set of perceptions within me which are triggered by certain symbolic patterns or more directly certain language patterns which i distinguish auditorily. Once i can distinguish a predicate auditorily or visually manipulations of this entity do not necessarily maintain its value as a predicate within a statement structure that is more complex than a simple statement. Thus to hold that the recognised entity will have that value throughout a complex argument may be true for an algorithm but is not consistent with any known language system used for communication between individuals. The iteration process of understanding produces widely differing referents and iterations between various entitic states. These i will call paradoxes, but they are only expected outcomes from an iteration that has no convergence to a single value. They are not monsters and may not be very useful in designing axiom systems to exclude them. in fact they are showing the lie of the land we exist in and should be included in our models of experience not excluded. We can then  classify them by how many states they iterate between. Unlike Russel who had a classical view of Nature, I view the experiential continuum within which i exist as having infinite possibilities of iterative outcomes: That is to say everything is a fractal, that is a product of an iteration process.

So to the point of fractal compression: the fact that a partition scheme is the de facto solution is in line with the other properties of iteration especially boundarisation and regionalisation. To assume that any random shape can be made up from a self similar shape arranged at smaller scales does not allow for structures within the regions that themselves are bounded by sub iterations in the overall iteration schema.

But as I see it, the purpose of fractal image compression is neither to theorize on the origin of the original shape, nor to predict the further detail that would be found by magnifying the original shape at any particular location. The purpose is to provide an un-intelligent, and thus un-biased, interpretation of the known, admittedly incomplete, data, in a way that our perception, which is optimized for viewing the high-resolution fractals of nature, can better understand it.

As such, it is useful only for applications in which an abstract representation is at least as good as the actual further details.

Of course, if you're interested only in pretty pictures, that's almost always the case.

I had hoped that Charles, who has had health problems would return to the forum.
However, the compression of image or data as charles points out has some pretty fundamenal definition issues. Within a computer paradigm a set can be nested within itself, and the issue is related to scale. Scale is related to what i might call sequence load, which is to say that a certain set of sequences have to be carried out at each nest level befor thenext level can be affected. This translates into time and space constraints in an objective space, ie the real world.

The simplest and natural solution is to do things in lower levels smaller and quicker. This is a natural programming ,structural consequence of any constraint on the action of running the sequence.

What this means is that copies of a the larger or higher level will play out at lower or smaller levels  with less and less influence on the higher level output depending on spatial availability.

Because we can now print in 3d ,the mandelbrot set looks different simply because more room is available to allow the substructure to be formed, and regions are not obscured , overlapped or over printed simply because there is no space on the printing media to represent the region.

The paradoxes, though interesting are always subjective. In "real life", things resolve one way or another. Russels paradox resolve into an "infinite" undecidability loop in he computing paradigm, and the solution is nested "levels" which of course translate in Gödel's terms to sets that enclose sets indefinitely, which is of course the structure of a fractal .

Barnsley's practical solution involves recognising and using these structurl boundaries and developing the coreect minimum sequence load at each level. Once that has been achieved for the given image, enlarging the image by scale does not effect the sharpness of the final iterated image, as the smaller sequence load at the lower levels has negligible to vanishing impact, but the spatial relationship of the enlarged pixel areas remain the exact same . Infilling in the larger canvas is then not by block colour but by iterated repetition of the structure for that region. We subjectively see then a variegated region that we would expect to see not an unexpected block.

Our process of perception undoubtedly uses many of the same techniques Barnesly has discovered to compute surface outputs for our own subjective experience. No one is saying that the extra detail is in fact what we would find if we looked through a microscope. What is being said is that the extra detail is consistent with expectations for that surface. Most of us would find a microscopic image of a surface totally contrary to expectations.

It is also True, that at the right scale many macro features are indistinguishable from microfeatures, thus expected surfaces are a food approximaion to reality, and a nested fractal paradigm provides that self similarity.

It seems likely to me that we may come to realise that we can not progress beyond a fractal self similarity in pursuing our quest for a deeper understanding of reality, to which i say "thank God!" Endless mindless questioning is very draining!

http://www.youtube.com/watch?v=Lte3xpmH2_g

Hopefully an update.

Imagine for a moment a fractal compression scheme fast enough to compress the data in a keyframe, whilst also compressing changes to the keyframe during the cycle of compressing the key frame. Thus as soon as the compression is complete, or the function for searching for change becomes a search of the whole key frame a new keyframe is declared and compressed.

Thus video could be stored directly to a memory chip as a compressed data set, saving memory space. However the cost of frame rate must not be compromised. Presumably the advantage would be clearer images at post processing . However the multiplexing of sound is another technical issue..