Skip to main content
MathOverflow

Return to Answer

links added
Source Link
Goldstern
Goldstern
  • 14k
  • 1
  • 47
  • 71

(Another try at a comprehensive answer, summarizing comments, omitting names of commenters, and adding a bit of context:)

On any class $C$ of structures there is a natural quasiorderquasiorder: For two structures $A,B\in C$ we say $A \le B$ if there is a structure-preserving embedding of $A$ into $B$; this notion, as well as the related equivalence relation (bi-embeddability, $A\le B \ \wedge \ B\le A$) are ubiquitous in mathematics.

(By "embedding" I will always mean a structure-preserving 1-1 map; category theory offers an abstract variant of this notion, a "monic""monic" or "left cancellative" morphism. There is a natural dual notion, which I will ignore here.)

While the existence of an isomorphism between $A$ and $B$ clearly implies bi-embeddability, the converse is rare. Most prominently, the converse does hold for "naked sets" "structureless structures"; the Cantor-Schroeder-Bernstein theorem states theCantor-Schroeder-Bernstein theorem says that the existence of injective maps from $A$ to $B$ and from $B$ to $A$ implies the existence of a bijection.

Other examples are:

  • (trivially:) any class of finite structures

  • (slightly less trivially:) any class of well-ordered structures (if we require the embeddings to respect order)

For linear orderings, even for countable linear orderings, bi-embeddability does not imply isomorphism. However, LindenbaumLindenbaum proved the following curious fact (which is true in any cardinality): if a linear ordering $A$ is isomorphic to an initial segment (downwards closed set, ideal) of a linear ordering $B$, and $B$ is isomorphic to a final segment (upwards closed) of $A$, then $A$ and $B$ are isomorphic.

The rest of this answer will deal with countable structures only. (All the non-structure results mentioned will be "even more true" if uncountable structures are allowed. Structure theorems, such as Laver's theorem, either become more complicated or fail.)

CLO:= countable linear order.

For (countable) linear orders in general, bi-embeddability does not imply isomorphism. First, both the rational numbers as well as the closed rational unit interval are universal (contain an isomorphic copy of any linear countable order), and certainly any two universal CLOs are bi-embeddable.

Secondly, isomorphism preserves many properties of linear orders, such as the existence of a least element, the existence of an empty interval (p,q), the number of such intervals, etc. None of these is preserved under bi-embeddability.

Many classical theorems about linear orders can be found in Rosenstein's 1982 book "Linear Orderings", among them also Laver's theorem: The quasiorder of countable linear orders (under embeddability) is a well-quasi-order and even a "better quasi-order", and there are exactly $\aleph_1$ classes under bi-embeddability. (I find this theorem really remarkable, as I think this is one of the few cases where $\aleph_1$ rather than "continuum" or "a perfect set" appears as the answer to a question about cardinality, without any explicit reference to well-orders.)

Both Rosenstein's book and the wonderful book of "exercises""Problems and Theorems" by Komjath and Totik (which presents a nice short proof of Lindenbaum's theorem) are available legally from bookstores (and libraries) (Rosenstein, Komjath-Totik), and illegally from gigapedia.

(Another try at a comprehensive answer, summarizing comments, omitting names of commenters, and adding a bit of context:)

On any class $C$ of structures there is a natural quasiorder: For two structures $A,B\in C$ we say $A \le B$ if there is a structure-preserving embedding of $A$ into $B$; this notion, as well as the related equivalence relation (bi-embeddability, $A\le B \ \wedge \ B\le A$) are ubiquitous in mathematics.

(By "embedding" I will always mean a structure-preserving 1-1 map; category theory offers an abstract variant of this notion, a "monic" or "left cancellative" morphism. There is a natural dual notion, which I will ignore here.)

While the existence of an isomorphism between $A$ and $B$ clearly implies bi-embeddability, the converse is rare. Most prominently, the converse does hold for "naked sets" "structureless structures"; the Cantor-Schroeder-Bernstein theorem states the existence of injective maps from $A$ to $B$ and from $B$ to $A$ implies the existence of a bijection.

