Descriptive set theory and classification problems

Descriptive set theory

and classification problems

Descripive set theory is about definability in Polish (=separable, completely metrisable) spaces.

Standard Borel space: a set X together with A ⊆ P(X ) that is the

σ-algebra of Borel subsets for some Polish topology on X .

Descripive set theory is about definability in Polish (=separable, completely metrisable) spaces.

Standard Borel space: a set X together with A ⊆ P(X ) that is the

σ-algebra of Borel subsets for some Polish topology on X .

L = {R

, f

, c

| i ∈ I , j ∈ J, k ∈ K } non-empty countable language

A = (N, R

, f

, c

)

countable L-structure X

= Y

i ∈I

2

× Y

j ∈J

2

× N

Polish space of countable L-stuctures

X

' 2

or X

' N

or X

' N

However, the additional information about the elements of X

may help

in studying properties of the space.

L = {R

, f

, c

| i ∈ I , j ∈ J, k ∈ K } non-empty countable language A = (N, R

, f

, c

)

countable L-structure

X

= Y

i ∈I

2

× Y

j ∈J

2

× N

Polish space of countable L-stuctures

X

' 2

or X

' N

or X

' N

However, the additional information about the elements of X

may help

in studying properties of the space.

L = {R

, f

, c

| i ∈ I , j ∈ J, k ∈ K } non-empty countable language A = (N, R

, f

, c

)

countable L-structure

X

= Y

i ∈I

2

× Y

j ∈J

2

× N

Polish space of countable L-stuctures

X

' 2

or X

' N

or X

' N

However, the additional information about the elements of X

may help

in studying properties of the space.

L = {R

, f

, c

| i ∈ I , j ∈ J, k ∈ K } non-empty countable language A = (N, R

, f

, c

)

countable L-structure

X

= Y

i ∈I

2

× Y

j ∈J

2

× N

Polish space of countable L-stuctures

X

' 2

or X

' N

or X

' N

However, the additional information about the elements of X

may help

in studying properties of the space.

L = {R

, f

, c

| i ∈ I , j ∈ J, k ∈ K } non-empty countable language A = (N, R

, f

, c

)

countable L-structure

X

= Y

i ∈I

2

× Y

j ∈J

2

× N

Polish space of countable L-stuctures

X

' 2

or X

' N

or X

' N

However, the additional information about the elements of X

may help

in studying properties of the space.

Borel subsets of X

invariant under isomorphism are the classes of countable L-structures satisfying a given L

-sentence.

Examples.

Countable graphs, groups, fields, linear orders, Boolean algebras, . . .

Borel subsets of X

invariant under isomorphism are the classes of countable L-structures satisfying a given L

-sentence.

Examples.

Countable graphs, groups, fields, linear orders, Boolean algebras, . . .

Study of subsets of Polish spaces

X a Polish space. A ⊆ X .

• A is Borel if if belongs to the σ-algebra generated by open sets.

• A is analytic (Σ

) if it is the continuous image of a Borel set.

• A is coanalytic (Π

) if X \ A is Σ

.

• A is Σ

if it is the continuous image of a Π

set.

• A is Π

if X \ A is Σ

.

• A set A in a class Γ is Γ-complete if for every B ∈ Γ there is f continuous such that B = f

(A).

Lusin separation theorem. If A, B ⊆ X are disjoint analytic sets, there is a Borel set C that separates them: A ⊆ C , B ∩ C = ∅.

This does not hold for coanalytic sets.

Study of subsets of Polish spaces

X a Polish space. A ⊆ X .

• A is Borel if if belongs to the σ-algebra generated by open sets.

• A is analytic (Σ

) if it is the continuous image of a Borel set.

• A is coanalytic (Π

) if X \ A is Σ

.

• A is Σ

if it is the continuous image of a Π

set.

• A is Π

if X \ A is Σ

.

• A set A in a class Γ is Γ-complete if for every B ∈ Γ there is f continuous such that B = f

(A).

Lusin separation theorem. If A, B ⊆ X are disjoint analytic sets, there is a Borel set C that separates them: A ⊆ C , B ∩ C = ∅.

This does not hold for coanalytic sets.

Study of subsets of Polish spaces

X a Polish space. A ⊆ X .

• A is Borel if if belongs to the σ-algebra generated by open sets.

• A is analytic (Σ

) if it is the continuous image of a Borel set.

• A is coanalytic (Π

) if X \ A is Σ

.

• A is Σ

if it is the continuous image of a Π

set.

• A is Π

if X \ A is Σ

.

• A set A in a class Γ is Γ-complete if for every B ∈ Γ there is f continuous such that B = f

(A).

Lusin separation theorem. If A, B ⊆ X are disjoint analytic sets, there is a Borel set C that separates them: A ⊆ C , B ∩ C = ∅.

This does not hold for coanalytic sets.

Study of subsets of Polish spaces

X a Polish space. A ⊆ X .

• A is Borel if if belongs to the σ-algebra generated by open sets.

• A is analytic (Σ

) if it is the continuous image of a Borel set.

