0
$\begingroup$

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}$ ?

$\endgroup$
  • 1
    $\begingroup$ ${\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}$. $\endgroup$ – Git Gud Jan 31 '14 at 1:49
1
$\begingroup$

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.

You must start with :

$\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) )]$.

$\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.