1
$\begingroup$

I have a question about the first part of the proof for the statement "If $x$ and $y$ are odd integers, then $xy$ is odd" if we are using a direct proof.

Now i've gotten the proof roughly correct but I have an issue with what we write at the beginning of the proof. If we were to put the statement into first order logic, wouldn't we start off with two universal quantifiers $\forall x \forall y \alpha$ where $\alpha$ is the rest of the formula?

If this is the case, shouldn't we use universal instantiation at the beginning of the proof? Is it okay to start off with "For any arbitrary $x$ and $y$ integers, suppose $x$ and $y$ are odd integers." Or is that incorrect since, in essence, we have assumed something about the integers, namely that they are odd, and thus they cannot be arbitrary?

All the answers to the basic proof which i've found on the net that use a direct proof approach, all just say "suppose $x$ and $y$ are odd integers", so I'm just wondering if adding the line about $x$ and $y$ being arbitrary is fine.

$\endgroup$
2
$\begingroup$

It's fine.   The predicate is a material implication.   This is evaluated as true if either its antecedant is false or the consequent is true.

So for any two arbitary integers, we claim either they are not both odd or their product is odd.

Thus, in the case where at least one of our arbitrary integers is not odd, then our claim is clearly true.   So we only need to ensure the product is odd in the case of where both arbitrary integers are odd.

Hence in general practice we begin such proofs as "Let $x,y$ be any odd integers."

$\endgroup$
1
$\begingroup$

The formal formula is $$ \forall x \forall y (x \in \mathbb Z \land y \in \mathbb Z \land x \text{ odd}\land y \text{ odd} \implies xy \text{ odd}) $$ Since $P \implies Q$ is true when $P$ is false, one generally omits the cases when $P$ is false, because there is nothing to prove in these cases.

In our context, $P$ is false when $x \not\in \mathbb Z \lor y \not\in \mathbb Z \lor x \text{ even}\lor y \text{ even}$.

Thus, everyone starts with "Let $x,y$ be odd integers".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.