• A is coanalytic (Π

) if X \ A is Σ

.

• A is Σ

if it is the continuous image of a Π

set.

• A is Π

if X \ A is Σ

.

• A set A in a class Γ is Γ-complete if for every B ∈ Γ there is f continuous such that B = f

(A).

Lusin separation theorem. If A, B ⊆ X are disjoint analytic sets, there is a Borel set C that separates them: A ⊆ C , B ∩ C = ∅.

This does not hold for coanalytic sets.

Study of subsets of Polish spaces

X a Polish space. A ⊆ X .

• A is Borel if if belongs to the σ-algebra generated by open sets.

• A is analytic (Σ

) if it is the continuous image of a Borel set.

• A is coanalytic (Π

) if X \ A is Σ

.

• A is Σ

if it is the continuous image of a Π

set.

• A is Π

if X \ A is Σ

.

• A set A in a class Γ is Γ-complete if for every B ∈ Γ there is f continuous such that B = f

(A).

Lusin separation theorem. If A, B ⊆ X are disjoint analytic sets, there is a Borel set C that separates them: A ⊆ C , B ∩ C = ∅.

This does not hold for coanalytic sets.

Study of subsets of Polish spaces

X a Polish space. A ⊆ X .

• A is Borel if if belongs to the σ-algebra generated by open sets.

• A is analytic (Σ

) if it is the continuous image of a Borel set.

• A is coanalytic (Π

) if X \ A is Σ

.

• A is Σ

if it is the continuous image of a Π

set.

• A is Π

if X \ A is Σ

.

• A set A in a class Γ is Γ-complete if for every B ∈ Γ there is f continuous such that B = f

(A).

Lusin separation theorem. If A, B ⊆ X are disjoint analytic sets, there is a Borel set C that separates them: A ⊆ C , B ∩ C = ∅.

This does not hold for coanalytic sets.

For G a countable group, let

U

= {A ∈ X

| Aut(A) ' G }.

Theorem (Kechris, C.). Suppose L contains infinitely many unary function symbols, or at least one symbol of arity ≥ 2. Then each U

is Π

-complete. Moreover, for G , H non-isomorphic, the sets U

, U

are Borel-inseparable.

A model theoretic interpretation:

If σ is an L

-sentence satisfied by all countable L-structures whose automorphism group is isomorphic to G , then for every countable group H there is a countable structure whose automorphism group is

isomorphic to H satisfying σ.

All the above remains true by restricting to the class of countable graphs.

For G a countable group, let

U

= {A ∈ X

| Aut(A) ' G }.

Theorem (Kechris, C.). Suppose L contains infinitely many unary function symbols, or at least one symbol of arity ≥ 2. Then each U

is Π

-complete. Moreover, for G , H non-isomorphic, the sets U

, U

are Borel-inseparable.

A model theoretic interpretation:

If σ is an L

-sentence satisfied by all countable L-structures whose automorphism group is isomorphic to G , then for every countable group H there is a countable structure whose automorphism group is

isomorphic to H satisfying σ.

All the above remains true by restricting to the class of countable graphs.

For G a countable group, let

U

= {A ∈ X

| Aut(A) ' G }.

Theorem (Kechris, C.). Suppose L contains infinitely many unary function symbols, or at least one symbol of arity ≥ 2. Then each U

is Π

-complete. Moreover, for G , H non-isomorphic, the sets U

, U

are Borel-inseparable.

A model theoretic interpretation:

If σ is an L

-sentence satisfied by all countable L-structures whose automorphism group is isomorphic to G , then for every countable group H there is a countable structure whose automorphism group is

isomorphic to H satisfying σ.

All the above remains true by restricting to the class of countable graphs.

How many such classes U

are there?

The trivial answer is 2

. However, the answer depends on which concept of cardinality is used. In a sense, here the answer is much bigger then 2

. More on this in a moment.

But first, another such example (Darji, C.).

For K a compact subset of N

, let T

be the set of subtrees T of N

whose body [T ] is homeomorphic to K . Each T

is a Π

-complete subset

of Tr , the Polish space of trees on N. If K , L are non-homeomorphic

compact subsets of N

, then T

, T

are Borel inseparable.

How many such classes U

are there?

The trivial answer is 2

. However, the answer depends on which concept of cardinality is used. In a sense, here the answer is much bigger then 2

. More on this in a moment.

But first, another such example (Darji, C.).

For K a compact subset of N

, let T

be the set of subtrees T of N

whose body [T ] is homeomorphic to K . Each T

is a Π

-complete subset

of Tr , the Polish space of trees on N. If K , L are non-homeomorphic

compact subsets of N

, then T

, T

are Borel inseparable.

How many such classes U

are there?

The trivial answer is 2

. However, the answer depends on which concept of cardinality is used. In a sense, here the answer is much bigger then 2

. More on this in a moment.

But first, another such example (Darji, C.).

For K a compact subset of N

, let T

be the set of subtrees T of N

whose body [T ] is homeomorphic to K .

Each T

is a Π

-complete subset

of Tr , the Polish space of trees on N. If K , L are non-homeomorphic

compact subsets of N

, then T

, T

are Borel inseparable.

How many such classes U

are there?

The trivial answer is 2

. However, the answer depends on which concept of cardinality is used. In a sense, here the answer is much bigger then 2

. More on this in a moment.

But first, another such example (Darji, C.).

For K a compact subset of N

, let T

be the set of subtrees T of N

whose body [T ] is homeomorphic to K . Each T

is a Π

-complete subset of Tr , the Polish space of trees on N.

If K , L are non-homeomorphic

compact subsets of N

, then T

, T

are Borel inseparable.

How many such classes U

are there?

The trivial answer is 2

. However, the answer depends on which concept of cardinality is used. In a sense, here the answer is much bigger then 2

. More on this in a moment.

But first, another such example (Darji, C.).

For K a compact subset of N

, let T

be the set of subtrees T of N

whose body [T ] is homeomorphic to K . Each T

is a Π

-complete subset

of Tr , the Polish space of trees on N. If K , L are non-homeomorphic

compact subsets of N

, then T

, T

are Borel inseparable.

Tools for classification

Basic example: Equivalence relations.

E , F equivalence relations on standard Borel spaces X , Y , respectively.

Define E ≤

F iff there exists f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)).

This means the existence of an injection X /E → Y /F with Borel lifting

X → Y (the Borel cardinality of X /E is ≤ the Borel cardinality of Y /F ).

The problem of E -equivalence is transfered to that of F -equivalence: the

complexity of E is bounded by that of F .

Tools for classification

Basic example: Equivalence relations.

E , F equivalence relations on standard Borel spaces X , Y , respectively.

Define E ≤

F iff there exists f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)).

