I've been trying to negate the following statement using quantifiers, but I can't seem to totally make sense of it (let $n$ be an integer.):
- There exists an odd integer $k$ such that $n=2k$.
One of my attempts at negation was, "For all integers $k$, $n=2k$ implies that $k$ is even," though I'm not entirely sure of this. Even if it is, it's still not the most practical negation for proof purposes. I was told by my professor that the negation of the original statement is, "$n$ is odd or $n=2k$ for even $k$." I'm not sure how to get to that statement using purely symbolic logic and quantifiers. Can anybody show this using quantified statements?
Thanks in advance!
Best Answer
The problem is that the negation of the original statement is not logically equivalent of the statement from your professor. You need to add all kinds of basic arithmetical truths (such as that every integer is either even or odd) in order to infer your professor's statement from it ... These are arithmetical truths, but not logical truths. So if you try to do this using pure logic, it's not going to work.
The best you can do is to indeed define a bunch of axioms about integers, defining the numbers 1 and 2, defining addition and multiplication, and defining even and odd. Then, you should be able to derive the following statement from those axioms as a theorem:
$\forall n (\neg \exists k (Odd(k) \land n =2k) \leftrightarrow (Odd(n) \lor \exists k (Even(k) \land n =2k)))$
Or, if you don't like to use $Even$ and $Odd$ predicates:
$\forall n (\neg \exists k (\exists m \: k =2m+1 \land n=2k) \leftrightarrow (\exists m \: n=2m+1 \lor \exists k (\exists m \: k=2m \land n=2k)))$
These biconditionals show that arithmetically the two claims are the same (just as saying that 'integer n is even' is arithmetically the same claim as 'integer n is not odd'), but the two claims are not logically the same!