Big Red Jeff Rubard
2010-02-06 18:24:53 UTC
The Metamathematics of the Mathematics of Metamathematics
----
Bisimulation: A Metaphysical Perspective
Since I’ve already explained how models of (propositional) modal logic
work, I feel comfortable talking about a logical concept that doesn’t
get much play in the philosophical world: bisimulation. In computer
science, bisimulation relates labeled transition systems, which are a
convenient notation for modeling computational processes; an LTS
consists of a (possibly infinite) set of computational states and
“labeled” transition arrows from one state to another (or back to
itself). Two LTSes are “bisimilar” if a relation exists between them
which maps the states and transitions of one system onto those of the
other, and vice versa. (These sort of methods, known as “back and
forth conditions”, play an important role in other sectors of
mathematical logic as well.) This bisimilarity preserves computational
structure: no “moves” in the computation will be lost by using one of
the systems rather than the other.
Since Kripke models of modal logics consist of states (possible
worlds) and transitions (the accessibility relation), bisimulation
applies to them too. In fact, the specifically “modal” formulas of a
Kripke model are the ones preserved by bisimulation: formulas in first-
order logic can be true in a model and not true in a bisimilar model,
but since the truth of propositional modal formulas depends only on
the “local” character of possible worlds and the accessibility
relation connecting those worlds, both of which are “mapped” by the
bisimulation relation, it cannot vary between bisimilar models.
Everybody who is a CS-inflected modal logician thinks this is a big
deal: why should anyone else care? Well, I’ve been thinking (very
speculative) thoughts about this for a couple of years, and here’s
what I can come up with.
I’ve spoken before about David Lewis’ use of a “counterpart” relation
of similarity between individuals in possible worlds to analyze modal
phenomena like counterfactual conditionals. Now, it seems to me that
bisimulation is something like a “global” or metalinguistic
counterpart relation, operating on the level of Weltanschauungen
rather than possible individuals: and (abstracting away complications
introduced by moving to the level of modal predicate logic) this could
have lots of important consequences for modal analyses of language and
other more “subjective” modal phenomena. For instance, perhaps we
might say that two terms of Chomskyan “I-language” are synonymous if
the structures of the computational “mind/brains” that realize them
are bisimilar, or that two social processes are functionally
equivalent if their normative consequences map onto each other in this
way.
Obviously this requires a lot more work to be anything other than a
suggestive image, but I’ve thought for a while it’s a little
unfortunate that newer logical concepts like bisimulation don’t
regularly make their way into “rigorous” analytic philosophy. At any
rate, it enthuses me quite a bit. (Perhaps determining that the
discourses of two people are “bisimilar” and using one to model the
behavior of another is just as sophomoric a temptation as a
phenomenologist’s urge to put someone under the “epoché” at a party,
but on the other hand words and concepts are our own to use, requiring
only logical coherence and maybe a little historical good sense.)
----
The Metamathematics of the Mathematics of Metamathematics
Riddle me this, algebraic logicians and model theorists: a filter
defines a set D over a “base” set I where the “meet” (intersection) of
two set elements is a member of the set and set inclusion is
transitive (a set included in a subset of D is also a member of D). If
you are modeling propositional logic with a Boolean algebra or first-
order logic with a cylindric algebra, a filter on the algebra defines
a theory: the representation of a conjunctive statement is only
included in the filter if the two conjuncts both are, preserving truth
in the fashion of regular model theory.
Now, Rasiowa and Sikorski told us a long time ago that a proper filter
(one which does not include the empty set) defines a consistent theory
(one which does not include falsum as one of its consequences), and a
maximal proper filter (one not included in any other filter) defines a
complete theory (one where either a statement or its negation is
true). Now, in model theory maximal proper filters are called
ultrafilters, and the equivalence class of functional values for
functions with range I and domain in D is called an ultraproduct, or
an ultrapower when the filter is an ultrafilter.
Question: given the basic algebraic logic above, isn’t an ultrapower
equivalent to the set of logical consequences of the “axioms” I, i.e.
all the theorems of a theory? It seems it must be, and although
ultrapowers are not introduced in this way, if it’s so it’s
illuminating.
~ by jeffrubard on May 17, 2008.
----
*Point d'caption*:
http://www.worldcat.org/oclc/235547&referer=brief_results
----
*Point d'capitation* [!!!!]:
----
Bisimulation: A Metaphysical Perspective
Since I’ve already explained how models of (propositional) modal logic
work, I feel comfortable talking about a logical concept that doesn’t
get much play in the philosophical world: bisimulation. In computer
science, bisimulation relates labeled transition systems, which are a
convenient notation for modeling computational processes; an LTS
consists of a (possibly infinite) set of computational states and
“labeled” transition arrows from one state to another (or back to
itself). Two LTSes are “bisimilar” if a relation exists between them
which maps the states and transitions of one system onto those of the
other, and vice versa. (These sort of methods, known as “back and
forth conditions”, play an important role in other sectors of
mathematical logic as well.) This bisimilarity preserves computational
structure: no “moves” in the computation will be lost by using one of
the systems rather than the other.
Since Kripke models of modal logics consist of states (possible
worlds) and transitions (the accessibility relation), bisimulation
applies to them too. In fact, the specifically “modal” formulas of a
Kripke model are the ones preserved by bisimulation: formulas in first-
order logic can be true in a model and not true in a bisimilar model,
but since the truth of propositional modal formulas depends only on
the “local” character of possible worlds and the accessibility
relation connecting those worlds, both of which are “mapped” by the
bisimulation relation, it cannot vary between bisimilar models.
Everybody who is a CS-inflected modal logician thinks this is a big
deal: why should anyone else care? Well, I’ve been thinking (very
speculative) thoughts about this for a couple of years, and here’s
what I can come up with.
I’ve spoken before about David Lewis’ use of a “counterpart” relation
of similarity between individuals in possible worlds to analyze modal
phenomena like counterfactual conditionals. Now, it seems to me that
bisimulation is something like a “global” or metalinguistic
counterpart relation, operating on the level of Weltanschauungen
rather than possible individuals: and (abstracting away complications
introduced by moving to the level of modal predicate logic) this could
have lots of important consequences for modal analyses of language and
other more “subjective” modal phenomena. For instance, perhaps we
might say that two terms of Chomskyan “I-language” are synonymous if
the structures of the computational “mind/brains” that realize them
are bisimilar, or that two social processes are functionally
equivalent if their normative consequences map onto each other in this
way.
Obviously this requires a lot more work to be anything other than a
suggestive image, but I’ve thought for a while it’s a little
unfortunate that newer logical concepts like bisimulation don’t
regularly make their way into “rigorous” analytic philosophy. At any
rate, it enthuses me quite a bit. (Perhaps determining that the
discourses of two people are “bisimilar” and using one to model the
behavior of another is just as sophomoric a temptation as a
phenomenologist’s urge to put someone under the “epoché” at a party,
but on the other hand words and concepts are our own to use, requiring
only logical coherence and maybe a little historical good sense.)
----
The Metamathematics of the Mathematics of Metamathematics
Riddle me this, algebraic logicians and model theorists: a filter
defines a set D over a “base” set I where the “meet” (intersection) of
two set elements is a member of the set and set inclusion is
transitive (a set included in a subset of D is also a member of D). If
you are modeling propositional logic with a Boolean algebra or first-
order logic with a cylindric algebra, a filter on the algebra defines
a theory: the representation of a conjunctive statement is only
included in the filter if the two conjuncts both are, preserving truth
in the fashion of regular model theory.
Now, Rasiowa and Sikorski told us a long time ago that a proper filter
(one which does not include the empty set) defines a consistent theory
(one which does not include falsum as one of its consequences), and a
maximal proper filter (one not included in any other filter) defines a
complete theory (one where either a statement or its negation is
true). Now, in model theory maximal proper filters are called
ultrafilters, and the equivalence class of functional values for
functions with range I and domain in D is called an ultraproduct, or
an ultrapower when the filter is an ultrafilter.
Question: given the basic algebraic logic above, isn’t an ultrapower
equivalent to the set of logical consequences of the “axioms” I, i.e.
all the theorems of a theory? It seems it must be, and although
ultrapowers are not introduced in this way, if it’s so it’s
illuminating.
~ by jeffrubard on May 17, 2008.
----
*Point d'caption*:
http://www.worldcat.org/oclc/235547&referer=brief_results
----
*Point d'capitation* [!!!!]: