When does $(square P land square Q) to square (P land Q)$ hold?
up vote
2
down vote
favorite
If all axioms of classical propositional calculus hold and we work in modal logic that is at least K (ie. extremely weak), it is trivial to show $square(P land Q) to (square P land square Q)$. What other modality axioms, if any, have to be added for $(square P land square Q) to square (P land Q)$ to hold?
logic propositional-calculus proof-theory modal-logic hilbert-calculus
add a comment |
up vote
2
down vote
favorite
If all axioms of classical propositional calculus hold and we work in modal logic that is at least K (ie. extremely weak), it is trivial to show $square(P land Q) to (square P land square Q)$. What other modality axioms, if any, have to be added for $(square P land square Q) to square (P land Q)$ to hold?
logic propositional-calculus proof-theory modal-logic hilbert-calculus
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
If all axioms of classical propositional calculus hold and we work in modal logic that is at least K (ie. extremely weak), it is trivial to show $square(P land Q) to (square P land square Q)$. What other modality axioms, if any, have to be added for $(square P land square Q) to square (P land Q)$ to hold?
logic propositional-calculus proof-theory modal-logic hilbert-calculus
If all axioms of classical propositional calculus hold and we work in modal logic that is at least K (ie. extremely weak), it is trivial to show $square(P land Q) to (square P land square Q)$. What other modality axioms, if any, have to be added for $(square P land square Q) to square (P land Q)$ to hold?
logic propositional-calculus proof-theory modal-logic hilbert-calculus
logic propositional-calculus proof-theory modal-logic hilbert-calculus
edited Nov 12 at 23:21
Taroccoesbrocco
5,46261839
5,46261839
asked Nov 12 at 17:37
Michał Zapała
10712
10712
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
You don't need any other axiom, $(square P land square Q) to square (P land Q)$ is derivable in the system $mathbf{K}$, i.e. in the propositional calculus (with modus ponens and closure under substitution) augmented with the necessitation rule (i.e. if $A$ is derivable then $square A$ is derivable) and the distribution axiom (i.e. $square (P to Q) to (square P to square Q)$).
A formal proof in Hilbert system for $mathbf{K}$ is the following:
$P to (Q to (P land Q)) qquad$ (axiom for conjunction in propositional calculus)
$square (P to (Q to (P land Q))) qquad$ (necessitation rule applied to 1.)
$square (P to (Q to (P land Q))) to (square P to square (Q to (P land Q))) qquad$ (distribution axiom)
$square P to square (Q to (P land Q)) qquad$ (modus ponens of 3. and 2.)
$square (Q to (P land Q)) to (square Q to square (P land Q)) qquad$ (distribution axiom)$(square P to square(Q to (P land Q)) ) to big( ( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) big) qquad (*)$
$( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) qquad$ (modus ponens of 6. and 4.)
$(square P land square Q) to square(P land Q) qquad$ (modus ponens of 7. and 5.)
where the formula in ($*$) is derivable because it is an instance of the tautology in propositional $(p to q) to big( (q to (r to s)) to ((p land r) to s)big)$ obtained through the substitution
begin{equation}begin{cases}
p mapsto square P \
q mapsto square (Q to (P land Q)) \
r mapsto square Q \
s mapsto square (P land Q)
end{cases}end{equation}
Remind that, by the completeness theorem, any tautology in propositional calculus can be derived in a formal proof system such the Hilbert system.
For a reference, you can see "A New Introduction to Modal Logic" by Hughes and Cresswell, p. 27.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
You don't need any other axiom, $(square P land square Q) to square (P land Q)$ is derivable in the system $mathbf{K}$, i.e. in the propositional calculus (with modus ponens and closure under substitution) augmented with the necessitation rule (i.e. if $A$ is derivable then $square A$ is derivable) and the distribution axiom (i.e. $square (P to Q) to (square P to square Q)$).
A formal proof in Hilbert system for $mathbf{K}$ is the following:
$P to (Q to (P land Q)) qquad$ (axiom for conjunction in propositional calculus)
$square (P to (Q to (P land Q))) qquad$ (necessitation rule applied to 1.)
$square (P to (Q to (P land Q))) to (square P to square (Q to (P land Q))) qquad$ (distribution axiom)
$square P to square (Q to (P land Q)) qquad$ (modus ponens of 3. and 2.)
$square (Q to (P land Q)) to (square Q to square (P land Q)) qquad$ (distribution axiom)$(square P to square(Q to (P land Q)) ) to big( ( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) big) qquad (*)$
$( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) qquad$ (modus ponens of 6. and 4.)
$(square P land square Q) to square(P land Q) qquad$ (modus ponens of 7. and 5.)
where the formula in ($*$) is derivable because it is an instance of the tautology in propositional $(p to q) to big( (q to (r to s)) to ((p land r) to s)big)$ obtained through the substitution
begin{equation}begin{cases}
p mapsto square P \
q mapsto square (Q to (P land Q)) \
r mapsto square Q \
s mapsto square (P land Q)
end{cases}end{equation}
Remind that, by the completeness theorem, any tautology in propositional calculus can be derived in a formal proof system such the Hilbert system.
For a reference, you can see "A New Introduction to Modal Logic" by Hughes and Cresswell, p. 27.
add a comment |
up vote
4
down vote
accepted
You don't need any other axiom, $(square P land square Q) to square (P land Q)$ is derivable in the system $mathbf{K}$, i.e. in the propositional calculus (with modus ponens and closure under substitution) augmented with the necessitation rule (i.e. if $A$ is derivable then $square A$ is derivable) and the distribution axiom (i.e. $square (P to Q) to (square P to square Q)$).
A formal proof in Hilbert system for $mathbf{K}$ is the following:
$P to (Q to (P land Q)) qquad$ (axiom for conjunction in propositional calculus)
$square (P to (Q to (P land Q))) qquad$ (necessitation rule applied to 1.)
$square (P to (Q to (P land Q))) to (square P to square (Q to (P land Q))) qquad$ (distribution axiom)
$square P to square (Q to (P land Q)) qquad$ (modus ponens of 3. and 2.)
$square (Q to (P land Q)) to (square Q to square (P land Q)) qquad$ (distribution axiom)$(square P to square(Q to (P land Q)) ) to big( ( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) big) qquad (*)$
$( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) qquad$ (modus ponens of 6. and 4.)
$(square P land square Q) to square(P land Q) qquad$ (modus ponens of 7. and 5.)
where the formula in ($*$) is derivable because it is an instance of the tautology in propositional $(p to q) to big( (q to (r to s)) to ((p land r) to s)big)$ obtained through the substitution
begin{equation}begin{cases}
p mapsto square P \
q mapsto square (Q to (P land Q)) \
r mapsto square Q \
s mapsto square (P land Q)
end{cases}end{equation}
Remind that, by the completeness theorem, any tautology in propositional calculus can be derived in a formal proof system such the Hilbert system.
For a reference, you can see "A New Introduction to Modal Logic" by Hughes and Cresswell, p. 27.
add a comment |
up vote
4
down vote
accepted
up vote
4
down vote
accepted
You don't need any other axiom, $(square P land square Q) to square (P land Q)$ is derivable in the system $mathbf{K}$, i.e. in the propositional calculus (with modus ponens and closure under substitution) augmented with the necessitation rule (i.e. if $A$ is derivable then $square A$ is derivable) and the distribution axiom (i.e. $square (P to Q) to (square P to square Q)$).
A formal proof in Hilbert system for $mathbf{K}$ is the following:
$P to (Q to (P land Q)) qquad$ (axiom for conjunction in propositional calculus)
$square (P to (Q to (P land Q))) qquad$ (necessitation rule applied to 1.)
$square (P to (Q to (P land Q))) to (square P to square (Q to (P land Q))) qquad$ (distribution axiom)
$square P to square (Q to (P land Q)) qquad$ (modus ponens of 3. and 2.)
$square (Q to (P land Q)) to (square Q to square (P land Q)) qquad$ (distribution axiom)$(square P to square(Q to (P land Q)) ) to big( ( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) big) qquad (*)$
$( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) qquad$ (modus ponens of 6. and 4.)
$(square P land square Q) to square(P land Q) qquad$ (modus ponens of 7. and 5.)
where the formula in ($*$) is derivable because it is an instance of the tautology in propositional $(p to q) to big( (q to (r to s)) to ((p land r) to s)big)$ obtained through the substitution
begin{equation}begin{cases}
p mapsto square P \
q mapsto square (Q to (P land Q)) \
r mapsto square Q \
s mapsto square (P land Q)
end{cases}end{equation}
Remind that, by the completeness theorem, any tautology in propositional calculus can be derived in a formal proof system such the Hilbert system.
For a reference, you can see "A New Introduction to Modal Logic" by Hughes and Cresswell, p. 27.
You don't need any other axiom, $(square P land square Q) to square (P land Q)$ is derivable in the system $mathbf{K}$, i.e. in the propositional calculus (with modus ponens and closure under substitution) augmented with the necessitation rule (i.e. if $A$ is derivable then $square A$ is derivable) and the distribution axiom (i.e. $square (P to Q) to (square P to square Q)$).
A formal proof in Hilbert system for $mathbf{K}$ is the following:
$P to (Q to (P land Q)) qquad$ (axiom for conjunction in propositional calculus)
$square (P to (Q to (P land Q))) qquad$ (necessitation rule applied to 1.)
$square (P to (Q to (P land Q))) to (square P to square (Q to (P land Q))) qquad$ (distribution axiom)
$square P to square (Q to (P land Q)) qquad$ (modus ponens of 3. and 2.)
$square (Q to (P land Q)) to (square Q to square (P land Q)) qquad$ (distribution axiom)$(square P to square(Q to (P land Q)) ) to big( ( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) big) qquad (*)$
$( square(Q to (P land Q)) to (square Q to square(P land Q) )) to ((square P land square Q) to square(P land Q) qquad$ (modus ponens of 6. and 4.)
$(square P land square Q) to square(P land Q) qquad$ (modus ponens of 7. and 5.)
where the formula in ($*$) is derivable because it is an instance of the tautology in propositional $(p to q) to big( (q to (r to s)) to ((p land r) to s)big)$ obtained through the substitution
begin{equation}begin{cases}
p mapsto square P \
q mapsto square (Q to (P land Q)) \
r mapsto square Q \
s mapsto square (P land Q)
end{cases}end{equation}
Remind that, by the completeness theorem, any tautology in propositional calculus can be derived in a formal proof system such the Hilbert system.
For a reference, you can see "A New Introduction to Modal Logic" by Hughes and Cresswell, p. 27.
edited Nov 12 at 23:22
answered Nov 12 at 18:58
Taroccoesbrocco
5,46261839
5,46261839
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2995598%2fwhen-does-square-p-land-square-q-to-square-p-land-q-hold%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown