Below are some proofs in predicate logic and some
examples of how to show a statement is invalid with a model.
(x)~Kx, (x)(~Kx→~Sx)
├ (x)(Hx v ~Sx)
1 (1) (x) ~Kx A
2 (2) (x)(~K → ~Sx) A
1 (3) ~Ka 1, UE
2 (4) ~Ka →
~Sa 2,
UE
1, 2 (5) ~Sa 3,
4 MPP
1, 2 (6) Ha v ~Sa 5, v-I
1, 2 (7) (x)(Hx v ~Sx) 6,
UI
(x)(Gx
→ ~Fx), (x)(~Fx → ~Hx) ├ (x)(Gx
→ ~Hx)
1 (1) (x)(Gx → ~Fx) A
2 (2) (x)(~Fx → ~Hx) A
1 (3) Ga
→ ~ Fa 1, UE
2 (4) ~Fa
→ ~Ha 2, UE
5 (5) Ga A
1,
5 (6) ~Fa 3,
5 MPP
1,
2, 5 (7) ~Ha 4,
6 MPP
1,
2 (8) Ga → ~Ha 5,
7 CP
1,
2 (9) (x)(Gx → ~Hx) 8, UI
($x)~(Cx
v ~ Rx) ├ ($x)~Cx
1 (1) ($x)~(Cx
v ~ Rx) A
2 (2) ~(Ca v ~Ra) A
2 (3) ~Ca & Ra 2, DeMorgan’s law
2 (4) ~Ca 3,
&-E
2 (5) $x(~Cx) 4, $-I
1 (6) $x(~Cx) 1, 2, 5,
$-E
$xFx→"xGx ├ (x)(Fx→Gx)
1 (1) $xFx→"xGx A
2 (2) Fa A
2 (3) $xFx 2,
EI
1,2 (4) "xGx 1, 3 MPP
1,2 (5) Ga 4,
UE
1 (6) Fa→Ga 2, 5 CP
1 (7) "x(Fx→Gx) 6, UI
(P→ ~"xFx)├
~"x(P & Fx)
1 (1) P→~"xFx A
2 (2) "x(P
& Fx) A
2 (3) P & Fa 2, UE
2 (4) P 3,
&-E
1,2 (5) ~"xFx 1, 4 MPP
2 (6) Fa 3,
&-E
2 (7) "xFx 6, UI
1,2 (8) "xFx
& ~"xFx 5, 7
1 (9) ~"x(P
& Fx) 2, 8 RAA
$x(P v
Fx) ├ ~P→$xFx
1 (1) $x(P v
Fx) A
2 (2) P v Fa A
3 (3) P A
3 (4) ~~P 3,
DN
3 (5) ~P→$xFx Negated antecedent (51)
6 (6) Fa A
6 (7) $xFx 6, E-I
6 (8) ~P→$xFx Affirmed consequence (50)
2 (9) ~P→$xFx 2, 3, 5, 6, 8 v-elim
1 (10) ~P→$xFx 1,2,9 $-elim
~P→$xFx ├
$x(P v Fx)
1 (1) ~P→$xFx A
2 (2) ~$x(P v
Fx) A
2 (3) "x~(P
v Fx) 2, QE
2 (4) ~(P v Fa) 3, UE
2 (5) ~P & ~Fa 4, De Morgan
2 (6) ~P 5,
&-E
1, 2 (7) $xFx 1, 6 MPP
2 (8) ~Fa 5,
&-E
2 (9) "x~Fx 8, UI
2 (10) ~$xFx 9, QE
1, 2 (11) $xFx & ~$xFx 7, 10 &-I
1 (12) $x(P v
Fx) 2, 11 RAA
Note: To show a sequent is invalid, one needs to
find an interpretation where the interpretation makes the premises true but the
conclusion false.
$x)Fx ├ Fm
Let: U = N
Fx = x is odd
m = 4
Under
this interpretation, ($x)Fx is true (for example 3 satisfies it), but Fm is false,
since 4 is not odd. Therefore, this interpretation shows that the sequent is
invalid.
(x)(Fx→Gx), (x)(Hx→Gx)
├ ($x)(Hx & Fx)
Let: U = N
Fx = x < 5
Hx = 5 < x < 10
Gx = x < 10
Under this interpretation,
clearly, (x)(Fx → Gx) and (x)(Hx → Gx) are true, since, for all x,
if x is less than 5, its obviously less than 10 and for all x greater than 5
and less than 10, it is true that x is also less than 10. But, there is no x, such that x is both
5<x<10 and x<5, hence ($x)(Hx
& Fx) is false under this interpretation.
So, we have found an interpretation that makes (x)(Fx
→ Gx) and (x)(Hx → Gx) true, but ($x)(Hx & Gx) false, in other
words we have shown that the sequent is invalid.
(x)($y)~Lxy ├ (x)~Lxx
Let: U = N
Lxy = x is equal to y
With
this interpretation, it is obvious that (x)($y)~Lxy
is true, since, for any x, there is a y (say let y =x+1) such that x is not
equal to y. But, (x)~Lxx is false, since
(x)~Lxx is equalivent to ~($x)Lxx
and we know that there is a natural number (all of them in fact) such that x=x,
other words we know that ($x)Lxx
is true, so (x)~Lxx must be false. Thus, with this interpretation the sequent
is shown to be invalid.