Re: what does it mean to say a logic is more expressive than another?


Rupert wrote:
Per Freem wrote:
hi,

i am curious about the following question: given two logics, what does
it mean to say one is 'more expressive' than the other? does it mean
that the more expressive logic admits models that no possible statement
in the less expressive one could admit? for example, it's clear that
second-order logic is more expressive than first-order predicate logic,
since the former allows quantification over predicates. but is that
the real reason that second-order logic is more expressive, or is it
more correct to use the models formulation i have just given? e.g. in
second-order logic i believe you can construct a sentence with only
infinite models, while in first-order logic you cannot.

is there a better definition than the models formulation? what if
given two logics, one had more expressivity in the sense that it had
more constructs but there existed a translation between them? for
example most nonmonotonic logics are first-order representable or have
some mapping to first order logic, but they still allow you to express
things like 'default rules' which in first order logic, you cannot do.
which is more expressive then?

thanks, --per

Suppose you have a particular class of structures. You have two
languages. Given any sentence in the first language, there exists a
sentence in the second language such that the class of structures which
are models for the sentence in the first language is the same as the
class of structures which are models for the sentence in the second
language. However, this is not the case when you swap the roles of the
two languages. In that case it would be reasonable to call the second
language more expressive than the first. This seems to be the
definition you were getting at, and I think it is the best definition.

.

Relevant Pages