Intro to Math - 1

The logical underbelly of mathematics feels almost secretive, like something "big mathematics" does not want you to see. But the truth is, there is probably no single exact formal logic used all the time everywhere.

(I am not a formal logic guy, so this section will be short and take it with a big pile of salt).

Among other things, mathematical logic is the study of writing mathematical arguments in formal logical systems. But mathematics itself is not only the study of formal logic.

One of the things that bothered me when I first started out was the act of over-formalization. I thought I would have to write all my mathematical arguments in perfect first-order logic.

There has been a lot of work on making formal foundations for set theory, the natural numbers, and constructions that extend from the natural numbers all the way to the algebraically closed complex numbers (meaning any univariate polynomial with complex coefficients has zeros in the complex numbers).

And now, the formal logical foundations of mathematics are quite strong. Today, most textbooks and papers are not sticklers for setting up set theory from scratch every time, or being extremely careful about which formal logic system we are (implicitly) using and so on.

Instead, there is comfort in writing mathematics in what I call mathematical English. This is some mixture of English, notation, and something resembling first-order logic, where you have propositions but also quantifiers.

Propositions

A proposition is a statement that is clearly either true or false, never both, and never ambiguous.

For example:

"Pigs have the innate biological ability to fly with no external assistance whatsoever."

This is a statement we can all agree is false.

Similarly, in mathematics, a statement like:

"1 is a natural number"

is a proposition.

Classical logic works on the principle that if $p$ is a proposition, then $p$ is exactly one of two things: TRUE or FALSE.

This includes the law of the excluded middle: if a statement is not true, then it is false; if it is not false, then it is true.

We can also negate a proposition. The negation of $p$ is denoted $\mathrm{\neg }p$, and it is true exactly when $p$ is false, and false exactly when $p$ is true.

Implication

One of the most important tools in mathematics is implication, written $p⟹q$, or in words, "if $p$ then $q$".

For example:

"If $2$ is a natural number, then $2+1$ is a natural number."

We know this implication is true, because $2$ is a natural number, and whenever $2$ is a natural number, adding $1$ gives another natural number.

To be precise, we can connect implication to the logical connectives $\vee$ (or) and $\wedge$ (and).

Formally:

Now, let us look at the truth table. (Here $0$ means false and $1$ means true.)

We see that the only case where $p⟹q$ is false is when $p$ is true but $q$ is false.

This matches our intuition: starting from a true statement and then claiming it implies something false is simply wrong.

On the other hand, if $p$ is false, then the implication is automatically true. This is why statements like "If pigs can fly, then I am God" are technically true, because the premise "pigs can fly" is false.

In mathematical writing, implications are usually hidden inside plain English, but it is good to be able to recognize them.

The Converse and the Contrapositive

The converse of $p⟹q$ is $q⟹p$.
You should pause and ask: if an implication is true, is its converse always true? (Try reasoning in natural language, or check with a truth table if you are not convinced.)

The contrapositive of $p⟹q$ is $(\mathrm{\neg }q)⟹(\mathrm{\neg }p)$.

The key fact is that the contrapositive is logically equivalent to the original implication: both have the same truth table.

That is why in mathematics we often use "proof by contrapositive", or the stronger "proof by contradiction".

If and Only If

If both $p⟹q$ and $q⟹p$ are true, we write $p⟺q$.
This is read as "p if and only if q", or simply "p iff q".

This kind of two-way implication is very common. Let us break it down.

• When $p⟹q$ is true, we can say: whenever $p$ is true, $q$ must also be true. So $q$ is necessary for $p$.
• When $q⟹p$ is true, then whenever $q$ is true, $p$ must also be true. So $q$ is sufficient for $p$.

Thus, $p⟺q$ can be expanded as:

$q$ is necessary and sufficient for $p$.

Variables and Quantifiers

We really want to write statements like: "if $n$ is a natural number, then $n+1$ is a natural number." Hence, we need to allow variables in our statements, and math does allow them of course.

A quantifier allows you to make a statement about a variable.

Let us see another statement:

"For all natural numbers $n$, there exists a unique natural number called the successor of $n$, $s(n)$".

Here, we see two quantifiers (the most common in mathematics): For all, which in notation uses the inverted 'A', $\mathrm{\forall }$, and there exists, which uses the mirrored E, $\mathrm{\exists }$.

Okay, let us examine them individually.

Take the statement:

"For all natural numbers $n$, $n+1$ is a natural number too."

What do you think is the negation of the above statement?

Is it: "For all natural numbers $n$, $n+1$ is never a natural number"?

Well, obviously not. When you make an assertion about all elements of some object, to negate that assertion, you only need to show ONE element of that object that does not fit the assertion.

The correct negation then is:

"Not all natural numbers $n$ have the property that $n+1$ is also a natural number."

which naturally becomes a statement about the existence of a counterexample:

"There exists a natural number $n$ such that $n+1$ is not a natural number."

That is, the negation of a "for all" assertion is a "there exists" counterexample assertion.

Next consider:

"There exists a rational number $x$ for which $x^2=2$."

And its negation:

"There exists no rational number $x$ for which $x^2=2$."

