Welcome back to logic language and information.
In today's lesson we will compare and contrast finite versus infinite models.
So far in this series of lessons we have mostly looked at finite models.
Such as our four world leaders 2014 model.
A model is called finite whenever its domain is a finite set of objects.
Next, in contrast, some models have infinite domains.
For example, the natural numbers.
Zero, one, two, three and so on.
The symbol blackboard bold N, is standardly used for this infinite set.
Technically it is known as a countably infinite set.
There are even larger infinities that we will look
at briefly in the mathematics implication section of the course.
The definition of truths in a model is the same for all models, finite or infinite.
But in a finite model, we can simplify the
clauses for truth in a model, for quantified formulas.
In a finite model M, a universally quantified
formula is true in the model, if only if the
conjunction of all its instances is true in M.
So if we have 1,022 objects in the domain, we write out the conjunction
of 1,022 instances, using some standard name for the objects.
And we check the truth of that conjunction.
In a finite model M, an existentially quantified formula is true in M.
If and only if the disjunction of all it's instances is true in A.
So again, if we have 942 objects in the domain, then this time we write out
the disjunction, the or of 942 instances.
Again using some standard names for the objects, and
we need to check the truth of that disjunction.
For example, in our running example of models the domain containing
Obama, G, Merkel and Abay with the standard names o, i, m and e.
The universal formula for x Rax is true in the model if and only if the
conjunction Rao and Rai
and Ram and Rae is true in M.
This means that when we have a particular finite model in mind,
the quantifiers are useful and allow us to be more concise,
but they do not give us anything we cannot already express.
Using the propositional connectives of conjunction and disjunction.
But this changes when we turn to infinite models.
Our original definition of truth from last lesson
is needed because some models just are infinite.
Consider formalizing arithmetic properties in predicate logic.
The domain is the countably infinite set of natural numbers.
Consider the, less than predicate.
Interpreted 2-place predicate symbol s to mean is strictly smaller than.
We can describe the interpretation i of s, in an infinite table.
The row for zero, shows that zero is strictly less than 1, 2, 3, 4 and so on.
But zero is not strictly less than zero.
The row for 1 shows that 1 is strictly less than 2, 3, 4, and so on.
But one is not strictly less than, either zero or one.
We can use the bold symbols as standard names for the numbers in the
domain, and use these to take instances of qualified formulas.
So let's evaluate the truth of some complex formulas in this infinite model.
First, the formula for all x S0x.
This formula expresses that for all numbers x, zero is strictly less than x.
So this formula is true if and only if, all the instances are true.
So we would need S00, S01, S02, S03, S04, and so on.
These must all be true.
But the first of these s00 is false, because
zero is not strictly less than zero, hence the
formula for all x, s0x, evaluates as false.
Now try at nested quantify formula.
For all x, there exists y, Sxy.
Which expresses that, for every number x, there is a
number y, such that x is strictly smaller than y.
More succinctly for every x there is a y strictly larger than x.
Again, the outermost quantifier is universal.
So the formula is true, if and only if, all its instances are true.
Exist y, s0y must be true.
Exist y, S1y must be true.
Exists y S2y, must be true and so on.
Since S01 is true,
the zero instance,
exists y S0y is true.
Since s12 is true, the
1 instance exists ys1y is true.
Since s23 is true.
The 2 instance exists y S2y is true, and so on.
We can see the general pattern.
Exists y Sny comes out as true, because
the atomic formula, Snn plus 1 is true,
where n plus 1 is the next numeral after n.
So, we can conclude that, the formula for all x exists y Sxy is true.
In this infinite model.
Now it's your turn.
The model has the same domain, the infinite set of natural numbers.
The two place predicate s is still
interpreted as is strictly less than, as before.
And we have an additional two place predicate
R, which is interpreted as, differing by one.
So r a b is true.
Exactly when b is a plus 1, or a is b plus 1.
In particular, R01 and R10 are true.
R12 and R21 are true.
R23 and R32 are true.
And so on.
In the setting, which of the following
four quantified formulas are true in this model?
BLANK_AUDIO How did you go?
For a, the answer is false.
Because, in fact, the opposite is true.
Look down, the diagonal, of the table,
and we see that for all x, not r x x.
>> Formula B asserts that for all x and y if
rxy, then either
Sxy or Syx this is true.
If two number defer, by one then either the first is
smaller than the second, or the second is smaller than the first.
For formula c the answer is true.
The formula asserts that, r is interpreted by a, symmetric relation.
And this is visible from the table for I of R because
there is, there are mirror images across the diagonal of the table.
The final formula d asserts that for all x, there exists y
such that, Sxy and rxy.
This is also true.
For each choice of x as say the number n, we can choose y to
be the, number n plus 1, the next number, so that we have both.
Sn n plus 1 and Rnn plus 1 being true in this model.
You might need some time to think about this one.
As usual, if you have any comments or questions go first to the course
notes and then to the discussion boards, and I'll check in on the discussion there.
This brings us to the end of this lesson on finite versus infinite models.
In the next and last lesson in this series on predicate logic
semantics, we will turn to the semantic classification of formulas and arguments.
So see you then.