# Logical Statements involving the definition of Separability

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.

• Don't forget the part $S\subset X$ in your condition – Sudix May 12 '18 at 20:45
• Next thing to do is use some logical equivalence laws to simplify the right hand side of your contraposition (De Morgans Laws) – Sudix May 12 '18 at 20:53
• 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. – yoshi May 12 '18 at 20:59
• 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? – Sudix May 12 '18 at 21:04
• $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))$ – 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.

• 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) – yoshi May 13 '18 at 14:08
• $\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. – 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.

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