Possible interpretations for a predicate symbol in first order logic

163 Views Asked by At

PART A

So, given as structure A :{1,2,3} and we are studying the languge of the real numbers. We are asked to say how many possible interpretations for the predicate symbol $<$. My question is since we are working on real numbers, do we take for granded that symbol $<$ has arity 2? Or we combine all possible interpretations for $ A $? Meaning possible interpretations for < are: (those for arity 1)X(those for arity 2)X(those for arity 3) or simply all the arity 2 combinations for {1,2,3}?

PART B

Give the **smallest* interpretation for symbol <. Depending on what we answer above, if arity 2 is granded then i have no clue what smallest interpretation means. If we multiply the possible interpretation for arity 1,2,3 in part A then i suppose that smallest interpretation is the one with arity 1 containing ∅ (empty set)???

2

There are 2 best solutions below

6
On BEST ANSWER

Part A

You should assume that $<$ is a binary relation (arity 2). Otherwise, the question would have been stated in terms of an arbitrary relation symbol such as $R$.

A binary relation on $A$ is a subset of $A\times A$, so the number of possible interpretations of $<$ in $A$ is the number of binary relations on A, which is the number of subsets of $A\times A$. The size of that collection is: $$ \lvert \mathcal{P}(A\times A)\rvert = 2^{|A\times A|} = 2^{3x3} = 2^9 = 512. $$

Re your idea that perhaps you should "combine all possible interpretations for [$<$ in] A": The cardinality of the structure's universe has no bearing on the arity of its relations. Why stop at 3? Relations on $A$ can also be 4-ary, 5-ary, ... 17-ary, ... . If you were to "combine all possible interpretations", then there are $\aleph_0$ many.

Part B (Hint)

Again, $<$ is binary. "Smallest" means in terms of set inclusion, or — what amounts to the same thing in this case — in terms of cardinality. So: what's the smallest possible interpretation?

4
On

The arity of a relational symbol is defined by the language. So if we're talking about the usual language of real numbers, < is 2-arity, so any interpretation must also be 2-arity.

For "smallest interpretation", I would guess that means the interpretation of < with the lowest cardinality, in which case I think you almost have the answer already.