This means the existence of an injection X /E → Y /F with Borel lifting

X → Y (the Borel cardinality of X /E is ≤ the Borel cardinality of Y /F ).

The problem of E -equivalence is transfered to that of F -equivalence: the

complexity of E is bounded by that of F .

Tools for classification

Basic example: Equivalence relations.

E , F equivalence relations on standard Borel spaces X , Y , respectively.

Define E ≤

F iff there exists f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)).

This means the existence of an injection X /E → Y /F with Borel lifting X → Y (the Borel cardinality of X /E is ≤ the Borel cardinality of Y /F ).

The problem of E -equivalence is transfered to that of F -equivalence: the

complexity of E is bounded by that of F .

Tools for classification

Basic example: Equivalence relations.

E , F equivalence relations on standard Borel spaces X , Y , respectively.

Define E ≤

F iff there exists f : X → Y Borel such that

∀x, x

∈ X (xEx

⇔ f (x)Ff (x

)).

This means the existence of an injection X /E → Y /F with Borel lifting X → Y (the Borel cardinality of X /E is ≤ the Borel cardinality of Y /F ).

The problem of E -equivalence is transfered to that of F -equivalence: the

complexity of E is bounded by that of F .

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable. 1 <

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1

<

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2

<

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N

<

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N <

R

<

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

≤

is a preorder between equivalence relations on standard Borel spaces.

Let: E ≡

F ⇔ E ≤

F ≤

E E <

F ⇔ E ≤

F 

E

Countable Borel equivalence relations.

An equivalence relation E is countable iff each [x ]

is countable.

1 <

2 <

. . . <

N <

R <

E

<

. . . <

E

E

is the equivalence relation on 2

defined by xE

y iff ∃n ∀m ≥ n x (m) = y (m).

E

is the equivalence relation on 2

generated by the shift action F

× 2

→ 2

:

hp(g ) = p(h

g ).

Theorem (Adams, Kechris). There is an assignment A 7→ E

from Borel subsets of R to countable Borel equivalence relations such that

A ⊆ B ⇔ E

≤

E

.

Every countable Borel equivalence relation E bireducible with E

is

called a universal countable Borel equivalence relation.

Theorem (Adams, Kechris). There is an assignment A 7→ E

from Borel subsets of R to countable Borel equivalence relations such that

A ⊆ B ⇔ E

≤

E

.

Every countable Borel equivalence relation E bireducible with E

is

called a universal countable Borel equivalence relation.

Examples:

For A, B ∈ X

, let

A '

B iff ∃f : N → N recursive s.t. f : A ' B.

This is indeed a countable Borel equivalence relation as it is induced by a Borel (actually continuous) action of a countable group:

Rec × X

→ X

.

This is the restriction of the logic action Sym(N) × X

→ X

Theorem (Feldman, Moore). The countable Borel equivalence relations

on standard Borel spaces are exactly the orbit relations induced by Borel

actions of countable groups.

Examples:

For A, B ∈ X

, let

A '

B iff ∃f : N → N recursive s.t. f : A ' B.

This is indeed a countable Borel equivalence relation as it is induced by a Borel (actually continuous) action of a countable group:

Rec × X

→ X

.

This is the restriction of the logic action Sym(N) × X

→ X

Theorem (Feldman, Moore). The countable Borel equivalence relations

on standard Borel spaces are exactly the orbit relations induced by Borel

actions of countable groups.

Examples:

For A, B ∈ X

