Metric Spaces

49 Replies

One of the things that topologists like to say is that a topological set is just a set with some structure. That structure is, basically, the nearness relation – a relation that allows us to talk about what points are near other points.

So to talk about topology, you need to be able to talk about nearness. The way that we do that in topology is through a fundamental concept called an open sphere. An open sphere defines the set of all points that are close to a particular point according to some metric. That’s not the only way of defining it; there are various other ways of explaining it, but I find the idea of using a metric to be the easiest one to understand.

Of course, there’s a catch. (There’s always a catch, isn’t there?) The catch is, we need to define just what we mean by “according to some metric”.Fundamentally, we need to understand just what we mean by distance. Remember – we’re starting with a completely pure set of points. Any structure like a plane, or a sphere, or anything like that will be defined in term of our open spheres – which, in turn, will be defined by the distance metric. So we can’t use any of that to define distance.

Defining Distance

So. Suppose we’ve got a totally arbitrary set of points, S, consisting of elements s_1, s_2, s_3, s_4, ..., s_n, .... What’s the distance between s_i and s_j?

Let’s start by thinking about a simple number line with the set of real numbers. What’s the distance between two numbers on the number line? It’s a measure of how far over the number line you have to go to get from one point to the other. But that’s cheating: how far you have to go is really just a re-arrangement of the words; it’s defining distance in terms of distance.

But now, suppose that you’ve got your real number line, and you’ve got a ruler. Then you can measure distances over the number line. The ruler defines what distances are. It’s something in addition to the set of pointsthat allows you to define distance.

So what we really want to do is to define an abstract ruler. In pure mathematical terms, that ruler is just a function that takes two elements, s_i and s_j, and returns a real number. That real number is the distance between those two points.

To be a metric, a distance function d needs to have four fundamental properties:

Non-Negativity
\forall s_i, s_j \in S: d(s_i, s_j) \geq 0: distance is never negative.
Identity
\forall s_i, s_j \in S: d(s_i, s_j) = 0 \iff i=j; that is,
the distance from a point to itself is 0; and no two distinct points are separated by a 0 distance.
Symmetry
\forall s_i, s_j \in S: d(s_i, s_j) = d(s_j, s_i). It doesn’t matter which way you measure: the distance between two points is always the same.
Triangle Inequality
\forall s_i, s_j, s_k \in S: d(s_i, s_j) + d(s_j, s_k) \geq d(s_i, s_k).

A metric space is a pair (S, d) of a set, and a metric over the set.

For example:

  1. The real numbers are a metric space with the ruler-metric function. You can easily verify that properties of a metric function all work with the ruler-metric. In fact, they are are all things that you can easily check with a ruler and a number-line, to see that they work. The function that you’re creating with the ruler is: d(x,y) = |x-y| (the absolute value of x - y). So the ruler-metric distance from 1 to 3 is 2.
  2. A cartesian plane is a metric space whose distance function is the euclidean distance: d((a_x,ay_), (b_x,b_y)) = ((a_x-b_x)^2 + (a_y-b_y)^2 )^{frac{1}{2}}. In fact, for every n, the euclidean n-space is a metric space using the euclidean distance.
  3. A checkerboard is a metric space if you use the number of kings moves as the distance function.
  4. The Manhattan street grid is a metric space where the distance function between two intersections is the sum of the number of horizontal blocks and the number of vertical blocks between them.

With that, we can define the open spheres.

Open and Closed Sets

You can start moving from metric spaces to topological spaces by looking at open sets. Take a metric space, (S,d), and a point p \in S. An open sphere B(p,r) (a ball of radius r around point p) in S is the set of points x such that d(p,x) < r.

Now, think of a subset T \subseteq S. A point p \in S is in the interior of T if/f there is some point r where B(p,r) \in T. T is an open subset of S if every element of T is in its interior. A subset of space formed by an open ball is always an open subset. An open subset of a metric space S is also called an open space in S.

Here’s where we can start to do some interesting things, that foreshadow what we’ll do with topological spaces. If you have two open spaces T and U in a metric space S, then T cup U is an open space in S. So if you have open spaces, you can glue them together to form other open spaces.

