Mathematical statements with logical symbols

[Fredrik]

I'd like to get better at writing mathematical statements using logical symbols. Let's start out with something simple. "For every A with property x, there's a B with property y". How should I write that? I don't even know if there's a symbol for "with property". How about this?

\forall A:x\quad \exists B:y

Am I supposed to just leave a space before the \exists or is there a symbol I should use?

Now consider the definition of a compact set. A subset K of a topological space X is said to be compact if every open cover of K has a finite subcover. How can I write this with logical symbols? Suppose I start by saying that K is a subset of a topological space with topology \tau, and then start the next sentence with "K is said to be compact if". How should I finish it? Here's a suggestion (which probably needs to be improved):

\{U_i\in\tau|i\in I\}: \bigcup_{i\in I}U_i\supset K\implies \exists I_0\subset I:\bigg(|I_0|<\infty\quad \bigcup_{i\in I_0}U_i\supset K\bigg)

Can I use parentheses like that? Do I have to include an "and" symbol between the two statements in parentheses? Should I have made it a "for all" statement instead of making the whole thing an implication?

The next thing I'm going to ask about is the proper way to rewrite the statement in an equivalent way. For example, if we've written down an implication A\implies B, I'd like to rewrite it as \lnot B\implies \lnot A. And if we've written down a "for all" statement, I'd like to rewrite that in a way that corresponds to what I just said I want to do to the implication.

 

[Landau]

The problem with being too formal in using logical symbols, is that it soon becomes very cumbersome to read and write. That's why most people are a bit sloppy, and use a lot of words in combination with logical symbols: it's more readable.

Let's say you want to express that every real number other than zero has a multiplicative inverse. Most would write

\forall x\in\mathbb{R}-\{0\}\exists y\in\mathbb{R}: xy=1.

But \forall x\in A, where A is a set, is not really correct. You can quantify over variables such as "x", but "x\in A" is not a variable. Better would be

\forall x(x\in\mathbb{R}-\{0\}\Rightarrow\exists y(y\in\mathbb{R}\ \wedge\ xy=1)).

This is tiring to keep doing, and everyone knows what you mean by \forall x\in A.

I'd like to get better at writing mathematical statements using logical symbols. Let's start out with something simple. "For every A with property x, there's a B with property y". How should I write that? I don't even know if there's a symbol for "with property". How about this?

\forall A:x\quad \exists B:y

It's a bit general, but you could define sets X and Y consisting of elements having property x, y respectively. Than you'd say
\forall A\in X\quad \exists B\in Y

Am I supposed to just leave a space before the \exists or is there a symbol I should use?

There are not really strict rules about this. Readability is the norm. You can always use parenthesis to improve readability. One of my professors consistently writes
(\forall x)(\exists y)(bla)
for "for all x there exists y such that bla".

Here's a suggestion (which probably needs to be improved):

\{U_i\in\tau|i\in I\}: \bigcup_{i\in I}U_i\supset K\implies \exists I_0\subset I:\bigg(|I_0|<\infty\quad \bigcup_{i\in I_0}U_i\supset K\bigg)

Can I use parentheses like that?

Yes, you certainly can.

Do I have to include an "and" symbol between the two statements in parentheses?

Formally, yes. Informally, most people write a comma, and this is also what I would do:
\bigg(|I_0|<\infty,\quad \bigcup_{i\in I_0}U_i\supset K\bigg)

Should I have made it a "for all" statement instead of making the whole thing an implication?

Yes, I think a 'for all' symbol is needed here.
Also, you haven't said anything about the set I. Formally, you should also say "for all I" in the beginning, since it holds for arbitrary index sets I.

The next thing I'm going to ask about is the proper way to rewrite the statement in an equivalent way. For example, if we've written down an implication A\implies B, I'd like to rewrite it as \lnot B\implies \lnot A. And if we've written down a "for all" statement, I'd like to rewrite that in a way that corresponds to what I just said I want to do to the implication.

I don't quite understand this last question. Are you still referring to the definition of compact?

 

[Fredrik]

Thank you. That certainly helps. I will write a more thorough answer later. Unfortunately all I have time for right now is to answer your question at the end. I would like to write down the standard definition of "compact" (number (iii) here) using logical symbols, and then rewrite it in an equivalent way, which will turn out to be number (iv) on that list.

 

[Fredrik]

OK, I think I got it. My first thought was do give a name to the "set of open covers", say M, and then say that K is compact if

\forall m(m\in M)\ \exists m_0 (m_0\in M \land |m_0|<\infty)

But this is hard to rewrite in a way that makes the equivalence between (iii) and (iv) on that list easy to see. It can be expressed as an implication

m\in M\Rightarrow \exists m_0 (m_0\in M \land |m_0|<\infty)

