Mathematical Proof/Introduction/Notation

While a comprehensive list of notation is included in the appendix, that is meant mostly as a reference tool to refresh the reader of what notation means. This section is to introduce the notation to the reader and explain its usage.

Basic Set Theory

This is not meant to be a comprehensive or rigorous definition of set theory. We will define a minimal amount of set-theoretical objects, so that the concept of mathematical thinking can be understood. In this book, we will use capital letters for sets and lowercase letters for elements of sets. This convention is not to discourage creativity or to bore your socks off, but to avoid confusion.

Axioms

An axiom is something that is assumed, or believed to be true. It is where mathematical proof starts; you cannot prove the axioms, you merely believe them and use them to prove other things. There are different sets of axioms, the most current and widely-used being Zermelo–Fraenkel set theory. I will give a list of axioms here that will suffice for the studies in this book.

1. A set exists. (A set, for our purposes, will be a collection of objects that we will call elements. A set is said to contain its elements, and the elements are said to be contained in the set.)
2. An empty set exists. This set will be denoted as $\varnothing$ and will contain no elements.
3. Two sets are equal if and only if they contain the same elements.
4. If $A$ and $B$ are sets, then there is a set containing only the elements of $A$ and $B$. This is called the union of $A$ and $B$.
5. If $A$ is a set and $P(x)$ is a truth statement defined for all $x$ contained in $A$, then there is a set $B$ so that $x$ is in $B$ whenever $P(x)$ is true.
6. The set of counting numbers $(1,2,3,\dots )$ exists; or, an infinite set exists.

Some of these are worded rather formally, which is a tendency for mathematicians. First of all, let's explain why we need these axioms.

The first axiom says "a set exists." So you might ask—don't we know that it exists? Can't we just define it to exist? The answer is, yes, and that's why it's an axiom. Axioms are supposed to be self-evident truths. Now that we've established the fact that sets exist, why would we want one with no elements? Well, the empty set turns out to be both a very useful and a very annoying set. You'll learn to be good friends with the empty set by the end of the text.

Axiom 3 could be considered a definition, rather than an axiom, of what we mean when we say that two sets are equal. Axiom 4 just says that if we have two sets then we can get a new set with all of those elements in it. For example, the set of all people and all dogs.

The fifth axiom is probably the most confusing. All it says is that if we have a set and we want to pick out certain elements, we can do that. For example, out of the set of all integers, we can choose the ones that are even, or the ones that are positive, or the ones that are perfect squares.

Finally, the infinity axiom is nice because we will do lots of things with infinite sets.

Definitions

As mentioned above, a set will be a collection of elements. For example, let $A$ be the set of all cheesecakes, and let $B$ be the set of all things that are chocolate. Mathematically, this would be denoted as:

$A=\{x|x{\mbox{ is a cheesecake}}\}$
$B=\{x|x{\mbox{ is chocolate}}\}$

The vertical bar | is read "such that". We can select elements in that way by using Axiom 5 from above. In the case of $A$, the predicate (truth statement) $P(x)$ used to select elements is:

$P(x)\ :\ x{\mbox{ is a cheesecake}}$

Note that we have implicitly assumed the existence of a universal set of all elements over which we are making a selection. In the example above, this universal set could be the set of all pastries. In general, if a universal set is not specified, we shall assume that we are talking about the real numbers $\mathbb {R}$. Thus, $C=\{x|x>2\}$ can be read as: "$C$ is the set of all real numbers strictly greater than $2$."

To say that $x$ is an element of $A$ is equivalent to saying that $A$ contains $x$. These concepts are notated mathematically by $x\in A$ (x belongs to the set A) and $A\ni x$. If $x$ is not a member of $A$ then we write $x\notin A$ (x does not belong to the set A).

The union of $A$ and $B$ is defined in axiom 4. It consists of all the elements in $A$ and $B$ and is denoted $A\cup B$. We can also use the | to say

$A\cup B=\{x|x\in A{\mbox{ or }}x\in B\}=\{x|x{\mbox{ is a cheesecake or is chocolate}}\}$

The intersection of $A$ and $B$ is the set containing all things that are in both $A$ and $B$. The notation for this is $A\cap B$.

$A\cap B=\{x|x\in A{\mbox{ and }}x\in B\}=\{x|x{\mbox{ is a chocolate cheesecake}}\}$

If $A\cap B=\varnothing$ then $A$ and $B$ are said to be disjoint. This means that there is nothing that is in both sets. For example, if $A$ is the set of all even integers and $B$ is the set of all odd integers, then they are disjoint.

Notice that the logical connectors $\lor ,\land$ coincide with the set operators $\cup ,\cap$. This is deliberate, since the concepts are related. This is obvious when the two symbols are juxtaposed:

$A\cup B=\{x|(x\in A)\lor (x\in B)\}$
$A\cap B=\{x|(x\in A)\land (x\in B)\}$

Quantifiers

Quantifiers are used to establish what elements are currently being discussed. They are like adjectives in English—they tell how much or what kind of thing we're talking about.

For All

The most common quantifier is for all. This is written mathematically as $\forall$. It is also "for each" or "for every." It is used to make statements like "All humans have eyeballs." That is, if $H$ is the set of all humans and $E$ is the set of all things with eyeballs, then

