I have measured out my life with adjustments

To my lightbulb contraption and the proliferation of its

Switches.

-Thomas Stearns Edison

Everyone is of course familiar with famed inventor/poet T.S. Edison (the wizard of Faber and Faber), but what most people don’t know is that he spent the last years of his life building an elaborate light bulb contraption. The device consisted of a single bulb, which could emit blue, green, or red light, connected to a set of switches, each of which had three settings: blue, green, and red. Edison’s set of switches grew throughout his life (unconfirmed rumors suggest that, by the time of his death, the number of switches was greater than the size of the continuum), but, at any given time, there was a deterministic rule that associated each possible switch setting with a specific color for the bulb to emit. Edison tinkered with these rules but required that they all satisfy the following basic criteria:

1) If every switch is pointing to the same color, then that is the color of the bulb.

2) If every switch is changed, then the bulb must change color.

Let us call a rule that satisfies these two criteria an acceptable lightswitch rule. Just as we saw with elections last week, ultrafilters provide an easy way of generating acceptable lightswitch rules. Namely, let S be the set of all switches, and let \mathcal{U} be an ultrafilter on S. For any given configuration of the switches, there is a single color (red, say) such that the set of switches pointing to that color (i.e. red) is in \mathcal{U}. The rule associated with \mathcal{U} (call it the \mathcal{U}-rule) then says that the lightbulb should be red. This rule is easily seen to be an acceptable lightswitch rule.

T.S. Edison was aware of these ultrafilter rules but found them unsatisfactory and tried tirelessly to develop a different sort of acceptable lightswitch rule. Unfortunately, he never succeeded; in fact, we shall prove today that his search was in vain.

Theorem: Every acceptable lightswitch rule is in fact the \mathcal{U}-rule for some ultrafilter \mathcal{U} on S.

Proof: Suppose that we are given an acceptable lightswitch rule and that S is the set of all switches. We will define an ultrafilter \mathcal{U} on S and show that our given rule is in fact the \mathcal{U}-rule.

First, a quick observation: if all of the switches point to one of two colors, then the lightbulb must be one of those two colors. Why? Well, suppose there were a situation in which all of the switches point to, say, blue or green, while the bulb is red. Now change all of the switches to red. By criterion (1), the bulb must be red. However, by criterion (2), since all of the switches were changed, the bulb must change, so it can no longer be red. Contradiction! We illustrate this, as we will illustrate our future arguments, with a picture. In our pictures, the set of all switches will be depicted by a rectangle. Imagine that the switches are physically located in the rectangle and that the color of a switch is determined by the color of the region in which it is located. The switch configurations are numbered in the order in which we imagine them occurring, and the pictures are labeled with the state of the lightbulb.

two_color_unison_drawing (1)
Figure 1: Suppose we start with a situation in which all switches are either blue or green and the lightbulb is red. If all of the switches are then turned to red, there is no consistent state for the lightbulb.

We are now ready to define our ultrafilter, \mathcal{U}. First, some notation. If X \subseteq S, then we let X^c denote the complement of X, i.e. S \setminus X. Given a subset X \subseteq S, we let X \in \mathcal{U} if and only if when the switches are set so that all switches in X are blue and all switches in X^c are red, the lightbulb is blue. We must now show that \mathcal{U} is indeed an ultrafilter and that our rule is the \mathcal{U}-rule. We do this in a series of steps.

Step 1: S \in \mathcal{U} and \emptyset \not\in \mathcal{U}.

This follows precisely from criterion 1: if all switches in S are blue, the bulb must be blue, while, if all switches in \emptyset^c = S are red, the bulb is not blue.

Step 2: Suppose X \subseteq S. Then either X \in \mathcal{U} or X^c \in \mathcal{U}.

Suppose that all switches in X are set to blue and those in X^c are set to red. By our prior observation, the bulb must be either blue or red. If the bulb is blue, then X \in \mathcal{U} by the definition of \mathcal{U}. If the bulb is red, then change the switches in X to red and those in X^c to blue. Since all of the switches have changed, the bulb must change and therefore must be blue. In this case, X^c \in \mathcal{U}, again by the definition of \mathcal{U}.

