wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Topologically Employed?
        
(Message started by: Michael_Dagg on Aug 10^th, 2006, 7:19pm)

Title: Topologically Employed?
Post by Michael_Dagg on Aug 10^th, 2006, 7:19pm

Let S be a set which consists of an office staff whose members are the president p,
four secretaries s1,s2,s3, s4, and four office boys b1,b2,b3,b4. These members
occupy nine rooms arranged as indicated in the matrix below:

-----------------
| b2 | s2 | b1 |
| s3 | p | s1 |
| b3 | s4 | b4 |
-----------------

The following rules prevail in the office:

(i) The president can give orders to everybody.
(ii) Each secretary can give orders to two office boys only, namely those
whose rooms are immediately adjacent.
(iii) No office boy is permitted to give orders to any other member of the staff.
(iv) Each member can give orders to them-self.

We make the definition: If B can give orders to A, then A is a servant of B.

Let a general topological correspondence be defined in S as follows:

If M is a subset of S, then M bar consists of those elements of S which are
servants of at least one element of M.

1. Is S a topological space under the given general topological correspondence?
2. If an open set in S is defined as the complement in S of the closure of a set, list
all the open sets in S.
3. If the neighborhoods of every element x of S are defined to be the open sets
containing x, is the resulting neighborhood space a Hausdorff space?

Title: Re: Topologically Employed?
Post by Hooie on Aug 13^th, 2006, 4:17pm

3. It's not Hausdorff- there's no way to separate an office boy from adjacent secretaries. For an open set to have an office boy but no adjacent secretary, you'd need a closed set that had the secretary but not the office boy. But any set with a secretary would have their adjacent office boys in the closure.

ETA:

1. It's a TS. All the closed sets are either S itself, sets with only office boys, and sets that contain secretaries and all their adjacent office boys along with other office boys.

I think the only thing that could go wrong is if you intersected two closed sets and got a set that had a secretary but not her adjacent office boys. No set has a closure of that form, and the only way for the intersection to have that form is if one of the closed sets you were intersecting already had that form.

Title: Re: Topologically Employed?
Post by Icarus on Aug 14^th, 2006, 5:49pm

Denote "x is a servant of y" by x < y.

To show that the definition provides a topology we need to show that
(1) both the empty set and S are closed, but these are both obvious.
(2) that the union of 2 closed sets are closed: Let A and B be closed sets. If y is in A U B, and x < y, then y must be in one of A or B - wlog, say A. But A is closed, so x is in A as well, and therefore in A U B. Hence A U B is closed.
(3) that the intersection of 2 closed sets is closed: Again, let A, B be closed and let y be in A n B, and let x < y. Then y is in A, so x is in A, and y is in B, so x is in B. Hence x is in A n B. Therefore A n B is closed

Therefore, the definition of closure does define S as a topological space.

As Hooie has said, a set in S is closed if (i) it is S, or (ii) it does not contain p, and for every secretary in it, it also contains both adjacent office boys.

Conversely, a set is open if (i) it is empty, or (ii), it contains p, and for every office boy in it, it also contains both adjacent secretaries. (For otherwise one of the secretaries would be in the complement without her adjacent office boy, and hence the complement would not be closed.)

As Hooie has noted, S is not Hausdorff. It is not even T1. However, it is T0. (http://mathworld.wolfram.com/SeparationAxioms.html) For the boss is an open set by himself, and thus separated from secretaries and office boys. Each secretary forms an open set when combined with the boss, separating her from the other secretaries and the office boys, and each office boy with his two ruling secretaries and the boss forms an open set separating him from the other office boys.