Given the following structure, how do I translate the these statements into formulas in predicate logic?

53 Views Asked by At

The following is a problem from our book in predicate logic.

"Work over the arity type: 'one binary relation, one constant symbol, one binary operation' and then consider the structure $$ Q := \ <\mathbb{Q};\leq;1,+> $$ (a) Give a formula that represents the statement: "$x_0$ is equal to 1/2" in $Q$.

(b) Give a formula that represents the statement: "$x_0 \leq 0$" in $Q$.

(c) Give a formula that represents the statement: "there does not exist any $x_1$ that is strictly greater than $x_0$" in $Q$."

I have an idea as to how to construct the formula in the first question: if one has "$x_0 \leq 1/2$" and "$1/2 \leq x_0$", one can deduce $x_0 = 1/2$. My initial attempt looked something like this: $$ P_1\big(x_0, f_1/(f_2(f_1,f_1))\big) \wedge P_1\big(f_1/(f_2(f_1,f_1)), x_0\big) $$ where $P_1$ represents the relation symbol $\leq$; $f_1$ represents the constant symbol 1 and $f_2$ the binary operation $+$. I doubt this is correct, since I've used the operator "/", which is not part of my structure. As for the rest, I don't really know where to begin.

1

There are 1 best solutions below

2
On BEST ANSWER

As commented, the answer to this problem has to use the formula $2x = 1$ to define the number 1/2. You don't have the function symbol $/$ in your structure. So your attempt cannot succeed, because you are writing your formula:

$$P_1\big(x_0, f_1/(f_2(f_1,f_1))\big) \wedge P_1\big(f_1/(f_2(f_1,f_1)), x_0\big)$$

with a $/$ symbol. You don't have $/$ defined in the structure, not to say in the language. Note also (I am guessing this is your nomenclature) that the language itself has only the symbols:

$$f_1, f_2, P_1, =, \land, \neg, \exists $$

Suppose you had $/$ in your structure and a symbol $f_3$ in the language corresponding to it, and suppose it is well defined everywhere but not in 0 for the denominator, you could just write the formula that says $x_0 = 1/2$:

$$ x_0 = f_3(f_1,f_2(f_1,f_1))$$

Your answer should fit also, with this extra $f_3$ in the place of $/$.

But you don't have this symbol. So you have to do this trick:

$$f_2(x_0 ,x_0) = f_1$$

to represent the statement.

The same goes for the others ones. As for the third one, note that you don't have the symbol $<$ in your structure, but you can create it by this trick:

$$(x_0 \leq x1) \land \neg (x_0 = x_1)$$