Descriptive set theory

Descriptive set theory

Descriptive set theory: classical and effective

I Classical descriptive set theory was founded by people like Baire, Borel, Lebesgue, Luzin, Suslin, Sierpinskpi and others in the first two decades of the XXth century. It studies the descriptive complexity of sets of real numbers.

I Effective descriptive set theory was created later by introducing into the classical theory the new and powerful tools developed from recursion theory.

Descriptive set theory: classical and effective

I Classical descriptive set theory was founded by people like Baire, Borel, Lebesgue, Luzin, Suslin, Sierpinskpi and others in the first two decades of the XXth century. It studies the descriptive complexity of sets of real numbers.

I Effective descriptive set theory was created later by introducing into the classical theory the new and powerful tools developed from recursion theory.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T1and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T1and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods;

equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T1and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T1and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T₁and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T₁and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T₁and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets.

The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T₁and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T₁and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d .

Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Let X be a topological space.

I X is T1if given x , y ∈ X there is a neighbourhood of x that does not contain y (and viceversa); equivalently, every singleton is closed.

I X is regular if X is T1and whenever x ∈ X , A ⊆ X , A is closed and x /∈ A, point x and set A have disjoint neighbourhoods; equivalently, x is T1and for all x and any open neighbourhood U of x , there is an open neighbourhood V of x with ¯V ⊆ U.

I X is normal if X is T₁and any two disjoint closed subsets have disjoint neighbourhoods.

I X is Baire if the intersection of countably many open dense sets is dense.

I A subset of X is Gδ if it is a countable intersection of open sets. The complement of a Gδ is an Fσ set: a countable union of closed sets.

I If (X , d ) is a metric space, then d⁰= _1+d^d is a metric compatible with d . Notice that d⁰ ≤ 1 and d is complete iff d⁰ is complete.

Basic review on topological and metric spaces

Urysohn’s theorem. Let X be second countable. Then X is metrisable iff it is regular.

Urysohn’s lemma. If X is metrisable and A, B ⊆ X are closed and disjoint, then ∃f : X → [0, 1] continuous s.t. f (A) ⊆ {0}, f (B) ⊆ {1}. Tietze’s extension theorem. If X is metrisable, A ⊆ X is closed and f : A → R is continuous, then ∃g : X → R continuous s.t. f ⊆ g . If moreover sup f ≤ M, then one can find g with sup g ≤ M.

Basic review on topological and metric spaces

Urysohn’s theorem. Let X be second countable. Then X is metrisable iff it is regular.

Urysohn’s lemma. If X is metrisable and A, B ⊆ X are closed and disjoint, then ∃f : X → [0, 1] continuous s.t. f (A) ⊆ {0}, f (B) ⊆ {1}.

Tietze’s extension theorem. If X is metrisable, A ⊆ X is closed and f : A → R is continuous, then ∃g : X → R continuous s.t. f ⊆ g . If moreover sup f ≤ M, then one can find g with sup g ≤ M.

Basic review on topological and metric spaces

Urysohn’s theorem. Let X be second countable. Then X is metrisable iff it is regular.

Urysohn’s lemma. If X is metrisable and A, B ⊆ X are closed and disjoint, then ∃f : X → [0, 1] continuous s.t. f (A) ⊆ {0}, f (B) ⊆ {1}.

Tietze’s extension theorem. If X is metrisable, A ⊆ X is closed and f : A → R is continuous, then ∃g : X → R continuous s.t. f ⊆ g .

If moreover sup f ≤ M, then one can find g with sup g ≤ M.

Basic review on topological and metric spaces

Urysohn’s theorem. Let X be second countable. Then X is metrisable iff it is regular.

Urysohn’s lemma. If X is metrisable and A, B ⊆ X are closed and disjoint, then ∃f : X → [0, 1] continuous s.t. f (A) ⊆ {0}, f (B) ⊆ {1}.

Tietze’s extension theorem. If X is metrisable, A ⊆ X is closed and f : A → R is continuous, then ∃g : X → R continuous s.t. f ⊆ g . If moreover sup f ≤ M, then one can find g with sup g ≤ M.

Trees

Definition

I T is a (descriptive) tree on set A if T is non-empty, T ⊆ A^<ω and T is closed under subsequences.

I If T is a tree on A, then [T ] = {f ∈ A^N| ∀n f |n∈ T } is the body of T .

Example. [2^<ω] = 2^Nis the Cantor space.

Trees

Definition

I T is a (descriptive) tree on set A if T is non-empty, T ⊆ A^<ω and T is closed under subsequences.

I If T is a tree on A, then [T ] = {f ∈ A^N| ∀n f |n∈ T } is the body of T .

Example. [2^<ω] = 2^Nis the Cantor space.

Trees

Definition

I T is a (descriptive) tree on set A if T is non-empty, T ⊆ A^<ω and T is closed under subsequences.

I If T is a tree on A, then [T ] = {f ∈ A^N| ∀n f |n∈ T } is the body of T .

