Back to the on-screen lesson ·
What a structure is — a domain, what the names denote, what the predicates hold of — and how that fixes the value of every sentence of the language.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write out the extension of a one-place or two-place predicate, decide which sentences are true in a given structure, count the objects satisfying a negation, say what each part of an interpretation settles, choose a structure that falsifies a universal conditional, order the stages of evaluating a sentence, and count the interpretations a predicate can be given over a finite domain.
You have been reading sentences off small structures already. This lesson says exactly what a structure is, so that true in a structure becomes a definition rather than a way of speaking.
An interpretation, or structure, fixes a non-empty domain, an object for each name, and an extension for each predicate — the objects, or ordered pairs of objects, it holds of. A sentence is true in a structure when the definition of truth makes it so; a structure in which a set of sentences is all true is a model of that set.
A structure is three things: a non-empty domain of objects; for each name, one object of the domain; and for each predicate, its extension — a set of objects for a one-place predicate, a set of ordered pairs for a two-place one. Nothing else is said. There is no meaning behind an extension, only the list. Truth is then defined outwards. An atomic sentence $Fa$ is true when the object denoted by $a$ is in the extension of $F$; the connectives work by their truth tables; $\forall x\, \phi$ is true when every object of the domain satisfies $\phi$ and $\exists x\, \phi$ when at least one does. The domain is required to be non-empty, which is why $\forall x\, \phi$ entails $\exists x\, \phi$. What the structure does not interpret is as important as what it does: the connectives and quantifiers mean the same in every structure, and that is what makes validity a matter of form rather than of subject matter.
Another way: steps
Another way: example
Domain $\{a, b, c\}$; $F$ holding of $a, b$; $G$ holding of $b, c$. The sentence saying that some object is both $F$ and $G$ is true, witnessed by $b$; $\forall x\,(Fx \to Gx)$ is false, refuted by $a$.
The first error is expecting an extension to mean something — treating $F$ as is red and then arguing about a borderline case. The extension is the list, and a structure is free to put any objects in it. The second is forgetting that ordered pairs are ordered, which quietly makes every relation symmetric. The third is reading a universal conditional as falsified by an object outside its antecedent's extension; such an object satisfies the instance and cannot refute anything.
Domain $\{a, b\}$; $R$ holding of $\langle a, b \rangle$ only.
The list is the interpretation.
$Rab$ is true and $Rba$ is false: the pairs are ordered, and only one of them is in the list.
Order is part of the pair.
$\forall x \exists y\, Rxy$ is false, because $b$ is related to nothing.
Quantifiers run over the domain.
Domain $\{a, b, c\}$; $F$ holding of $a, b$; $G$ holding of $b, c$.
Fix everything first.
$\forall x\,(Fx \vee Gx)$: $a$ passes on $F$, $c$ passes on $G$, $b$ on both. True.
Every object has to pass.
$\forall x\,(Fx \to Gx)$: $a$ is an $F$ and not a $G$. False. Same lists, different connective, different answer.
One object refutes a universal.
Take any object as the witness; the relation holds of it and every second object, since it holds of every pair.
So the sentence is true, and any object at all could have been named as the witness.
The domain is $\{a, b\}$, and $R$ holds of the single pair $\langle a, b \rangle$. Fill in the table: the row is the first object of the pair and the column is the second.
| Second object $a$ | Second object $b$ | |
|---|---|---|
| First object $a$ | ||
| First object $b$ |
The domain is $\{a, b, c\}$. $F$ holds of $a$ and $b$; $G$ holds of $b$ and $c$. Mark every sentence that is true in this structure.
This task has no paper form; do it on a device.
A structure has a domain of $6$ objects, and $F$ holds of exactly $1$ of them. Complete the sentence about $\neg Fx$.
It is satisfied by exactly m objects of the domain.
Match each part of an interpretation to what it settles.
| Which objects there are, and it is never allowed to be empty | Which single object of the domain it picks out | Which objects of the domain it holds of | Which ordered pairs of objects of the domain it holds of | |
|---|---|---|---|---|
| The domain | ||||
| A name | ||||
| A one-place predicate | ||||
| A two-place predicate |
In which of these structures is $\forall x\,(Fx \to Gx)$ false?
A domain has $3$ objects. How many different interpretations can be given to a single one-place predicate over it?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put these four stages of evaluating a sentence in a structure into the order they have to be done in.
Number the steps in order (write the number in the box):
You can state what a structure consists of and evaluate a first-order sentence in one. Say in your own words why the connectives and quantifiers are not part of what an interpretation fixes.
8. Your turn: is $\exists x \forall y\, Rxy$ true when $R$ holds of every pair?, step 2