Describing the set $\{n\in \Bbb N\lvert (n>1)\wedge (\forall x,y\in \Bbb N)[(xy=n)\implies (x=1\lor y=1)]\}$

Question

This set appears in an exercise of the course Introduction to Mathematical Thinking, by Dr.Keith Devlin

$A$=$\{n\in \Bbb N\lvert (n>1)\wedge (\forall x,y\in \Bbb N)[(xy=n)\implies (x=1\lor y=1)]\}$

Although this is the very first question of the exercise on a refresher to Set Theory, I cannot process the logical syntax as it is. I'll break down my approach to understanding this set:

1. The domain of discourse is the set of natural numbers(the convention followed in the course is to exclude $0$ from $\Bbb N$). The set $A$, first and foremost, requires $n$ to be greater than $1$.
2. Next, $A$ requires $n$ to satisfy the implication $(xy=n)\implies (x=1\lor y=1)$ for every $x, y$ chosen from $\Bbb N$(this is precisely where I feel I might be wrong).
3. Clearly, in the event of both $x,y$ being greater than 1 the entire implication will be falsified. Thus, there does not exist any $n\in \Bbb N$ satisfying the conditions required by $A$, which means $A$ is an empty set.

I'd like to know which part of my reasoning is incorrect(if any at all). I believe such case-by-case splitting may not be necessary for trivial examples like this one (at least for math students and professionals), but I'm a layman and would hence appreciate such an approach.

Answer 1

Let's break it down step by step.

1. You're first point is right, for $n \in A$, $n$ must be an natural number greater than $1$.

2. $n$ must also satify $(xy=n)\implies(x=1\vee y=1)$ for all natural numbers $x$ and $y$, which can be $1$.

3. Now let's look at the general cases for the form of $A\implies B$

If $A$ is false, then $(A\implies B)$ is true. If $A$ is true, then $(A\implies B)$ is true if an only if $B$ is also true.

So now we know that if

$(xy=n)$ is false for all natural numbers of $x,y$, then $n\in A$. However, it's very easy to see that it's not always false, because if $x=1$ and $y=n$ (which is a perfectly valid possibility!), then $(xy=n)$ is clearly true.

What that means is that for the cases where $(xy=n)$ is true, we must also have that $(x=1\vee y=1)$ to be true. That is the part that restricts $n$ to be a prime number.

I.e; if $n$ is a multiple of two natural numbers $x,y$, it's only prime when for all $x,y$, either $x$ or $y$ is $1$.

Answer 2

Your third point is false. An implication is not necessarily falsified when the conclusion is false.

For instance, (False) $\implies$ (False) is always true.

It might be appropriate to recall the definition : $A \implies B$ holds if, whenever $A$ holds, $B$ holds as well. If $A$ is false, then the implication $A \implies B$ is true, by definition.