Skip to main content
added 26 characters in body
Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

Is there a sensible classification of the properties of structures with a given signature $\sigma$, e.g. graphs with $\sigma = \lbrace R \rbrace$?

For example like this:

  1. properties defined by first-order sentences over $\sigma$ (with or without specific syntactical properties)

  2. properties defined by monadic second-order sentences over $\sigma$ (with or without specific syntactical properties)

  3. properties stating the existence of another structure (of the same kind or another) and a specific mappingmapping relation to it

  4. properties stating that a given structure invariant has a specific value

  5. properties stating that a given structure invariant has a specific property

How can this list be expanded, can it be completed or can it never be exhaustive?

Is there a sensible classification of the properties of structures with a given signature $\sigma$, e.g. graphs with $\sigma = \lbrace R \rbrace$?

For example like this:

  1. properties defined by first-order sentences over $\sigma$ (with or without specific syntactical properties)

  2. properties defined by monadic second-order sentences over $\sigma$ (with or without specific syntactical properties)

  3. properties stating the existence of another structure (of the same kind or another) and a specific mapping to it

  4. properties stating that a given structure invariant has a specific value

  5. properties stating that a given structure invariant has a specific property

How can this list be expanded, can it be completed or can it never be exhaustive?

Is there a sensible classification of the properties of structures with a given signature $\sigma$, e.g. graphs with $\sigma = \lbrace R \rbrace$?

For example like this:

  1. properties defined by first-order sentences over $\sigma$ (with or without specific syntactical properties)

  2. properties defined by monadic second-order sentences over $\sigma$ (with or without specific syntactical properties)

  3. properties stating the existence of another structure (of the same kind or another) and a specific mapping relation to it

  4. properties stating that a given structure invariant has a specific value

  5. properties stating that a given structure invariant has a specific property

How can this list be expanded, can it be completed or can it never be exhaustive?

Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 54
  • 113

Classification of properties of structures

Is there a sensible classification of the properties of structures with a given signature $\sigma$, e.g. graphs with $\sigma = \lbrace R \rbrace$?

For example like this:

  1. properties defined by first-order sentences over $\sigma$ (with or without specific syntactical properties)

  2. properties defined by monadic second-order sentences over $\sigma$ (with or without specific syntactical properties)

  3. properties stating the existence of another structure (of the same kind or another) and a specific mapping to it

  4. properties stating that a given structure invariant has a specific value

  5. properties stating that a given structure invariant has a specific property

How can this list be expanded, can it be completed or can it never be exhaustive?