Complexity in set theory (and beyond)

Complexity in set theory (and beyond)

Riccardo Camerlo

What is complexity?

In its most general form, the notion of complexity seems to be identifiable with that of a preorder (a reflexive, transitive relation):

A ≤ B

means: A is at most as complex as B (whatever A and B are)

What is complexity?

The point is to identify a good way of comparing A and B, in order to state that

A ≤ B

To explore the notion of complexity, descriptive set theory exploits the

concepts of definability and topological complexity.

What is complexity?

The point is to identify a good way of comparing A and B, in order to state that

A ≤ B

To explore the notion of complexity, descriptive set theory exploits the

concepts of definability and topological complexity.

Polish spaces

The most basic objects investigated by descriptive set theory are Polish spaces.

Definition

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

Examples.

I

Countable, discrete spaces; R; real intervals; R \ Q; C; R

; Cantor space 2

; Baire space N

I

Q is not a Polish space

Polish spaces

The most basic objects investigated by descriptive set theory are Polish spaces.

Definition

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

Examples.

I

Countable, discrete spaces; R; real intervals; R \ Q; C; R

; Cantor space 2

; Baire space N

I

Q is not a Polish space

Polish spaces

The most basic objects investigated by descriptive set theory are Polish spaces.

Definition

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

Examples.

I

Countable, discrete spaces; R; real intervals; R \ Q; C; R

; Cantor space 2

; Baire space N

I

Q is not a Polish space

Polish spaces

Theorem

A subspace Y of a Polish space X is Polish if and only if it is G

— i.e., a countable intersection of open sets.

Remark. Unless Y is closed, a complete metric in Y is not the restriction of a complete metric on X .

Example. The usual (Euclidean) metric on R \ Q is not complete.

However, N

w R \ Q via continued fractions.

Polish spaces

Theorem

A subspace Y of a Polish space X is Polish if and only if it is G

— i.e., a countable intersection of open sets.

Remark. Unless Y is closed, a complete metric in Y is not the restriction of a complete metric on X .

Example. The usual (Euclidean) metric on R \ Q is not complete.

However, N

w R \ Q via continued fractions.

Polish spaces

Theorem

A subspace Y of a Polish space X is Polish if and only if it is G

— i.e., a countable intersection of open sets.

Remark. Unless Y is closed, a complete metric in Y is not the restriction of a complete metric on X .

Example. The usual (Euclidean) metric on R \ Q is not complete.

However, N

w R \ Q via continued fractions.

Definability: Borel sets

The subsets of a topological space X can be classified according to the number of operations (complementation, countable unions) to perform to obtain them starting with open sets:

G = open F

G

F

. . . F = closed G

F

G

. . . in logical notation:

Σ

Σ

Σ

Σ

. . . Σ

Σ

. . . Π

Π

Π

Π

. . . Π

Π

. . . This sequence stabilises at some ordinal α ≤ ω

.

However, in general, B = S

α∈ω₁

Σ

6= P(X ). In fact, B is the σ-algebra

of Borel subsets of X .

Definability: Borel sets

The subsets of a topological space X can be classified according to the number of operations (complementation, countable unions) to perform to obtain them starting with open sets:

G = open F

G

F

. . . F = closed G

F

G

. . .

in logical notation:

Σ

Σ

Σ

Σ

. . . Σ

Σ

. . . Π

Π

Π

Π

. . . Π

Π

. . . This sequence stabilises at some ordinal α ≤ ω

.

However, in general, B = S

α∈ω₁

Σ

6= P(X ). In fact, B is the σ-algebra

of Borel subsets of X .

Definability: Borel sets

The subsets of a topological space X can be classified according to the number of operations (complementation, countable unions) to perform to obtain them starting with open sets:

G = open F

G

F

. . . F = closed G

F

G

. . . in logical notation:

Σ

Σ

Σ

Σ

. . . Σ

Σ

. . . Π

Π

Π

Π

. . . Π

Π

. . .

This sequence stabilises at some ordinal α ≤ ω

. However, in general, B = S

α∈ω₁

Σ

6= P(X ). In fact, B is the σ-algebra

of Borel subsets of X .

Definability: Borel sets

The subsets of a topological space X can be classified according to the number of operations (complementation, countable unions) to perform to obtain them starting with open sets:

G = open F

G

F

. . . F = closed G

F

G

. . . in logical notation:

Σ

Σ

Σ

Σ

. . . Σ

Σ

. . . Π

Π

Π

Π

. . . Π

Π

. . . This sequence stabilises at some ordinal α ≤ ω

.

However, in general, B = S

α∈ω₁

Σ

6= P(X ). In fact, B is the σ-algebra

of Borel subsets of X .

Definability: Borel sets

The subsets of a topological space X can be classified according to the number of operations (complementation, countable unions) to perform to obtain them starting with open sets:

G = open F