Other examples are:

  • (trivially:) any class of finite structures

  • (slightly less trivially:) any class of well-ordered structures (if we require the embeddings to respect order)

For linear orderings, even for countable linear orderings, bi-embeddability does not imply isomorphism. However, Lindenbaum proved the following curious fact (which is true in any cardinality): if a linear ordering $A$ is isomorphic to an initial segment (downwards closed set, ideal) of a linear ordering $B$, and $B$ is isomorphic to a final segment (upwards closed) of $A$, then $A$ and $B$ are isomorphic.

The rest of this answer will deal with countable structures only. (All the non-structure results mentioned will be "even more true" if uncountable structures are allowed. Structure theorems, such as Laver's theorem, either become more complicated or fail.)

CLO:= countable linear order.

For (countable) linear orders in general, bi-embeddability does not imply isomorphism. First, both the rational numbers as well as the closed rational unit interval are universal (contain an isomorphic copy of any linear countable order), and certainly any two universal CLOs are bi-embeddable.

Secondly, isomorphism preserves many properties of linear orders, such as the existence of a least element, the existence of an empty interval (p,q), the number of such intervals, etc. None of these is preserved under bi-embeddability.

Many classical theorems about linear orders can be found in Rosenstein's 1982 book "Linear Orderings", among them also Laver's theorem: The quasiorder of countable linear orders (under embeddability) is a well-quasi-order and even a "better quasi-order", and there are exactly $\aleph_1$ classes under bi-embeddability. (I find this theorem really remarkable, as I think this is one of the few cases where $\aleph_1$ rather than "continuum" or "a perfect set" appears as the answer to a question about cardinality, without any explicit reference to well-orders.)

Both Rosenstein's book and the wonderful book of "exercises" by Komjath and Totik (which presents a nice short proof of Lindenbaum's theorem) are available legally from bookstores, and illegally from gigapedia.

(Another try at a comprehensive answer, summarizing comments, omitting names of commenters, and adding a bit of context:)

On any class $C$ of structures there is a natural quasiorder: For two structures $A,B\in C$ we say $A \le B$ if there is a structure-preserving embedding of $A$ into $B$; this notion, as well as the related equivalence relation (bi-embeddability, $A\le B \ \wedge \ B\le A$) are ubiquitous in mathematics.

(By "embedding" I will always mean a structure-preserving 1-1 map; category theory offers an abstract variant of this notion, a "monic" or "left cancellative" morphism. There is a natural dual notion, which I will ignore here.)

While the existence of an isomorphism between $A$ and $B$ clearly implies bi-embeddability, the converse is rare. Most prominently, the converse does hold for "naked sets" "structureless structures"; the Cantor-Schroeder-Bernstein theorem says that the existence of injective maps from $A$ to $B$ and from $B$ to $A$ implies the existence of a bijection.

Other examples are:

  • (trivially:) any class of finite structures

  • (slightly less trivially:) any class of well-ordered structures (if we require the embeddings to respect order)

For linear orderings, even for countable linear orderings, bi-embeddability does not imply isomorphism. However, Lindenbaum proved the following curious fact (which is true in any cardinality): if a linear ordering $A$ is isomorphic to an initial segment (downwards closed set, ideal) of a linear ordering $B$, and $B$ is isomorphic to a final segment (upwards closed) of $A$, then $A$ and $B$ are isomorphic.