, let

A '

B iff ∃f : N → N recursive s.t. f : A ' B.

This is indeed a countable Borel equivalence relation as it is induced by a Borel (actually continuous) action of a countable group:

Rec × X

→ X

.

This is the restriction of the logic action Sym(N) × X

→ X

Theorem (Feldman, Moore). The countable Borel equivalence relations

on standard Borel spaces are exactly the orbit relations induced by Borel

actions of countable groups.

Examples:

For A, B ∈ X

, let

A '

B iff ∃f : N → N recursive s.t. f : A ' B.

This is indeed a countable Borel equivalence relation as it is induced by a Borel (actually continuous) action of a countable group:

Rec × X

→ X

.

This is the restriction of the logic action Sym(N) × X

→ X

Theorem (Feldman, Moore). The countable Borel equivalence relations

on standard Borel spaces are exactly the orbit relations induced by Borel

actions of countable groups.

Theorem. On the following classes of countable models the relation of recursive isomorphism is a universal countable Borel equivalence relation:

I

graph-theoretic trees;

I

groups;

I

Boolean algebras;

I

fields;

I

linear orderings.

The relation of isomorphism on a Borel class of countable structures is analytic but in general not Borel. It is the orbit equivalence relation generated by the logic action, a continuous action

Sym(N) × X

→ X

.

Definition. An S

-equivalence relation is an orbit equivalence relation of a Borel action of a closed subgroup of Sym(N) on a standard Borel space. As every countable group is isomorphic to a closed subgroup of Sym(N), countable Borel equivalence relations fall in this class.

Theorem (Friedman, Stanley). There is a class of countable structures

whose isomorphism relation is universal for S

-equivalence relations.

The relation of isomorphism on a Borel class of countable structures is analytic but in general not Borel. It is the orbit equivalence relation generated by the logic action, a continuous action

Sym(N) × X

→ X

.

Definition. An S

-equivalence relation is an orbit equivalence relation of a Borel action of a closed subgroup of Sym(N) on a standard Borel space.

As every countable group is isomorphic to a closed subgroup of Sym(N), countable Borel equivalence relations fall in this class.

Theorem (Friedman, Stanley). There is a class of countable structures

whose isomorphism relation is universal for S

-equivalence relations.

The relation of isomorphism on a Borel class of countable structures is analytic but in general not Borel. It is the orbit equivalence relation generated by the logic action, a continuous action

Sym(N) × X

→ X

.

Definition. An S

-equivalence relation is an orbit equivalence relation of a Borel action of a closed subgroup of Sym(N) on a standard Borel space.

As every countable group is isomorphic to a closed subgroup of Sym(N), countable Borel equivalence relations fall in this class.

Theorem (Friedman, Stanley). There is a class of countable structures

whose isomorphism relation is universal for S

-equivalence relations.

The relation of isomorphism on a Borel class of countable structures is analytic but in general not Borel. It is the orbit equivalence relation generated by the logic action, a continuous action

Sym(N) × X

→ X

.

Definition. An S

-equivalence relation is an orbit equivalence relation of a Borel action of a closed subgroup of Sym(N) on a standard Borel space.

As every countable group is isomorphic to a closed subgroup of Sym(N), countable Borel equivalence relations fall in this class.

Theorem (Friedman, Stanley). There is a class of countable structures

whose isomorphism relation is universal for S

-equivalence relations.

Examples: The relation of isomorphism is S

-universal on the following classes of countable structures:

I

graph-theoretic trees (Friedman, Stanley);

I

groups (Mekler);

I

Boolean algebras (Gao, C.);

I

fields (Friedman, Stanley);

I

linear orderings (Friedman, Stanley).

Reducibility for more general relations:

R: n-ary relation on the st. Borel space X ; S : n-ary relation on the st. Borel space Y .

R ≤

S iff ∃f : X → Y Borel s.t.

∀x

. . . x

∈ X (R(x

, . . . , x

) ⇔ S (f (x

), . . . f (x

)))

Reducibility for more general relations:

R: n-ary relation on the st. Borel space X ; S : n-ary relation on the st. Borel space Y .

R ≤

S iff ∃f : X → Y Borel s.t.

∀x

. . . x

∈ X (R(x

, . . . , x

) ⇔ S (f (x

), . . . f (x

)))

Borel reducibility for general analytic equivalence relations and preorders

A first generalisation of isomorphism is biembeddability: A  B iff ∃f : N ,→ N embedding A into B.

A ≡ B iff A  B  A.

 is an analytic preorder;

≡ is an analytic equivalence relation. Theorem (Louveau, Rosendal).

(a) There is a universal analytic preorder.

(b) If R is a universal analytic preorder and E is the induced equivalence

relation, then E is a universal analytic equivalence relation.

Borel reducibility for general analytic equivalence relations and preorders

A first generalisation of isomorphism is biembeddability:

A  B iff ∃f : N ,→ N embedding A into B. A ≡ B iff A  B  A.

 is an analytic preorder;

≡ is an analytic equivalence relation. Theorem (Louveau, Rosendal).