G

F

. . . F = closed G

F

G

. . . in logical notation:

Σ

Σ

Σ

Σ

. . . Σ

Σ

. . . Π

Π

Π

Π

. . . Π

Π

. . . This sequence stabilises at some ordinal α ≤ ω

.

However, in general, B = S

α∈ω₁

Σ

6= P(X ). In fact, B is the σ-algebra

of Borel subsets of X .

Projective sets

The preceding hierarchy can be enlarged by taking continuous images:

A PCA PCPA . . .

B

CA CPCA CPCPA . . .

in logical notation:

Σ

Σ

Σ

. . . B

Π

Π

Π

. . .

Projective sets

The preceding hierarchy can be enlarged by taking continuous images:

A PCA PCPA . . .

B

CA CPCA CPCPA . . . in logical notation:

Σ

Σ

Σ

. . . B

Π

Π

Π

. . .

What is this good for?

An example: sets of uniqueness for trigonometric series A set E ⊆ S

is a set of uniquess if any trigonometric series P

n=−∞

c

e

that is 0 outside E has all coefficients c

= 0.

Classically, several characterisations of sets of uniqueness have been conjectured. All of these where described by formulas built up mixing countable quantifications and Borel operations on sets. Consequently, restricted to the Polish space of compact subsets of S

, they identify a Borel subset.

However Kaufmann and Solovay proved that the class of sets of

uniqueness is not Borel, so none of the proposed characterisation can

work (and — in some sense — no satisfactory characterisation can exist).

What is this good for?

An example: sets of uniqueness for trigonometric series A set E ⊆ S

is a set of uniquess if any trigonometric series P

n=−∞

c

e

that is 0 outside E has all coefficients c

= 0.

Classically, several characterisations of sets of uniqueness have been conjectured. All of these where described by formulas built up mixing countable quantifications and Borel operations on sets.

Consequently, restricted to the Polish space of compact subsets of S

, they identify a Borel subset.

However Kaufmann and Solovay proved that the class of sets of

uniqueness is not Borel, so none of the proposed characterisation can

work (and — in some sense — no satisfactory characterisation can exist).

What is this good for?

An example: sets of uniqueness for trigonometric series A set E ⊆ S

is a set of uniquess if any trigonometric series P

n=−∞

c

e

that is 0 outside E has all coefficients c

= 0.

Classically, several characterisations of sets of uniqueness have been conjectured. All of these where described by formulas built up mixing countable quantifications and Borel operations on sets. Consequently, restricted to the Polish space of compact subsets of S

, they identify a Borel subset.

However Kaufmann and Solovay proved that the class of sets of

uniqueness is not Borel, so none of the proposed characterisation can

work (and — in some sense — no satisfactory characterisation can exist).

What is this good for?

An example: sets of uniqueness for trigonometric series A set E ⊆ S

is a set of uniquess if any trigonometric series P

n=−∞

c

e

that is 0 outside E has all coefficients c

= 0.

Classically, several characterisations of sets of uniqueness have been conjectured. All of these where described by formulas built up mixing countable quantifications and Borel operations on sets. Consequently, restricted to the Polish space of compact subsets of S

, they identify a Borel subset.

However Kaufmann and Solovay proved that the class of sets of

uniqueness is not Borel, so none of the proposed characterisation can

work (and — in some sense — no satisfactory characterisation can exist).

The Wadge hierarchy

All preceding classes of sets are invariant under continuous preimages. A finer way to compare subsets of a topological space X is the Wadge hierarchy

: given A, B ⊆ X ,

A ≤

B ⇔ ∃f : X → X continuous s.t. A = f

(B) Say: A continuously reduces (or Wadge reduces to B).

The equivalence classes [A]

associated to the preorder ≤

are the Wadge degrees.

The single most important and best studied space from the point of view

of Wadge reducibility is Baire space N

. This is because of the existence

of a powerful tool: Wadge game.

The Wadge hierarchy

All preceding classes of sets are invariant under continuous preimages. A finer way to compare subsets of a topological space X is the Wadge hierarchy: given A, B ⊆ X ,

A ≤

B ⇔ ∃f : X → X continuous s.t. A = f

(B) Say: A continuously reduces (or Wadge reduces to B).

The equivalence classes [A]

associated to the preorder ≤

are the Wadge degrees.

The single most important and best studied space from the point of view

of Wadge reducibility is Baire space N

. This is because of the existence

of a powerful tool: Wadge game.

The Wadge hierarchy

All preceding classes of sets are invariant under continuous preimages. A finer way to compare subsets of a topological space X is the Wadge hierarchy: given A, B ⊆ X ,

A ≤

B ⇔ ∃f : X → X continuous s.t. A = f

(B) Say: A continuously reduces (or Wadge reduces to B).

The equivalence classes [A]

associated to the preorder ≤

are the Wadge degrees.

