A Nonstandard Approach to Baire Category

Set theory and game theory

London

Richard Kaye

http://www.mat.bham.ac.uk/R.W.Kaye/

27th September 2000 Introduction.

This talk presents my attempts to understand the ideas of Baire category from a ‘logical point of view’, using nonstandard analysis as a tool.

As quoted in Models of Peano arithmetic:

‘Consider it logically,’ Valdez said. ‘What is my problem? To find Cathy. What do I know about Cathy? Nothing.’

‘That doesn’t sound so good,’ Marvin said.

‘But it is only half of the problem. Granted that I know nothing about Cathy, what do I know about Finding?’

‘What?’ Marvin asked.

‘It happens that I know everything about Finding,’ Valdez said triumphantly, gesturing with his graceful terracotta hands. ‘For it happens that I am an expert in the Theory of Searches!’

Robert Sheckley Mindswap

The starting point is the well-known observation that measure and category are analogous (or ‘dual’).

Standard result in the literature:

Theorem [Sierpiński–Erdős, CH.] There is a bijection f: ℝ → ℝ such that f^{−1} = f and for any set A ⊆ ℝ,

A has measure 0 ⇔ f′′A is meagre.

However this does not explain the situation completely.

In particular there is no analogue of the ‘measure’ function itself!

Since Lebesgue measure has a particularly nice presentation using nonstandard analysis (Löb), it’s natural to look for analogues of measure for Baire category using NSA, and based on combinatorial principles in nonstandard discrete spaces.

‘Measure’.

If measure and category are dual, a ‘measure’ for Baire categorical notions would be dual to Lebesgue measure.

I shall use the term ‘comeasure’ for the dual of ‘measure’. But I will only use this term informally.

Future project (?) An axiomatic approach to measure and comeasure.

Expected differences between measure and comeasure.

1. Measure takes values in a set with additive algebraic structure and order relation ⩽, whereas comeasure may be expected to have a multiplicative algebraic structure.

2. Measure is additive for disjoint sets, and more generally we have

m(A ∪ B) ⩽ m(A) + m(B),

on the other hand, comeasures would have

m(A ∩ B) ⩾ m(A) · m(B).

Large and small sets. Let X be a set. A notion of large subset of X is a collection L ⊆ 𝒫 X such that:

1. A ⊇ B ∈ L implies A ∈ L; and

2. A ∈ L implies A ≠ ∅. A notion of small subset of X is a collection S ⊆ 𝒫 X such that:

1. A ⊆ B ∈ S implies A ∈ S; and

2. A ∈ S implies A ≠ X. L^{c} =_{def} {A ⊆ X : A^{c} ∈ L} Dual. L^{†} =_{def} {A ⊆ X : A^{c} ∉ L}. Equivalently, L^{†} =_{def} {A ⊆ X : ∀B∈L A ∩ B ≠ ∅}. E.g., if X = [0, 1], take for L the sets of Lebesgue measure 1. Then L^{†} is the sets of nonzero outer measure.

Sample space.

Let X = [0, 1], and fix a sufficiently saturated nonstandard universe ^{∗}V.

Fix some N ∈ ^{∗}ℕ \ ℕ, and let

Ω =_{def} {n : n ∈ ^{∗}ℕ, 0 ⩽ n < N},
Ω/N =_{def} {n/N : n ∈ Ω}.

The standard part map Ω/N → X is denoted by st. (For this talk, this always has domain Ω/N, so for A ⊆ X, st^{−1}A is unambiguous.)

A set A ⊆ Ω/N is internal if it is the extension of a set in ^{∗}V.

It is convex if ∀u, v, w ∈ Ω/N (u<v<w & u, w∈A ⇒ v∈A).

Lebesgue measure.

The measure, μ(B), of an internal B ⊆ Ω/N is ^{∗}card (B). The normalized measure, μ̂(B), is

\frac{^{∗}card (B)}{^{∗}card (Ω/N)} = \frac{^{∗}card (B)}{N} .

Also define

∘μ(B) =_{def} st μ̂(B).

A set A ⊆ X has outer Lebesgue measure

\overline{λ}(A) = inf \{^{∘}μ(B) : B ⊆ Ω internal , B ⊇ st^{−1}A\}

and inner Lebesgue measure given by

λ(A) = sup {^{∘}μ(B) : B ⊆ Ω internal , B ⊆ st^{−1}A}.

If these agree then A is Lebesgue measurable with Lebesgue measure λ(A) = λ(A) = \overline{λ}(A).

Baire category.

Fix X = [0, 1], with the usual topology.

A corare set is one whose interior is dense in X. A rare set is the complement in X of a corare set.

