Sunday, February 03, 2008

Metric Spaces (a metric on a set)

I had a few interesting lectures this week, albeit introductory in some sense, and the one which made me think "hmm, must blog about this" was the first metric spaces lecture.

The lecture began with a definition, so who am I to break tradition?

Let X be a non-empty set and let d:X \times X \to \mathbb{R} be a function. Then d is a metric on X if, and only if the following properties are satisfied:

\text{(i) } d(x,y) \ge 0 \text{ and } d(x,y)=0 \Leftrightarrow x=y \qquad \text{(Positive Definite)}
\text{(ii)}\:d(x,y)=d(y,x) \qquad \text{(Symmetric)}\\\
\text{(iii)}\: d(x,z) \le d(x,y) + d(y,z) \qquad \text{(Triangle Inequality). }

The function d is also known as the distance function, and (X, d) is a metric space. That is, a metric space is "a set where pair of things have distance between pairs defined". (The last sentence is my baby interpretation).

That isn't the word to word definition from my notes, so if there are any mistakes do let me know. I understand that strictly speaking, whenever a definition is of the form "so and so IF such is true", we really mean to say if, and only if in place of the "if" (or is my thinking wrong). As bad habits go, I no longer write if but if, and only if for definitions, when writing them out for fun in my spare time!

After doing a question, I think it is obvious(?) that if d gives a metric on X, then d naturally gives a metric on any subset of X. This is probably what Prof. S would call a FACT! (But I'm afraid I have no proof for this).

The definition above is pretty harmless and not very interesting. The thing which intrigued me the most (one could say) was the following example:

Example of a metric on the space W of words.
Let W be the set of all "words", i.e. dog, idiot etc.

The distance between two "words" is the fewest number of changes it takes to get from one word to another, where in each change you can:
(i) delete any letter (GREY--> GRY)
(ii) insert any letter (SAY --> SLAY)
(iii) replace any letter (BAT--> BIT)
(iv) switch adjacent letters.

The example in lectures was d(MATH, MONEY)= 4. (You may check that if you want).

I had actually wanted to post about the space of words! The lecture had ended after the above example and a few grumbles along the lines "Pfft- words, we're doing a maths degree" could be heard, which amused me. I find different and exotic(!) examples rather interesting, and the above metric reminded me of something I had read in a book. I'm sure that anyone who has read an Ian Stewart book will know what I speak of--that of going from the word ORDER to CHAOS by changing just one letter at a time. (Or indeed, any other two words). In Stewart's case you don't have much freedom during each change, but nevertheless it is still interesting.

Now for anyone who wants to check my homework! How many words can you find at distance \le 1 from "pat" in the space W of words. Remember that the distance is the fewest number of changes, so in this instance we only want to do one of the four possible options. (I get 29).

The space of words can be used as a good game for the "younger generation" *cough including me!* Well it is enough to keep one busy for quite some time....


Wow-- I actually did what I said I would, for once in my life. Does this call for a celebration? Well I can always reward myself with a quick ramble about my weekend...

In terms of maths I haven't done much apart from a few questions from the metric spaces problem sheet. On my answers I wrote "I'm stuck but I'll be back", to remind myself of what I wasn't able to do! The weird thing is that as soon as I sit down to do some work, my teeth clench in frustration as the pain in my forehead drops for a visit without a call. This has happened on two separate occasions when I have sat to do work; but today I fought back, as one hand applied pressure to my forehead and the other wrote. Yesterday I just needed an excuse, but today I was in the mood for maths.

The question I am asking, as I look at my logic homework is: how do you know whether something is a sentence or not? My mind is hazy and all I see in my notes is propositional variables and connectives. Do we require the string of connectives and variables to be a tautology? Or does it just have to be something which is either true or false?

From most interesting to not as interesting, here's how I would rate the material covered this week:
(1) Geometry and Logic
Discrete maths and Metric spaces
(3) Algebra and Calculus of Several Variables joint last

Well (1) and (2) are interchangeable because they were all interesting, but there is no changing my mind about (3). Geometry is probably (1) because of Dr. K and his enthusiam. Note to anyone who takes a course by Dr. K-- don't mention MATLAB!! Logic is a funny looking module and it's very different to what we normally do, which is what probably attracts me towards it. Discrete is another one which is different and hence why I am intrigued by it; but metric spaces was saved by the exotic example above, because we didn't really do much else. Algebra was just a recap as was calculus hence why they're last. In algebra it seems that the emphasis has switched onto rings, which means bah humbug for me.

People taking fluid mechanics are making me turn green! I'm so green that tomorrow I am going to
(hopefully) attend both applied maths modules lectures. I spoke to Professor Abrahams on Friday, and it is unfortunate that he is really busy this year. Honestly, he is a brilliant teacher. Just brilliant. I don't think you will find anyone who disagrees with that. I did obviously whinge about why he wasn't teaching this year, but I might as well satisfy my curiosity and see what is exciting all the second year applied mathematicians on campus! (Boy have I been lucky when it has come to supervisors. All four of them last year were cool.)

My headache still hasn't gone and I am too tired to fight it. That means no more maths for me, but tomorrow I have a nice relaxing day with only one offical lecture so I'm not worried. Even now, the prospect of not having to wake up at 9am tomorrow, brings a smile to my face!


Beans said...

I've answered my own question about sentences. I had become confused with arguments and sentences. If I am correct, sentences are made from propositional variables, connectives and brackets. The question was technically asking whether the sentences were "well formed sentences". For them to be so, they have to unambiguous and satisfy certain properties.

This is all from memory, but I'm sure you will be hearing more about this soon.

Jake said...

To be a sentence means that the 'word' is a member of SL. We defined SL inductively and then proved that members of SL can be parsed unambiguously in a certain sense due to the construction itself, so you needn't worry about that but just as to whether word can be formed by following the inductive procedure of SL.
L = {p,q,...,(p^q),(p v q),(p->q),¬p}

Take the word '((p->q)v p)'

(p->q) \in SL_1, call it phi, say
then (phi v p) = ((p->q)v p) \in SL_2

and so ((p->q)v p) is a sentence.

Beans said...

I think I was (and am still) slightly unsure about some of the notation. Dumb question one, but can (p^q)etc be members of L? I thought it was only propositional variables that could be so.

Hmm, I think the best way of answering the question is to draw a diagram like in todays lecture. Or how I did it, was to reconstruct the sentence and then check for anything incorrect.

I'm guessing that we can also say ((p->q)vp) is a word?

Jake said...

Sorry, my L was meant to be SL_1

L was meant to be L = {p,q,...,^,v,->,¬,(,)}

All sentences are words, but the converse isn't true.

A word is just a string composed of prop. variables, the connectives and brackets.

The diagrams in the lecture today was just a graphical form of what I was saying; building up the sentence inductively layer by layer. The top of the diagram featured elements of SL_0 = L and every time you went down a layer, it featured elements of SL_(n+1)

Beans said...

Ah, I get it now (I think!) This SL_n business had me confused, but it makes sense now. If only it was just about truth tables! ;) I tend to understand some things better when a graph or diagram is included.