The single most important and best studied space from the point of view

of Wadge reducibility is Baire space N

. This is because of the existence

of a powerful tool: Wadge game.

Wadge game

Wadge game is a two-players, zero-sum, perfect information game.

Fix A, B ⊆ N

. Players I and II alternate rounds, playing natural numbers. Player II is allowed to skip:

I x

x

x

x

x

x

. . .

II y

y

skip y

skip y

. . .

Let x , y be the sequences played by I, II, resp.

Player II wins this run of the game G

(A, B) if and only if:

• y is infinite (i.e., II played infinitely many times); and

• x ∈ A ⇔ y ∈ B

Wadge game

Wadge game is a two-players, zero-sum, perfect information game.

Fix A, B ⊆ N

. Players I and II alternate rounds, playing natural numbers. Player II is allowed to skip:

I x

x

x

x

x

x

. . .

II y

y

skip y

skip y

. . .

Let x , y be the sequences played by I, II, resp.

Player II wins this run of the game G

(A, B) if and only if:

• y is infinite (i.e., II played infinitely many times); and

• x ∈ A ⇔ y ∈ B

Wadge game

Wadge game is a two-players, zero-sum, perfect information game.

Fix A, B ⊆ N

. Players I and II alternate rounds, playing natural numbers. Player II is allowed to skip:

I x

x

x

x

x

x

. . .

II y

y

skip y

skip y

. . .

Let x , y be the sequences played by I, II, resp.

Player II wins this run of the game G

(A, B) if and only if:

• y is infinite (i.e., II played infinitely many times); and

• x ∈ A ⇔ y ∈ B

Wadge game

Wadge game is a two-players, zero-sum, perfect information game.

Fix A, B ⊆ N

. Players I and II alternate rounds, playing natural numbers. Player II is allowed to skip:

I x

x

x

x

x

x

. . .

II y

y

skip y

skip y

. . .

Let x , y be the sequences played by I, II, resp.

Player II wins this run of the game G

(A, B) if and only if:

• y is infinite (i.e., II played infinitely many times); and

• x ∈ A ⇔ y ∈ B

Wadge game

Wadge game is a two-players, zero-sum, perfect information game.

Fix A, B ⊆ N

. Players I and II alternate rounds, playing natural numbers. Player II is allowed to skip:

I x

x

x

x

x

x

. . .

II y

y

skip y

skip y

. . .

Let x , y be the sequences played by I, II, resp.

Player II wins this run of the game G

(A, B) if and only if:

• y is infinite (i.e., II played infinitely many times); and

• x ∈ A ⇔ y ∈ B

Wadge game

Wadge game is a two-players, zero-sum, perfect information game.

Fix A, B ⊆ N

. Players I and II alternate rounds, playing natural numbers. Player II is allowed to skip:

I x

x

x

x

x

x

. . .

II y

y

skip y

skip y

. . .

Let x , y be the sequences played by I, II, resp.

Player II wins this run of the game G

(A, B) if and only if:

• y is infinite (i.e., II played infinitely many times); and

• x ∈ A ⇔ y ∈ B

Wadge game

Fact. Given A, B ⊆ N

one has that A ≤

B is and only if player II has a winning strategy in G

(A, B).

By Martin’s Borel determinacy, if A, B are Borel, then one of the two players has a winning strategy in G

(A, B).

Using this, the structure of ≤

restricted to Borel sets becomes transparent. Most notably, ≤

satisfies the Wadge duality principle on Borel subsets: given A, B Borel,

A ≤

B or N

\ B ≤

A

Wadge game

Fact. Given A, B ⊆ N

one has that A ≤

B is and only if player II has a winning strategy in G

(A, B).

By Martin’s Borel determinacy, if A, B are Borel, then one of the two players has a winning strategy in G

(A, B).

Using this, the structure of ≤

restricted to Borel sets becomes transparent.

Most notably, ≤

satisfies the Wadge duality principle on Borel subsets: given A, B Borel,

A ≤

B or N

\ B ≤

A

Wadge game

Fact. Given A, B ⊆ N

one has that A ≤

B is and only if player II has a winning strategy in G

(A, B).

By Martin’s Borel determinacy, if A, B are Borel, then one of the two players has a winning strategy in G

(A, B).

Using this, the structure of ≤

restricted to Borel sets becomes transparent. Most notably, ≤

satisfies the Wadge duality principle on Borel subsets: given A, B Borel,

A ≤

B or N

\ B ≤

A

Wadge hierarchy on Borel sets

The Wadge hierarchy on Borel subsets of N

goes as follows:

{∅} Σ

D

(Σ

) . . .

∆

∆(D

(Σ

)) . . . {N

} Π

D ˇ

(Σ

) . . . The first ω

levels are occupied by sets that are both F

and G

.

Remark. (Under AC ) This semi-linearity does not extend to all subsets of N

