This is primarily a question about related literature. I am looking for specific references, or terminology that I can use to search for references.

Let A a well defined mathematical structure of some sort: string, graph, etc. Let P be the set of all properties of A. By this I really mean to include all true statements about A. (For example, P could contain, among other things, any Turing machine that outputs a 1 on some representation of A.)

What area, if any, has even attempted to tackle such a formalization? Logic? Formal language theory? Model theory? Set theory?

I know my question is slightly vague, but I am hoping to get some related work which will help me cast my question it in the right framework.


For some family of structures A, I would like to obtain a formal way of talking about all possible properties of A. I need the language for describing these properties to be ``computable:'' I would like to design algorithms that examine these properties and compute using them. I am looking for any terminology or references that will help me achieve this goal. Answers would be more appreciated if they also provide examples of how properties may be discussed in the framework being suggested.


2 Answers 2


I'm no expert in this area, but I do have some background in mathematical logic, so I'll give it a shot.

Indeed, a vast amount of work has been done in this area over the last century (e.g. Godel, Tarski). Your first look should be towards model theory; Wilfred Hodges' "A shorter model theory" is a great place to start and should keep you busy for quite some time. You'll learn about relational structures (a very general type of mathematical structure via which all of the objects you mentioned can be realized), the "first-order languages" associated to these structures, and all of the true, "first-order" statements that you can make about them, using the basic underlying relations and functions on your objects as the primitive elements of your language.

You need to be careful however about what you mean by the "set of all true statements you can make about ...". One must always have in mind a well defined language with which you are allowed to make statements and formulas, and the most commonly studied is first-order languages. I'll leave it to Hodges to explain the particulars, but the defining feature of first-order is, you are only allowed to quantify over elements of your structure, not subsets. For example, the following is a first-order statement in the (typical) language of fields, let's say about the real numbers $\mathbb{R}$:

"(for all elements x and y of $\mathbb{R}$)( x*y = y*x)"

which is obviously asserting that multiplication in $\mathbb{R}$ is commutative. However, the following is not first-order:

"(for all subsets $S$ of $\mathbb{R}$)(if $S$ is bounded from above, then it has a least upper bound)"

which is asserting the completeness property of $\mathbb{R}$. It can be shown in fact, no matter how clever you are, you can't express the completeness property of the reals in a first-order way.

Despite its inherent limitations, there are very good reasons for restricting yourself to first-order languages, whenever possible. Firstly, it is a wonderfully expressive language, and there are in fact a good many interesting mathematical statements one can make with it. But secondly, and more importantly, first-order logic satisfies some extremely useful regularity conditions, ones that higher order languages (e.g. those that allow quantification over subsets) do not, and is in some sense the most robust language that satisfies these conditions. Principal among them are the so-called compactness theorem for first-order logic, and Godel's completeness (not incompleteness!) theorem.

But anyway, check out Hodges' book. He's an extremely readable and enlightening author, especially for a logician.

  • $\begingroup$ Thank you Mike, I will definitely check out this Hodges person. Indeed, I am interested in a much narrower set of structures A, and intend to define a formal language for describing objects and properties about them. I framed the question broadly in the hopes that more people will be able to provide help. Thanks! $\endgroup$ Jul 1, 2012 at 2:42
  • 1
    $\begingroup$ How about a vote on which answer you like best? $\endgroup$ Jul 18, 2012 at 3:47

If the class of structures is infinite there are going to be uncountably many properties. So there is no computable language that can capture all of them since any computable language is going to be countable.

If the class of structures is finite, there are (essentially) finite number of properties corresponding to the subsets of the classes. Consider binary numbers where bit $i$ represents whether the $i$th structure has the property.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.