A comeagre set is the intesection of countably many corare sets. A meagre set is the complement in X of a comeagre set.

Alternative terminology:

1. comeagre = residual

2. meagre = 1st category

3. not meagre = 2nd category

A set has the property of Baire if it is the symmetric difference of an open set with a meagre set.

A comeasure for corare sets. For x ∈ Ω, an x-interval of Ω/N is an internal convex I ⊆ Ω/N with ^{∗}card (I) = x. A y-subinterval of such I is B ⊆ I which is also a y-interval. Definition. If B ⊆ Ω/N is internal, δ(B) is the internal function δ(B): Ω → Ω defined by x ↦ max {y : every x-interval of Ω/N contains a y-subinterval I ⊆ B }. By convention, δ(B)(0) = 0. The normalized version δ̂(B): Ω/N → Ω/N is

δ̂(B)(x) = (δ(NB)(Nx))/N

where NB = {Nb : b ∈ B}.

Lemma. For x, y ∈ Ω and internal B, C ⊆ Ω:

i) x ⩽ y ⇒ δ(B)(x) ⩽ δ(B)(y); ii) 0 ⩽ δ(B)(x) ⩽ x; iii) if B ⊆ C then δ(B)(x) ⩽ δ(C)(x); iv) δ(B ∩ C)(x) ⩾ δ(B) ∘ δ(C) (x);

v) δ(B)(x) ⩽ δ(B)(x + 1) ⩽ δ(B)(x) + 1; vi) δ(B)(x) ⩽ δ(B)(x + y) ⩽ δ(B)(x) + y.

For internal B ⊆ Ω/N, ^{∘}δ(B): [0, 1] → [0, 1] is defined by ^{∘}δ(B)(st x) = st δ̂(B)(x).

𝔉 =_{def} set of continuous functions f: [0, 1] → [0, 1] such that

0 ⩽ f(x_{1}) − f(x_{0}) ⩽ x_{1} − x_{0}

for all x_{0} ⩽ x_{1} in [0, 1]. (Such f are necessarily nondecreasing with f(0) = 0.)

For f, g ∈ 𝔉, f ⩽ g ⇔ f(x) ⩽ g(x) for all x ∈ [0, 1] f ∘ g is the composite x ↦ f(g(x)).

Lemma. For internal B, C ⊆ Ω:

i) ^{∘}δ(B) ∈ 𝔉;

ii) if A ⊆ B then ^{∘}δ(A) ⩽ ^{∘}δ(B);

iii) ^{∘}δ(A ∩ B) ⩾ ^{∘}δ(A) ∘^{∘}δ(B); ρ-comeasure.

Define the outer comeasure of A ⊆ [0, 1] by \overline{ρ}(A) = ⋀\{^{∘}δ(B) : B ⊆ Ω internal , B ⊇ st^{−1}A\} and the inner comeasure by ρ(A) = ⋁{^{∘}δ(B) : B ⊆ Ω internal , B ⊆ st^{−1}A}.

These are well-defined, e.g., because \overline{ρ}(A) (x) = inf \{^{∘}δ(B)(x) : B ⊆ Ω internal B ⊇ st^{−1}A \} .

ρ(A) is the common value of these two when they agree.

Results on the ρ-comeasure.

1. Every A ⊆ X is ρ-comeasurable.

2. A is dense in X iff ^{∘}δ(B)(x) > 0 for all internal B ⊇ st^{−1}A and all x > 0.

3. A is corare in X iff there is f ∈ 𝔉 such that f(x) > 0 for all x > 0, and ^{∘}δ(B) ⩾ f for all internal B ⊇ st^{−1}A.

[Compare with: A has nonzero outer Lebesgue measure if there is ϵ > 0 such that ^{∘}μ(B) ⩾ ϵ for all internal B ⊇ st^{−1}A.]

Let 𝔊 be the set of germs of f ∈ 𝔉 at 0, that is, 𝔊 = 𝔉/∼ where

f ∼ g ⇔ ∃y > 0 ∀x < y f(x) = g(x).

4. A is corare in X iff there is g ∈ 𝔊 such that g > 0 and ^{∘}δ(B)/∼ ⩾ g for all internal B ⊇ st^{−1}A.

Comeagre sets. There is a problem applying this to comeagre sets! Our 𝔊 has the ‘no-zero divisors property’,

f/∼ ∘ g/∼ = 0 ⇒ f/∼ = 0 or g/∼ = 0, but not the ‘no σ-zero divisors property’,

_{n∈ω}^{⋀}(f_{n}/∼ ∘ ⋯ ∘ f_{1}/∼ ∘ f_{0}/∼) = 0