: if A is true G

and B is a Bernstein set, then A, B are

≤

-incomparable.

Wadge hierarchy on Borel sets

The Wadge hierarchy on Borel subsets of N

goes as follows:

{∅} Σ

D

(Σ

) . . .

∆

∆(D

(Σ

)) . . . {N

} Π

D ˇ

(Σ

) . . . The first ω

levels are occupied by sets that are both F

and G

. Remark. (Under AC ) This semi-linearity does not extend to all subsets of N

: if A is true G

and B is a Bernstein set, then A, B are

≤

-incomparable.

Wadge hierarchy on other spaces

I

For an arbitrary topological space X , one can only say that the Wadge hierarchy has a root of three degrees

{∅}

∆

{X }

which precede every other set.

I

P. Schlicht showed that if X is a positive dimensional metric space,

then there is ≤

has an antichain of size the continuum, consisting

of sets in D

(Σ

).

Wadge hierarchy on other spaces

I

For an arbitrary topological space X , one can only say that the Wadge hierarchy has a root of three degrees

{∅}

∆

{X }

which precede every other set.

I

P. Schlicht showed that if X is a positive dimensional metric space,

then there is ≤

has an antichain of size the continuum, consisting

of sets in D

(Σ

).

Tang-Pequignot hierarchy

A. Tang (1981) working with Scott domain, and Y. Pequignot (2015) for general second countable T

spaces, propose a different notion of reducibility, that I denote 

.



has the following features:

I

It refines Wadge hierarchy

I

It coincides with ≤

for zero-dimensional spaces

Tang-Pequignot hierarchy

A. Tang (1981) working with Scott domain, and Y. Pequignot (2015) for general second countable T

spaces, propose a different notion of reducibility, that I denote 

.



has the following features:

I

It refines Wadge hierarchy

I

It coincides with ≤

for zero-dimensional spaces

Tang-Pequignot hierarchy

A. Tang (1981) working with Scott domain, and Y. Pequignot (2015) for general second countable T

spaces, propose a different notion of reducibility, that I denote 

.



has the following features:

I

It refines Wadge hierarchy

I

It coincides with ≤

for zero-dimensional spaces

A detour via computable analysis: admissible representations

Let X be a second countable, T

space.

A continuous function ρ : Z ⊆ N

→ X is an admissible representation if for any continuous ρ

: Z

⊆ N

→ X there is a continuous h : Z

→ Z s.t. ρ

= ρh.

Fact.

I

Every second countable, T

space X has an admissible

representation ρ : Z ⊆ N

→ X

A detour via computable analysis: admissible representations

Let X be a second countable, T

space.

A continuous function ρ : Z ⊆ N

→ X is an admissible representation if for any continuous ρ

: Z

⊆ N

→ X there is a continuous h : Z

→ Z s.t. ρ

= ρh.

Fact.

I

Every second countable, T

space X has an admissible

representation ρ : Z ⊆ N

→ X

A detour via computable analysis: admissible representations

Let X be a second countable, T

space.

A continuous function ρ : Z ⊆ N

→ X is an admissible representation if for any continuous ρ

: Z

⊆ N

→ X there is a continuous h : Z

→ Z s.t. ρ

= ρh.

Fact.

I

Every second countable, T

space X has an admissible

representation ρ : Z ⊆ N

→ X

A definition of  ^X _TP

Definition

Let X be second countable, T

, and let ρ : Z ⊆ N

→ X be any admissible representation for X .

Then

A 

B ⇔ ρ

(A) ≤

ρ

(B)

Fact. A ≤

B ⇒ A 

B

A definition of  ^X _TP

Definition

Let X be second countable, T

, and let ρ : Z ⊆ N

→ X be any admissible representation for X . Then

A 

B ⇔ ρ

(A) ≤

ρ

(B)

Fact. A ≤

B ⇒ A 

B

A definition of  ^X _TP

Definition

Let X be second countable, T

, and let ρ : Z ⊆ N

→ X be any admissible representation for X . Then

A 

B ⇔ ρ

(A) ≤

ρ

(B)

Fact. A ≤

B ⇒ A 

B

An example: the conciliatory hierarchy

As a tool for the study of the ordinary Wadge hierarchy on N

, Duparc (2001) introduces the conciliatory hierarchy on subsets of N

.

Given A, B ⊆ N

, say that A ≤

B if player II has a winning strategy in the conciliatory game G

(A, B).

This is the same as the Wadge game G

(A, B) except that both players are allowed to skip their turn, so they produce sequences x , y ∈ N

. Player II wins the run of the game iff

x ∈ A ⇔ y ∈ B

An example: the conciliatory hierarchy

As a tool for the study of the ordinary Wadge hierarchy on N

, Duparc (2001) introduces the conciliatory hierarchy on subsets of N

.

Given A, B ⊆ N

, say that A ≤

