Wrong predicate-logic translation?

74 Views Asked by At

A set $S$ of whole numbers is called stapled if and only if for every whole number $a$ which is in $S$ there exists a prime factor of $a$ which divides at least one other number in $S.$

Let $T$ be a set of whole numbers. Which of the following is true if and only if $T$ is not stapled?

Taking the domain as all the whole numbers in the set, $S$ is stapled iff

$\forall a \exists b$(there exists a prime factor in $a$ which divides $b$).

Taking the negation:

$\exists a \forall b$(there does not exist a prime factor in $a$ which divides $b$).

In normal words:

There exists a whole number $a$ where there does not exist a prime factor in $a$ which divides all $b.$

So my answer would be:

There exists an number $a$ which is in $T$ such that there is no prime factor of $a$ which divides every other number in $T.$

However, the correct answer is:

There exists a number a which is in $T$ such that there is no prime factor of $a$ which divides at least one other number in $T.$

What went wrong in my solution?

1

There are 1 best solutions below

0
On BEST ANSWER

GIVEN DEFINITION: A set S of whole numbers is called stapled if and only if for every whole number $a$ which is in $S$ there exists a prime factor of $a$ which divides at least one other number in $S.$

Taking the domain as all the whole numbers in the set, $S$ is stapled iff

$\quad\forall a \exists b$(there exists a prime factor of $a$ which divides $b$).

You neglected to account for the word "other" in the given definition. A correct translation (where $\mathbb P$ denotes the set of prime numbers) is:

$$\forall a\in S \;\;\exists p\in\mathbb P \;\;\exists b\in S \;( p|a \;\text{and}\; p|b \;\text{and}\; a \neq b)\tag#$$

Taking the negation:

$\quad \exists a \forall b$(there does not exist a prime factor in $a$ which divides $b$).

$\quad$There exists a whole number $a$ where there does not exist a prime factor in $a$ which divides all $b.$

Your natural-language translation of your symbolic negation is wrong; it ought to be instead be (note that the placement of every/all $b$ is crucial because the meaning of the sentence varies according to that): "There exists a whole number $a$ such that for each $b,$ there does not exist a prime factor in $a$ which divides $b.$"

GIVEN EXERCISE: Let T be a set of whole numbers. Which of the following is true if and only if T is not stapled?

However, the correct answer is: "There exists a number a which is in T such that there is no prime factor of a which divides at least one other number in T."

This is correct, because it does correspond to the negation of $(\#):$ $$\exists a\in S \;\;\not\exists p\in\mathbb P \;\;\exists b\in S \;( p|a \;\text{and}\; p|b \;\text{and}\; a \neq b).$$ An equivalent negation of $(\#):$ $$\exists a\in T \;\;\forall p\in\mathbb P \;\;\forall b\in T \;( p\not|a \;\text{or}\; p\not|b \;\text{or}\; a = b).$$