Predicate logic & quantifiers question to write in symbolic form

Question

I'm practising for my math finals...

Question: Using D(x, y) to mean "x uses y". Write the following sentence in symbolic form. Make sure to specify the domain of all variables used.

---

Let c = {carpenters}, h = hammer, s = spatula.

a) Every carpenter uses a hammer

b) Some hammer is not used by any carpenter

c) No carpenter uses a spatula

d) Every carpenter that uses a spatula also uses a hammer

For a)

I wrote $D(∀c, h)$

... I'm not sure if thats the format they want it in? So I also wrote

$∀x ∈ C, y ∈ h$

or

$∀x ∈ C, h(y)$

For b)

I tried $D(-∃h, ∀c)$

For c)

I tried $D(∀c, s)$

For d)

I tried $D(-∀c, s -> h)$

---

Am I on the right path here? For a) can someone tell me which one of them is the correct format?

Answer 1

You really should familiarize yourself with the syntax of predicate logic formulas again. This is not about some "format they want", this is how predicate logic works. All of your attempts are syntactically incorrect, i.e. simply not formulas of predicate logic at all. Look at some examples in your textbook how to formalize simple sentences like "Some carpenters are working" or "All hammers are heavy", and try to understand the general pattern behind these formalizations, take a close look at how the formulas in your textbook are built up and compare them with yours.

---

First some notational issues:

Using D(x, y) to mean "x, y"

I assume you mean "$D(x,y)$ to mean "x uses y"?

c = {carpenters}, h = hammer, s = spatula.

$c = \{carpenters\}$ is a set which contains one object, and this object is called "carpenters". This doesn't make sense.
$h = hammer$ and $s = spatula$ presupposes that the sets named $hammer$ and named $spatula$ are defined.
Instead, write $c = \{x : x\text{ is a hammer}\}$ to express "$c$ is the set of all objects that are hammers". Likewise for the other two sets. A less formal possibility of expressing this is "$c = $ the set of hammers".
For sets, I would recommend you to use uppercase letters (this is just a convention that eases readability), so your specificaiton becomes

$C$ = the set of carpenters, $H$ = the set of hammers, $S$ = the set of spatulas

---

Now to your attempts:

$D(\forall c, h)$

This is not a well-formed formula. You can not have a quantifier inside the argument of a predicate. By the definition of "formula", $D(t_1,t_2)$ is a formula if $t_1$ and $t_2$ are terms. By the definition of "term", $t$ is a term if it is a variable (like $x$) or a constant name (like $a$) or an $n$-ary function applied to $n$ terms, $f(t_1, ..., t_n)$. A term is something that stands for an object, while a formula is something that can be true or false. $\forall c$ is not a term - it does not have one of the above mentioned forms, so it does not denote an object and can therefore not serve as an argument to a predicate.

$∀x ∈ C, y ∈ h$

That looks better, but it's still not a formula, because the formula you quantify over is missing. By the definition of "formula", $\forall x \phi$ is a formula if $\phi$ is a formula. But your $\phi$ is missing, you only have the quantification part.

$∀x ∈ C, h(y)$

That one is a not a well-formed formula either, assuming that (as you defined above) $h$ is a set and not a predicate. You seem to be thinking that using uppercase letters automatically gives you a set as in $x \in C$, and using lowercase letters automatically gives you a predicate as in $c(x)$. That's not how it works. If you want to make use of predicates, then you need to define them. So far, you only defined the sets $C, H, S$, not predicates $c(h), h(x), s(x)$. You can work with predicates instead of sets, but you shouldn't mix the two.

You have all the same issues in your other attempts: In

$D(-∃h, ∀c)$, $D(∀c, s)$, $D(-∀c, s -> h)$

you have quantifiers inside predicates, this is not possible.

In $D(-∀c, s -> h)$, you seem to be trying to put an implicational formula ($s \to h$) inside a predicate. This is not possible either: First, you can not put a formlua inside a predicate; second, $s \to h$ is not a formula, because $\to$ is a connective between formulas, but $s$ and $h$ are not formulas, but sets or variables - it's not clear exactly what you even mean by those symbols. Again, for a predicate $D(t_1, t_2)$, $t_1$ and $t_2$ need to be terms. $\neg \forall c$ and $s \to h$ are not terms, because they are neither variables nor constants nor funciton applications, and thus do not stand for an object, and hence can not serve as arguments to a predicate.