B if player II has a winning strategy in the conciliatory game G

(A, B).

This is the same as the Wadge game G

(A, B) except that both players are allowed to skip their turn, so they produce sequences x , y ∈ N

. Player II wins the run of the game iff

x ∈ A ⇔ y ∈ B

An example: the conciliatory hierarchy

As a tool for the study of the ordinary Wadge hierarchy on N

, Duparc (2001) introduces the conciliatory hierarchy on subsets of N

.

Given A, B ⊆ N

, say that A ≤

B if player II has a winning strategy in the conciliatory game G

(A, B).

This is the same as the Wadge game G

(A, B) except that both players are allowed to skip their turn, so they produce sequences x , y ∈ N

.

Player II wins the run of the game iff

x ∈ A ⇔ y ∈ B

An example: the conciliatory hierarchy

As a tool for the study of the ordinary Wadge hierarchy on N

, Duparc (2001) introduces the conciliatory hierarchy on subsets of N

.

Given A, B ⊆ N

, say that A ≤

B if player II has a winning strategy in the conciliatory game G

(A, B).

This is the same as the Wadge game G

(A, B) except that both players are allowed to skip their turn, so they produce sequences x , y ∈ N

. Player II wins the run of the game iff

x ∈ A ⇔ y ∈ B

An example: the conciliatory hierarchy

Theorem (Duparc, Fournier)

Endow N

with the prefix topology.

Then

≤

6= ≤

≤

= 

Question. (Duparc, Fournier) Is there a topology τ on N

such that

≤

=≤

?

More general question. Given a second countable, T

space

X = (X , T ), when there is a topology τ on X such that 

=≤

?

An example: the conciliatory hierarchy

Theorem (Duparc, Fournier)

Endow N

with the prefix topology. Then

≤

6= ≤

≤

= 

Question. (Duparc, Fournier) Is there a topology τ on N

such that

≤

=≤

?

More general question. Given a second countable, T

space

X = (X , T ), when there is a topology τ on X such that 

=≤

?

An example: the conciliatory hierarchy

Theorem (Duparc, Fournier)

Endow N

with the prefix topology. Then

≤

6= ≤

≤

= 

Question. (Duparc, Fournier) Is there a topology τ on N

such that

≤

=≤

?

More general question. Given a second countable, T

space

X = (X , T ), when there is a topology τ on X such that 

=≤

?

An example: the conciliatory hierarchy

Theorem (Duparc, Fournier)

Endow N

with the prefix topology. Then

≤

6= ≤

≤

= 

Question. (Duparc, Fournier) Is there a topology τ on N

such that

≤

=≤

?

More general question. Given a second countable, T

space

X = (X , T ), when there is a topology τ on X such that 

=≤

?

An example: the conciliatory hierarchy

Theorem (Duparc, Fournier)

Endow N

with the prefix topology. Then

≤

6= ≤

≤

= 

Question. (Duparc, Fournier) Is there a topology τ on N

such that

≤

=≤

?

More general question. Given a second countable, T

space

X = (X , T ), when there is a topology τ on X such that 

=≤

?

An answer

Theorem

Let X = (X , T ) be second countable, T

. Then there are three possibilities:

(0) There is no topology τ on X such that 

=≤

(1) There is just one topology τ on X such that 

=≤

: namely, τ = T

(2) There are exactly two topologies τ on X such that 

=≤

: namely τ = T and τ = Π

(T ) (in this case, T is an Alexandrov topology)

Corollary. The question of Duparc and Fournier has a negative answer.

An answer

Theorem

Let X = (X , T ) be second countable, T

. Then there are three possibilities:

(0) There is no topology τ on X such that 

=≤

(1) There is just one topology τ on X such that 

=≤

: namely, τ = T

(2) There are exactly two topologies τ on X such that 

=≤

: namely τ = T and τ = Π

(T ) (in this case, T is an Alexandrov topology)

Corollary. The question of Duparc and Fournier has a negative answer.

An answer

Theorem

Let X = (X , T ) be second countable, T

. Then there are three possibilities:

(0) There is no topology τ on X such that 

=≤

(1) There is just one topology τ on X such that 

=≤

: namely, τ = T

(2) There are exactly two topologies τ on X such that 

=≤

: namely τ = T and τ = Π

(T ) (in this case, T is an Alexandrov topology)

Corollary. The question of Duparc and Fournier has a negative answer.

An answer

Theorem

Let X = (X , T ) be second countable, T

. Then there are three possibilities:

(0) There is no topology τ on X such that 

=≤

(1) There is just one topology τ on X such that 

=≤

: namely, τ = T

(2) There are exactly two topologies τ on X such that 

=≤

: namely τ = T and τ = Π

(T )

(in this case, T is an Alexandrov topology)

Corollary. The question of Duparc and Fournier has a negative answer.

An answer

Theorem

Let X = (X , T ) be second countable, T

. Then there are three possibilities:

(0) There is no topology τ on X such that 

=≤

(1) There is just one topology τ on X such that 

=≤

: namely, τ = T

(2) There are exactly two topologies τ on X such that 

=≤

: namely τ = T and τ = Π

(T ) (in this case, T is an Alexandrov topology)

Corollary. The question of Duparc and Fournier has a negative answer.

A further question

Is there a nice characterisation of the spaces satisfying each of the alternatives above?

Rather unexpectedly — at least to me — the answer seems to depend on an analysis of the separation axioms satisfied by X :

I

Hausdorff spaces

I

T

, non-Hausdorff spaces

I

non-T

spaces

A further question

Is there a nice characterisation of the spaces satisfying each of the alternatives above?

Rather unexpectedly — at least to me — the answer seems to depend on an analysis of the separation axioms satisfied by X

:

I

Hausdorff spaces

I

T

, non-Hausdorff spaces

I

non-T

spaces

A further question

Is there a nice characterisation of the spaces satisfying each of the alternatives above?

Rather unexpectedly — at least to me — the answer seems to depend on an analysis of the separation axioms satisfied by X :

I

Hausdorff spaces

I

T

, non-Hausdorff spaces

I

non-T

spaces

Hausdorff spaces

Theorem

Let X be second countable, Hausdorff.

Then ≤

=

iff X is zero-dimensional.

Remark. Second countable, T

, zero-dimensional spaces are metrisable.

T ₁ , non-Hausdorff spaces

Theorem

Let X be second countable, T

, non-Hausdorff.

In order for the equality ≤

=

to be satisfied, it is necessary that

I

X is the union of at most countably many clopen connected components X

I

for every non-empty closed C ⊂ X there is x ∈ X \ C such that C , x do not have disjoint neighbourhoods

Example. Let X be a countable space with the cofinite topology. Then

≤

=

.

T ₁ , non-Hausdorff spaces

Theorem

Let X be second countable, T

, non-Hausdorff.

In order for the equality ≤

=

to be satisfied, it is necessary that

I

X is the union of at most countably many clopen connected components X

I

for every non-empty closed C ⊂ X there is x ∈ X \ C such that C , x do not have disjoint neighbourhoods

Example. Let X be a countable space with the cofinite topology. Then

≤

=

.

T ₁ , non-Hausdorff spaces

Theorem

Let X be second countable, T

, non-Hausdorff.

In order for the equality ≤

=

to be satisfied, it is necessary that

I

X is the union of at most countably many clopen connected components X

I

for every non-empty closed C ⊂ X there is x ∈ X \ C such that C , x do not have disjoint neighbourhoods

Example. Let X be a countable space with the cofinite topology. Then

≤

=

.

T ₁ , non-Hausdorff spaces

Theorem

Let X be second countable, T

, non-Hausdorff.

In order for the equality ≤

=

to be satisfied, it is necessary that

I

X is the union of at most countably many clopen connected components X

I

for every non-empty closed C ⊂ X there is x ∈ X \ C such that C , x do not have disjoint neighbourhoods

Example. Let X be a countable space with the cofinite topology. Then

≤

=

.

An open question

The cofinite topology on a countably infinite space is the Zariski topology on a countable field.

Question. Let K be a countable field, and endow K

with the Zariski topology. Does the equality

≤

=

hold?

An open question

The cofinite topology on a countably infinite space is the Zariski topology on a countable field.

Question. Let K be a countable field, and endow K

with the Zariski topology. Does the equality

≤

=

hold?

Non-T ₁ spaces

Theorem

Let X be second countable, T

, non-T

.

If ≤

=

, then X carries an Alexandrov topology, and it is the union of at most countably many clopen connected components.

As a consequence, card(X) ≤ ℵ

.

There are partial results giving conditions for the equality ≤

=

based on the combinatorics of the specialisation order of X .

Non-T ₁ spaces

Theorem

Let X be second countable, T

, non-T

.

If ≤

=

, then X carries an Alexandrov topology, and it is the union of at most countably many clopen connected components.

As a consequence, card(X) ≤ ℵ

.

There are partial results giving conditions for the equality ≤

=

based on the combinatorics of the specialisation order of X .

Non-T ₁ spaces

Theorem

Let X be second countable, T

, non-T

.

If ≤

=

, then X carries an Alexandrov topology, and it is the union of at most countably many clopen connected components.

As a consequence, card(X) ≤ ℵ

.

There are partial results giving conditions for the equality ≤

=

based on the combinatorics of the specialisation order of X .

Classification problems

In general, a classification problem consists in assigning a set of complete invariants for a given notion of equivalence.

To be meaningful, this assignment should be sufficiently concrete (explicitely computable or definable).

A — rather useless — assignment would be to assign to each object the set of objects equivalent to it.

