Back to the on-screen lesson ·
The one predicate every structure interprets the same way, and the at-least, at-most and exactly claims it makes expressible.
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 the at-least, at-most and exactly counting claims with quantifiers and identity, say why a structure has no choice about the extension of identity, count the non-identity clauses a claim needs, evaluate counting claims in a small structure, order them by strength, and find the smallest domain a set of sentences can be satisfied in.
You can write out a structure and evaluate a first-order sentence in it. What the language cannot yet do is count: nothing written so far can tell a structure with one $F$ from a structure with two.
$=$ is the identity predicate, written between two terms; $x \ne y$ abbreviates its negation. A symbol is logical when every structure interprets it the same way. At least, at most and exactly $n$ are the three counting claims, and the third is the first two together.
Identity is added as a two-place predicate with one difference from every other: its extension is not up to the structure. In every structure whatever, $=$ holds of an object and itself and of nothing else. That makes it a logical symbol, like the connectives and quantifiers, and it is what lets the language count. At least two $F$s is $\exists x \exists y\,(Fx \wedge Fy \wedge x \ne y)$ — two existentials are not enough on their own, because nothing stops them landing on the same object. At most one $F$ is $\forall x \forall y\,((Fx \wedge Fy) \to x = y)$, which makes no existential claim at all and is true when there are no $F$s. Exactly one is the two together, usually written $\exists x\,(Fx \wedge \forall y\,(Fy \to y = x))$. Larger numbers follow the same pattern, with one non-identity clause per pair. Two names may denote one object, so $a = b$ can be true; and two objects may satisfy all the same predicates and still be two.
Another way: steps
Another way: example
There are exactly two $F$s: two distinct $F$s, and every $F$ is one of the two. Dropping the second conjunct gives at least two, and a structure with three $F$s then satisfies it.
The commonest error is reading two existential quantifiers as two objects: $\exists x \exists y\,(Fx \wedge Fy)$ is satisfied by a single $F$, with both variables landing on it, and only the non-identity clause forbids that. The second is reading at most one as claiming there is one; it is true in a structure with no $F$s at all. The third is treating identity as an ordinary predicate a structure interprets, when its extension is fixed in advance and never varies.
$\exists x \exists y\,(Fx \wedge Fy)$ in a domain where only $a$ is an $F$.
Try to satisfy it with one object.
Let both variables take the value $a$. Both conjuncts hold, so the sentence is true.
Nothing forbade the repetition.
Adding $x \ne y$ rules that out, and the sentence then genuinely demands two objects.
Identity does the counting.
$\forall x \forall y\,((Fx \wedge Fy) \to x = y)$ in a structure where nothing is $F$.
Read it as a universal conditional.
Every instance has a false antecedent, so every instance is true.
Vacuously satisfied.
So at most one is true with no $F$s, which is why exactly one has to add an existential claim.
Two claims, not one.
No predicate is needed, only two existentials and the clause keeping them apart.
$\exists x \exists y\, x \ne y$, which is false in a one-object domain and true in every larger one.
Match each English claim to the formula that says it.
| $\exists x\, Fx$ | $\exists x \exists y\,(Fx \wedge Fy \wedge x \ne y)$ | $\forall x \forall y\,((Fx \wedge Fy) \to x = y)$ | $\exists x\,(Fx \wedge \forall y\,(Fy \to y = x))$ | |
|---|---|---|---|---|
| There is at least one $F$ | ||||
| There are at least two $F$s | ||||
| There is at most one $F$ | ||||
| There is exactly one $F$ |
A structure fixes an extension for each predicate. What does it fix as the extension of $=$?
To say that there are at least $4$ objects satisfying $F$, you write $4$ existential quantifiers, say that each of the objects is an $F$, and then say that they are pairwise distinct. Complete the sentence.
That takes m non-identity clauses.
The domain is $\{a, b\}$, two distinct objects, and $F$ holds of $a$ alone. Mark every sentence that is true in this structure.
This task has no paper form; do it on a device.
The domain is $\{a, b, c\}$, three distinct objects. Fill in the table of identity: the row is the first object and the column is the second.
| Second object $a$ | Second object $b$ | Second object $c$ | |
|---|---|---|---|
| First object $a$ | |||
| First object $b$ | |||
| First object $c$ |
A structure is to make all three of these true at once: there are exactly $2$ objects satisfying $F$; there are exactly $3$ objects satisfying $G$; and no object satisfies both. What is the smallest number of objects its domain can have?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put these four sentences in order, strongest first, so that each entails the next.
Number the steps in order (write the number in the box):
You can express counting claims with identity and evaluate them in a structure. Say in your own words why two existential quantifiers do not by themselves demand two objects.
8. Your turn: write *there are at least two objects*, step 2