In fact, in a metric space S, every open space is the union of a collection of open spheres in S.

In addition to the simple gluing, we can also prove that every intersection of two open subsets is open. In fact, the intersection of any finite set of open subsets form an open subset. So we can assemble open spaces with all sorts of bizarre shapes by gluing together collections of open balls, and then taking intersections between the shapes we’ve built.

So now, think about a subspace T of a metric space S. We can say that a point p is adherent to T if \forall r < 0; B(p, r) \cap T \neq \emptyset. The closure of T, written \overline{T} is the set of all points adherent to T.

A subset T of S is called a closed subset if and only if T=\overline{T}. Intuitively, T is closed if it contains the surface that forms its boundary. So in 3-space, a solid sphere is a closed space. The contents of the sphere (think of the shape formed by the air in a spherical balloon) is not a closed space; it’s bounded by a surface, but that surface is not part of the space.

Introducing Three-Valued Logic

52 Replies

So, finally, I’m getting around to three-valued logic!

To start, why are we even looking at three-valued logic? We want to get to fuzzy reasoning, and three valued logic really doesn’t do the job. But it’s a useful starting point, because in general, most of us have only worked with standard logics where statements are either true or false. In Fuzzy logic, we’re don’t have that – and that can lead to a lot of complexity. So looking at something simple that shows us how something either than “true” or “false” can actually make sense in logic.

Continue reading →

Lucky Me: the Return of John Davison to GM/BM

140 Replies

Being the incredibly lucky guy that I am, I somehow managed to attract the attention of John Davison. If you don’t know John, well.. you’re lucky.

He’s a rather infamous fellow. He’s got a rather peculiar hypothesis about evolution. Basically, he claims that evolution did occur, but it was front-loaded – the path that it took was dictated ahead of time by evolution encoded into the primitive genome.

To make matters worse, his approach to debate is, generally, to shout, call people names, make vague threats, and generally piss everyone off, regardless of whether or not they agree with him. He was the first person that I ever banned back at ScienceBlogs.

And to make it even worse, the guy doesn’t understand how blogs actually work. He started one blog, made one post, and then continued to post on the blog simply by adding comments to that post. Then he threw a tantrum, deleted it, started a new one, and did exactly the same thing. It appears that his current blog (which has the incredibly pompous name “The Proceedings of the Natural History Society of South Burlington Vermont”) actually has several posts on in – the most recent one being somewhat more than two and a half years old. But he’s still posting comments on it. Hundreds and hundreds of comments, nearly all by him. It appears that he progressed from thinking that a blog post was an entire blog (and thus adding new “posts” as comments on the only existing post on the blog), to thinking that a blog post is a category (and thus adding new posts on comments on the five different posts on his blog).

He’s showed up in the comments here. Naturally, being John, he’s commenting in the wrong place. And, of course, being John, he’s throwing tantrums about how nobody is paying attention to him.

The poor guy is clearly lonely and desperate for attention.

So. His comments are here, here, and here.

Please respond to them (if you must) in the comments on this post, so that it’s easy to keep track of. I warned John privately that I’m not going to tolerate him insulting other commenters; similarly, I’d ask that anyone who responds to him do so on the content of his posts, and refrain from just throwing insults at him.

Frankly, I doubt that he’s capable of actually engaging in a civil discussion. I’d put money on it taking less than an hour from the time this post goes up until he starts insulting people. But hey, why not give him the chance to try?

So, to repeat the warning: as always, my comment policy is:

  • you’re welcome to insult me: after all, I insult people in my posts; it’s only fair that they be allowed to insult me back
  • you are not allowed to insult other commenters. You can disagree as strongly as you want – but personal insults will not be tolerated.

If you break that simple rule, you get one warning, and then you get banned. That goes for John, and that goes for anyone else commenting.

An Introduction to Topology

52 Replies

When I took a poll of topics that people wanted my to write about, an awful lot of you asked me to write about topology. I did that before – right after I moved my blog to ScienceBlogs. But it’s been a while. So I’m going to go back to those old posts, do some editing and polishing, correct some errors, and repost them. Along the way, I’ll add a few new posts.