The general question is: when a classification problem is more complex

than another one?

Classification problems

In general, a classification problem consists in assigning a set of complete invariants for a given notion of equivalence.

To be meaningful, this assignment should be sufficiently concrete (explicitely computable or definable).

A — rather useless — assignment would be to assign to each object the set of objects equivalent to it.

The general question is: when a classification problem is more complex

than another one?

Classification problems

In general, a classification problem consists in assigning a set of complete invariants for a given notion of equivalence.

To be meaningful, this assignment should be sufficiently concrete (explicitely computable or definable).

A — rather useless — assignment would be to assign to each object the set of objects equivalent to it.

The general question is: when a classification problem is more complex

than another one?

Classification problems

In general, a classification problem consists in assigning a set of complete invariants for a given notion of equivalence.

To be meaningful, this assignment should be sufficiently concrete (explicitely computable or definable).

A — rather useless — assignment would be to assign to each object the set of objects equivalent to it.

The general question is: when a classification problem is more complex

than another one?

Classification problems

In general, a classification problem consists in assigning a set of complete invariants for a given notion of equivalence.

To be meaningful, this assignment should be sufficiently concrete (explicitely computable or definable).

A — rather useless — assignment would be to assign to each object the set of objects equivalent to it.

The general question is: when a classification problem is more complex

than another one?

An elementary example

Let ≡

be the similarity relation on M(n × n, C) — the Polish space of n × n complex matrices.

Then A ≡

B if and only if A, B has the same Jordan normal form.

So there is a map

J : M(n × n, C) → M(n × n, C)

A 7→ J(A)

such that

A ≡

B ⇔ J(A) = J(B)

Remark. Map J is Borel.

An elementary example

Let ≡

be the similarity relation on M(n × n, C) — the Polish space of n × n complex matrices. Then A ≡

B if and only if A, B has the same Jordan normal form.

So there is a map

J : M(n × n, C) → M(n × n, C)

A 7→ J(A)

such that

A ≡

B ⇔ J(A) = J(B)

Remark. Map J is Borel.

An elementary example

Let ≡

be the similarity relation on M(n × n, C) — the Polish space of n × n complex matrices. Then A ≡

B if and only if A, B has the same Jordan normal form.

So there is a map

J : M(n × n, C) → M(n × n, C)

A 7→ J(A)

such that

A ≡

B ⇔ J(A) = J(B)

Remark. Map J is Borel.

An elementary example

Let ≡

be the similarity relation on M(n × n, C) — the Polish space of n × n complex matrices. Then A ≡

B if and only if A, B has the same Jordan normal form.

So there is a map

J : M(n × n, C) → M(n × n, C)

A 7→ J(A)

such that

A ≡

B ⇔ J(A) = J(B)

Remark. Map J is Borel.

A less elementary example: isometry

Given a compact metric space X , for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

). Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example: isometry

Given a compact metric space X

, for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

). Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example: isometry

Given a compact metric space X , for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

). Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example: isometry

Given a compact metric space X , for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

).

Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example: isometry

Given a compact metric space X , for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

).

Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example: isometry

Given a compact metric space X , for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

).

Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example: isometry

Given a compact metric space X , for every n ≥ 2 let

ϕ

: X

→ M(n × n, R)

(x

, . . . , x

) 7→ (d (x

, x

))

Then X '

Y if and only if for all n one has ϕ

(X

) = ϕ

(Y

).

Remarks.

I

Every compact metric space is isometric to a compact subset of the Urysohn space U

I

Every ϕ

(X

) is compact in M(n × n, R)

I

Given a Polish space Z , the set K (Z ) of compact subset of Z

endowed with the Vietoris topology is a Polish space

A less elementary example

The map

Φ : K (U) → Q

n≥2

K (M(n × n, R)) X 7→ (ϕ

(X

))

is Borel. Moreover

X '

Y ⇔ Φ(X ) = Φ(Y )

A less elementary example

The map

Φ : K (U) → Q

n≥2

K (M(n × n, R)) X 7→ (ϕ

(X

)) is Borel.

Moreover

X '

Y ⇔ Φ(X ) = Φ(Y )

A less elementary example

The map

Φ : K (U) → Q

n≥2

K (M(n × n, R)) X 7→ (ϕ

(X

)) is Borel. Moreover

X '

Y ⇔ Φ(X ) = Φ(Y )

The formal setting

Definition

Let X , Y be spaces endowed with a σ-algebra of Borel sets. Let E , F be equivalence relations on X , Y , resp. Let

E ≤

F

(E Borel reduces to F ) if there is f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)) Let also

E <

F ⇔ E ≤

F 

E

E ≡

F ⇔ E ≤

F ≤

E

The formal setting

Definition

Let X , Y be spaces endowed with a σ-algebra of Borel sets.

Let E , F be equivalence relations on X , Y , resp. Let

E ≤

F