but to rewrite this as "\lnot B\Rightarrow\lnot A" instead of "A\Rightarrow B" doesn't seem to get me any closer to what I want to do. So I came up with this instead:

\forall I(I\subset\tau,\ \bigcup_{i\in I}i\supset K)\ \exists I_0(I_0\subset I,\ |I_0|<\infty,\ \bigcup_{i\in I_0}i\supset K)

This can also be expressed as an implication:

(I\subset\tau)\ \land\ \bigg(\bigcup_{i\in I}i\supset K\bigg)\Rightarrow\exists I_0(I_0\subset I,\ |I_0|<\infty,\ \bigcup_{i\in I_0}i\supset K)

(Unnecessary parentheses inserted for readability). There are several different ways to express this in the "\lnot B\Rightarrow\lnot A" form, since "P and Q" can be negated by negating either P or Q. The form that gives me the alternative definition is

\forall I_0(I_0\subset I,\ |I_0|<\infty)\ \lnot\bigg(\bigcup_{i\in I_0}i\supset K\bigg)\Rightarrow (I\subset\tau)\ \land\ \lnot\bigg(\bigcup_{i\in I}i\supset K\bigg)

(Hm, maybe I should put parentheses around the entire left-hand side of this one). To see that this is what we want, we must rewrite the statements I negated. I'm defining F_i=i^c.

\lnot\bigg(\bigcup_{i\in I_0}i\supset K\bigg)\iff\emptyset\neq K-\bigcup_{i\in I_0}i=K\cap\bigg(\bigcup_{i\in I_0}i\bigg)^c=K\cap\bigg(\bigcap_{i\in I_0}F_i\bigg)

So the definition turns into

\forall I_0(I_0\subset I,\ |I_0|<\infty)\ \bigg(\bigcap_{i\in I_0}F_i\cap K\neq\emptyset\bigg)\Rightarrow (I\subset\tau)\ \land\ \bigg(\bigcap_{i\in I}F_i\cap K\neq\emptyset\bigg)

which is (iv) on the list in the book I linked to...or is it? Hm, this looks weird. Don't we want the statement that I is a subset of the topology to appear on the left instead of the right?

I have to go to bed, so I can't think about this right now.

 

[Fredrik]

OK, I think I see what I did wrong. (P\land Q)\Rightarrow R is equivalent to \lnot R\Rightarrow (\lnot P\land Q)\lor(P\land\lnot Q), and you can't just drop one of the terms on the right in the last expression, which is essentially what I did. So let's go back to the implication that I want to rewrite:

(I\subset\tau)\ \land\ \bigg(\bigcup_{i\in I}i\supset K\bigg)\Rightarrow\exists I_0(I_0\subset I,\ |I_0|<\infty,\ \bigcup_{i\in I_0}i\supset K)

It implies several different things, one of which is

\bigg(\forall I_0(I_0\subset I,\ |I_0|<\infty) \bigcap_{i\in I_0}F_i\cup K\neq\emptyset\bigg)

\Rightarrow \bigg((I\not\subset\tau)\land\bigg(\bigcup_{i\in I}i\supset K\bigg)\bigg)\lor\bigg((I\subset\tau)\land\bigg(\bigcap_{i\in I}F_i\cup K\neq\emptyset\bigg)\bigg)

And this implies

(I\subset\tau)\land\bigg(\forall I_0(I_0\subset I,\ |I_0|<\infty) \bigcap_{i\in I_0}F_i\cup K\neq\emptyset\bigg) \Rightarrow \bigcap_{i\in I}F_i\cup K\neq\emptyset

Alternatively:

\forall I\bigg((I\subset\tau)\land\bigg(\forall I_0(I_0\subset I,\ |I_0|<\infty) \bigcap_{i\in I_0}F_i\cup K\neq\emptyset\bigg)\bigg)\quad \bigcap_{i\in I}F_i\cup K\neq\emptyset

This is the expression I want. I thought it would be possible to obtain it in a way that corresponds to A\Rightarrow B if and only if \lnot B\Rightarrow\lnot A, but it was more difficult than that.

 

[Landau]

OK, I think I see what I did wrong. (P\land Q)\Rightarrow R is equivalent to \lnot R\Rightarrow (\lnot P\land Q)\lor(P\land\lnot Q), and you can't just drop one of the terms on the right in the last expression, which is essentially what I did.

I haven't read your last post yet, but this is wrong.
(P\land Q)\Rightarrow R is equivalent to \lnot R\Rightarrow (\lnot P\vee \lnot Q). If you want, this last statement is equivalent to
(\lnot P\land Q)\vee(\lnot P\land \lnot Q)\vee(P\land \lnot Q).

The mathematical \vee is the inclusive disjunction: A\vee B means A or B or both.

 

[Fredrik]

Ah, of course. Thanks again. Back to the drawing board then...