---

Let me do one example for you and you try to apply this explanation to the rest:

d) Every carpenter that uses a spatula also uses a hammer

Formally, this pararahses as

"For every carpenter it holds that if there is a spatula that they use, then there is a hammer they use."

or, even more formally,

"For every member (call it $c$) of the set of carpenters ($C$) it holds that if there is a member (call tnat member $s$) of the set of spatulas ($S$) such that $c$ uses $s$, then there also exists a member (call that member $h$) of the set of hammers ($H$) such that $c$ uses $h$.

Let's work our way from the outside to the inside and first observe that we have a statement of the form "For all carpenters it holds that [something]", where "[something]" is an implication ("if they use a spautla, then they use a hammer"), so our formula has the form

$\forall c \in C(\phi \to \psi)$

where $\phi$ stands for "c uses a spatula" and $\psi$ stands for "c uses a hammer".

So let's formalize "c uses a spatula": As said above, this parphrases as "There is a member $s$ of the set of spatulas $S$ such that $c$ uses $s$, so we have

"c uses a spatula" = $\phi = \exists s \in S(\chi)$

where $\chi$ stands for "c uses s".

This is given by a simple predication over the terms $c$ and $s$:

"c uses s" = $\chi = D(c,s)$

We use $c$ as a variable for the carpenter because this is the variable we chose in the quantificaton $\forall c \in C$.

Assembling these formulas, we get

"c uses a spatula" = $\phi$ = $\exists s \in S (D(c,s))$

This is the left-hand side to your implication.

Notice the syntax: In $D(c,s)$, $c$ and $s$ are terms, because they are variables. So $D(c,s)$ is a well-formed formula. The quantification $\exists h$ is outside the predicate. It is made clear that the variable $s$ (which stands for the spatula) is the one which is existentially quantified over because the same variable is used in the quantifier binding ($\exists s$) and the predicaion ($D(c,s)$). This is what a syntactically well-formed quantified formula looks like: A quantification $\exists s \in S$ followed by a formula, and the formula here is the predication $D(c,s)$.

The same techique applies to the right-hand side of the implication, "c uses a hammer":

"c uses a hammer" = $\psi = \exists h \in H(D(c,h))$

Again, the quantification $\exists h \in H$ is outside the predication $D(c,h)$, and the $h$ in $D(c,h)$ is bound by $\exists h \in H$, while the $c$ in $D(c,h)$ is bound by the outermost $\forall c \in C$.

And now we just need to plug these pieces together, end end up with

$\forall c \in H(\exists s \in S(D(c,s)) \to \exists h \in H(D(c,h)))$

which translates as

"For all carpenters it holds that if there is a spatula they use, then there is a hammer they use", which correctly caputres sentence (d).

I'll leave the other formulas for you to try again along the lines of this explanation. Feel free to post your revised attempts for feedback after thoroughly reading and thinking through how to do it.

---

Update

Re. your revised versions:

Much better, now all of your formulas are syntactically well-formed.

a) Every carpenter uses a hammer $= ∀c∈C(∃h∈H(D(c,h)))$

b) Some hammer is not used by any carpenter $= ∃h∈H(∀c∈C(¬D(c,h)))$

Correct! I think you got the iea now.

¬c) No carpenter uses a spatula
$= ¬∀c∈C(∀s∈S(D(c,s)))$

Unfortunately, while this formula is a valid first-order logic formula, it doesn't capture the meaning correctly. This formula says "Not all carpenters use all spatulas". This is equivalent to "Some carpenters only use some but not all of the spatulas". Instead, you want to say "There exist no carpenter such that there exists any (= a) spatula they use. This translates as

$$\neg \exists c \in C(\exists s \in S(D(c,s)))$$

Equivalently, you could say "For all carpenters, there is no spatula they use":

$$\forall c \in C (\neg \exists s \in S(D(c,s)))$$

In general, "no" translates as $\neg \exists x \phi$ (= there is no), or equivalently $\forall x \neg \phi$ (= for all not).

Also, in d) did you make a mistake with the start where you are capturing the 'every carpenter' part? = ∀c∈H, isn't it supposed to be ∀c∈C? at the LHS.

Yes, this was a typo. Thanks for pointing it out.