{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Appendix A - Useful Mathematics not Covered in your Prerequisites\n",
    "\n",
    "Author: Michael Klinefelter\n",
    "\n",
    "Email: MK296@nau.edu\n",
    "\n",
    "## Introduction\n",
    "In talking with a number of current and previous students in this course, there appear to be a number of math terms which are widely used but not very well understood.  We often hear of \"Group\" or \"Field\" and have a general notion of what these terms mean, but formal definitions escape us. We will dive into some of those terms here, as well as cover some basic concepts in proof writing.\n",
    "These topics are typically covered in courses such as mathematical analysis (real, complex, functional, etc.) and abstract algebra.\n",
    "\n",
    "## Useful Terms\n",
    "### Group:\n",
    "First we need to define a binary operation:\n",
    "\n",
    "Let _G_ be a set. A Binary Operation on _G_ is a function that assigns each ordered pair of elements of _G_ an element of _G_. Addition, multiplication, subtraction, etc. are all examples of binary operations.  That is, they take two elements, do something to them, and get an element from the same set. A binary operation is a mapping $G\\cdot G\\rightarrow G$\n",
    "\n",
    "A Group is then defined as:\n",
    "\n",
    "Let _G_ be a set together with a binary operation that assigns each ordered pair (a,b) of elements of _G_ an element in _G_ denoted by _ab_. We say _G_ is a _Group_ under this operation if the following three properties are satisfied:\n",
    "1. _Associativity_ : The operation is associative; that is, $(ab)c=a(bc)$ for all _a,b,c_ in _G_.\n",
    "2. _Identity_ : There is an element _e_ (called the identity) in _G_ such that $ae=ea=a$ for all _a_ in _G_.\n",
    "3. _Inverses_ : For each element _a_ in _G_ , there is an element _b_ in _G_ (called an _inverse_ of _A_ ) such that $ab=ba=e$.\n",
    "\n",
    "Examples: Under the binary operation of addition, the set of integers, rational numbers, and real numbers are all groups.  In each case, 0 is the identity element, and the inverse of an element _a_ is simply _-a_.\n",
    "\n",
    "### Field:\n",
    "Fields form the foundational mathematical domains upon which most engineering applications rely on. Nearly all of the math learned up to this point in your education relies on centuries of work in mathematical analysis on or involving fields, including calculus and linear algebra. Formally, a _field_ is a commutative ring with unity in which every nonzero element is a unit.  This definition, however, is not very useful without a background in abstract algebra.  Broken down, a field can be defined as a set _F_ together with two binary operations (usually addition and multiplication) with the following properties:\n",
    "1. Additive Commutativity $\\forall a,b\\in F$, $a+b=b+a$\n",
    "2. Additive Associativity $\\forall a,b,c\\in F, (a+b)+c=a+(b+c)$\n",
    "3. Additive Identity $\\exists! 0\\in F$ such that $\\forall a\\in F, a+0=a$\n",
    "4. Additive Inverse $\\forall a\\in F, \\exists b\\in F$ such that $a+b=0$\n",
    "5. Multiplicative Commutativity $\\forall a,b\\in F, a\\cdot b=b\\cdot a$\n",
    "6. Multiplicative Associativity $\\forall a,b,c\\in F, a(bc)=(ab)c$\n",
    "7. Multiplicative Identity $\\exists! 1\\in F$ such that $\\forall a\\in F, a\\cdot 1=a$\n",
    "8. Multiplicative Inverse $\\forall a\\in F$ such that $a\\neq 0$, $\\exists b\\in F$ such that $a\\cdot b=1$\n",
    "9. Distributivity between operators $\\forall a,b,c\\in F, a(b+c)=ab+ac$\n",
    "\n",
    "These nine properties are known as the field axioms, from which nearly all mathematical properties that you have learned from highschool on can be derived.\n",
    "\n",
    "Common examples of fields used in engineering are the rational number, the real numbers, the complex number, and GF(2) or the binary field.  Fields range greatly in 'size' with the binary field only having two elements, to the rational numbers which are countably infinite, to the reals which are uncountable.\n",
    "\n",
    "Because the real numbers tend to come up quite a bit in engineering, we formally define them here. In addition to the nine field axioms above, the real numbers are well ordered.  For a field to contain an order structure, the following must be true:\n",
    "1. $\\forall a,b\\in F$ exactly one of the following is true\n",
    "    a. $a=b$\n",
    "    b. $a>b$\n",
    "    c. $a<b$\n",
    "2. $\\forall a,b,c\\in F$ if $a<b$ and $b<c$ then $a<c$\n",
    "3. $\\forall a,b,c\\in F$ if $a<b$, then $a+c<b+c$\n",
    "4. $\\forall a,b,c\\in F$ if $a<b$, then $ac<bc$ for all $c>0$\n",
    "\n",
    "Additionally the real numbers are Dedekind complete, which is an additional property on the order structure.  This is called a _well-ordered structure_ , which is to say:\n",
    "Given a non-empty subset $G$ of $F$, which has an upper bound IN $F$, there exists a least upper bound, which must also be in $F$.\n",
    "\n",
    "This property is what separates the rational numbers from the real numbers and is one of many equivalent definitions of the irrational numbers. Irrational numbers can be thought of as the limit of a sequence of rational numbers.  This is, in-fact, what we are doing when we write out the decimal approximation of an irrational number.  We create a sequence of powers of ten which approach the irrational number.  The combined properties above form the real numbers, or a well-ordered field.  It is important to note that for ANY two well-order fields, there exists a unique isomorphism (one to one and onto relationship) between them, and they can thus be thought of as the same set.\n",
    "\n",
    "## Proofs\n",
    "There are a number of different methods for solving mathematical proofs.  Here is are a few common methods with simple examples.\n",
    "### Direct Proof\n",
    "Perhaps the most common type of proof.  Given a statement _A Implies B_ we take A and theorems which we have at our disposal and through manipulation of A, we end up at B. Example:\n",
    "\n",
    "Prove $(-1)^{2}=1$.\n",
    "\n",
    "Proof:\n",
    "$$1+-(1)=0$$ by additive inverse properties (see Field above) implies\n",
    "$$(-1)1+(-1)(-1)=(-1)0$$ by distributive property implies\n",
    "$$(-1)1+(-1)^{2}=0$$ by definition implies\n",
    "$$-1+(-1)^{2}=0$$ by multiplicative inverse implies\n",
    "$$1+(-1)+(-1)^{2}=0+1$$\n",
    "$$0+(-1)^{2}=1$$ by additive inverse implies\n",
    "$$(-1)^{2}=1$$ thus completing our proof.\n",
    "\n",
    "### Proof by Contradiction\n",
    "\n",
    "Proof by Contradiction assumes the negation of the statement, then from there shows (often directly) that the statement cannot be true. Example:\n",
    "Prove for all real numbers $x$ and $y$, if $x\\neq y, x>0, y>0,$ then $\\frac{x}{y}+\\frac{y}{x}>2$.\n",
    "Proof:  Assume the negation.  Let $x\\neq y, x>0, y>0$ and $\\frac{x}{y}+\\frac{y}{x}\\leq 2$. Then $$x^{2}y+y^{2}<2xy$$ since $x,y>0$. Then $$x^{2}y+y{2}x-2xy=xy(x+y+2)\\leq 0$$ which is a contradiction, as all 3 terms $x,y,(x+y+2)$ are positive by assumption.  Thus the original statement is true.\n",
    "\n",
    "### Proof by Contraposition\n",
    "\n",
    "Proof by contraposition takes a statement _A implies B_ and attempts to prove the contrapositive.  The contrapositive of _A implies B_ is _Not B implies Not A_.  If _A implies B_ is true, then _Not B implies Not A_ is always true.  Think of the statement \"All humans are mammals,\" which is clearly true.  The contrapositive \"nonmammals are not humans\" is also true. Here is a mathematical example:\n",
    "Prove that if $x^{2}$ is even, then $x$ is even.\n",
    "\n",
    "Proof: The contrapositive of the above statement is:\n",
    "If $x$ is not even, then $x^{2}$ is not even.\n",
    "\n",
    "If $x$ is not even, then $x$ is odd by definition. The product of two odd numbers is odd, thus $x^{2}=x\\cdot x$ is odd. Thus $x^{2}$ is not even, proving our statement. Thus we can infer the original statement to be true.\n",
    "\n",
    "### Proof by Induction\n",
    "\n",
    "Proof by induction is useful for showing that a statement is true for any infinite set of natural numbers (note that transfinite induction exists, but is outside the scope of most engineering proofs).  The proofs involve proving a base case to be true (usually n=0 or n=1) then showing for and k≥0 if P(k) holds, then P(k+1) holds. An example:\n",
    "Prove that the sum of $n$ natural numbers is $$\\frac{n(n+1)}{2}.$$\n",
    "\n",
    "Proof: Base Case $n=0$:\n",
    "The base case clearly holds $$0=\\frac{0(0+1)}{2}=0.$$\n",
    "\n",
    "Inductive Step: Assume the statement is true for any $k\\geq 0$. We must show that the statement holds for $k+1$. From the statement $$0+1+...+k=\\frac{k(k+1)}{2}$$ it follows that $$(0+1+...+k)+(k+1)=\\frac{k(k+1)}{2}+(k+1).$$ This simplifies to $$\\frac{k(k+1)}{2}+(k+1)=\\frac{k(k+1)+2(k+1)}{2}$$\n",
    "$$=\\frac{(k+1)(k+2)}{2}$$\n",
    "$$=\\frac{(k+1)((k+1)+1)}{2}.$$\n",
    "which proves the inductive step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}