Help writing the contradiction of this statement

Question

I was given the statement and asked to write it out symbolically and negate it.

"Given any integer $n>1$, there is a power of $2$ that is bigger than $n/2$ and less than or equal to $n.$"

First, would this statement symbolically be

n∈$\mathbb{Z}$ (∀n>1) $\rightarrow$ ∃x∈$\mathbb{R}$ $(\frac{n}{2} <2^x \ge n)$

so if this is correct the negation would be

n∈$\mathbb{Z}$ (∀n>1) $\land$ ∀x∈$\mathbb{R}$ $(\frac{n}{2} >2^x \le n)$

Answer 1

Your initial symbolic statement is wrong. The phrase "power of 2" implies "integer power of 2". There's no need to talk about $\mathbb R$, so we can assume all quantification ranges over integers. So let's break this down.

given any integer n>1, [something about n]

Symbolically, this is $\forall n( n>1\rightarrow \mathrm{something})$

there is a power of 2 that is bigger than n/2 and less than or equal to n.

Symbolically, this is $\exists m\left(\frac{n}{2} < 2^m \le n\right)$

Putting them together gives $$ \forall n\left[n>1\rightarrow\exists m\left(\frac{n}{2}<2^m\le n\right)\right] $$ Can you negate this from here?

Answer 2

Write $$\forall n \,(1<n\in \Bbb Z\implies \exists x \,(n/2<2^x\leq n)).$$ This can be read aloud verbatim, from L to R, in English: For every $n,$ if $1<n\in \Bbb Z$ then there exists $x$ with the property that $n/2<2^x\leq n.$ ( The bracket immediately after "$\exists x$" is "such that" or "with the property that".)

The algorithm for getting the negation is:

(1). We have $\neg \forall n\,( A)$ where $A$ is the rest of the sentence. This is equivalent to $$\exists n\,(\neg A).$$(2) . "$A$" is $B\implies C$ where $B $ is $1<n\in \Bbb Z$ and where $C$ is the rest of the sentence after $B$. Now $\neg (B\implies C)$ is equivalent to $(B\land \neg C)$. So far we have $\exists n \,(B\land \neg C),$ which is $$\exists n\; (1<n\in \Bbb Z \land \neg C).$$ (3). $\neg C$ is $\neg \exists x\; (D)$ where $D$ is the rest of the sentence afterwards. Now $\neg \exists x\,(D)$ is equivalent to $\forall x\; (\neg D).$ And $D$ is $(n/2<2^x\leq n).$ So we have $$\exists n\;(q<n\in \Bbb Z \land \forall x \;(\neg (n/2 <2^x\leq n))).$$ (4). The phrase $\neg (n/2 \leq 2^x\leq n)$ can be left as is, or changed to the equivalent $(2^x\leq n/2\lor 2^x>n).$ So we have $$\exists n\;(1<n\in \Bbb Z\; (\forall x\; (2^x\leq n/2\lor 2^x>n))).$$ That is, reading from L to R: There exists (at least one) $n$ with $1<n\in \Bbb Z$, with the property that for every $x$ , either $2^x\leq n/2$ or $2^x>n.$

Observe that $\neg \forall y\; (P)$ is equivalent to $\exists y\; (\neg P).$ And $\neg \exists y (Q)$ is equivalent to $\forall y\,(\neg Q).$ Observe how the $\neg$ "travels" from L to R.

You can argue, logically, that the negation of a statement $S$ is just $\neg S$, and stop there, but human brains have difficulty understanding $\neg S$ "as is" even when $S$ is short.