Skip to main content
MathOverflow

Return to Answer

deleted 444 characters in body
Source Link
Willie Wong
Willie Wong
  • 39.1k
  • 4
  • 94
  • 176

In first-order logic, some of the most natural inheritance properties have been studied.

First, you should recall what a substructure means in the sense of model theory -- basically just that you're closed under all the operations of the bigger structure, and the interpretation of any relational symbols in your language agrees on tuples common to the two structures. (I'm using the "non-weak" sense in the link I provided.)

A first-order axiomatizable class of structures is closed under substructures if and only if it can be axiomatized by a set of universal sentences (of the form: \forall x\sb 1 \ldots \forall x\sb n \varphi(\overline{x}) http://latex.mathoverflow.net/png?%5Cforall%20x%5F1%20%5Cldots%20%5Cforall%20x%5Fn%20%5Cvarphi%28%5Coverline%7Bx%7D%29$\forall x_1 \ldots \forall x_n \varphi(\overline{x})$, where phi$\varphi$ is quantifier-free). Think of groups (in a language with a function symbol for inverses) or ordered groups.

A first-order axiomatizable class of structures is closed under superstructures if and only if it can be axiomatized by a set of existential sentences (\exists x\sb 1 \ldots \exists x\sb n \varphi(\overline{x}) http://latex.mathoverflow.net/png?%5Cexists%20x%5F1%20%5Cldots%20%5Cexists%20x%5Fn%20%5Cvarphi%28%5Coverline%7Bx%7D%29$\exists x_1 \ldots \exists x_n \varphi(\overline{x})$, with phi$\varphi$ quantifier-free).

An axiomatizable class of structures is closed under unions of ascending chains of superstructures if and only if it can be axiomatized by a set of "AE-sentences," of the form \forall x\sb 1 \ldots \forall x\sb n \exists y\sb 1 \ldots \exists y\sb m \varphi(\overline{x}, \overline{y}) http://latex.mathoverflow.net/png?%5Cforall%20x%5F1%20%5Cldots%20%5Cforall%20x%5Fn%20%5Cexists%20y%5F1%20%5Cldots%20%5Cexists%20y%5Fm%20%5Cvarphi%28%5Coverline%7Bx%7D%2C%20%5Coverline%7By%7D%29$\forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_m \varphi(\overline{x}, \overline{y})$ with phi$\varphi$ quantifier-free. Think of fields in the language with only the symbols for 0, 1, and the two field operations: the axiom expressing that every element has a muliplicative inverse is AE.

Inheritance under products in first-order logic is trickier. Any class that can be axiomatized by first-order Horn sentences is closed under products, but the converse is false, and I've never heard of a good syntactic characterization of such classes. (I think this is why logicians are so fond of ultraproducts, which automatically preserve the truth of all first-order sentences!)

I'm not sure how useful these results actually are, since many (most?) properties that algebraists care about are not first-order axiomatizable. E.g. the class of all Noetherian rings is not axiomatizable (by the compactness theorem).

In first-order logic, some of the most natural inheritance properties have been studied.

First, you should recall what a substructure means in the sense of model theory -- basically just that you're closed under all the operations of the bigger structure, and the interpretation of any relational symbols in your language agrees on tuples common to the two structures. (I'm using the "non-weak" sense in the link I provided.)

A first-order axiomatizable class of structures is closed under substructures if and only if it can be axiomatized by a set of universal sentences (of the form: \forall x\sb 1 \ldots \forall x\sb n \varphi(\overline{x}) http://latex.mathoverflow.net/png?%5Cforall%20x%5F1%20%5Cldots%20%5Cforall%20x%5Fn%20%5Cvarphi%28%5Coverline%7Bx%7D%29, where phi is quantifier-free). Think of groups (in a language with a function symbol for inverses) or ordered groups.

A first-order axiomatizable class of structures is closed under superstructures if and only if it can be axiomatized by a set of existential sentences (\exists x\sb 1 \ldots \exists x\sb n \varphi(\overline{x}) http://latex.mathoverflow.net/png?%5Cexists%20x%5F1%20%5Cldots%20%5Cexists%20x%5Fn%20%5Cvarphi%28%5Coverline%7Bx%7D%29, with phi quantifier-free).

An axiomatizable class of structures is closed under unions of ascending chains of superstructures if and only if it can be axiomatized by a set of "AE-sentences," of the form \forall x\sb 1 \ldots \forall x\sb n \exists y\sb 1 \ldots \exists y\sb m \varphi(\overline{x}, \overline{y}) http://latex.mathoverflow.net/png?%5Cforall%20x%5F1%20%5Cldots%20%5Cforall%20x%5Fn%20%5Cexists%20y%5F1%20%5Cldots%20%5Cexists%20y%5Fm%20%5Cvarphi%28%5Coverline%7Bx%7D%2C%20%5Coverline%7By%7D%29 with phi quantifier-free. Think of fields in the language with only the symbols for 0, 1, and the two field operations: the axiom expressing that every element has a muliplicative inverse is AE.

Inheritance under products in first-order logic is trickier. Any class that can be axiomatized by first-order Horn sentences is closed under products, but the converse is false, and I've never heard of a good syntactic characterization of such classes. (I think this is why logicians are so fond of ultraproducts, which automatically preserve the truth of all first-order sentences!)

I'm not sure how useful these results actually are, since many (most?) properties that algebraists care about are not first-order axiomatizable. E.g. the class of all Noetherian rings is not axiomatizable (by the compactness theorem).

In first-order logic, some of the most natural inheritance properties have been studied.

First, you should recall what a substructure means in the sense of model theory -- basically just that you're closed under all the operations of the bigger structure, and the interpretation of any relational symbols in your language agrees on tuples common to the two structures. (I'm using the "non-weak" sense in the link I provided.)

A first-order axiomatizable class of structures is closed under substructures if and only if it can be axiomatized by a set of universal sentences (of the form: $\forall x_1 \ldots \forall x_n \varphi(\overline{x})$, where $\varphi$ is quantifier-free). Think of groups (in a language with a function symbol for inverses) or ordered groups.

A first-order axiomatizable class of structures is closed under superstructures if and only if it can be axiomatized by a set of existential sentences ($\exists x_1 \ldots \exists x_n \varphi(\overline{x})$, with $\varphi$ quantifier-free).

An axiomatizable class of structures is closed under unions of ascending chains of superstructures if and only if it can be axiomatized by a set of "AE-sentences," of the form $\forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_m \varphi(\overline{x}, \overline{y})$ with $\varphi$ quantifier-free. Think of fields in the language with only the symbols for 0, 1, and the two field operations: the axiom expressing that every element has a muliplicative inverse is AE.

Inheritance under products in first-order logic is trickier. Any class that can be axiomatized by first-order Horn sentences is closed under products, but the converse is false, and I've never heard of a good syntactic characterization of such classes. (I think this is why logicians are so fond of ultraproducts, which automatically preserve the truth of all first-order sentences!)

I'm not sure how useful these results actually are, since many (most?) properties that algebraists care about are not first-order axiomatizable. E.g. the class of all Noetherian rings is not axiomatizable (by the compactness theorem).

Source Link
John Goodrick
John Goodrick
  • 4k
  • 22
  • 27

In first-order logic, some of the most natural inheritance properties have been studied.

First, you should recall what a substructure means in the sense of model theory -- basically just that you're closed under all the operations of the bigger structure, and the interpretation of any relational symbols in your language agrees on tuples common to the two structures. (I'm using the "non-weak" sense in the link I provided.)

A first-order axiomatizable class of structures is closed under substructures if and only if it can be axiomatized by a set of universal sentences (of the form: \forall x\sb 1 \ldots \forall x\sb n \varphi(\overline{x}) http://latex.mathoverflow.net/png?%5Cforall%20x%5F1%20%5Cldots%20%5Cforall%20x%5Fn%20%5Cvarphi%28%5Coverline%7Bx%7D%29, where phi is quantifier-free). Think of groups (in a language with a function symbol for inverses) or ordered groups.

A first-order axiomatizable class of structures is closed under superstructures if and only if it can be axiomatized by a set of existential sentences (\exists x\sb 1 \ldots \exists x\sb n \varphi(\overline{x}) http://latex.mathoverflow.net/png?%5Cexists%20x%5F1%20%5Cldots%20%5Cexists%20x%5Fn%20%5Cvarphi%28%5Coverline%7Bx%7D%29, with phi quantifier-free).

An axiomatizable class of structures is closed under unions of ascending chains of superstructures if and only if it can be axiomatized by a set of "AE-sentences," of the form \forall x\sb 1 \ldots \forall x\sb n \exists y\sb 1 \ldots \exists y\sb m \varphi(\overline{x}, \overline{y}) http://latex.mathoverflow.net/png?%5Cforall%20x%5F1%20%5Cldots%20%5Cforall%20x%5Fn%20%5Cexists%20y%5F1%20%5Cldots%20%5Cexists%20y%5Fm%20%5Cvarphi%28%5Coverline%7Bx%7D%2C%20%5Coverline%7By%7D%29 with phi quantifier-free. Think of fields in the language with only the symbols for 0, 1, and the two field operations: the axiom expressing that every element has a muliplicative inverse is AE.

Inheritance under products in first-order logic is trickier. Any class that can be axiomatized by first-order Horn sentences is closed under products, but the converse is false, and I've never heard of a good syntactic characterization of such classes. (I think this is why logicians are so fond of ultraproducts, which automatically preserve the truth of all first-order sentences!)

I'm not sure how useful these results actually are, since many (most?) properties that algebraists care about are not first-order axiomatizable. E.g. the class of all Noetherian rings is not axiomatizable (by the compactness theorem).