Invariant descriptive set theory

Invariant descriptive set theory

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

Invariant descriptive set theory is the study of the complexity of equivalence relations on standard Borel spaces.

Motivation. In mathematics one often looks for complete invariants to assign to some notion of equivalence:

I Vector spaces on some fixed field are isomorphic iff they have the same dimension

I Compact orientable surfaces are homeomorphic iff they have the same genus

I Complex square matrices are similar iff they have the same Jordan normal form

I (Ornstein) Bernoulli shifts are isomorphic if they have the same entropy

I . . .

Invariant descriptive set theory: an introduction

I (Baer) To each countable torsion free Abelian group G of rank 1 it is possible to assign a sequence hG of natural numbers s.t. G ∼ G⁰ iff hG, hG⁰ are eventually equal

I Commutative AF -algebras are isomorphic iff their dimension groups are isomorphic

I . . .

In order for these assignment to be of some use, they should be sufficiently effective.

The right notion of effectiveness turns out to be that of a Borel function, provided the collections of objects to be classified form a standard Borel space — which is often the case.

Invariant descriptive set theory: an introduction

I (Baer) To each countable torsion free Abelian group G of rank 1 it is possible to assign a sequence hG of natural numbers s.t. G ∼ G⁰ iff hG, hG⁰ are eventually equal

I Commutative AF -algebras are isomorphic iff their dimension groups are isomorphic

I . . .

In order for these assignment to be of some use, they should be sufficiently effective.

The right notion of effectiveness turns out to be that of a Borel function, provided the collections of objects to be classified form a standard Borel space — which is often the case.

Invariant descriptive set theory: an introduction

I (Baer) To each countable torsion free Abelian group G of rank 1 it is possible to assign a sequence hG of natural numbers s.t. G ∼ G⁰ iff hG, hG⁰ are eventually equal

I Commutative AF -algebras are isomorphic iff their dimension groups are isomorphic

I . . .

In order for these assignment to be of some use, they should be sufficiently effective.

The right notion of effectiveness turns out to be that of a Borel function, provided the collections of objects to be classified form a standard Borel space — which is often the case.

Invariant descriptive set theory: an introduction

I (Baer) To each countable torsion free Abelian group G of rank 1 it is possible to assign a sequence hG of natural numbers s.t. G ∼ G⁰ iff hG, hG⁰ are eventually equal

I Commutative AF -algebras are isomorphic iff their dimension groups are isomorphic

I . . .

In order for these assignment to be of some use, they should be sufficiently effective.

The right notion of effectiveness turns out to be that of a Borel function,

provided the collections of objects to be classified form a standard Borel space — which is often the case.

Invariant descriptive set theory: an introduction

I (Baer) To each countable torsion free Abelian group G of rank 1 it is possible to assign a sequence hG of natural numbers s.t. G ∼ G⁰ iff hG, hG⁰ are eventually equal

I Commutative AF -algebras are isomorphic iff their dimension groups are isomorphic

I . . .

In order for these assignment to be of some use, they should be sufficiently effective.

The right notion of effectiveness turns out to be that of a Borel function, provided the collections of objects to be classified form a standard Borel space —

which is often the case.

Invariant descriptive set theory: an introduction

I (Baer) To each countable torsion free Abelian group G of rank 1 it is possible to assign a sequence hG of natural numbers s.t. G ∼ G⁰ iff hG, hG⁰ are eventually equal

I Commutative AF -algebras are isomorphic iff their dimension groups are isomorphic

I . . .

In order for these assignment to be of some use, they should be sufficiently effective.

The right notion of effectiveness turns out to be that of a Borel function, provided the collections of objects to be classified form a standard Borel space — which is often the case.

Borel reducibility

Definition

Let E , F be equivalence relations on standard Borel spaces X , Y , resp. Then E is Borel reducible to F , denoted

E ≤_B F , iff there is f : X → Y Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x)Ff (x⁰))

When E ≤_B F , any classification of objects in Y up to F -equivalence can be translated to a classification of objects of X up to E -equivalence, by applying function f . In this sense, the complexity of E is less than or equal to the complexity of F .

If E ≤_B F ≤_B E , one writes E ∼_B F : the equivalence relations E , F are Borel bireducible.

Borel reducibility

Definition

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

Then E is Borel reducible to F , denoted E ≤_B F , iff there is f : X → Y Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x)Ff (x⁰))

When E ≤_B F , any classification of objects in Y up to F -equivalence can be translated to a classification of objects of X up to E -equivalence, by applying function f . In this sense, the complexity of E is less than or equal to the complexity of F .

If E ≤_B F ≤_B E , one writes E ∼_B F : the equivalence relations E , F are Borel bireducible.

Borel reducibility

Definition

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

Then E is Borel reducible to F , denoted E ≤_B F ,

iff there is f : X → Y Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x)Ff (x⁰))

When E ≤_B F , any classification of objects in Y up to F -equivalence can be translated to a classification of objects of X up to E -equivalence, by applying function f . In this sense, the complexity of E is less than or equal to the complexity of F .

If E ≤_B F ≤_B E , one writes E ∼_B F : the equivalence relations E , F are Borel bireducible.

Borel reducibility

Definition

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

Then E is Borel reducible to F , denoted E ≤_B F , iff there is f : X → Y Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x)Ff (x⁰))

When E ≤_B F , any classification of objects in Y up to F -equivalence can be translated to a classification of objects of X up to E -equivalence, by applying function f .

In this sense, the complexity of E is less than or equal to the complexity of F .

If E ≤_B F ≤_B E , one writes E ∼_B F : the equivalence relations E , F are Borel bireducible.

Borel reducibility

Definition

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

Then E is Borel reducible to F , denoted E ≤_B F , iff there is f : X → Y Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x)Ff (x⁰))

When E ≤_B F , any classification of objects in Y up to F -equivalence can be translated to a classification of objects of X up to E -equivalence, by applying function f . In this sense, the complexity of E is less than or equal to the complexity of F .

If E ≤_B F ≤_B E , one writes E ∼_B F : the equivalence relations E , F are Borel bireducible.

Borel reducibility

Definition

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

Then E is Borel reducible to F , denoted E ≤_B F , iff there is f : X → Y Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x)Ff (x⁰))

When E ≤_B F , any classification of objects in Y up to F -equivalence can be translated to a classification of objects of X up to E -equivalence, by applying function f . In this sense, the complexity of E is less than or equal to the complexity of F .

If E ≤B F ≤B E , one writes E ∼B F : the equivalence relations E , F are Borel bireducible.

Smooth equivalence relations

Among the simplest equivalence relations are those whose classes can be characterised by a single real number:

Definition

An equivalence relation E on a standard Borel X is smooth if E ≤B=, i.e., there exists f : X → R Borel s.t.

∀x, x⁰∈ X (xEx⁰ ⇔ f (x) = f (x⁰))

Fact

Given two uncountable standard Borel spaces Y , Z there is always a Borel isomorphism g : Y → Z .

Smooth equivalence relations

Among the simplest equivalence relations are those whose classes can be characterised by a single real number:

Definition

An equivalence relation E on a standard Borel X is smooth if E ≤B=, i.e., there exists f : X → R Borel s.t.

∀x, x⁰∈ X (xEx⁰ ⇔ f (x) = f (x⁰))

Fact

Given two uncountable standard Borel spaces Y , Z there is always a Borel isomorphism g : Y → Z .

Smooth equivalence relations

Among the simplest equivalence relations are those whose classes can be characterised by a single real number:

Definition

An equivalence relation E on a standard Borel X is smooth if E ≤B=,

i.e., there exists f : X → R Borel s.t.

∀x, x⁰∈ X (xEx⁰ ⇔ f (x) = f (x⁰))

Fact

Given two uncountable standard Borel spaces Y , Z there is always a Borel isomorphism g : Y → Z .

Smooth equivalence relations

Among the simplest equivalence relations are those whose classes can be characterised by a single real number:

Definition

An equivalence relation E on a standard Borel X is smooth if E ≤B=, i.e., there exists f : X → R Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x) = f (x⁰))

Fact

Given two uncountable standard Borel spaces Y , Z there is always a Borel isomorphism g : Y → Z .