Example. [2^<ω] = 2^N

is the Cantor space.

Trees

Definition

I T is a (descriptive) tree on set A if T is non-empty, T ⊆ A^<ω and T is closed under subsequences.

I If T is a tree on A, then [T ] = {f ∈ A^N| ∀n f |n∈ T } is the body of T .

Example. [2^<ω] = 2^Nis the Cantor space.

A metric on A^N

d (a, b) =

 0 if a = b

1

2ⁿ if n is least with a(n) 6= b(n) is a ultrametric on A^N, i.e. a metric such that

d (a, b) ≤ max(d (a, c), d (c, b)). Exercise. Check this.

Open balls centered in g ∈ A^Nare sets of the form N_{g |n} = {f ∈ A^N| g |n= f |n} for n ∈ N.

Thus d is compatible with the product topology on A^N, where A is given the discrete topology.

A metric on A^N

d (a, b) =

 0 if a = b

1

2ⁿ if n is least with a(n) 6= b(n) is a ultrametric on A^N, i.e. a metric such that

d (a, b) ≤ max(d (a, c), d (c, b)). Exercise. Check this.

Open balls centered in g ∈ A^Nare sets of the form N_{g |n} = {f ∈ A^N| g |n= f |n} for n ∈ N.

Thus d is compatible with the product topology on A^N, where A is given the discrete topology.

A metric on A^N

d (a, b) =

 0 if a = b

1

2ⁿ if n is least with a(n) 6= b(n)

is a ultrametric on A^N, i.e. a metric such that d (a, b) ≤ max(d (a, c), d (c, b)).

Exercise. Check this.

Open balls centered in g ∈ A^Nare sets of the form N_{g |n} = {f ∈ A^N| g |n= f |n} for n ∈ N.

Thus d is compatible with the product topology on A^N, where A is given the discrete topology.

A metric on A^N

d (a, b) =

 0 if a = b

1

2ⁿ if n is least with a(n) 6= b(n) is a ultrametric on A^N, i.e. a metric such that

d (a, b) ≤ max(d (a, c), d (c, b)).

Exercise. Check this.

Open balls centered in g ∈ A^Nare sets of the form N_{g |n} = {f ∈ A^N| g |n= f |n} for n ∈ N.

Thus d is compatible with the product topology on A^N, where A is given the discrete topology.

A metric on A^N

d (a, b) =

 0 if a = b

1

2ⁿ if n is least with a(n) 6= b(n) is a ultrametric on A^N, i.e. a metric such that

d (a, b) ≤ max(d (a, c), d (c, b)).

Exercise. Check this.

Open balls centered in g ∈ A^Nare sets of the form N_{g |n} = {f ∈ A^N| g |n= f |n} for n ∈ N.

Thus d is compatible with the product topology on A^N, where A is given the discrete topology.

A metric on A^N

d (a, b) =

 0 if a = b

1

2ⁿ if n is least with a(n) 6= b(n) is a ultrametric on A^N, i.e. a metric such that

d (a, b) ≤ max(d (a, c), d (c, b)).

Exercise. Check this.

Open balls centered in g ∈ A^Nare sets of the form N_{g |n} = {f ∈ A^N| g |n= f |n} for n ∈ N.

Thus d is compatible with the product topology on A^N, where A is given the discrete topology.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N. For any m, eventually all fn’s will have the first n digits fixed. These digits define an element f ∈ A^Nsuch that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable. This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N.

For any m, eventually all fn’s will have the first n digits fixed. These digits define an element f ∈ A^Nsuch that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable. This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N. For any m, eventually all fn’s will have the first n digits fixed.

These digits define an element f ∈ A^Nsuch that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable. This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N. For any m, eventually all fn’s will have the first n digits fixed. These digits define an element f ∈ A^N

such that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable. This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N. For any m, eventually all fn’s will have the first n digits fixed. These digits define an element f ∈ A^Nsuch that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable. This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N. For any m, eventually all fn’s will have the first n digits fixed. These digits define an element f ∈ A^Nsuch that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable.

This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

A metric on A^N

Proposition

d is a complete metric.

Proof.

Let fn be a Cauchy sequence in A^N. For any m, eventually all fn’s will have the first n digits fixed. These digits define an element f ∈ A^Nsuch that limn→∞fn= f .

Notice that A^N is separable if (and only if) A is at most countable.

This is a first example and will consitute the motivating example for the first fundamental definition, that of a Polish space.

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s. Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}. Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω| st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes:

∀t ∈ T ∃s ∈ T t ⊂ s. Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}. Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω| st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s.

Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}. Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω| st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s.

Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}. Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω| st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s.

Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}.

Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω| st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s.

Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}.

Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω| st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s.

Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}.

Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω | st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

A tree T is pruned if it has no terminal nodes: ∀t ∈ T ∃s ∈ T t ⊂ s.

Example. Finite non-empty trees are not pruned.

Exercise. The map T 7→ [T ] is a bijection between pruned trees on A and closed subsets of A^N. Its inverse is F 7→ TF = {x |n| x ∈ F , n ∈ N}.

Some induced trees. If T is a tree on A and s ∈ A^<ω, then the following are trees on A:

I Ts = {t ∈ A^<ω | st ∈ T }

I T_[s]= {t ∈ T | t is compatible with s}

Basics on trees

Definition

Let T a tree on A and S a tree on B.

A function ϕ : T → S is monotone if

∀t1, t2∈ T (t1⊆ t2⇒ ϕ(t1) ⊆ t2)

Let D(ϕ) = {x ∈ [T ] | limn→∞length(ϕ(x |n)) = +∞}. Then one can define

ϕ^∗(x ) = [

n∈N

ϕ(x |n) ∈ [S ]

Exercise. D(ϕ) is G_δ in [T ] and ϕ^∗: D(ϕ) → [S ] is continuous.

Basics on trees

Definition

Let T a tree on A and S a tree on B. A function ϕ : T → S is monotone if

∀t₁, t₂∈ T (t₁⊆ t₂⇒ ϕ(t₁) ⊆ t₂)

Let D(ϕ) = {x ∈ [T ] | limn→∞length(ϕ(x |n)) = +∞}. Then one can define

ϕ^∗(x ) = [

n∈N

ϕ(x |n) ∈ [S ]

Exercise. D(ϕ) is G_δ in [T ] and ϕ^∗: D(ϕ) → [S ] is continuous.

Basics on trees

Definition

Let T a tree on A and S a tree on B. A function ϕ : T → S is monotone if

∀t₁, t₂∈ T (t₁⊆ t₂⇒ ϕ(t₁) ⊆ t₂)

Let D(ϕ) = {x ∈ [T ] | limn→∞length(ϕ(x |n)) = +∞}.

Then one can define

ϕ^∗(x ) = [

n∈N

ϕ(x |n) ∈ [S ]

Exercise. D(ϕ) is G_δ in [T ] and ϕ^∗: D(ϕ) → [S ] is continuous.

Basics on trees

Definition

Let T a tree on A and S a tree on B. A function ϕ : T → S is monotone if

∀t₁, t₂∈ T (t₁⊆ t₂⇒ ϕ(t₁) ⊆ t₂)

Let D(ϕ) = {x ∈ [T ] | limn→∞length(ϕ(x |n)) = +∞}. Then one can define

ϕ^∗(x ) = [

n∈N

ϕ(x |n)

∈ [S]

Exercise. D(ϕ) is G_δ in [T ] and ϕ^∗: D(ϕ) → [S ] is continuous.

Basics on trees

Definition

Let T a tree on A and S a tree on B. A function ϕ : T → S is monotone if

∀t₁, t₂∈ T (t₁⊆ t₂⇒ ϕ(t₁) ⊆ t₂)

Let D(ϕ) = {x ∈ [T ] | limn→∞length(ϕ(x |n)) = +∞}. Then one can define

ϕ^∗(x ) = [

n∈N

ϕ(x |n)∈ [S]

Exercise. D(ϕ) is G_δ in [T ] and ϕ^∗: D(ϕ) → [S ] is continuous.

Basics on trees

Definition

Let T a tree on A and S a tree on B. A function ϕ : T → S is monotone if

∀t₁, t₂∈ T (t₁⊆ t₂⇒ ϕ(t₁) ⊆ t₂)

Let D(ϕ) = {x ∈ [T ] | limn→∞length(ϕ(x |n)) = +∞}. Then one can define

ϕ^∗(x ) = [

n∈N

ϕ(x |n)∈ [S]

Exercise. D(ϕ) is G_δ in [T ] and ϕ^∗: D(ϕ) → [S ] is continuous.

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

Polish spaces

Definition

I A Polish space is a separable, completely metrisable topological space

I A Polish metric space is a separable metric space (X , d ) such that d is complete

Basic properties.

I Any Polish space is second countable and normal

I A finite or countable product of Polish spaces is Polish

I (Baire category theorem) Polish spaces are Baire (in fact every completely metrisable space is Baire)

I A quotient of a Polish space and a subspace of a Polish space are not necessarily Polish

I A closed subspace of a Polish space is Polish

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1]

via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹

I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1])

, using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.

First examples.

I All countable discrete spaces

I Cantor space 2^N

Exercise. Prove that is homeomorphic to the ¹₃-Cantor set E1

3 ⊆ [0, 1] via x 7→P∞ n=0

2x (n) 3ⁿ⁺¹ I Baire space N^N

Exercise. Prove that it is homeomorphic to R \ Q (equivalently, to (R \ Q) ∩ [0, 1]), using continued fractions.

I Rⁿ, R^N

I ]0, 1[, {z ∈ C | |z| = 1}, [0, 1]

I Hilbert cube [0, 1]^N

I All separable Banach spaces

Exercise. Compact metrisable spaces are Polish.