# 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.

## Contents

## Basic Set Theory[edit]

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[edit]

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.

- 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.) - An empty set exists. This set will be denoted as
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): \varnothing**and will contain no elements. - Two sets are equal if and only if they contain the same elements.
- If
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): A**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): B**are sets, then there is a set containing only the elements of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): A**and . This is called the*union*of and . - If
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): A**is a set and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): P(x)**is a truth statement defined for all**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): x**contained in , then there is a set so that is in whenever**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): P(x)**is true. - The set of counting numbers
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): (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[edit]

As mentioned above, a *set* will be a collection of *elements*. For example, let

The vertical bar | is read "such that". We can select elements in that way by using Axiom 5 from above. In the case of , the predicate (truth statement) **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): P(x)**
used to select elements is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): 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 **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): \mathbb {R} **
. Thus, can be read as: " is the set of all real numbers strictly greater than ."

To say that is an element of is equivalent to saying that contains **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): x**
. These concepts are notated mathematically by **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): x\in A**
(x belongs to the set A) and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): A\ni x**
. If is not a member of then we write (x does not belong to the set A).

The *union* of and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): B**
is defined in axiom 4. It consists of all the elements in

```
```

The *intersection* of and is the set containing all things that are in *both* and . The notation for this is .

```
```

If then and are said to be *disjoint*. This means that there is nothing that is in both sets. For example, if is the set of all even integers and is the set of all odd integers, then they are disjoint.

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

## Quantifiers[edit]

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[edit]

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

```
```

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

```
```

This notation, , 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 that is not in **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): B**
are not equal) and use **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): A\subseteq B**
to denote that

### There Exists[edit]

This is probably as common as *for all* and is equally useful. Its mathematical symbol is . It is almost always followed by a "such that" statement. For example, "There exists a computer that has 8GB of RAM." and 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

or, when and are understood,

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: .

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,

```
```

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[edit]

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[edit]

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[edit]

Now, we're not going to begin a discussion of astronomy. In mathematics, the *universe* is overall, 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[edit]

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. ( denotes the difference of *A* and *B*.) The difference is the set of all things that are in *A* that are not in *B*.

```
```

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

### Complement[edit]

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 . If *U* is the universe, then the complement of *A* is defined to be .

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 . This is a general drawing, since it is not known whether there are elements in *A* and *B*. If 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 , then .

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

## Exercises[edit]

- Express the following statements in terms of sets, using difference or complement.
- All people that have two legs.
- All mythological creatures that are not Greek.
- All pudding pies that have no cream on top.

- Draw a Venn Diagram to illustrate the following.
- Negate the following statements.
- All quick, brown foxes jump over some lazy dog.