I'm reading the following two passages and am having trouble understanding how their contrapositives are constructed.

Consider the following statements:

If $X$ is a separable metric space, and $S \subset X$ is a subset such that there exists $d_0>0$ with $d(s,s') \geq d_0$ for all distinct $s,s'\in S$, then $S$ is countable.

This will read: $$(\text{X is separable)&(}(\forall s,s'\in S\subset X)(\exists d_0>0)(d(s,s')>d_0))\implies\text{S is countable}$$

Conversely, if $X$ is a metric space containing an uncountable subset $S$ any two of whose points are at least $d_0$ apart, then $X$ is not separable.

I want to take the contrapositive of the logical implication I wrote previously to conclude the second passage. So far:

$$S \subset X\text{ is uncountable} \implies \neg \big( (\text{X is separable)&(}(\forall s,s'\in S)(\exists d_0>0)(d(s,s')>d_0)) \big)$$

Now I'm stuck.

  • 1
    $\begingroup$ Don't forget the part $S\subset X$ in your condition $\endgroup$ – Sudix May 12 '18 at 20:45
  • 1
    $\begingroup$ Next thing to do is use some logical equivalence laws to simplify the right hand side of your contraposition (De Morgans Laws) $\endgroup$ – Sudix May 12 '18 at 20:53
  • $\begingroup$ Aha, okay I tried this. But now the logical statement seems to diverge strongly from the the meaning of the second passage. I'm worried now I encoded the original statement incorrectly. $\endgroup$ – yoshi May 12 '18 at 20:59
  • 1
    $\begingroup$ No, as far as I can see it, the logical statement you've made is fine. If anything is wrong, it's probably in this last step. What formula did you get? $\endgroup$ – Sudix May 12 '18 at 21:04
  • $\begingroup$ $S \subset X\text{ is uncountable} \implies (\text{X is not separable) or }(\exists s,s'\in S)(\forall d_0>0)(d(s,s')\leq d_0))$ $\endgroup$ – yoshi May 12 '18 at 21:10

The first statement is just (written as a logical formula) (your interpretation of it is not quite right):

$$(X \text{ separable }) \to \left(\forall S\subseteq X: (\exists d_0 >0: \forall x,y \in S: d(x,y) > d_0) \to (S \text{ at most countable })\right)$$

So its contrapositive is ($p \to q$ is equivalent to $\lnot q \to \lnot p$):

$$\lnot \left(\forall S\subseteq X: (\exists d_0 >0: \forall x,y \in S: d(x,y) > d_0) \to (S \text{ at most countable })\right) \to (X \text{ not separable })$$

where the first negation can be "expanded" (a $\lnot (\forall x: \phi(x))$ is equivalent to $\exists x : \lnot \phi(x)$ and an implication $p \to q$ is false exactly when $p$ is true and $q$ is false) to:

$$\left(\exists S\subseteq X: (\exists d_0 >0: \forall x,y \in S: d(x,y) > d_0) \land (S \text{ uncountable })\right) \to (X \text{ not separable })$$

which exactly says that if we have an uncountable set all $d_0$ apart, $X$ is not separable, as claimed.

  • $\begingroup$ Thanks! Just some questions on notation -- what does ":" mean as a logical symbol, and the "up carrot" is "and", correct? (this is what I'm assuming from my knowledge of how to negate implications) $\endgroup$ – yoshi May 13 '18 at 14:08
  • 1
    $\begingroup$ $\land$ is and, yes. $:$ has no meaning in itself, but is used after quantifiers $\exists$, $\forall$, I read it as "it holds" or something like that; $\forall x: \phi(x)$ for all $x$ , $\phi(x)$ holds. etc. $\endgroup$ – Henno Brandsma May 13 '18 at 14:12

Let S be a subset of X.
If X is separable and exists d > 0 with for all x,y, d(x,y) >= d,
then S is countable.

Notice how when you write "this will read" that
you reversed the proper order of the quantifiers.

Using DeMorgan's rules for logical connectives and
quantifiers and that <= is a linear order one obtains

if S is uncountable, then X is not separable
or for all d > 0, exists x,y with d(x,y) < d.

  • $\begingroup$ I see, but how is this equivalent to the second passage (in tan). Also see my last comment under the question. $\endgroup$ – yoshi May 12 '18 at 21:47
  • $\begingroup$ @yoshi. I do not see anything in tan. $\endgroup$ – William Elliot May 13 '18 at 2:58

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.