which naturally becomes a statement about universality:

"For all rational numbers $x$, $x^2\ne 2$."

Cool!

Sets, and functions

You might see a statement compressed in math notation (note that $a\in A$ means "$a$ is an element of the set $A$") like:

That is a bit of notation mess. Let us unpack it.

The blackboard capital fonts $\mathbb{N}$ often denote important number systems, like: $\mathbb{N}$ is the natural numbers, $\mathbb{Z}$ is the integers, $\mathbb{Q}$ is the rational numbers, $\mathbb{R}$ is the real numbers, and $\mathbb{C}$ is the complex numbers.

We need a little more machinery to unpack the above statement. (We will not do a formal and axiomatic treatment of set theory.)

A set (often denoted with capital letters) $A$ is a thingy that holds elements like $a$ in it.

In order to do math, one has to allow undefined terms like "set" and "element", otherwise you can get into an infinite descent of defining a term, then defining the terms in that term, and so on.

The elements of a set can themselves be sets too. (There are some paradoxes that arise from this. However, for most math, there usually isn't a situation where such paradoxes arise, so we can ignore dealing with them.)

A set does not hold copies of elements — every element of a set is unique.

The only thing we need to build most of the set operations is the following: for any element $a$, and any set $A$, we can check if the element $a$ is present in the set $A$ or not.

That is, we write $a\in A$ to say $a$ is an element of $A$, and $a\notin A$ otherwise.

We can then use this "belongs to" or "is in" relation between elements and sets to define our familiar union, intersection, and difference.

The most common way to build sets is to use set-builder notation, which looks like $A=\{x:p(x)\}$.

This means that $A$ collects elements $x$ that satisfy all the properties imposed by $p$. You can think of $p$ as a "properties checker" where if you give it $x$, it will output true only if $x$ satisfies all the conditions imposed by $p$.

But in practice, of course, $p$ is some kind of mathematical statement. We will see plenty of examples.

For the following section, let $A,B$ be sets.

• Union: The set $A\cup B:=\{x:x\in A\text{or}x\in B\}$.
• Intersection: The set $A\cap B:=\{x:x\in A\text{and}x\in B\}$.
• Difference: The set $A-B:=\{x\in A:x\notin B\}$.

When we write $:=$ this is to be read as "defined equal to".

The empty set, and subsets

The empty set $\mathrm{\varnothing }$ is the set that contains no elements. Its importance is analogous to the importance of $0$. It lets many objects be defined in all cases.

That is, in the same way that it is nice to have an answer to "I give you X apples and then take them back, now how many do you have," it is also nice to have an answer to:

$A=\{1,2,3\},B=\{5,6\}$ what is $A\cap B$?

Now, we say that $A$ is a subset of $B$ and write $A\subset B$ (in some texts you may see $A\subseteq B$) if the following statement is true:

"For each $x\in A$, $x\in A$ implies $x\in B$."

(Note that for style and emphasis, "for all" may be written as "for every", "for each", and so on.)

Due to the logic of implications, the empty set $\mathrm{\varnothing }$ is a subset of all sets. (Think about it.)

Now, two sets are equal if they both contain the exact same elements. That is, $A=B$ means that $x\in A⟺x\in B$.

In many proofs involving equality of two sets, we may first prove that $A$ is a subset of $B$, and then that $B$ is a subset of $A$. (Why does this work?)

Note: the properties of union, intersection, De Morgan laws, and all that good stuff, are left as exercises for the reader. This is a good way to understand math logic, sets, and proofs for those that are new.

Functions

Functions are the heart of math. Almost everything is a "function + more rules". A linear map is just a function between vector spaces that respects the linear combination structure.

So what are they?

A function is an object that takes elements from one set and assigns them to elements of another set, but there are some rules.

First, write $f:A\to B$ to mean "$f$ is a function from set $A$ to set $B$."

Now, what are the rules?

• Every element $a$ of $A$ (often called the domain of $f$) has to have an element $f(a)$ in $B$.
• For a single input $a$, the function $f$ can only give a single output $f(a)$. That is, $f(a)$ always denotes ONE element in $B$. No more, no less.

And that's it.

Let us understand a little more now.

Firstly, I want you to think of the function as three things:

• The input set $A$, often called the domain of the function.
• The output set $B$, which is called many things: "codomain", "range", "target" are some that I've seen.
• A prescription or a rule, which tells us how elements of $A$ are mapped to elements of $B$.

To give this prescription explicitly, we write $a\mapsto f(a)$ (where the goofy looking arrow is to be read as "maps to" or "goes to"). For example, a prescription can be $a\mapsto a^2$.

Another way to write this prescription is the familiar $f(a)=a^2$.

It is a little problematic to think of the function only as the prescription $f(a)=a^2$, because this prescription can be applied on many input and output sets.

The inputs and outputs can be natural numbers, integers, rational numbers, real numbers, or even complex numbers. In some cases, the function may even be ill-defined (the reader can pause here and work things out).

This is going to be a series, writing some basic equipment for doing math in a slightly conversational style.

Why do this when lots of texts do it better? I don't know, maybe one person will find this particular writing useful. And that's guuci.