FO validity, FO consequence, FO equivalence
Another look at the central topics of the course. The general notions we want to capture are logical truth, logical consequence, and logical equivalence. Propositional logic gives us attempts to capture at least part of these general notions: tautology, tautological consequence, and tautological equivalence. These notions have the advantages of precision and mechanical testability, but they don't give us everything we want (there are logical truths that are not tautologies, logical consequences of a set of premises that are not tautological consequences of those premises, etc.).
Now that we have added quantifiers, we can get closer to the general notions. We now add the concepts of first-order validity (FO validity for short), FO consequence, and FO equivalence.
(Note: in Fitch, Taut Con tests for tautological consequence and
FO Con tests for first-order consequence.)
Truth-functional form of quantifier sentences
The notion of a tautology is still applicable to first-order
logic, but is a little trickier to apply. We can no longer simply pull out the
atomic sentences in a compound sentence and use those to form the reference
columns of a truth table. But we can do something very similar. We first
determine the truth-functional form of the quantifier sentence(s) we want to
check, and then do a truth table for the truth-functional forms of the sentences
rather than the sentences themselves. See the text for details.
(including DeMorgan's, left over from last time) Why the DeMorgan's
equivalences for quantifiers are called "DeMorgan's equivalences for
quantifiers": the analogy between universal quantification and conjunction,
and between existential quantification and disjunction. Other equivalences.
Caution: some things that look similar to genuine equivalences aren't
Can be thought of as helping to take up the slack between first-order
consequence and the intuitive notion of logical consequence. Axioms specify
relations between predicates that depend on their meaning. (For instance, it
isn't part of logic proper to express the fact that for any objects x and y, x
is larger than y if and only if y is smaller than x. But we can formulate an
axiom that states this.) Occasionally axioms may express background assumptions
about a particular domain rather than purely logical relationships: for
instance, if we are discussing Tarski's World, we may want an axiom stating that
for all objects x, either x is a cube or x is a dodecahedron or x is a
tetrahedron. This clearly is not a purely logical truth -- there are many
counterexamples in the actual world! But it is true in Tarski's World, so as
long as we know we are dealing with Tarski's world, it can be useful to have it
as an axiom.
Sentences with multiple quantifiers
(Introduction only.) The amazing riches made possible by quantifiers.
Remarkable number (six, to be precise) of distinct propositions we can express
using only a single two-place predicate and two quantifiers.
To say, for example, that one object is larger than every other object, we need to explicitly express the "other" part by using the negation of an identity statement. Example: suppose we want to say that there is a cube that is larger than every other cube. The following sentence will not work: ∃x (Cube(x) ∧∀y (Cube(y) → Larger(x,y)). In fact, this sentence will never be true! The only way it could be true is if there were a cube that is larger than everything, including itself. Since nothing can be larger than itself, this sentence cannot be true under any circumstances. Instead, we need to translate "other" by using x ≠ y, like this:
∃x (Cube(x) ∧∀y((Cube(y) ∧ x ≠ y) → Larger(x,y))