# Negate Implication Written as a Sentence without “If …, Then …” [Chartrand P246]

P246 Theorem 10.4: Every infinite subset of a denumerable set is denumerable.

P252 Theorem 10.10: Let $A \subseteq B$ be sets. If $A$ is uncountable, then $B$ is uncountable.

I'm aware how to do this with the implication rewritten in the manner of "If..., Then,...": $\text{if P, then Q} \equiv \text{if not Q, then not P}.$
Here, I must rewrite Theorem 10.4 as: "If a set is denumerable, then every infinite subset of it is denumerable." Then P = "a set is denumerable" and Q = "every infinite subset of it is denumerable."

Nonetheless, how would you negate the conditional/implication without allusion to "If..., Then,...", purely considering the sentence as expressed in the form "... is ..." ?

I tried ${\Large{\neg}}\text{denumerable} \implies {\Large{\neg}}\text{Every infinite subset of a denumerable set}.$
How would you unscramble ${\Large{\neg}}\text{Every infinite subset of a denumerable set}$ ?

• ${\Large{\neg}}\text{Every infinite subset of a denumerable set}$ isn't a statement, you can't negate it. The same goes for ${\Large{\neg}}\text{denumerable}$. – Git Gud Jan 31 '14 at 1:49

About Th.10.4 : "Every infinite subset of a denumerable set is denumerable", if you try to translate it into propositional logic (in your attempt, you have $Q$ = "every ...") you will lose some relevant information.

$\forall X \forall Y ( ( Denum(X) \land Y \subseteq X ) \rightarrow (Inf(Y) \rightarrow Denum(Y))$.

Now, in order to "negate" it, you must take into account the relations between quantifiers :

$\lnot \forall$ is "replaceable" by $\exists \lnot$

and

$\lnot \exists$ is "replaceable" by $\forall \lnot$.

The negation of the above statement will be :

"$\lnot \forall X \forall Y$ ..." i.e. "$\exists X \lnot \forall Y$ ..." i.e. "$\exists X \exists Y \lnot$ ..."

i.e.

$\exists X \exists Y \lnot [ (Denum(X) \land Y \subseteq X ) \rightarrow (Inf(Y) \rightarrow Denum(Y) )]$.

Now we must use truth-tables (or definition of $\rightarrow$ in terms of $\lnot$ and $\lor$ , De Morgan laws and Double Negation) : $\lnot(P \rightarrow Q)$ is equivalent to : $(P \land \lnot Q)$, so that we can rewrite the above formula as :

$\exists X \exists Y [ (Denum(X) \land Y \subseteq X ) \land \lnot (Inf(Y) \rightarrow Denum(Y) )]$.

Repeting the operation with the inner $\rightarrow$ we get :

$\exists X \exists Y [ (Denum(X) \land Y \subseteq X \land Inf(Y) \land \lnot Denum(Y) )]$.