1. Alphabet of symbols(infinite):
$$
\neg ,(,),p_{ 1 },p_{ 2 },p_{ 3 },\quad ...
$$
2. Set of wfs. Instead of specifying the set explicitly we give an inductive rule in three parts.
(i) $p_{i}$ is a wf. for each $i>1$.
(ii) if $\phi$ and $\chi$ are wfs. then $(\neg\phi)$ and $(\phi \rightarrow \chi)$ are wfs.
(ii) The set of all wfs. is generated by (i) and (ii).
3. Axioms.There are infinitely many axioms, so we cannot list them all. However we can specify all of them by means of three axiom schemes.For any wfs.
$\phi$,$\chi$, $\zeta$, the following wfs. are axioms of L:
(L1) $(\phi \rightarrow (\chi \rightarrow \phi))$
(L2) $(\phi \rightarrow (\chi \rightarrow \zeta)) \rightarrow ((\phi \rightarrow \chi) \rightarrow (\phi \rightarrow \zeta))$
(L3) $((\neg \phi) \rightarrow (\neg \chi)) \rightarrow (\chi \rightarrow \phi)$
Note that each axiom scheme has infinitely many 'instances', as $\phi,\chi,\zeta$rane over all wfs of L.
4. Rules of deduction. In L there is only one rule of deduction. namely modus ponens(abbreviated by MP). It says: From $\phi$ and $(\phi \rightarrow \chi)$, $\chi$ is a direct consequence, where $\phi$ and $\chi$ are wfs. of L.
-----------------------------------------------------------------------------
Definition 2.2
A proof in L is a sequence of wfs. $\phi_{1}, ..., \phi_{n}$ such for each i $(1\leq i\leq n)$, either $\phi_{i}$ is anaxiom of L or $\phi_{i}$ follows from two previus members of the sequence, say $\phi_{j}$ and $\phi_{k}$ $(j<i,k<i)$ as a direct consequence using the rule of deduction MP. Such a proof will be referred to as a proof of $\phi_{n}$ in L. and $\phi_{n}$ is said to be a theorem of L.
Remark 2.3
(a) in the above deifintion, observe that $\phi_{i}$ and $\phi_{k}$ must necessarily be of the form $\chi$ and $\chi \rightarrow \phi_{i}$, or vice versa.
(b) If $\phi_{1}, ..., \phi_{n}$ is a proof in L and $k<n$ then $\phi_{1}, ..., \phi_{k}$ is also a proof in L(its clearly satisfies the definition), and so $\phi_{k}$ is a theorem of L.
(c) Axioms of L are certainly theorem of L. Their proofs in L are one-member sequences.
----------------------------------------------------------------------------------
Definiton 2.5
Let $\Gamma $ be a set of wfs. of L (which may or may not be axioms or theorems of L). A sequence $\phi_{1},...,\phi_{n}$ of wfs. of L is a deduction from $\Gamma$ if for each i $(1\leq i \leq n)$
, one of the following holds:
(a) $\phi_{i}$ is an axiom of L,
(b) $\phi_{i}$ is a member of $\Gamma$, or
(c) $\phi_{i}$ follows from two previous members of the sequence as direct consequence using MP.
So a deduction from $\Gamma$ is just a 'proof' in which the members of $\Gamma$ are considered as temporary axioms.
the last Member $\phi_{n}$, of a sequence which is a deduction from $\Gamma$ is said to be deducible from $\Gamma$, or to be a consequence of $\Gamma$ in L.
if a wf. $\phi$ is the last member of some deduction from $\Gamma$, we say $\Gamma$ yields $\Gamma\vdash_{L} \phi$.
Notice that a theorem of L is deducible from empty set of wfs.(a proof in L is a deduction from $\emptyset$), so if $\phi$ is a theorem of Lwe may write $\emptyset \vdash_{L} \phi $,or more normally for brevity, just $\vdash_{L} \phi $
---------------------------------------------------------------------------------------
Proposition 2.8(The Deduction Theorem)
if $\Gamma \cup \{ \phi \} \vdash \chi$ then $\Gamma \vdash_{l} (\phi \rightarrow \chi $, where $\phi$ and $\chi$ are wfs. of L, and $\Gamma$ is a set of wfs. of L(possibly empty).
Proof. The proof is by induction on the number of wfs, in seqence foming the deduction...
Note that each axiom scheme has infinitely many 'instances', as $\phi,\chi,\zeta$rane over all wfs of L.
4. Rules of deduction. In L there is only one rule of deduction. namely modus ponens(abbreviated by MP). It says: From $\phi$ and $(\phi \rightarrow \chi)$, $\chi$ is a direct consequence, where $\phi$ and $\chi$ are wfs. of L.
-----------------------------------------------------------------------------
Definition 2.2
A proof in L is a sequence of wfs. $\phi_{1}, ..., \phi_{n}$ such for each i $(1\leq i\leq n)$, either $\phi_{i}$ is anaxiom of L or $\phi_{i}$ follows from two previus members of the sequence, say $\phi_{j}$ and $\phi_{k}$ $(j<i,k<i)$ as a direct consequence using the rule of deduction MP. Such a proof will be referred to as a proof of $\phi_{n}$ in L. and $\phi_{n}$ is said to be a theorem of L.
Remark 2.3
(a) in the above deifintion, observe that $\phi_{i}$ and $\phi_{k}$ must necessarily be of the form $\chi$ and $\chi \rightarrow \phi_{i}$, or vice versa.
(b) If $\phi_{1}, ..., \phi_{n}$ is a proof in L and $k<n$ then $\phi_{1}, ..., \phi_{k}$ is also a proof in L(its clearly satisfies the definition), and so $\phi_{k}$ is a theorem of L.
(c) Axioms of L are certainly theorem of L. Their proofs in L are one-member sequences.
----------------------------------------------------------------------------------
Definiton 2.5
Let $\Gamma $ be a set of wfs. of L (which may or may not be axioms or theorems of L). A sequence $\phi_{1},...,\phi_{n}$ of wfs. of L is a deduction from $\Gamma$ if for each i $(1\leq i \leq n)$
, one of the following holds:
(a) $\phi_{i}$ is an axiom of L,
(b) $\phi_{i}$ is a member of $\Gamma$, or
(c) $\phi_{i}$ follows from two previous members of the sequence as direct consequence using MP.
So a deduction from $\Gamma$ is just a 'proof' in which the members of $\Gamma$ are considered as temporary axioms.
the last Member $\phi_{n}$, of a sequence which is a deduction from $\Gamma$ is said to be deducible from $\Gamma$, or to be a consequence of $\Gamma$ in L.
if a wf. $\phi$ is the last member of some deduction from $\Gamma$, we say $\Gamma$ yields $\Gamma\vdash_{L} \phi$.
Notice that a theorem of L is deducible from empty set of wfs.(a proof in L is a deduction from $\emptyset$), so if $\phi$ is a theorem of Lwe may write $\emptyset \vdash_{L} \phi $,or more normally for brevity, just $\vdash_{L} \phi $
---------------------------------------------------------------------------------------
Proposition 2.8(The Deduction Theorem)
if $\Gamma \cup \{ \phi \} \vdash \chi$ then $\Gamma \vdash_{l} (\phi \rightarrow \chi $, where $\phi$ and $\chi$ are wfs. of L, and $\Gamma$ is a set of wfs. of L(possibly empty).
Proof. The proof is by induction on the number of wfs, in seqence foming the deduction...
No comments:
Post a Comment