$\forall x\in H,x\in E$

which is read "For all $x$ in $H$, $x$ is in $E$." This introduces a special relationship between sets that is called a subset. In this case, $H$ is a subset of $E$ since every element of $H$ is also in $E$. (For the sake of the logical argument, just assume there aren't any people without eyeballs.) We write this as

$H\subset E.$ 

This notation, $A\subset B$, is ambiguous because some authors use it to mean just a subset, while others use it to mean a proper subset (meaning there is an element of $B$ that is not in $A$, and thus $A$ and $B$ are not equal) and use $A\subseteq B$ to denote that $A$ is a subset of $B$. In this book we will go with the convention that $A\subset B$ could mean that $A$ is a proper subset of $B$ or that $A$ = $B$, and we will use $A\subsetneq B$ when we wish to emphasize that $A\neq B$.

There Exists

This is probably as common as for all and is equally useful. Its mathematical symbol is $\exists$. It is almost always followed by a "such that" statement. For example, "There exists a computer that has 8GB of RAM." $\forall$ and $\exists$ are often used in pairs, such as, "Everyone has a mother.", or, worded logically, "For each human, there exists a mother for that human.". Let H be the set of all humans and M be the set of all mothers. Then we have

$\forall h\in H,\exists m\in M{\mbox{ such that }}m{\mbox{ is the mother of }}h.$

or, when $H$ and $M$ are understood,

$\forall h,\exists m{\mbox{ such that }}m{\mbox{ is the mother of }}h.$

This quantifier is also read as there is or there are. To signify that there is only one of something, we say "There exists a unique..." and place an exclamation point after the exists symbol: $\exists !$.

In the same way that "not and" gives "or", "not for all" gives "there exists." That is, the opposite of the statement "All cheesecakes are chocolate." is "There is a cheesecake that is not chocolate." In logical terms,

$\lnot (\forall x\in A,P(x)){\mbox{ is equivalent to }}\exists x\in A:\lnot P(x).$

The above statement is read "the negation of 'For all x in A, P(x) is true.' is 'There is an x in A such that P(x) is false."

Such That

As we have seen, such that can be used in at least two cases: in conjunction with there exists and in picking out elements of a set. Of course, if you think about it, these two are really the same application because the statement "there exists" gives you the set of all things that exist, and the such that statement decreases the size of that set to focus just on the things in which you are interested. Such that is normally denoted as a colon(:) or as a vertical bar (|), and sometimes as "s.t."

Without Loss of Generality

This is a very helpful phrase in making proofs more concise and less redundant. For example, assume we have two integers x and y and that we know one of them is odd and one of them is even. Instead of trying to do two different parallel proofs, one where we assume that x is even and y is odd and another where we assume that y is even and x is odd, we simply say "Without loss of generality, assume x is even." Then we continue with the proof. This is done since the exact same argument applies if y actually was the even number, all we have to do is relabel x and y.

The Universe

Now, we're not going to begin a discussion of astronomy. In mathematics, the universe is overall, the biggest set that your discussion is referring to. For example, if the universe is not restricted, then the set of all things would truly be the set containing every single thing. However, if your universe is the set of all things on Earth, then the "set of all things" would not include Jupiter, since Jupiter is not on Earth.

Difference

In arithmetic, difference means the distance between two numbers—how far apart they are on the number line. In set theory, difference means something slightly different, but the same notation is used. ($A-B$ denotes the difference of A and B.) The difference is the set of all things that are in A that are not in B.

$A-B=\{x\in A|x\notin B\}=\{x|x\in A\land x\notin B\}$

In normal English, we use this concept when we say things like "Everyone with no demerits gets an A in this course."

Complement

A Venn Diagram of A, B, and U.

The complement of a set contains everything that is not in the original set. This definition only makes sense when a universe is understood. The complement is usually denoted by $A^{c}$. If U is the universe, then the complement of A is defined to be $A^{c}=U-A$.

The diagram to the right is a Venn diagram. A Venn diagram shows the relationships of sets. Note that in the figure, U is the universe, and A and B are sets in U. The blue portion is the complement of $A\cup B$. This is a general drawing, since it is not known whether there are elements in A and B. If $A\cap B$ is known to be empty, then they may be drawn disjoint.

The complement of a set is essentially the same as the negation of a statement. That is,

if $A=\{x|P(x)\}$, then 
$A^{c}=\{x|\lnot P(x)\}$.  

Thus, complements are used when saying what something is not.

Exercises

1. Express the following statements in terms of sets, using difference or complement.
   1. All people that have two legs.
   2. All mythological creatures that are not Greek.
   3. All pudding pies that have no cream on top.
2. Draw a Venn Diagram to illustrate the following.
   1. $A\cap B\cap C$
   2. $A\cup B-C$
   3. $(A^{c}\cap B^{c})\cup C$
   4. $A\cap (B\cup C)$
   5. $A-(U-B)$
3. Negate the following statements.
   1. $\forall x\in A,\exists y\in B:P(x,y)$
   2. All quick, brown foxes jump over some lazy dog.