Verified answer

Since we say ds(x,y) is defined to be 1 over 2 to the power of the length of longest initial sequence common to both x and y, then k (possibly infinity) is the largest integer such such that xi=yi for each i ≤ k. If x_1 ≠ y_1 then k = 0 and d(x, y) = 1/2^0 = 1. If we define 1/2^∞ = 0, then d(x,x) = 0. It follows that 0 ≤ d(x,y) ≤ 1.

To show d is a metric, we must check that:

a) d(x, y) ≥ 0 for every x and y in Sʷ

This follows directly from the definition of d. As we've seen above for every x and y 0 ≤ d(x,y) ≤ 1.

b) d(x,y) = 0 if and only if x = y.

As we've seen, if x = y then d(x,y) = 1/2^∞ = 0

If x ≠ y, we don't have x_i = y_i for each positive integer i. Then, there is a smallest positive integer j for which x_j ≠ y_j. If we put k = j - 1, then k ≥ 0 is an integer and d(x,y) = 1/2^k > 0

c) For every x, y and z in Sʷ, d(x, z) ≤ d(x,y) + d(y, z) (triangle inequality)

Let k' and k'' be the values of k associated with (x, y) and (y, z), respectively.

If both k' and k'' are positive, suppose, WLOG, that k' ≤ k''. Then, The, for i ≤ k' we have x_i = y_i = z_i, so that k''' ≥ k', where k''' is associated with (x, z).

Then, d(x,y) + d(y, z) = 1/2^k' + 1/2^k'' ≥ 1/2^k''' + 1/2^k'' ≥ 1/2^k'' = d(x, z). Hence, d(x,z) ≤ d(x,y) + d(y,z)

If at least one of the numbers k' and k'' is 0, then at least one of the distances d(x,y) and d(y,z) is 1 and, therefore, d(x,y) + d(y,z) ≥ 1. Since, as, we've seen, d(x,y) ≤ 1, then, again, d(x,z) ≤ d(x,y) + d(y,z)

Hence, the triange inequality holds for every x, y and z in Sʷ

This proves d is indeed a metric and ( Sʷ,d) is a metric space