(E Borel reduces to F ) if there is f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)) Let also

E <

F ⇔ E ≤

F 

E

E ≡

F ⇔ E ≤

F ≤

E

The formal setting

Definition

Let X , Y be spaces endowed with a σ-algebra of Borel sets. Let E , F be equivalence relations on X , Y , resp.

Let E ≤

F

(E Borel reduces to F ) if there is f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)) Let also

E <

F ⇔ E ≤

F 

E

E ≡

F ⇔ E ≤

F ≤

E

The formal setting

Definition

Let X , Y be spaces endowed with a σ-algebra of Borel sets. Let E , F be equivalence relations on X , Y , resp. Let

E ≤

F (E Borel reduces to F )

if there is f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)) Let also

E <

F ⇔ E ≤

F 

E

E ≡

F ⇔ E ≤

F ≤

E

The formal setting

Definition

Let X , Y be spaces endowed with a σ-algebra of Borel sets. Let E , F be equivalence relations on X , Y , resp. Let

E ≤

F

(E Borel reduces to F ) if there is f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

))

Let also

E <

F ⇔ E ≤

F 

E

E ≡

F ⇔ E ≤

F ≤

E

The formal setting

Definition

Let X , Y be spaces endowed with a σ-algebra of Borel sets. Let E , F be equivalence relations on X , Y , resp. Let

E ≤

F

(E Borel reduces to F ) if there is f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)) Let also

E <

F ⇔ E ≤

F 

E

E ≡

F ⇔ E ≤

F ≤

E

Heuristic justification

A standard Borel space X = (X , B) is a set endowed with a sigma-algebra that is the family of Borel subsets for some Polish topology on X .

I

In most cases, classes of objects that one wants to classify carry a natural structure of standard Borel space. This allows to use the rich theory of this class of spaces.

I

The operations that one usually perform to build new object in an

explicit way turn out to be Borel functions.

Heuristic justification

A standard Borel space X = (X , B) is a set endowed with a sigma-algebra that is the family of Borel subsets for some Polish topology on X .

I

In most cases, classes of objects that one wants to classify carry a natural structure of standard Borel space. This allows to use the rich theory of this class of spaces.

I

The operations that one usually perform to build new object in an

explicit way turn out to be Borel functions.

Smooth equivalence relations

The preceding examples give:

≡

≤

= '



≤

=

(the result about isometry on compact metric spaces is originally due to Gromov, with a different proof)

Definition

Whenever E is an equivalence relation such that E ≤

, one says that E is smooth, or concretely classifiable

This is far from being a common situation.

Smooth equivalence relations

The preceding examples give:

≡

≤

= '



≤

=

(the result about isometry on compact metric spaces is originally due to Gromov, with a different proof)

Definition

Whenever E is an equivalence relation such that E ≤

, one says that E is smooth, or concretely classifiable

This is far from being a common situation.

Smooth equivalence relations

The preceding examples give:

≡

≤

= '



≤

=

(the result about isometry on compact metric spaces is originally due to Gromov, with a different proof)

Definition

Whenever E is an equivalence relation such that E ≤

, one says that E is smooth, or concretely classifiable

This is far from being a common situation.

Smooth equivalence relations

The preceding examples give:

≡

≤

= '



≤

=

(the result about isometry on compact metric spaces is originally due to Gromov, with a different proof)

Definition

Whenever E is an equivalence relation such that E ≤

, one says that E is smooth, or concretely classifiable

This is far from being a common situation.

Smooth equivalence relations

The preceding examples give:

≡

≤

= '



≤

=

(the result about isometry on compact metric spaces is originally due to Gromov, with a different proof)

Definition

Whenever E is an equivalence relation such that E ≤

, one says that E is smooth, or concretely classifiable

This is far from being a common situation.

Some examples on isometries

The following equivalence relations are way more complicated than smooth equivalence relations.

I

(Hjorth) Isometry on connected locally compact Polish metric spaces

≡

Universal countable Borel equivalence relation

I

(Gao-Kechris) Isometry on 0-dimensional locally compact Polish metric spaces ≡

Isometry on ultrametric Polish spaces ≡

Countable graph isomorphism

I

(Gao-Kechris) Isometry on Polish metric spaces ≡

The universal

orbit equivalence relation induced by an action of a Polish group on

a standard Borel space

Some examples on isometries

The following equivalence relations are way more complicated than smooth equivalence relations.

I

(Hjorth) Isometry on connected locally compact Polish metric spaces

≡

Universal countable Borel equivalence relation

I

(Gao-Kechris) Isometry on 0-dimensional locally compact Polish metric spaces ≡

Isometry on ultrametric Polish spaces ≡

Countable graph isomorphism

I

(Gao-Kechris) Isometry on Polish metric spaces ≡

The universal

orbit equivalence relation induced by an action of a Polish group on

a standard Borel space