(a) There is a universal analytic preorder.

(b) If R is a universal analytic preorder and E is the induced equivalence

relation, then E is a universal analytic equivalence relation.

Borel reducibility for general analytic equivalence relations and preorders

A first generalisation of isomorphism is biembeddability:

A  B iff ∃f : N ,→ N embedding A into B.

A ≡ B iff A  B  A.

 is an analytic preorder;

≡ is an analytic equivalence relation. Theorem (Louveau, Rosendal).

(a) There is a universal analytic preorder.

(b) If R is a universal analytic preorder and E is the induced equivalence

relation, then E is a universal analytic equivalence relation.

Borel reducibility for general analytic equivalence relations and preorders

A first generalisation of isomorphism is biembeddability:

A  B iff ∃f : N ,→ N embedding A into B.

A ≡ B iff A  B  A.

 is an analytic preorder;

≡ is an analytic equivalence relation.

Theorem (Louveau, Rosendal).

(a) There is a universal analytic preorder.

(b) If R is a universal analytic preorder and E is the induced equivalence

relation, then E is a universal analytic equivalence relation.

Borel reducibility for general analytic equivalence relations and preorders

A first generalisation of isomorphism is biembeddability:

A  B iff ∃f : N ,→ N embedding A into B.

A ≡ B iff A  B  A.

 is an analytic preorder;

≡ is an analytic equivalence relation.

Theorem (Louveau, Rosendal).

(a) There is a universal analytic preorder.

(b) If R is a universal analytic preorder and E is the induced equivalence

relation, then E is a universal analytic equivalence relation.

Examples:

I

(Laver): The relation of embeddability on linear orderings is a bqo; thus not a universal analytic preorder.

I

(Louveau, Rosendal): The relation of embeddability on graph-theoretic trees is a universal analytic preorder.

Consequence: Biembeddability is more complex than isomorphism.

Question. What is the complexity of embeddability for countable

groups, fields, Boolean algebras?

Examples:

I

(Laver): The relation of embeddability on linear orderings is a bqo;

thus not a universal analytic preorder.

I

(Louveau, Rosendal): The relation of embeddability on graph-theoretic trees is a universal analytic preorder.

Consequence: Biembeddability is more complex than isomorphism.

Question. What is the complexity of embeddability for countable

groups, fields, Boolean algebras?

Examples:

I

(Laver): The relation of embeddability on linear orderings is a bqo;

thus not a universal analytic preorder.

I

(Louveau, Rosendal): The relation of embeddability on graph-theoretic trees is a universal analytic preorder.

Consequence: Biembeddability is more complex than isomorphism.

Question. What is the complexity of embeddability for countable

groups, fields, Boolean algebras?

Examples:

I

(Laver): The relation of embeddability on linear orderings is a bqo;

thus not a universal analytic preorder.

I

(Louveau, Rosendal): The relation of embeddability on graph-theoretic trees is a universal analytic preorder.

Consequence: Biembeddability is more complex than isomorphism.

Question. What is the complexity of embeddability for countable

groups, fields, Boolean algebras?

Examples:

I

(Laver): The relation of embeddability on linear orderings is a bqo;

thus not a universal analytic preorder.

I

(Louveau, Rosendal): The relation of embeddability on graph-theoretic trees is a universal analytic preorder.

Consequence: Biembeddability is more complex than isomorphism.

Question. What is the complexity of embeddability for countable

groups, fields, Boolean algebras?

How to generate an analytic preorder

• Analytic binary relations on X :

If B(f , x , y ) is a Borel (or analytic) subset of S × X × X (S a standard Borel space)

R(x , y ) ⇔ ∃f B(f , x , y ) is an analytic relation on X .

• Suppose:

- ∀x ∃i

B(i

, x , x ).

- Given f

, f

with B(f

, x , y ), B(f

, y , z) there is some form of composition f

such that B(f

, x , z).

Then R is an analytic preorder.

How to generate an analytic preorder

• Analytic binary relations on X :

If B(f , x , y ) is a Borel (or analytic) subset of S × X × X (S a standard Borel space)

R(x , y ) ⇔ ∃f B(f , x , y ) is an analytic relation on X .

• Suppose:

- ∀x ∃i

B(i

, x , x ).

- Given f

, f

with B(f

, x , y ), B(f

, y , z) there is some form of composition f

such that B(f

, x , z).

Then R is an analytic preorder.

How to generate an analytic preorder

• Analytic binary relations on X :

If B(f , x , y ) is a Borel (or analytic) subset of S × X × X (S a standard Borel space)

R(x , y ) ⇔ ∃f B(f , x , y ) is an analytic relation on X .

• Suppose:

- ∀x ∃i

B(i

, x , x ).

- Given f

, f

with B(f

, x , y ), B(f

, y , z) there is some form of composition f

such that B(f

, x , z).

Then R is an analytic preorder.

How to generate an analytic preorder

• Analytic binary relations on X :

If B(f , x , y ) is a Borel (or analytic) subset of S × X × X (S a standard Borel space)

R(x , y ) ⇔ ∃f B(f , x , y ) is an analytic relation on X .

