Cue a key

There is a typical problem with Emacs experienced by people frequently switching between different keyboard mappings, for example, to work with non ASCII languages: fundamental Emacs keyboard shortcuts (and one has to invoke them a lot to use Emacs efficiently) all use ASCII keys. For example, when I want to save my work, while entering some Russian text, I have to do something like Alt-Space (switch to the US keyboard layout) Control-x-s (a Emacs shortcut to save buffers) Alt-Space (shift back to the Cyrillic keyboard layout). Switching out and back to a keyboard layout only to tap a short key sequence is really annoying.

Two solutions are usually proposed:

• Duplicate standard key sequences in other keyboard layouts. For example,
  

  (global-set-key [(control ?ч ?ы)] 'save-some-buffers)
  

  expression in .emacs binds Control-ч-ы to the same command as Control-x-s is usually bound. This eliminates the need to switch layout, because ч-x (and ы-s) symbols are located on the same key (in QWERTY and JCUKEN layouts respectively).

• Another solution employs the fact that Emacs is a complete operating system and, therefore, has its own keyboard layout switching mechanism (bound to Control-\ by default). When this mechanism is used, Emacs re-interprets normals keys according to its internal layout, so that typing s inserts ы when in internal Russian mode, while all command sequences continue to work independently of layout. The mere idea of having two independent layout switching mechanisms and two associated keyboard state indicators is clearly ugly beyond words (except for people who use Emacs as their /sbin/init).

Fortunately, there is another way:

; Map Modifier-CyrillicLetter to the underlying Modifier-LatinLetter, so that
; control sequences can be used when keyboard mapping is changed outside of
; Emacs.
;
; For this to work correctly, .emacs must be encoded in the default coding
; system.
;
(mapcar* 
 (lambda (r e) ; R and E are matching Russian and English keysyms
   ; iterate over modifiers
   (mapc (lambda (mod)
    (define-key input-decode-map 
      (vector (list mod r)) (vector (list mod e))))
  '(control meta super hyper))
   ; finally, if Russian key maps nowhere, remap it to the English key without
   ; any modifiers
   (define-key local-function-key-map (vector r) (vector e)))
   "йцукенгшщзхъфывапролджэячсмитьбю"
   "qwertyuiop[]asdfghjkl;'zxcvbnm,.")

(Inspired by a cryptic remark about "Translation Keymaps" in vvv's .emacs.)

Unintentionally yours.

Extension.

This post is about set theory, which is a framework to reason about collections, elements and membership.

We start with a informal and naïve outline, which is (very loosely) based on a Godel-Bernays version of set theory. This theory is about sets (collections) which contain elements, which can in turn be sets. When a set \(X\) contains an element \(t\), it is written \(t\in X\).

First, set equality has to be defined:

E0 Axiom of extensionality:
$$X = Y \equiv (t \in X \equiv t \in Y)$$
(Here \(\equiv\) is a logical equivalence, pronounced "if and only if".) This axiom means that sets are equal if and only if they have the same elements. (In this and following formulae, free variables are implicitly universally quantified.)

Subsets are defined by \(X \subseteq Y \equiv (t\in X \Rightarrow t\in Y)\), that is, X is a subset of Y when every element of X is also an element of Y. It's easy to check that \(X = Y \equiv (X\subseteq Y \wedge Y\subseteq X)\), where \(\wedge\) means "and".

Next, a way to build new sets is needed:

E1 Axiom of (extensional) comprehension:
$$t \in \{u \mid P(u)\} \equiv P(t)$$
This axiom introduces a "set-builder notation" \(\{u \mid P(u) \}\) and states that \(\{u \mid P(u) \}\) is exactly the set of all \(t\) such that \(P(t)\) holds.

Now, there is already enough machinery for two famous collections to be immediately constructed: empty set, \(\varnothing = \{t \mid false \}\), which contains no elements, and the collection of all sets: \(U = \{t \mid true \}\), which contains all possible elements.

With these axioms, conventional set operations can be defined:

• singleton: \(\{t\} = \{u\mid u = t\}\), for each \(t\) a singleton set \(\{t\}\) can be constructed that contains \(t\) as its only element. Note that \(t\in\{t\}\)
  
• union: \(X\cup Y = \{t\mid t \in X \vee t \in Y\}\) (\(\vee\) means "or")
  
• intersection: \(X\cap Y = \{t\mid t\in X \wedge t\in Y\}\)
  
• complement: \(\complement X = \{t \mid t \notin X\}\)
  
• (unordered) pair: \(\{t,u\} = \{t\}\cup\{u\}\)
  
• ordered pair: \((t,u) = \{t, \{t, u\}\}\)
  
• power set: \(\mathfrak{P}(X) = \{t \mid t \subseteq X\}\)
  

From here, one can build hierarchical sets, representing all traditional mathematical structures, starting with natural numbers:

$$0 = \varnothing, 1 = \{0\}, 2 = \{0, 1\}, \ldots n + 1 = \{0, \ldots, n\}, \ldots$$

then integers, rationals, reals, &c., adding more axioms (of infinity, of foundation, of replacement, &c.) along the way.

It was discovered quite early that this system is not entirely satisfactory. First defect is that it is impossible to have elements which are not sets themselves. For example, one would like to talk about a "set of all inhabited planets in the Solar system". Elements of this set (planets) are not sets, they are called ur-elements. Unfortunately, the axiom of extensionality makes all ur-elements equal to the empty set. Note, that this indicates that the axiom of extensionality doesn't work well with sets that have very few (none) elements. This was never considered a problem, because all sets of interest to mathematics can be constructed without ur-elements.

Another, more serious drawback, arises in the area of very large sets: existence of a set \(\{t\mid t\notin t\}\) directly leads to a contradiction known as Russel's paradox.

Among several methods to deal with this, one separates sets into two types: "smaller" collections which are continued to be called "sets" and "proper classes", which are collections so large that they cannot be a member of any collection. Axiom of comprehension is carefully modified so that set-builder never produces a collection having some class as its element. In this setup Russel's paradox becomes a theorem: \(\{t\mid t\notin t\}\) is a proper class.

Intention.

The axiom of extensionality states that sets are equal when they contain the same elements. What would happen, if set theory were based on a dual notion of intentional equality (which will be denoted by \(\sim\) to tell it from extensional one), where sets are equal when they are contained in the same collections?

I0 Axiom of intensionality:
$$X \sim Y \equiv (X \in t \equiv Y\in t)$$
This looks bizarre: for any "normal" set \(X\) a collection of all sets containing \(X\) as element is unmanageably huge. But as a matter of fact, intentional equality is much older than extensional, it is variously known as Leibniz's law, identity of indiscernibles and, in less enlightened age, as duck typing.

There is a nice symmetry: while intensional equality myopically confuses small sets (ur-elements), extensional equality cannot tell very large collections (proper classes) from each other, because they are not members of anything and, therefore, intentionally equal.

The whole extensional theory buildup can be mirrored easily by moving things around \(\in\) sign:

Intensional subsets: \(X \unlhd Y \equiv (X\in t \Rightarrow Y\in t)\)

I1 Axiom of intensional comprehension (incomprehension):
$$[u \mid P(u)]\in t \equiv P(t)$$

And associated operations:

• uniqum (or should it have been "s-ex-gleton?): \([t] = [u\mid u \sim t]\), note that \([t]\in t\).
  
• intentional union: \(X\triangledown Y = [t\mid X \in t \vee Y \in t]\)
  
• intentional intersection: \(X\triangle Y = [t\mid X \in t \wedge Y \in t]\)
  
• intentional complement: \(\Game X = [t \mid X \notin t]\)
  
• intentional pair: \([t,u] = [t]\triangledown [u]\)
  
• intentional ordered pair: \(<t,u> = [t, [t, u]]\)
  
• intentional power set: \(\mathfrak{J}(X) = [t \mid X \unlhd t\}\)
  

What do all these things mean? In extensional world, a set is a container, where elements are stored. In intensional world, a set is a property, which other sets might or might not enjoy. If \(t\) has property \(P\), it is written as \(t\in P\). In the traditional notation, \(P\) is called a predicate and \(t\in P\) is written as \(P(t)\). The axiom of intentional equality claims that sets are equal when they have exactly the same properties (quite natural, right?). \(X\) is an intentional subset of \(Y\) when \(Y\) has all properties of \(X\) and perhaps some more (this looks like a nice way to express LSP). Intentional comprehension \([u \mid P(u)]\) is a set having exactly all properties \(t\) for which \(P(t)\) holds and no other properties. Intentional union of two sets is a set having properties of either and their intentional intersection is a set having properties of both, &c. Uniqum \([P]\) is the set that has property \(P\) and no other properties.

Because intensional theory is a perfect dual of extensional nothing interesting is obtained by repeating extensional construction, for example, by building "intensional natural numbers" as

$$0' = U, 1' = [0'], 2' = [0', 1'], \ldots (n + 1)' = [0', \ldots, n'], \ldots$$

What is more interesting, is how intensional and extensional twins meet. With some filial affection it seems:

• by uniqum property \([\varnothing] \in\varnothing\), which contradicts the definition of \(\varnothing\), also
  
• set \([t\mid false]\) is not a member of any set (perhaps it's a proper class) and set \([t\mid true]\) is a member of every set, which is strange;
  
• a set of which a singleton can be formed has very shallow intentional structure. Indeed:
  

  	\(x \unlhd y\)
  \(\equiv\)	{ definition of intensional subset }
  	\(x\in t \Rightarrow y\in t\)
  \(\Rightarrow\)	{ substitute \(\{x\}\) for \(t\)}
  	\(x\in \{x\} \Rightarrow y\in \{x\}\)
  \(\equiv\)	{ \(x\in \{x\}\) is true by the singleton property, modus ponens }
  	\(y\in \{x\}\)
  \(\equiv\)	{ the singleton property, again }
  	\(x = y\)

To get rid of contradictions and to allow intensional and extensional sets to co-exist peacefully, domains on which singleton and uniqum operations are defined must be narrowed. To be continued.

From the traveller diary.

Note to oneself: general anaesthesia is a very efficient cure for jet lag.

An obscure generalisation: a redundancy domain should be transversal (better yet, orthogonal) to a potential failure vector. Hello, Karmarkar!

The Hunt for Addi(c)tive Monster 2.

In the previous post, we were looking for a monster—a nonlinear additive function. We found that such a function is extremely pathological: it is nowhere locally monotone, nowhere continuous and nowhere locally bounded. Worse than that, it's easy to prove that the graph of a monster is dense in , that is, for every x and y, an arbitrary neighborhood of x contains a point that monster sends arbitrarily close to y.

Recall our attempt to construct a monster. Any additive function is linear on any -set and is fully determined on this set by a value it has in any single of its points. Our Direchlet function derived monster failed (or rather fell) because the slopes an additive function has on different -sets are not independent. Indeed, given that f has a slope on a -set and a slope on a -set , it has to have a slope on a -set . This shows a way to construct a monster: one has to find a collection B of real numbers such that (i) every real number can be represented as a sum  , with rational coefficients of which only finite number is non-zero (so that the sum is defined) and (ii) that such representation is unique. Then one can select arbitrary values on elements of B and take moster's value on to be , which is well-defined thanks to (ii).

Looks familiar? It should be: the definition of B is exactly the definition of a basis of a vector space. Real numbers can be added to each other and multiplied by rationals and, therefore, form a vector space over . This space is very different from a usual one-dimensional vector space real numbers form over  (i.e., over themselves).

After a streak of bad and unlikely properties that a monster has, we now got something positive: a monster exists if and only if  as a vector space over  has a basis. Does it?

But of course. Any vector space has a basis—this is a general theorem almost immediately following from the Zorn's lemma. The basis we are looking for even got a name of its own: Hamel basis.

At last we stumbled across the whole family on monsters. Specifically, there exists a set  and a function such that every real number r can be uniquely represented as

where only finite number of  are non-zero for a given r. From this it immediately follows that .

Take an arbitrary function , and define

  

Now,

that is, f is additive. Intuitively,  is a slope f has at the -set . f is linear if and only if is a constant function, in all other cases f is a monster. If one takes , then

 

is an especially weird monster function: it takes only rational values!

Note that almost all additive functions are, after all, monsters—only very small sub-set of them is linear.

The Hunt for Addi(c)tive Monster

This is another spurious post about mathematics that happened instead of something more useful. Let's talk about one of the most common mathematical objects: a function that maps real numbers () to real numbers. We shall call such a function additive iff for any real x and y

This is a natural and simple condition. Well-known examples of additive functions are provided by linear functions , where k is called a slope. Are there other, non-linear additive functions? And if so, how do they look like? A bit of thinking convinces one that a non-linear additive function is not trivial to find. In fact, as we shall show below, should such a function exist, it would exhibit extremely weird features. Hence, we shall call a non-linear additive function a monster. In the following, some properties that a monster function has to possess are investigated, until a monster is cornered either out of existence or into an example. Out of misplaced spite we shall use technique in some proofs.

First, some trivial remarks about the collection of all additive functions (which will be denoted ).

If ,  are two additive functions and — an arbitrary real number, then , and are additive. This means that additive functions form a vector space over field with constant zero additive function as a zero vector. This vector space is a sub-space of a vector space of all functions from to . Product of two additive functions is not in general additive (when it is?), but their composition is:

Unfortunately, composition is not compatible with scalars (i.e., ), and additive functions are not an algebra over a field , but see below.

Looking at an individual additive function , it's easy to see that even it is not clear that it must be linear everywhere, there are some subsets of  on which is obviously has to be linear:

For any real number x and for any natural number n,

that is, restriction of f to any subset is linear and in particular, f is linear when restricted to the natural numbers. Specifically, , from this

Similarly,

Combining these results, for any rational number ,

That is, f is linear when restricted to any subset of the form . We shall call such subset a -set.

Notice that we just proved that composition of linear functions is compatible with multiplication on rational scalars (see above), so that is an algebra over .

Having briefly looked over the landscape of , let's start converging on our prey. How bad a monster function must be? A linear function has all the good qualities one might wish for: it is monotonic, continuous, differentiable, smooth, it's even... linear. Which of these it enjoys together with a monster? It's intuitively very unlikely that an additive, but non-linear function might happen to be differentiable, so let's start with checking continuity.

Statement 0. If an additive function is continuous at point x, then .

Indeed,

That is, an additive function is linear everywhere it is continuous. This means that a monster must be discontinuous at least in one point. Note that linear functions are precisely everywhere continuous additive functions. Can a monster function be discontinuous in a single point? Or, even, can it be continuous somewhere? It is easy to show that property of additivity constrains structure of sets on which function is continuous severely:

Statement 1. If an additive function is continuous at point x, it is linear.

Take an arbitrary non-zero point y. By statement 0, . By definition of continuity at x,

 ,

For any natural n, take  and find a rational number , such that . Such always exists due to density of rationals. By choice of we have:

and by the sandwich theorem, converges: . Now, again, by choice of : , so y satisfies the condition on x' above and

Taking the (obviously existing) limits of both sides of this inequality, one gets

The case of y being 0 is trivial.

Oh. A monster function cannot be continuous even at a single point—it is discontinuous everywhere. Additive functions are divided into two separated classes: nice, everywhere continuous linear functions and  unseemly, everywhere discontinuous monsters. (We still don't know whether the latter class is populated, though.) Our expectations of capturing a monster and placing a trophy in a hall must be adjusted: even if we prove that a monster exists and construct it, an idea of drawing its graph must be abandoned—it's too ugly to be depicted.

Let's think for a moment how a monster might look like. Every additive function is linear on any -set. If it is linear with the same slope on all -sets—it is linear. A monster must have different slopes for at least some of -sets. In the simplest case there is a single -set with a slope different from the others. There is a famous function (a freshman nightmare and examiner delight) immediately coming into a mind: the Dirichlet function, , equal 1 on rationals and 0 on irrationals. The function  is identity (and hence linear) when restricted to rationals and is constant zero (again linear) when restricted to irrationals. Looks promising? Unfortunately,

Also, d is continuous at 0 and thus disqualified from monstrousness by statement 1. This shot into darkness missed. At at least we now see that not only monster must have different slopes at different -sets, but these slopes must be selected to be consistent with addition.

Let's return to monster properties. A monster function is discontinuous everywhere, but how badly is it discontinuous? E.g., a function is locally bounded at every point where it is continuous. A monster is continuous nowhere, but is it still locally bounded anywhere or somewhere? In a way similar to statement 1 it's easy to prove the

Statement 2. If an additive function is bounded on any segment [a, b], a < b, then it is linear.

First, by using that ,  and restricting segment if necessary, one can assume that , and .

Let's prove that f is continuous at 0, then it will be linear by the statement 1. For arbitrary , let's select , such that  (this choice is a typical magician hat trick of proofs). For arbitrary x from the -vicinity of 0 there is always a rational q, such that . For such q we have:

on the other hand, we have:

establishing that f is continuous at 0.

This indicates that a monster is not just a bad function, it's a very bad function, that takes arbitrarily large absolute values in arbitrarily small segments. Too bad. As a byproduct, a monster cannot be monotonic on any segment, because a function monotonic on [a, b] is bounded there:  (for increasing function, similarly for decreasing).

[continued.]