| infinite countermodel |
Comment. Sometimes an invalid argument cannot
be shown invalid by means of a finite countermodel.
Such cases require an INFINITE COUNTERMODEL,
i.e., one with an infinite number of objects
in its domain. |
|
Comment. A formal treatment of infinite sets
requires an advanced course in set theory. Nonetheless,
it is possible to exploit knowledge about sets of numbers to
construct counterexamples for invalid arguments that require
infinite models. The wffs of predicate logic can be
given interpretations in terms of arithmetical relationships
in infinite domains such as the natural numbers or the set of
positive and negative integers. |
|
For ease of exposition we will take the natural numbers
(0,1,2,3, etc.) to be the infinite domain to be used.
(This set is denoted N.) Note also that we
cannot use expansions to construct countermodels,
since an expansion for an infinite number of objects
would involve infinitely long sentences. |
| b>numerical countermodel |
Definition. A NUMERICAL COUNTERMODEL
to an argument is a countermodel whose universe is
N. |
|
Example.
@xyz(Rxy & Ryz -> Rxz), @xy(Rxy -> ~Ryx),
@x~Rxx, @x$yRxy |- $y@xRxy.
Model:
U: N.
R: {<m,n> such that m<n}
(also written {<m,n> : m<n}.
That is, Rxy means that x is strictly less than y.
|
|
The four premises are true, since (i) if x is less than
y and y is less than z then x is less than z, (ii) if x is
less than y then y is not less than x, (iii) no number is
less than itself, and (iv) for any number there is a greater.
The conclusion is false, however, since it says that there is
a number greater than any number. That is, no number y
is such that for every number x, <x,y> belongs to R. |
|
It can be shown that only an infinite model can make all
four premises true. A given single object bears R to
something (fourth premise), but it doesn't bear R to itself
(third premise), so a second object must be present. This
second object bears R to something (fourth premise), but it
doesn't bear R to the first object (second premise) and it
doesn't bear R to itself (third premise). Hence, a
third object must be present. This third object doesn't
bear R to itself (third premise), and it doesn't bear R to
the second object (second premise), and since the first
object bears R to this third object as well as the second
(first premise), the third doesn't bear R to the first
(second premise). But this third object bears R to
something (fourth premise), hence a fourth object must
be present, and so forth. Thus, the four premises
require an infinite universe. |
| Exercise 4.5 |
(1) Return to any invalid sequent of this chapter,
and give a numerical countermodel for it. (Of course, up to
this point infinite models were not necessary for
demonstrating invalidity, but they are possible.) |
|
(2) Give numerical countermodels to the following sequents. |
| i* |
@xyz(Fxy & Fyz -> Fxz), @x$yFxy |- $xFxx |
| ii* |
@x$y@z(Fxy & (Fyz -> Fxz)) |- $xFxx |
| iii* |
@x$yFxy, @xyz(Fxy & Fyz -> Fxz), @x~Fxx |
|
|- @xy(Gx & ~Gy -> Fxy v Fyx) |
| iv* |
@x$yz(Fxy & Fzx), @xyz(Fxy & Fyz -> Fxz) |
|
|- $xy(Fxy & Fyx) |
| v* |
@x~Fxx, @x$y@z(Fxy & (Fyz -> Fxz)) |
|
|- @xyz(Fxy & Fyz -> Fxz) |
| Exercise 4.6 |
Establish whether each of the following sequents is valid or
invalid with either a proof or a counter-model. |
| 1 |
@x(Fx -> ~Gx), $x(Gx & ~Fx) |- ~$xFx v @x~Gx |
| 2 |
@x(Fx -> ~Gx), $x(Gx & Fx) |- ~$xFx v @x~Gx |
| 3 |
$x(Fx -> Gx) -> $x(Fx & ~Hx) |
|
|- $x(Fx & Gx) -> ~@x(Gx -> Hx) |
| 4 |
$x(Fx -> Gx) -> $x(Fx & ~Hx) |
|
|- $x(Fx & Gx) -> @x(Gx -> Hx) |
| 5 |
$x(Fx v P), P « ~$xGx, ~$x(Fx & Gx), |
|
@x(Hx -> ~Fx & ~Gx) |- P v @x(Hx -> P) |
| 6 |
@x(Fx & Gx -> Hx), $xFx |- $x(Gx -> Hx) |
| 7 |
@x(Fx & ~Gx -> Hx), $xFx |- $x(Hx -> ~Gx) |
| 8 |
|- @xFx v $x~Gx -> ~$x(Fx v Gx) |
| 9 |
|- @xFx v $xGx -> $x(Fx v Gx) |
| 10 |
$x(Fx v Gx), $xFx -> @xHx, $xGx -> ~$xHx |
|
|- ~($xHx & $x~Hx) |
| 11 |
$x(Fx v Gx), $xFx -> @xHx, $xGx -> ~$xHx |
|
|- ~(@xHx v @x~Hx) |
| 12 |
|- ~$x(Bx & @y(Sxy <-> ~Syy)) |
| 13 |
|- @xy(Fxy -> Fyx) <-> @xy(Fxy <-> Fyx) |
| 14 |
|- @xy(Fxy fi Fxy) <-> @xy(Fxy <-> Fyx) |
| 15 |
@xyz(Rxy & Rxz -> ~Ryz) |- ~@xRxx |
| 16 |
@xyz(Rxy & Ryz -> ~Rxz) |- @x~Rxx |
| 17 |
@xyz(Fxy & Fyz -> Fxz), @xy(Fxy -> Fyx) |
|
|- @x$yFxy -> @xFxx |
| 18 |
@xyz(Fxy & Fyz -> Fxz), @x$y(Fxy -> Fyx) |
|
|- @x$yFxy -> @xFxx |
| 19 |
$x@y~Fxy |- $x@yz(Fxz -> Fzy) |
| 20 |
$x@yFxy |- $x~@yz(Fxz -> Fzy) |