Step 3: Suppose X \in \mathcal{U}, C_1 and C_2 are two different colors (chosen from blue, green, and red), and the switches are configured so that all switches in X point to C_1 and all switches in X^c point to C_2. Then the bulb has color C_1.

If C_1 is blue and C_2 is red, then this is precisely the definition of \mathcal{U}. We prove it here when C_1 is green and C_2 is red. The other cases are dealt with similarly. As before, we use a picture. In the picture below, the left side of the rectangle corresponds to X and the right side to X^c. We start with all switches in X blue and all switches in X^c red. Since X \in \mathcal{U}, the bulb must be blue. We then perform a series of manipulations, and repeated applications of criterion 2 will lead to our conclusion.

four_two_color_drawing (1)
Figure 2: In configuration 1, the bulb is blue. Going from 1 to 2, all switches are changed, so the bulb must change. Since all switches are either green or blue, the bulb must therefore be green. Going from 2 to 3, all switches again change, so the bulb must change, this time to red. The same argument shows that, in 4, the bulb must be green. But this is precisely what we wanted to show.

Step 4: Suppose X, Y \subseteq S, X \in \mathcal{U}, and X \subseteq Y. Then Y \in \mathcal{U}.

We again employ a picture. In the picture, the left half of the rectangle represents X and the left three-quarters of the rectangle represents Y. We start with all switches in X blue and those in X^c red. We then change all of the switches in Y to green and those in Y^c to blue. We changed all of the switches, so the color of the bulb must change and therefore must be green. But then, by Step 3, we have Y \in \mathcal{U}.

superset_drawing (1)
Figure 3: Moving from 1 to 2, all switches change, so the bulb must change from blue to green.

Step 5: Suppose we are given a configuration of switches, possibly using all three colors, and X is the set of switches matching the color of the bulb. Then X \in \mathcal{U}.

For concreteness, suppose that the bulb is blue and X \subseteq S is the set of all switches pointing to blue (so all switches in X^c are pointing to green or red). Now change all switches in X to red and all switches in X^c to blue. The bulb must switch colors, so it must be red. But, in our new configuration, we are using only two colors, so, by steps 2 and 3, we must have  X \in \mathcal{U}.

three_to_two_drawing (1)
Figure 4: The left of the rectangle corresponds to X. Going from 1 to 2, the bulb must change from blue to red.

Step 6: If X, Y \in \mathcal{U}, then X \cap Y \in \mathcal{U}.

Once more, a picture. We draw the picture in such a way that implies that X \cup Y = S. If this is not the case, then simply replace Y by Y \cup (S \setminus X). By step 4, this is in \mathcal{U}, and its intersection with X is the same as X \cap Y. In the picture, the left \frac{5}{8} of the rectangle corresponds to X and the right \frac{5}{8} corresponds to Y. Their intersection is thus the middle \frac{1}{4} of the rectangle. Since X \in \mathcal{U}, if all switches in X are blue and all other switches are red, the bulb is blue (call this Configuration A). Since Y \in \mathcal{U}, if all switches in Y are green and all other switches are red, then the bulb is green (call this Configuration B). Now suppose that all switches in X \cap Y are red, all switches in X \setminus Y are green, and all switches in Y \setminus X are blue (call this Configuration C). Going from either Configuration A or B to Configuration C, all switches change, so the bulb must change. Therefore, the bulb in Configuration C can be neither blue nor green, so it must be red. By Step 5, this means that X \cap Y \in \mathcal{U}.

intersection_drawing (1)
Figure 5: Since all switches change going from either configuration in 1 to the configuration in 2, the bulb must be red in 2.

 And now we are done! Why? Steps 1, 4, and 6 are precisely the verifications that \mathcal{U} is an filter, Step 2 shows it is an ultrafilter, and Step 5 implies that the given rule is the \mathcal{U}-rule.

P.S. I found this result in Komjath and Totik’s excellent book, Problems and Theorems in Classical Set Theory. Also, it is interesting to note that the result continues to hold (by essentially the same proof) for any finite number of colors greater than or equal to 3 but fails if only two colors are allowed. So here’s an exercise for you, reader: come up with an acceptable lightswitch rule for two colors that is not equal to an ultrafilter rule.

 

Advertisements

One thought on “Ultrafilters IV: The Light Bulb

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s