• Suppose:

- ∀x ∃i

B(i

, x , x ).

- Given f

, f

with B(f

, x , y ), B(f

, y , z) there is some form of composition f

such that B(f

, x , z).

Then R is an analytic preorder.

How to generate an analytic preorder

• Analytic binary relations on X :

If B(f , x , y ) is a Borel (or analytic) subset of S × X × X (S a standard Borel space)

R(x , y ) ⇔ ∃f B(f , x , y ) is an analytic relation on X .

• Suppose:

- ∀x ∃i

B(i

, x , x ).

- Given f

, f

with B(f

, x , y ), B(f

, y , z) there is some form of composition f

such that B(f

, x , z).

Then R is an analytic preorder.

Example (most general). A Borel action of a standard Borel monoid S × X → X

generates an analytic preorder.

An instance of this is the relation of embeddability for countable models. Definition. An epimorphism between n-ary relations R, R

is a surjection g : N → N such that

R(x

, . . . , x

) ⇒ R

(g (x

), . . . , g (x

)).

Theorem. The relation of epimorphism between countable graphs is a

universal analytic preorder.

Example (most general). A Borel action of a standard Borel monoid S × X → X

generates an analytic preorder.

An instance of this is the relation of embeddability for countable models.

Definition. An epimorphism between n-ary relations R, R

is a surjection g : N → N such that

R(x

, . . . , x

) ⇒ R

(g (x

), . . . , g (x

)).

Theorem. The relation of epimorphism between countable graphs is a

universal analytic preorder.

Example (most general). A Borel action of a standard Borel monoid S × X → X

generates an analytic preorder.

An instance of this is the relation of embeddability for countable models.

Definition. An epimorphism between n-ary relations R, R

is a surjection g : N → N such that

R(x

, . . . , x

) ⇒ R

(g (x

), . . . , g (x

)).

Theorem. The relation of epimorphism between countable graphs is a

universal analytic preorder.

Example (most general). A Borel action of a standard Borel monoid S × X → X

generates an analytic preorder.

An instance of this is the relation of embeddability for countable models.

Definition. An epimorphism between n-ary relations R, R

is a surjection g : N → N such that

R(x

, . . . , x

) ⇒ R

(g (x

), . . . , g (x

)).

Theorem. The relation of epimorphism between countable graphs is a

universal analytic preorder.

Some topological results

There are some related topological classification results.

Definition. A continuum is a compact connected metric space.

A dendrite is a locally connected continuum that does not contain copies of the circle S

.

Theorem. (Marcone, Rosendal) The relation of continuous embeddability on dendrites is a universal analytic preorder.

Theorem. The relation of being continuous image is a universal analytic

relation on continua.

Some topological results

There are some related topological classification results.

Definition. A continuum is a compact connected metric space.

A dendrite is a locally connected continuum that does not contain copies of the circle S

.

Theorem. (Marcone, Rosendal) The relation of continuous embeddability on dendrites is a universal analytic preorder.

Theorem. The relation of being continuous image is a universal analytic

relation on continua.

Some topological results

There are some related topological classification results.

Definition. A continuum is a compact connected metric space.

A dendrite is a locally connected continuum that does not contain copies of the circle S

.

Theorem. (Marcone, Rosendal) The relation of continuous embeddability on dendrites is a universal analytic preorder.

Theorem. The relation of being continuous image is a universal analytic

relation on continua.

Some topological results

There are some related topological classification results.

Definition. A continuum is a compact connected metric space.

A dendrite is a locally connected continuum that does not contain copies of the circle S

.

Theorem. (Marcone, Rosendal) The relation of continuous embeddability on dendrites is a universal analytic preorder.

Theorem. The relation of being continuous image is a universal analytic

relation on continua.

Some topological results

There are some related topological classification results.

Definition. A continuum is a compact connected metric space.

A dendrite is a locally connected continuum that does not contain copies of the circle S

.

Theorem. (Marcone, Rosendal) The relation of continuous embeddability on dendrites is a universal analytic preorder.

Theorem. The relation of being continuous image is a universal analytic

relation on continua.

Remark. The relation of being continuous image on locally connected continua trivialises: every two such continua are continuous images of each other.

Theorem. The relation of being continuous open image is a universal analytic preorder on dendrites.

Question.

I

What is the complexity of epimorphism on linear orderings?

Remark. The relation of being continuous image on locally connected continua trivialises: every two such continua are continuous images of each other.

Theorem. The relation of being continuous open image is a universal analytic preorder on dendrites.

Question.

I

What is the complexity of epimorphism on linear orderings?

Remark. The relation of being continuous image on locally connected continua trivialises: every two such continua are continuous images of each other.

Theorem. The relation of being continuous open image is a universal analytic preorder on dendrites.

Question.

I

What is the complexity of epimorphism on linear orderings?

Classification by countable structures and turbulence

(Hjorth)

Definition. E an equivalence relation on the Polish space X . E admits classification by countable structures if for some countable language L and Borel map f : X → X

,

xEy ⇔ f (x ) ' f (y ).

Equivalently, E ≤

F for some S

-equivalence relation F .

The notion of turbulence gives an exact obstruction for an orbit

equivalence relation for being classifiable by countable structures.

Classification by countable structures and turbulence

(Hjorth)

Definition. E an equivalence relation on the Polish space X . E admits classification by countable structures if for some countable language L and Borel map f : X → X

,

xEy ⇔ f (x ) ' f (y ).

Equivalently, E ≤

F for some S

-equivalence relation F .

The notion of turbulence gives an exact obstruction for an orbit

equivalence relation for being classifiable by countable structures.

Classification by countable structures and turbulence

(Hjorth)

Definition. E an equivalence relation on the Polish space X . E admits classification by countable structures if for some countable language L and Borel map f : X → X

,

xEy ⇔ f (x ) ' f (y ).

Equivalently, E ≤

F for some S

-equivalence relation F .

The notion of turbulence gives an exact obstruction for an orbit

equivalence relation for being classifiable by countable structures.

Classification by countable structures and turbulence

(Hjorth)

Definition. E an equivalence relation on the Polish space X . E admits classification by countable structures if for some countable language L and Borel map f : X → X

,

xEy ⇔ f (x ) ' f (y ).

Equivalently, E ≤

F for some S

-equivalence relation F .

The notion of turbulence gives an exact obstruction for an orbit

equivalence relation for being classifiable by countable structures.

Definition. G a Polish group, X a Polish space, G × X → X a continuous action.

U ⊆ X open; V ⊆ G an open symmetric neighbourhood of 1

.

I

The (U, V )-local graph is the (reflexive, symmetric) relation on U: xR

y ⇔ x , y ∈ U ∧ ∃g ∈ V gx = y .

I

The (U, V )-local orbit O(x, U, V ) of x ∈ U is the connected component of x in this graph.

Example: O(x , X , G ) = Gx .

Definition. G a Polish group, X a Polish space, G × X → X a continuous action.

U ⊆ X open; V ⊆ G an open symmetric neighbourhood of 1

.

I

The (U, V )-local graph is the (reflexive, symmetric) relation on U:

xR

y ⇔ x , y ∈ U ∧ ∃g ∈ V gx = y .

I

The (U, V )-local orbit O(x, U, V ) of x ∈ U is the connected component of x in this graph.

Example: O(x , X , G ) = Gx .

Definition. G a Polish group, X a Polish space, G × X → X a continuous action.

U ⊆ X open; V ⊆ G an open symmetric neighbourhood of 1

.

I

The (U, V )-local graph is the (reflexive, symmetric) relation on U:

xR

y ⇔ x , y ∈ U ∧ ∃g ∈ V gx = y .

I

The (U, V )-local orbit O(x, U, V ) of x ∈ U is the connected component of x in this graph.

Example: O(x , X , G ) = Gx .

Definition. G a Polish group, X a Polish space, G × X → X a continuous action.

U ⊆ X open; V ⊆ G an open symmetric neighbourhood of 1

.

I

The (U, V )-local graph is the (reflexive, symmetric) relation on U:

xR

y ⇔ x , y ∈ U ∧ ∃g ∈ V gx = y .

I

The (U, V )-local orbit O(x, U, V ) of x ∈ U is the connected component of x in this graph.

Example: O(x , X , G ) = Gx .

Definition.

I

The action G × X → X is turbulent if every orbit is dense and meagre, and each local orbit is somewhere dense.

I

The action G × X → X is generically turbulent if its restriction to some invariant dense G

subset of X is turbulent.

Theorem. The following are equivalent:

I

The action G × X → X is generically turbulent.

I

For every Borel Sym(N) × Y → Y and Baire measurable f : X → Y which is invariant (xE

y ⇒ f (x )E

f (y )) there is a dense G

set C ⊆ X mapped by f to a single orbit.

Corollary. If the action G × X → X is generically turbulent and

E

≤

E , then E is not classifiable by countable structures.

For nice Polish groups (GE groups) the converse holds too.

Definition.

I

The action G × X → X is turbulent if every orbit is dense and meagre, and each local orbit is somewhere dense.

I

The action G × X → X is generically turbulent if its restriction to some invariant dense G

subset of X is turbulent.

Theorem. The following are equivalent:

I

The action G × X → X is generically turbulent.

I

For every Borel Sym(N) × Y → Y and Baire measurable f : X → Y which is invariant (xE

y ⇒ f (x )E

f (y )) there is a dense G

set C ⊆ X mapped by f to a single orbit.

Corollary. If the action G × X → X is generically turbulent and

E

≤

E , then E is not classifiable by countable structures.

For nice Polish groups (GE groups) the converse holds too.

Definition.

I

The action G × X → X is turbulent if every orbit is dense and meagre, and each local orbit is somewhere dense.

I

The action G × X → X is generically turbulent if its restriction to some invariant dense G

subset of X is turbulent.

Theorem. The following are equivalent:

I

The action G × X → X is generically turbulent.

I

For every Borel Sym(N) × Y → Y and Baire measurable f : X → Y which is invariant (xE

y ⇒ f (x )E

f (y )) there is a dense G