We’ll start with the fundamental question: just what is topology?

I’ve said before that the way that I view math is that it’s fundamentally about abstraction. Math is taking complex ideas, breaking down to simple concepts, and then exploring what those concepts really mean, and exactly what you can build using them.

I argue that topology, at its deepest level, is about continuity and nearness. In a continuous surface, what does in mean for things to be close to one another? What kind of structures can you build using nothing but nearness relationships? What is a structure defined solely by that notion of nearness?

Continue reading →

Preachy Twits: Please Go Away!

150 Replies

And I fell into a rant… Please pardon this off-topic diversion. I’m almost certainly going to get myself into trouble with this, but I don’t care. I’m sick of being harassed by twits of all stripes. (Do go listen to the song at that link; it’s a very fun bit of silly modern Klezmer by a really brilliant performer.)

I’ve mentioned around here that I’m Jewish. I don’t actually talk about what I believe – but I’ve mentioned the fact that I am a religious, theistic, reconstructionist Jew.

Every time I mention my Judaism, I get two related clumps of email. One of them is from Christians, who feel a deep need to tell about how my beliefs are all wrong, and I desperately need to listen to them tell me about Jesus. And the other clump is from atheists, who feel a deep need to tell me about how my beliefs are all wrong, and I desperately need to listen to them tell me about why there is no god. I don’t know quite why, but this seems to have gotten worse since we launched scientopia; even though my average daily pageview rate is down by about 50%, the number of preachy emails I’m getting from both christians and atheists is up by about 30%.

Continue reading →

Return of the Revenge of the Return of the Compression Schmuck

44 Replies

Well, folks, this one is going to be boring for most of you. But the
compression jackass, Jules “Julie-baby-dumbass” Gilbert has been repeatedly
bugging me. And today, he replied to my latest “fuck off and stop sending me
mail” with a long-winded proselytizing response in which he requested that I
be courteous and not publicize the discussion of his “work”.

Fuck that

The entire correspondence is below.

Before I get to it: the short summary of what Jules is doing
is munging a file in a way that makes it amenable to recompression. In
the classic sense, this is removing a trivial bit of information from the
file, which thus allows is to be re-compressed just a tiny bit
more.

The catch is, of course, you can’t un-compress it without re-introducing
the information that you removed. In his case, you need to repeatedly
un-compress, un-munge, un-compress, un-munge, and so on –
exactly the right number of times. From some of his emails, he
does this hundreds to thousands of times.

You can’t un-compress his stuff without knowing how many times the compressor
ran. And how many times is that? Well, gosh, to know that, you need to know
some extra information. Anyone want to take a bet on what the
relationship is between the amount of additional compression he can get, and
the number of repetitions of his system? Anyone?

Ok. On to the transcript.

Continue reading →

Euclid? Moron!

45 Replies

A coworker of mine at Google sent me a link this morning to an interesting piece of crackpottery: a guy who calls himself “the Soldier of the Truth” who claims to have proved Euclid’s parallel postulate; and that therefore, all of non-Euclidean geometry, and anything in the realms of math and science that in any way rely on non-Euclidean stuff, is therefore incorrect and must be discarded. This would include, among numerous other things, all of relativity.

Continue reading →

Holy Freaking Cow… P != NP??

65 Replies

Very big, very exciting news in the theoretical comp sci world today!

A group at HP research has published a proof that, if correct, shows that the classic problem of computational complexity has been solved, once and for all. It’s still far from certain that it’s correct. But it’s the most credible attempt that I’ve ever seen, and it’s getting some preliminary favorable feedback from big-names in complexity theory. In fact, one of the biggest names in complexity theory, Stephen Cook, has apparently said that it should be taken seriously. If Cook thinks it’s credible, then it’s damn-well credible. It might not be correct, but it’s not just crackpottery either.

For the non-CS folks out there, here’s my attempt to explain what the problem is, and what the solution means.

Continue reading →

Leading in to Fuzzy Logic

94 Replies

So, as I said in the intro to the new Scientopical Good Math/Bad Math, I’m
going to writing some articles about fuzzy logic.

Before diving into the fuzzy stuff, let’s start at the beginning. What
is fuzzy logic? More fundamentally, what is logic? And what problem does fuzziness solve?

So, first, what’s logic?

Logic isn’t really a single thing. There are many different logics, for different purposes. But at the core, all logics have the same basic underlying concept: a logic is a symbolic reasoning system. A logic is a system for expressing statements in a form where you reason about them in a completely mechanical way, without even knowing what they mean. If you know that some collection of statements is true, using the logic, you can infer – meaning derive from a sequence of purely mechanical steps – whether or not other statements are true. If the logic is formulated properly, and you started with an initial set of true statements, then any conclusions drawn using the inference process from those statements will also be true.

When we say logic, we tend to automatically think of a particular logic: the first order predicate logic, which is the most common, fundamental logic used in both mathematics, and in rhetoric and debate. But there are an astonishing number of different logics for different purposes. Fuzzy logic is one particular
variation, which tries to provide a way of reasoning about vagueness.

Continue reading →

Revenge of the Return of the Compression Idiot

63 Replies

Do I really need to go through this again? Argh!

As long-time readers will remember, a while back, I had an encounter with
a crackpot named Jules Gilbert who claimed to be able to cyclically compress
files. That is, he could take a particular input file, compress it, do
something to it, and then compress it again, making it smaller. He claimed to
be able to do this for any input.

And to make it more annoying, his claim to be able to do this brilliant
magical cyclical compression was attached to an obnoxious christian “I want to
save you soul” rant, where he effectively offered to share the profits from
this brilliant invention with me, if I’d only give him the chance to tell me
about Jesus.

I tried to get rid of the schmuck. I asked him to leave me alone politely.
Then I asked him to leave me alone not-so politely. Then I asked him to
leave me alone very, very rudely. Then I publicly mocked him on this blog.
After the last, he finally seemed to take the hint and go away.

Unfortunately, good things often don’t last. And yesterday, I received
another new message from him, bragging about the results of his uber-magical
compression system. He has now perfected it to the point where he can take
any input file, and compress it down to about 50K:

I am now compressing single bit as:

I use C code to pack up one bit to a byte and call bzip2’s compress
buffer.

I print the result and compute the size.

(I did this for both gzip and bzip2.) Gzip didn’t compress; it gave
me back about 6.25, but I needed at least 8.0.

And bzip2 gave it to me. About 8.2 and higher. (This is with no
actual I/O, just buffer to buffer.)

This was with random data. At least that’s what people call it.
Bzip2 data. (It looks pretty random to me.)

I expect to show up at a friend’s house and show him the system on
Monday. THIS IS NOT A COMPLETE SYSTEM, but it’s not just research
either. The input was randomly chosen (not by me, by a C function,)
and the program has been arranged to simply open another file when a
current file is exhausted.

Every input file has been compressed once with bzip2. Each input file
is at least 5k bytes and was chosen with the intent to represent all
popular OS’s somewhat equally.

This program is easily able to process MN’s 415k file. And since it
uses 256 byte blocks, I can bring it down to about 50k (number
demonstrated in testing.) Another way to say this is that (with this
program,) all files greater than about 50k can be made that small.

This is the simplist system I have ever made that uses my “modern”

techniques (I mean, not my LSQ ideas of a decade ago.) i started
coding it this morning, to see if a certain idea worked…

I’m trying to drop bzip but it’s pretty good! I’m also trying to
modulate my input to it, in order to obtain a gain from the pattern
recognition (the BWT may not be an actual FFT but it’s a similar
idea.) If I can do this I will keep it.

If all this is greek to you, here’s the thing: Just about every other
computer scientist in the whole wide world believes this is
impossible. Why is this valuable? Because it means that all files
and messages can be compressed in while in transit to, say, 50k —
probably much less. (Or while sitting on a CD-ROM or DVD.)

I love that line in there: “Just about every other computer scientist in
the whole wide world believes this is impossible”.

Jules, baby, belief has nothing to do with it.

Continue reading →