On 06 Feb 2014, at 07:39, LizR wrote:
On 6 February 2014 08:25, Bruno Marchal <[email protected]> wrote:
Which among the next symbolic expressions is the one being a well
formed formula:
((p -> q) -> ((p& (p V r)) -> q))
))(p-)##à89-< a -> q)
OK?
I sure hope so.
Well, I will pray a little bit.
(to be sure the irst one might contain a typo, but I assure you
there are no typo in the second one (and there is no cat walking on
the keyboard).
***
Then a set of worlds get alive when each proposition (p, q, r), in
each world get some truth value, t, or f. I will say that the
mutiverse is illuminated.
And we can decide to put f and t is the propositional symbol for the
boolean constant true and false.
(meaning that "p -> f" is a proposition, or well formed formula).
In modal logic it is often simpler to use only the connector "->"
and that if possible if you have the constant f.
For example you can define ~p as an abbreviation for (p -> f), as
you should see by doing a truth table. OK?
p -> f is (~p V f), for which the truth table is indeed the same as ~p
OK.
(Can you define "&", "V", with "->" and "f" in the same way? This is
not an exercise, just a question!).
I don't think I can define those *literally* with p, -> and f if
that's what you mean.
That is what I mean, indeed.
But that doesn't make sense, because & requires two arguments, so it
would have to be something like ... well, p -> q is (~p V q) and
it's also ~(p & ~q), which contain V and & ... I'm not sure I know
what you mean.
Like for "~", to define "&" and "V" to a machine which knows only "-
>" and "f". You can use the "~", as you have alredy see that you
can define it with "->" and "f".
I reason aloud. Please tell me if you understand.
First we know that "p -> q" is just "~p V q", OK?
So the "V" looks already close to "->". Except that instead of "~p V
q" (which is p -> q) we want "p V q".
May be we can substitute just p by ~p: and p V q might be then ~p -> q,
Well, you can do the truth table of ~p -> q, and see that it is the
same as p V q.
To finish it of course, we can eliminate the "~", and we have that p V
q is entirely defined by (p -> f) -> q.
OK?
And the "&":
Well, we already know a relationship between the "&" and the "V", OK?
The De Morgan relations.
So, applying the de Morgan relation, p & q is the same as ~(~p V ~q),
(the same "logically", not pragmatically, of course).
That solves the problem.
But we can verify, perhaps simplify. We can eliminate the "V" by the
definition above (A V B = ~A -> B),
~(~p V ~q) becomes ~(~~p -> ~q), that is ~(p -> ~q). Or, to really
settle the things, and define & from -> and f:
p & q = ((p -> (q -> f)) -> f).
OK?
Each world, once "illuminated" (that is once each proposition letter
has a value f or t) inherits of the semantics of classical
proposition logic.
This means that if p and q are true in some world alpha, then (p &
q) is true in that world alpha, etc.
in particular all tautologies, or propositional laws, is true in all
illuminated multiverse, and this for all illuminations (that for all
possible assignment of truth value to the world).
OK?
Question: If the multiverse is the set {a, b}, how many illuminated
multiverses can we get?
I suppose 4, since we have a world with 2 propositions, and each can
be t or f?
Answer: there is three letters p, q, r, leading to eight valuations
possible in a, and the same in b, making a total of 64 valuations,
if I am not too much distracted. I go quick. This is just to test if
you get the precise meanings.
Oh, OK. So a and b are worlds, not ... sorry. I see.
Good.
So that is 2^3 x 2^3 because a has p,q,r = 3 values, all t or f, as
does b. OK now I see what you meant.
OK.
Of course with the infinite alphabet {p, q, r, p1, q1, r1, p2, ... }
we already have a continuum of multiverses.
I can't quite see why it's a continuum. Each world has a countable
infinity of letters, and the number of worlds is therefore 2 ^
countable infinity! Is that a continuum?
Yes. We proved it, Liz.
Take a the infinite propositional symbol letters {p, q, r, p1, q1, r1,
p2, ... } . They are well ordered. So a sequence of 1 and 0 (other
common name for t and f) can be interpreted as being a valuation. The
valuation are the infinite sequences of 1 and 0. Or the function from
N to {0, 1}.
If such a set of function was in bijection with N, i -> f_i, the
function g defined by g(n) = f_n(n) + 1 would be a function f_i, let
us sat f_k, and f_k, applied on k, would gives both f_k(k) + 1 and
f_k(k), and be well defined, making 0 = 1.
My transfinite maths may not be quite up to that one.
The infinite sequence of 0, and 1, if you put "0." at the front, you get
0.000011011111000011101101011111111000...
for all sequences of 0 and 1, that is you get the real numbers,
written in binary, belonging to the interval (0, 1].
That is the continuum. 2^aleph_0.
Well, that was Leibniz sort of multiverse, with all worlds quite
independent of each other.
With Kripke, we introduce a binary relation R on the set of world.
That's all. We read alpha R beta, as beta is accessible from alpha.
This seems like a way of getting subsets from the multiverse, but
I'm not completely sure what accessible means here.
I give you a concrete example. I take the set {a, b, c, d, e}, as the
set of worlds. That is already enough to get a Leibnizian multiverse,
which for all valuations (illuminations) of its propositional letters,
in all worlds, obeys classical logic, extended by the modal laws:
[](A->B) -> ([]A -> []B)
[]A -> [][]A
<>A -> []<>A
[]A -> <>A
p -> []<>A
As you have verified OK?
It is nice, but we want modal logic in which those modal laws are
independent, semantically, and later deductively.
So Kripke added a relation of accessibility between the worlds. And
the Kripke multiverse are any set (of "worlds") having a binary
relation.
So, to get a Kripke multiverse, I add, or not (!) a binary relation.
Written R. (but we could use another name).
So the following are example of kripke multiverse:
1) the set {a, b, c, d, e}, together with the complete relation: all
worlds can access to all worlds. We will get xRy for all worlds x y in
{a, b, c, d, e}.
2) the set {a, b, c, d, e}, together with the empty relation, no world
can access to any other worlds, nor even themselves. A dust of cul-de-
sac world!
3) the set {a, b, c, d, e} with the relation aRb, cRc, and dRe. And
that all.
4) any relation you want about: well good exercise: how many binary
relations can we defined on {a, b, c, d, e} ?
Answer: A relation on {a, b, c, d, e} is really just a part, or a
subset, of the cartesian product
{a, b, c, d, e} X {a, b, c, d, e},
And a subset is really (modulo natural bijection) a function from that
set in the set {0, 1},
so we have 2^(5*5), that is 33554432 Kripke multiverse (non
illuminated!).
A Leibniz multiverse is just a set.
A Kripke multiverse is just a set with a binary relations.
The set of reals, with the relation x < y, is also an example of
kripke multiverse. Using R instead of {a, b, c, d, e}.
The goal of the logician is not to explore the mutiverses, but to find
couterexamples to invalidate reasoning, notably here, modal reasoning.
OK. Time for the main recall:
We add then new unary connector "[]", and define <> by ~[]~
In Leibniz semantics, []A is true (absolutely) means that A is true
in all worlds.
The lines above are the important line.
And even more important is the passage from the line above to the line
below
In Kripke semantics []A is true in a world alpha means that A is
true in all worlds accessible from alpha.
If you remember this, there should be no problem.
And the only one exercise:
prove that "[]A -> A" is true in all worlds of a multiverse, for all
illumination possible (choice of valuation for the letter)
So []A means the proposition A is true in all worlds accessible
from ... somewhere.
Yes and no. []A has no more meaning at all.
In Kripke semantic all statements are relativized to the world you are
in. []A can be true in some world and false in another. The meaning of
"[]" is restricted, for each world, to the world they can access
(through the accessibility relation available in the Kripke multiverse).
[]A still keep a meaning, but only in each world. So everything is
said when we define the new meaning of "[]" by the rule
[]A is true in alpha, by definition, means that A is true in all world
beta *accessible* from alpha.
And
<>A is true in alpha iff there is a world beta; where A is true,
accessible from alpha.
Oh dear. I don't seem to be able to get my head around this.
That happens. Tell me if the explanations above help. Ask any question.
Maybe because I'm not sure what accessible means here...
Just keep in mind the definition: a Kripke muliverse is just a set
with a binary relation (any one you like a priori (the goal will be to
find counter-example, notably to Leibinizian laws).
I let you breath, and will come back, if you don't mind, I am aware I
go quick.
Do extremely simple exercise, build simple multiverse, with few
worlds, and simple relations accessibility, then illuminate them by
assignment of t or f (1 or 0) to p, and q, in those world, evaluate
the formula, by using classical logic, and the "new" definition of the
meaning of "[]".
Do that with your son!
Can you find counter-example to the Leibnizian laws?
This is not an exercise, just a remind of Kripke's goal. To contradict
all (well not all) leibnizian quasi "obvious" modal tautologies, and
refined considerably the field and the use of modal logical systems
(something known by the deductive approach, and older more topological
or algebraical semantics).
Next post: the discovery of a Kripke multiverse violating the
Leibnizian law []A -> A. (tataaaah... :)
Bruno
iff the relation is reflexive (that is: all world can access
themselves).
Hint: this should be easy. Any difficulty here is due to my probable
unclarity, or my excess of verbosity, or a lack of familiarity with
math of your part. I suggest you might search for counterexample.
And yes, this is truly two exercises, because to prove an iff, you
have to prove two if. You must prove:
1) if a multiverse is reflexive, then, whatever the illumination is,
each world satisfy []A -> A (for all formula A).
2) If, whatever the illumination is, each world satisfy []A -> A
(for all formula A), then the multiverse is reflexive.
"whatever the illumination" is important: for example in the simple
multiverse with one world: {alpha}, and the empty accessibility
relation (so that alpha does not access to itself, ~ (alpha R
alpha), and with p valuated to 1 in alpha, you have that []p is
true, p is true, so []p -> p is true in alpha, yet the mutiverse is
not reflexive.
OK?
Please, ask any question to clarify. Note in passing the beauty: a
modal formula, made into a law, impose some structure on a Kripke
multiverse, and inversely, an accessibility structure on a
multiverse impose a modal law.
And now a free subject of reflexion :) (to prepare the sequel)
If reflexivity in Kripke multiverse characterizes []A -> A
Which relations can characterize the following formula?
The Leibnizian one:
[]A -> [][]A
[]A -> <>A
p -> []<>A
<>A -> []<>A
[](A->B) -> ([]A -> []B)
And what about (more hard) the non Leibnizian one, which will play
some role (as scheme of some machines discourses)
<>A -> ~[]<>A (related to Gödel)
[]([]A -> A) -> []A (related to Löb)
[]([](p -> []p) -> p) -> p (related to Grzegorczyk, the Grz of
S4Grz).
Bruno
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