set C ⊆ X mapped by f to a single orbit.

Corollary. If the action G × X → X is generically turbulent and

E

≤

E , then E is not classifiable by countable structures.

For nice Polish groups (GE groups) the converse holds too.

Definition.

I

The action G × X → X is turbulent if every orbit is dense and meagre, and each local orbit is somewhere dense.

I

The action G × X → X is generically turbulent if its restriction to some invariant dense G

subset of X is turbulent.

Theorem. The following are equivalent:

I

The action G × X → X is generically turbulent.

I

For every Borel Sym(N) × Y → Y and Baire measurable f : X → Y which is invariant (xE

y ⇒ f (x )E

f (y )) there is a dense G

set C ⊆ X mapped by f to a single orbit.

Corollary. If the action G × X → X is generically turbulent and

E

≤

E , then E is not classifiable by countable structures.

For nice Polish groups (GE groups) the converse holds too.

Definition.

I

The action G × X → X is turbulent if every orbit is dense and meagre, and each local orbit is somewhere dense.

I

The action G × X → X is generically turbulent if its restriction to some invariant dense G

subset of X is turbulent.

Theorem. The following are equivalent:

I

The action G × X → X is generically turbulent.

I

For every Borel Sym(N) × Y → Y and Baire measurable f : X → Y which is invariant (xE

y ⇒ f (x )E

f (y )) there is a dense G

set C ⊆ X mapped by f to a single orbit.

Corollary. If the action G × X → X is generically turbulent and E

≤

E , then E is not classifiable by countable structures.

For nice Polish groups (GE groups) the converse holds too.

Definition.

I

The action G × X → X is turbulent if every orbit is dense and meagre, and each local orbit is somewhere dense.

I

The action G × X → X is generically turbulent if its restriction to some invariant dense G

subset of X is turbulent.

Theorem. The following are equivalent:

I

The action G × X → X is generically turbulent.

I

For every Borel Sym(N) × Y → Y and Baire measurable f : X → Y which is invariant (xE

y ⇒ f (x )E

f (y )) there is a dense G

set C ⊆ X mapped by f to a single orbit.

Corollary. If the action G × X → X is generically turbulent and E

≤

E , then E is not classifiable by countable structures.

For nice Polish groups (GE groups) the converse holds too.

Epimorphisms between total orders (some remarks, joint with A.

Marcone).

For L, M total orderings, let L  M iff there is a surjection f : M → L such that

∀a, b ∈ M (a ≤

b ⇒ f (a) ≤

f (b)).

Epimorphisms on ordinals.

• Let α, β be limit ordinals (successor cases are trivial). Then α  β if and only if

α ≤ β ∧ cof (α) = cof (β) ∧ ¯ α ≤ ¯ β

where ¯ ξ is the last exponent in the Cantor normal form of the limit

ordinal ξ.

Epimorphisms between total orders (some remarks, joint with A.

Marcone).

For L, M total orderings, let L  M iff there is a surjection f : M → L such that

∀a, b ∈ M (a ≤

b ⇒ f (a) ≤

f (b)).

Epimorphisms on ordinals.

• Let α, β be limit ordinals (successor cases are trivial). Then α  β if and only if

α ≤ β ∧ cof (α) = cof (β) ∧ ¯ α ≤ ¯ β

where ¯ ξ is the last exponent in the Cantor normal form of the limit

ordinal ξ.

Easy remarks. Suppose f : M → L is an epimorphism. Then:

• L embeds into M.

• If M is complete, then L too is.

• If L is dense, then M is dense and g is continuous.

• If M, L do not have biggest element, then cof (M) = cof (L). Similarly

for coinitiality.

Easy remarks. Suppose f : M → L is an epimorphism. Then:

• L embeds into M.

• If M is complete, then L too is.

• If L is dense, then M is dense and g is continuous.

• If M, L do not have biggest element, then cof (M) = cof (L). Similarly

for coinitiality.

Easy remarks. Suppose f : M → L is an epimorphism. Then:

• L embeds into M.

• If M is complete, then L too is.

• If L is dense, then M is dense and g is continuous.

• If M, L do not have biggest element, then cof (M) = cof (L). Similarly

for coinitiality.

Easy remarks. Suppose f : M → L is an epimorphism. Then:

• L embeds into M.

• If M is complete, then L too is.

• If L is dense, then M is dense and g is continuous.

• If M, L do not have biggest element, then cof (M) = cof (L). Similarly

for coinitiality.

Hausdorff ranks. For x , y in the total order L, define c(x ) = {y ∈ L | [x , y ] is finite}.

Let L

= {c

(x )}

, where:

• c

(x ) = c(x );

• c

(x ) = S c(c

(x )), the operation c be performed in L

;

• c

(x ) = S

1≤α<λ

c

(x ), for λ limit.

The Hausdorff rank of L is the least α such that L

= 1.

Proposition. The relation  restricted to total orders of Hausdorff rank at most 2 is a bqo.

Proof. At the moment, lots of hand-waving.