| ordered pair | The notation <a,b> denotes the ORDERED PAIR con-sisting of two objects named by a and b (a and b may be the same). So long as the two objects are different objects, the ordered pair denoted by <a,b> is different from the pair denoted by <a,b>. |
| Comment. The idea behind ordered pairs is easily extended to cover orderings of more than two objects. | |
| ordered n-tuple | An ORDERED n-TUPLE, <a0,a1, ..., an>, con-sists of the n objects named by a0 ,a1, ..., an. |
| Comment. As with ordered pairs, changing the ordering of a
|
|
| n-place extensions | Definition. The EXTENSION OF AN n-PLACE PREDICATE is a set of ordered n-tuples of objects from the universe. |
| Example. Given a universe containing the objects a, b, and c, and a two-place predicate R, the set { <a,b>, <c,b>, <a,a>} gives a possible extension for R. In this example, the sentences Rab, Rcb, and Raa are true, while the sentences Rac, Rbc, Rba, Rca, Rbb, and Rcc are all false. |
|
| finite interpretation | Definition. A finite interpretation for a set of
sentences containing one-place and many-place
predicates consists of the following:
· A finite universe, or domain.
· Extensions for all the predicates appearing in
the sentences.
· Truth value specifications for the sentence
letters appearing in the sentences.
Example.
Given a universe
U: {a, b},
the expansion of the wff
@x$yFxy
is constructed by first expanding the universal
quantifier (since it has wider scope) to yield
$yFay & $yFby.
Each existential is then ex-panded to yield
(Faa v Fab) & (Fba v Fbb).
|
| Comment. The definition of an interpretation for a set of sentences containing one-place predicates, given in section 4.1, is just a special case of the definition for many-place predicates. | |
| countermodels | Comment. As before, a countermodel for a given sequent is a model for the premises where the conclusion is false. |
Example.
The sequent
@x$yRxy |- $y@xRxy
is invalid, as shown by the following interpretation:
U: {a, b}
R: {<a, b>, <b, a>}.
Expansions:
Premise (Raa v Rab) & (Rba v Rbb)
F v T T v F
T & T
T
Conclusion (Raa & Rab) v (Rba & Rbb)
F & T T & F
F v F
F
|
|
| Exercise 4.4 | Construct countermodels for the following invalid sequents. |
| i* | $xFxx |- @xyFyx |
| ii* | @y$xFxy |- $xFxx |
| iii* | @x$yFxy |- $x@yFxy |
| iv* | @x$y~Fxy, @x@y(Gxy -> ~Fxy) |- @x$y~Gxy |
| v* | @x(Fx -> $yGxy) |- @x@y(Fx v ~Gxy) |
| vi* | @x$y@zVxyz |- $y@x@zVxyz |
| vii* | @x~@yTxy |- @x~$yTxy |
| viii* | $xyz((Fxy & Fyz) & ~(Fxz v Fyx)) |- @x$yFyx -> @x~Fxx |
| ix* | @x$yFxy, $x~@yGyx, $xyFxy <-> $xy(Gyx & ~Gxy) |- @x$y(Gxy v Gyx) |
| x* | $x$yFxy <-> ~$xGxx, @y$xGyx |- @x~Fxx |