Space Logic Lemmas

For my MATH-1001 final project, I will introduce some basic proof structures in an intuitive format, that of overlapping geometric shapes. There are problems with this form of visualization (it can be cumbersome or misleading) but also some great strengths.

While much of the content here might be seen as prerequisites for a theory, I think these results are interesting in their own right. Furthermore, they are self-contained, making them perfect for analysis.

I originally drew up sketches for equivalence and induction as well, but found those to sacrifice too much detail for too little intuition. In lieu of these, I expand on some quantifier logic that benefits greatly from the geometric approach.

Form follows function.

Everything

Everything is the set containing everything of interest. I promise this is going somewhere.

A

We draw the set A as a circle. I’ve tried other approaches but haven’t found anything that works as well; for inclusions and intersections, circles are the most suggestive of a set. Squiggles look like you’re trying to call attention to them, triangles, squares, and hexagons fail miserably at suggesting intersection, etc.

Not A

Let’s say we have A as above. We also can describe not A, $\sim A$ , as everything without A, producing the hole shape below.

A intersect B

One classic of Venn diagrams is set intersection. Given sets $A$ and $B$ , their intersection $A \cap B$ is all of the elements in both set $A$ and set $B$ . This is depicted as the overlapping area between $A$ and $B$ .

Direct Proof: A implies B

Here, we have the first way to express a statement, the direct proof $A \to B$ . In every world we have $A$ , we have $B$ . $B$ encircles $A$ .

Note that there is a difference between $\cap$ , $\cup$ etc. and $\to$ . The first examples are description within a world, while the second is a relation about a world.

Here are examples of A implies B:

In every world where $5$ divides $2 x$ , $5$ divides $x$ .

In every world where $x^{2} = 4$ , $x = 2$ .

In each, we go from a statement $A$ to a more general statement $B$ . It is not necessary that $B \to A$ , however; the two examples above show this.

Contrapositive: Not B implies not A

Here is an explanation for the contrapositive proof. The contrapositive is another way to prove that $A \to B$ . It says that if we prove that $\sim B \to \sim A$ , we are really proving the same thing. This does not feel intuitive.

However, we can make it clear with diagrams. If we have the direct proof $A \to B$ , it is the same as saying that $\sim B \to \sim A$ . That is, claiming $B$ encircles $A$ is really the same as claiming $\sim A$ encircles $\sim B$ . A statement must be claiming something, which is why in each approach we start with the smaller shapes $A$ and $\sim B$ . It is our task during the proof to show that this smaller shape is encircled by the larger one.

Because defining what something isn’t is the same as defining what it is, our two approaches end up showing the same thing.

upward entailing environments

Credit to Natalie Clarius on Linguistics Stack Exchange for the text of some of the examples here.

Here is a case I realized could be described with the same diagrams as above. In linguistics, all, some, no, most, many ... are known as quantifiers. Sentences with quantifiers usually assign relations between two sets, the restriction A and the body B.

When we say All women sang loudly, we are assigning a relation between those who are women (the restriction A) and those who sang loudly (the body B).

The terms may be a little confusing. The body of the sentence is sang loudly because the essential message of the sentence is that someone sang loudly; hence, it is the body. The restriction limits those involved to women.

Some quantifiers are known as upward entailing. They are upward entailing in the restriction (A), and downward entailing in the body (B). One example is the quantifier all.

all is considered to be upward entailing in the body, because we may widen $\equiv$ loosen the body (going from those who sang loudly, to those who sang). We have the entailment

All women sang loudly > All women sang

Illustrated, this says that one implication implies another (for convenience, each implication is now a single image, where the smaller shape implies the larger). The implication $A \to B$ implies $A \to B^{'}$ , where $B^{'}$ is larger:

And all is downward entailing in the restriction, because we may make smaller $\equiv$ tighten the subject (going from women, to young women) and still have it be true.

All women sang loudly > All young women sang loudly

We see a different implication $A \to B$ implying $A^{'} \to B$ , where $A^{'}$ is smaller:

downward entailing environments

Other quantifiers are known as downward entailing. They are downward entailing in both the restriction (A) and body (B). One example is the quantifier no.

Unlike all, no is downward entailing in the body, because we may make smaller $\equiv$ tighten the body (going from those who sang, to those who sang loudly) and still have it be true. We can see this clearly when we think of the statement no women sang as $A \to \sim B$ , where the restriction and body are disjoint. We see that $A \to \sim B$ implies $A \to \sim B^{'}$ , where $B^{'}$ is smaller:

No women sang > No women sang loudly

Like all, no is also downward entailing in the restriction, because we may make smaller $\equiv$ tighten the restriction (going from women, to young women), and still have it be true. We see that $A \to \sim B$ implies $A^{'} \to \sim B$ , where $A^{'}$ is smaller:

No women sang > No young woman sang.

Geometric Interpretation

Our diagrams can help us determine exactly how statements with all and no differ.

In all, the body (B) is inclusive of A: $A \to B$ .

In no, the body (B) is exclusive of A: $A \to \sim B$ .

Simply by looking at the shapes, we can see that all is upwards entailing in the body, while no is downwards entailing in the body.

With all, we cannot tighten the body. In all women sang loudly, tightening sang loudly to sang very loudly means that B is no longer inclusive of A:

With no, we cannot loosen the body. In no women sang, widening sang to made noise means that B is no longer exclusive of A:

Likewise, we can also see geometrically that both kinds of statements are downward entailing in the restriction.

In all women sang loudly, loosening women to persons means that (B) is no longer inclusive of A:

Likewise, in no women sang loudly, loosening women to persons means that B is no longer exclusive of A:

Proof by Contradiction

Like the contrapositive, proof by contradiction directly follows the direct proof. In every world where we don’t have the direct implication $A \to B$ , we must have $A \to \sim B$ . Our task is to show that this ends up as $C \land \sim C$ , which is impossible. Thus, we must have $A \to B$ .

We want to show that $A \to B$ must be the case. That is, in every world we have $A$ , we have $B$ .

So we assume $A \to \sim B$ .

Now, we show that $A \to \sim B$ leads to $C \to \sim C$ :

This is a contradiction. It is true that we have previously seen examples of disjoint shapes. But here, to claim that $C \to \sim C$ is to say that C is contained in $\sim C$ ! This is definitely impossible. Because in every world in which we have $A \to \sim B$ , we reach $C \to \sim C$ , we must have $A \to B$ instead.

This is less satisfying than showing the contrapositive, because it is not as clear how we would go from $A \to \sim B$ to $C \to \sim C$ . However, it does provide intuition about why we cannot have $C \to \sim C$ : a set can never be contained by its complement.

A if and only if B (lover’s quarrel, very cute)

We can say A $\leftrightarrow B$ to mean $A \to B$ and $B \to A$ at the same time.

If we have both $A \to B$ and $B \to A$ , we must have A contained by B and B contained by A. This is impossible … unless A and B are the same! This is same rationale for proving equality by double set inclusion.