⇒ f_{i}/∼ = 0 for some i ∈ ω .

One solution might be to ‘artificially’ complete 𝔊.

Definition. ℌ is the set ω-sequences (g_{i})_{i∈ω} from 𝔊 which are monotonic nonincreasing (i ⩽ j ⇒ g_{i} ⩾ g_{j}) modulo the equivalence ≡ given by

(g_{i})_{i∈ω} ⪯ (h_{i})_{i∈ω} ⇔ ∀i ∃j > i g_{j} ⩽ h_{i}

and

(g_{i}) ≡ (h_{i}) ⇔ (g_{i}) ⪯ (h_{i}) & (h_{i}) ⪯ (g_{i})

Definition.

α(A) = ⋁ { (g_{i})/≡ : A = ⋂_{i∈ω} A_{i} ; A_{0} ⊇ A_{1} ⊇ A_{2} ⊇ ⋯; g_{i} = ρ(A_{i})/∼ }

Theorem. A ⊆ [0, 1] is comeagre iff there is h > 0 in ℌ such that

α(B) ⩾ h for all B ⊇ A for which α(B) is defined .

Question: For which B ⊆ [0, 1] is α(B) defined?

A nonstandard version of the Banach–Mazur game.

Let ℐ be the set of all internal intervals of Ω/N, and let ℐ^{+} be the set of all I ∈ ℐ with ∘μI > 0.

These correspond to ‘standard’ intervals via the standard-part map

∘I = {st(x) : x ∈ I}

and

∘ℐ = {^{∘}I : I ∈ ℐ }

Theorem. A ⊆ X is comeagre iff there is an internal f: ℐ → ℐ such that:

1. f(I) ⊆ I for all I;

2. if I ∈ ℐ^{+} then f(I) ∈ ℐ^{+} ;

3. whenever B ⊇ st^{−1}A is internal and

I_{0} ⊇ I_{1} ⊇ I_{2} ⊇ ⋯

is an internal sequence of intervals in ℐ^{+} with I_{i+1} ⊆ f(I_{i}) for all i then there is n ∈ ℕ such that I_{n} ⊆ B.

The function f can always be chosen so that

f(I) ⊆ J ⊆ I ⇒ f(I) = f(J)

and for any maximal chain of open intervals 𝒞 ⊆ ^{∘}ℐ , the map 𝒞 → [0, 1] given by

∘I ↦ λ(^{∘}f(I))

is well-defined and continuous.

Internal functions on intervals.

Suppose f: ℐ → ℐ is internal such that

1. f(I) ⊆ I for all I;

2. for an end-point x of I and J = I \ {x}, either f(I) = f(J) or x ∈ f(I) and

∗card f(J) + 1 ⩾ ^{∗}card f(I) ⩾ card f(J); Then

δ̂(f): Ω/N → Ω/N

may be defined by δ̂(f)(x) = min {μ̂(fI) : I ∈ ℐ , μ̂(I) ⩾ x}.

The function ^{∘}δ(f): [0, 1] → [0, 1] defined by

∘δ(f)(st x) = st δ̂(f)(x)

is well-defined, continuous, and in 𝔉. It seems that ^{∘}δ(f)/∼ gives a good ‘measure’ of f.

Strategies for A ⊆ X.

Say f: ℐ → ℐ is a strategy for A ⊆ X if:

1. f(I) ⊆ I for all I;

2. I ⊆ J implies f(I) ⊆ f(J) for all I, J;

3. whenever B ⊇ st^{−1}A is internal and I_{0} ⊇ I_{1} ⊇ I_{2} ⊇ ⋯

is an internal sequence of intervals in ℐ with I_{i+1} ⊆ f(I_{i}) for all i then there is n ∈ ℕ s.t.

either I_{n+1} ∉ ℐ^{+} and f(I_{i}) ∈ ℐ^{+} or I_{n} ⊆ B;

4. f has the ‘continuity’ property on the previous slide.

Define, β(A) =_{def} ⋁{^{∘}δ(f)/∼: f is a strategy for A } Work remaining.

We just defined an ‘inner’ comeasure characterizing the comeagre sets. An ‘outer comeasure’ was expected, and is needed to develop these ideas further.

Something like

\overline{β}(A) =_{def} ⋀\{^{∘}δ(f)/∼: f covers A \}

(But what does ‘covers’ mean?)

Or,

\overline{β}(A) =_{def} ⋀ \{^{∘}δ(f)/∼: f is a best strategy for some B ⊇ st^{−1}A \}

(But what are these nonstandard finite games, and what does ‘best’ mean?)