The rest of this answer will deal with countable structures only. (All the non-structure results mentioned will be "even more true" if uncountable structures are allowed. Structure theorems, such as Laver's theorem, either become more complicated or fail.)

CLO:= countable linear order.

For (countable) linear orders in general, bi-embeddability does not imply isomorphism. First, both the rational numbers as well as the closed rational unit interval are universal (contain an isomorphic copy of any linear countable order), and certainly any two universal CLOs are bi-embeddable.

Secondly, isomorphism preserves many properties of linear orders, such as the existence of a least element, the existence of an empty interval (p,q), the number of such intervals, etc. None of these is preserved under bi-embeddability.

Many classical theorems about linear orders can be found in Rosenstein's 1982 book "Linear Orderings", among them also Laver's theorem: The quasiorder of countable linear orders (under embeddability) is a well-quasi-order and even a "better quasi-order", and there are exactly $\aleph_1$ classes under bi-embeddability. (I find this theorem really remarkable, as I think this is one of the few cases where $\aleph_1$ rather than "continuum" or "a perfect set" appears as the answer to a question about cardinality, without any explicit reference to well-orders.)

Both Rosenstein's book and the wonderful book of "Problems and Theorems" by Komjath and Totik (which presents a nice short proof of Lindenbaum's theorem) are available legally from bookstores (and libraries) (Rosenstein, Komjath-Totik), and illegally from gigapedia.

Source Link
Goldstern
Goldstern
  • 14k
  • 1
  • 47
  • 71

(Another try at a comprehensive answer, summarizing comments, omitting names of commenters, and adding a bit of context:)

On any class $C$ of structures there is a natural quasiorder: For two structures $A,B\in C$ we say $A \le B$ if there is a structure-preserving embedding of $A$ into $B$; this notion, as well as the related equivalence relation (bi-embeddability, $A\le B \ \wedge \ B\le A$) are ubiquitous in mathematics.

(By "embedding" I will always mean a structure-preserving 1-1 map; category theory offers an abstract variant of this notion, a "monic" or "left cancellative" morphism. There is a natural dual notion, which I will ignore here.)

While the existence of an isomorphism between $A$ and $B$ clearly implies bi-embeddability, the converse is rare. Most prominently, the converse does hold for "naked sets" "structureless structures"; the Cantor-Schroeder-Bernstein theorem states the existence of injective maps from $A$ to $B$ and from $B$ to $A$ implies the existence of a bijection.

Other examples are:

  • (trivially:) any class of finite structures

  • (slightly less trivially:) any class of well-ordered structures (if we require the embeddings to respect order)

For linear orderings, even for countable linear orderings, bi-embeddability does not imply isomorphism. However, Lindenbaum proved the following curious fact (which is true in any cardinality): if a linear ordering $A$ is isomorphic to an initial segment (downwards closed set, ideal) of a linear ordering $B$, and $B$ is isomorphic to a final segment (upwards closed) of $A$, then $A$ and $B$ are isomorphic.

The rest of this answer will deal with countable structures only. (All the non-structure results mentioned will be "even more true" if uncountable structures are allowed. Structure theorems, such as Laver's theorem, either become more complicated or fail.)

CLO:= countable linear order.

For (countable) linear orders in general, bi-embeddability does not imply isomorphism. First, both the rational numbers as well as the closed rational unit interval are universal (contain an isomorphic copy of any linear countable order), and certainly any two universal CLOs are bi-embeddable.

Secondly, isomorphism preserves many properties of linear orders, such as the existence of a least element, the existence of an empty interval (p,q), the number of such intervals, etc. None of these is preserved under bi-embeddability.

Many classical theorems about linear orders can be found in Rosenstein's 1982 book "Linear Orderings", among them also Laver's theorem: The quasiorder of countable linear orders (under embeddability) is a well-quasi-order and even a "better quasi-order", and there are exactly $\aleph_1$ classes under bi-embeddability. (I find this theorem really remarkable, as I think this is one of the few cases where $\aleph_1$ rather than "continuum" or "a perfect set" appears as the answer to a question about cardinality, without any explicit reference to well-orders.)

Both Rosenstein's book and the wonderful book of "exercises" by Komjath and Totik (which presents a nice short proof of Lindenbaum's theorem) are available legally from bookstores, and illegally from gigapedia.