Smooth equivalence relations

Among the simplest equivalence relations are those whose classes can be characterised by a single real number:

Definition

An equivalence relation E on a standard Borel X is smooth if E ≤B=, i.e., there exists f : X → R Borel s.t.

∀x, x⁰∈ X (xEx⁰⇔ f (x) = f (x⁰))

Fact

Given two uncountable standard Borel spaces Y , Z there is always a Borel isomorphism g : Y → Z .

Smooth equivalence relations

So an equivalence relation is smooth if Borel reduces to equality on some uncountable standard Borel spaces

Using this, the following equivalence relations are smooth:

I Homeomorphism on compact orientable surfaces

I Similarity on complex square matrices

I Isomorphism on Bernoulli shifts

I (Gromov) Isometry on compact metric spaces

I . . .

Smooth equivalence relations

So an equivalence relation is smooth if Borel reduces to equality on some uncountable standard Borel spaces

Using this, the following equivalence relations are smooth:

I Homeomorphism on compact orientable surfaces

I Similarity on complex square matrices

I Isomorphism on Bernoulli shifts

I (Gromov) Isometry on compact metric spaces

I . . .

Non-smooth equivalence relations

Not all equivalence relations are smooth:

Examples

I Vitali equivalence. On R let xE^Vy ⇔ x − y ∈ Q.

I Eventual equality on N^N. Let xE₀y ⇔ ∀^∞n x (n) = y (n).

I Isomorphism 'TFA₁ for torsion free Abelian groups of rank 1. It turns out that =_R<B EV ∼B E0∼B'TFA₁.

Non-smooth equivalence relations

Not all equivalence relations are smooth:

Examples

I Vitali equivalence.

On R let xE^Vy ⇔ x − y ∈ Q.

I Eventual equality on N^N. Let xE₀y ⇔ ∀^∞n x (n) = y (n).

I Isomorphism 'TFA₁ for torsion free Abelian groups of rank 1. It turns out that =_R<B EV ∼B E0∼B'TFA₁.

Non-smooth equivalence relations

Not all equivalence relations are smooth:

Examples

I Vitali equivalence. On R let xE^Vy ⇔ x − y ∈ Q.

I Eventual equality on N^N. Let xE₀y ⇔ ∀^∞n x (n) = y (n).

I Isomorphism 'TFA₁ for torsion free Abelian groups of rank 1. It turns out that =_R<B EV ∼B E0∼B'TFA₁.

Non-smooth equivalence relations

Not all equivalence relations are smooth:

Examples

I Vitali equivalence. On R let xE^Vy ⇔ x − y ∈ Q.

I Eventual equality on N^N.

Let xE₀y ⇔ ∀^∞n x (n) = y (n).

I Isomorphism 'TFA₁ for torsion free Abelian groups of rank 1. It turns out that =_R<B EV ∼B E0∼B'TFA₁.

Non-smooth equivalence relations

Not all equivalence relations are smooth:

Examples

I Vitali equivalence. On R let xE^Vy ⇔ x − y ∈ Q.

I Eventual equality on N^N. Let xE₀y ⇔ ∀^∞n x (n) = y (n).

I Isomorphism 'TFA₁ for torsion free Abelian groups of rank 1.

It turns out that =_R<B EV ∼B E0∼B'TFA₁.

Non-smooth equivalence relations

Not all equivalence relations are smooth:

Examples

I Vitali equivalence. On R let xE^Vy ⇔ x − y ∈ Q.

I Eventual equality on N^N. Let xE₀y ⇔ ∀^∞n x (n) = y (n).

I Isomorphism 'TFA₁ for torsion free Abelian groups of rank 1.

It turns out that =_R<B EV ∼B E0∼B'TFA₁.

Spaces of countable structures

Let

L = {R_i, f_j, c_k | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp.

A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ,

i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N,

i.e. f_j^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K

So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

Spaces of countable structures

Let

L = {Ri, fj, ck | i ∈ I , j ∈ J, k ∈ K }

be a countable first-order language, where n_i, m_j are the arities of R_i, f_j, resp. A countable structure A — say with universe N — is defined by fixing interpretations

I R_i^A⊆ Nⁿⁱ, i.e. R_i^A∈ 2^Nni, for each i ∈ I

I f_j^A: N^mj → N, i.e. fj^A∈ N^Nmj, for each j ∈ J

I c_k^A∈ N, for each k ∈ K So

A ∈ (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K and

XL= (Y

i ∈I

2^Nni) × (Y

j ∈J

N^Nmj) × N^K

is the Polish space of countable L-structures (with universe N)

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff

1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N.

This is a Gδ

subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff 1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N:

for every g ∈ N^N, one has g ∈ S∞ iff 1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff

1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff

1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff

1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m)) So S_∞is a Polish space.

Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff

1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞,

so it is a Polish group.

The logic action

To simplify notation, from now on I will assume that L is relational, i.e., XL=Y

i ∈I

2^Nni

Elements of XL will be usually denoted by letters like x , y , . . ..

Let S_∞= Sym(N) be the group of permutations of N. This is a G^δ subset of N^N: for every g ∈ N^N, one has g ∈ S∞ iff

1. g is surjective: ∀m ∃n g (n) = m

2. g is injective: ∀n, m (n 6= m ⇒ g (n) 6= g (m))

So S_∞is a Polish space. Moreover, the operations of composition (g , h) 7→ gh and inversion g 7→ g⁻¹ are continuous in S_∞, so it is a Polish group.

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n)) i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y . The orbit equivalence relation is isomorphism:

x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n))

i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y . The orbit equivalence relation is isomorphism:

x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n)) i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y .

The orbit equivalence relation is isomorphism: x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n)) i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y . The orbit equivalence relation is isomorphism:

x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n)) i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y . The orbit equivalence relation is isomorphism:

x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n)) i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y . The orbit equivalence relation is isomorphism:

x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A

So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

The logic action

The action of S_∞ on N induces an action of S∞on X_L, the logic action:

gx = y ⇔ ∀i y_i(h₁, . . . , h_n) = x_i(g⁻¹(h₁), . . . , g⁻¹(h_n)) i.e., gx = y iff g : N → N is an isomorphism between the L-structures x , y . The orbit equivalence relation is isomorphism:

x ' y ⇔ ∃g ∈ S_∞ gx = y .

Definition

A subset A of a standard Borel space X is analytic if it is the Borel image of a Borel subset of a standard Borel space:

A ∈ Σ¹₁(X ) ⇔ ∃f : Y → X Borel ∃B ∈ B(Y ) f (B) = A So the isomorphism relation ' on XL is analytic, as a subset of X_L²(but in general not Borel).

Borel sets in X_L

However, the following holds:

Theorem (Miller)

Let G be a Polish group, X a standard Borel space, (g , x ) 7→ gx a Borel action of G on X .

Then every orbit {gx }_{g ∈G} is Borel.

Definition

L_ω1ω is the extension of L obtained by allowing countable disjunctions and conjunctions

∨_nϕ_n, ∧_nϕ_n

where each ϕ_nhas free variables between v₀, . . . , v_k−1 for some k independent of n (so each formula has finitely many free variables).

Borel sets in X_L

However, the following holds:

Theorem (Miller)

Let G be a Polish group, X a standard Borel space, (g , x ) 7→ gx a Borel action of G on X . Then every orbit {gx }_{g ∈G} is Borel.

Definition

L_ω1ω is the extension of L obtained by allowing countable disjunctions and conjunctions

∨_nϕ_n, ∧_nϕ_n

where each ϕ_nhas free variables between v₀, . . . , v_k−1 for some k independent of n (so each formula has finitely many free variables).

Borel sets in X_L

However, the following holds:

Theorem (Miller)

Let G be a Polish group, X a standard Borel space, (g , x ) 7→ gx a Borel action of G on X . Then every orbit {gx }_{g ∈G} is Borel.

Definition

L_ω1ωis the extension of L obtained by allowing countable disjunctions and conjunctions

∨nϕ_n, ∧_nϕ_n

where each ϕ_nhas free variables between v₀, . . . , v_k−1 for some k independent of n (so each formula has finitely many free variables).