proof_strategies.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "proof-strategies",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/jgtiu/real-analysis-notes/blob/master/proof_strategies.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_pSz0gUzaF71",
        "colab_type": "text"
      },
      "source": [
        "**Read this notebook in colab! The TeX doesn't render correctly on GitHub.**\n",
        "\n",
        "# Proof strategies"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZJTbpsgToXmO",
        "colab_type": "text"
      },
      "source": [
        "## Intro and terminology\n",
        "In proving, a big part of the job is piecing together facts to logically show that a first statement implies a second one.\n",
        "\n",
        "**Theorems** are assertions that we prove; they're not self-evident but can be shown to be true by a chain of reasoning.\n",
        "\n",
        "Here are some common proof tasks and the strategies you can use to tackle them."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-0vBfym6-Z-c",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Tip: Always use definitions.\n",
        "\n",
        "Explanation: Definitions are the building blocks of proofs. Unlike a theorem, you take a definition as fact and don't have to prove it. Use them liberally and the task of proving becomes a lot easier.\n",
        "\n",
        "___\n",
        "Example: Prove that a square is a rectangle.\n",
        "\n",
        "Proof: A rectangle is a quadrilateral with four right angles. A square, by definition, satisfies these conditions, so a square is a rectangle."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qlhgT5hF8Tho",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that a statement is false.\n",
        "\n",
        "Strategy: Use counterexamples.\n",
        "\n",
        "Explanation: As a rule, you can't use an example to prove a general statement true, but you can use a counterexample to prove a statement false.\n",
        "\n",
        "___\n",
        "Example: Let $f(x) := x^2$ for $x \\in \\mathbb{R}$, and let $E := \\{x \\in \\mathbb{R}: -1 \\leq x \\leq 0\\}$ and $F := \\{x \\in \\mathbb{R}: 0 \\leq x \\leq 1\\}$. Show that it is _not_ true that $f(E \\backslash F) \\subseteq f(E) \\backslash f(F)$.\n",
        "\n",
        "Approach: For this example, you only need to find one element in $f(E \\backslash F)$ that is not in $f(E) \\backslash f(F)$. Once you find that element, you can already say that $f(E \\backslash F) \\nsubseteq f(E) \\backslash f(F)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0RugMngXg_f1",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "Full solution:\n",
        "\n",
        "$$\\begin{equation}\n",
        "\\begin{split}\n",
        "f(E \\backslash F) & = f(\\{x \\in \\mathbb{R}: -1 \\leq x \\leq 0\\} \\backslash \\{x \\in \\mathbb{R}: 0 \\leq x \\leq 1\\}) \\\\\n",
        " & = f(\\{x \\in \\mathbb{R}: -1 \\leq x < 0\\}) \\\\\n",
        " & = \\{f(x) \\in \\mathbb{R}: -1 \\leq x < 0\\} \\\\\n",
        " & = \\{y \\in \\mathbb{R}: 0 < y \\leq 1\\} \\\\\n",
        " & = (0, 1]\n",
        "\\end{split}\n",
        "\\end{equation}$$\n",
        "\n",
        "$$\\begin{equation}\n",
        "\\begin{split}\n",
        "f(E) \\backslash f(F) & = f(\\{x \\in \\mathbb{R}: -1 \\leq x \\leq 0\\}) \\backslash f(\\{x \\in \\mathbb{R}: 0 \\leq x \\leq 1\\}) \\\\\n",
        " & = \\{f(x) \\in \\mathbb{R}: -1 \\leq x \\leq 0\\} \\backslash \\{f(x) \\in \\mathbb(R): 0 \\leq x \\leq 1\\} \\\\\n",
        " & = \\{y \\in \\mathbb{R}: 0 \\leq y \\leq 1\\} \\backslash \\{y \\in \\mathbb{R}: 0 \\leq y \\leq 1\\} \\\\\n",
        " & = \\emptyset\n",
        "\\end{split}\n",
        "\\end{equation}$$\n",
        "\n",
        "$1 \\in f(E \\backslash F)$ but $1 \\notin f(E) \\backslash f(F)$. \\\\\n",
        "Therefore $f(E \\backslash F) \\nsubseteq f(E) \\backslash f(F)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3vl2FTCq8R_c",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that $P \\implies Q$. (if-then statements)\n",
        "\n",
        "💁<font color=\"red\"> **IMPORTANT!** </font> This is probably the most general kind of proof task you'll encounter and there are multiple ways to attack it. Be familiar with the three strategies below; they'll come in very handy later on.\n",
        "\n",
        "Note: $P \\implies Q$ is shorthand for \"if $P$, then $Q$.\"\n",
        "\n",
        "- Strategy 1 (Direct Proof): Use already-established axioms or theorems to prove directly from $P$ to $Q$.\n",
        "\n",
        "- Strategy 2 (Proof by Contradiction): Assume $P$ and $\\lnot Q$ (not $Q$) are true, then demonstrate a contradiction.\n",
        "\n",
        "- Strategy 3 (Proof by Contrapositive): A contrapositive is of the form $\\lnot Q \\implies \\lnot P$ (not $Q$ implies not $P$) and is exactly the same as saying $P \\implies Q$.\n",
        "\n",
        "Gotchas: Lots of people make the mistake of thinking proving $Q \\implies P$ proves $P \\implies Q$. Be careful that you don't fall into this circular argument.\n",
        "\n",
        "___\n",
        "Example: If $a$ and $b$ are consecutive integers, then the sum $a + b$ is odd."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kWiYkugzvdBk",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "Proof (Direct): Assume that $a$ and $b$ are consecutive integers. \\\\\n",
        "Because $a$ and $b$ are consecutive, $b = a + 1$. \\\\\n",
        "So $a + b$ may be re-written as $2a + 1$. \\\\\n",
        "So there exists a number $k$ such that $a + b = 2k + 1$ so $a + b$ is odd.\n",
        "\n",
        "___\n",
        "Proof (Contradiction): Assume that $a$ and $b$ are consecutive integers. \\\\\n",
        "Assume also that $a + b$ is not odd. \\\\\n",
        "Because $a + b$ is not odd, there exists no number $k$ such that $a + b = 2k + 1$. \\\\\n",
        "But! $a$ and $b$ are consecutive, so we may write $a + b$  as $2a + 1$. \\\\\n",
        "This is a contradiction. \\\\\n",
        "So $a + b$ must be odd.\n",
        "\n",
        "___\n",
        "Proof (Contrapositive): Assume that $a + b$ is not odd. \\\\\n",
        "Then there exists no integer $k$ such that $a + b= 2k + 1$. \\\\\n",
        "So $a + b \\neq k + (k + 1)$ for all integers $k$. \\\\ \n",
        "Because $k$ and $k + 1$ are consecutive $a$ and $b$ cannot be consecutive integers.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WLr88NPAIJd3",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that $P \\iff Q$ (if and only if statements)\n",
        "\n",
        "Strategy: There are two parts to this strategy. First show that $P \\implies Q$, then show that $Q \\implies P$. You can use contradictions and contrapositives here as well."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KDd4ILwI-7dH",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that $A \\subseteq B$.\n",
        "\n",
        "Strategy: This is actually a special case of \"if-then\". Why? You can rephrase $A \\subseteq B$ as \"If an arbitrary $a$ is in $A$, then $a$ is also in $B$\". Take an arbitrary element of $A$, say $a$, and prove that $a$ is also an lement of $B$. Once you've proven that, then you can assert that $A \\subseteq B$ because $a$ is arbitrary.\n",
        "\n",
        "___\n",
        "Example: Let $A$, $B$, and $C$ be sets. Prove that $A \\backslash (B \\cup C) \\subseteq (A\\backslash B) \\cap (A \\backslash C)$.\n",
        "\n",
        "Approach: Let $a$ be an element of $A \\backslash (B \\cup C)$ and show that it is an element of $(A\\backslash B) \\cap (A \\backslash C)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H81TW-ejOMZ7",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "Proof: Let $a \\in A \\backslash (B \\cup C)$. \\\\\n",
        "We know that $A \\backslash (B \\cup C) = \\{x: x \\in A, x\\notin B, x \\notin C\\}$. \\\\\n",
        "So $a \\in A$, $a \\notin B$, and $a \\notin C$. \\\\\n",
        "Is $a \\in A \\backslash B$? Yes, since $a \\in A$, $a \\notin B$. \\\\\n",
        "Is $a \\in A \\backslash C$? Yes, since $a \\in A$, $a \\notin C$. \\\\\n",
        "Since $a \\in A \\backslash B$ and $a \\in A \\backslash C$, $a \\in (A\\backslash B) \\cap (A \\backslash C)$. \\\\\n",
        "Since $a$ is arbitrary, we conclude that $A \\backslash (B \\cup C) \\subseteq (A\\backslash B) \\cap (A \\backslash C)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3JC5qaZR8JhL",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that two sets $A$ and $B$ are equal.\n",
        "\n",
        "Strategy: Show that $A \\subseteq B$ and $B \\subseteq A$.\n",
        "\n",
        "___\n",
        "Example: Let $A$, $B$, and $C$ be sets. Prove that $A \\backslash (B \\cup C) = (A\\backslash B) \\cap (A \\backslash C)$.\n",
        "\n",
        "Approach: We've already proven in the above example that $A \\backslash (B \\cup C) \\subseteq (A\\backslash B) \\cap (A \\backslash C)$. Now we just need to prove the reverse direction, i.e., $A \\backslash (B \\cup C) \\supseteq (A\\backslash B) \\cap (A \\backslash C)$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tZfqq4R1RaG1",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "Proof: We've already proven that $A \\backslash (B \\cup C) \\subseteq (A\\backslash B) \\cap (A \\backslash C)$. \\\\\n",
        "Let $a \\in (A\\backslash B) \\cap (A \\backslash C)$. \\\\\n",
        "We know that $A \\backslash B = \\{x: x \\in A, x\\notin B\\}$ and $A \\backslash C = \\{x: x \\in A, x\\notin C\\}$. \\\\\n",
        "So $(A\\backslash B) \\cap (A \\backslash C) = \\{x: x \\in A, x \\notin B, x \\notin C\\}$. \\\\\n",
        "So $a \\in A$, $a \\notin B$, and $a \\notin C$. \\\\\n",
        "Is $a \\in B \\cup C$? No, since $a \\notin B$, $a \\notin C$. \\\\\n",
        "Since $a \\in A $ and $a \\notin B \\cup C$, $a \\in A\\backslash (B \\cup C)$. \\\\\n",
        "Since $a$ is arbitrary, we conclude that $(A\\backslash B) \\cap (A \\backslash C) \\subseteq A \\backslash (B \\cup C)$. \\\\\n",
        "We conclude that $A \\backslash (B \\cup C) = (A\\backslash B) \\cap (A \\backslash C)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3VW0vH26F-fi",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that a function is injective.\n",
        "\n",
        "Strategy 1: Show that for the function $f: A \\to B$, for all $x_1, x_2 \\in A$ if $x_1 \\neq x_2$, then $f(x_1) \\neq f(x_2)$.\n",
        "\n",
        "Strategy 2: You can also use the contrapositive for this, and instead prove that if $f(x_1) = f(x_2)$, then $x_1 = x_2$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Tc-2kp9sG47c",
        "colab_type": "text"
      },
      "source": [
        "___\n",
        "## Task: Prove that a function is surjective.\n",
        "\n",
        "Strategy: Show that for the function $f: A \\to B$, for all $b \\in B$, there exists at least one $x \\in A$ such that $f(x) = b$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1FTT61Y8h9JG",
        "colab_type": "text"
      },
      "source": [
        "# Last notes\n",
        "\n",
        "Proving is a lot about connecting little ideas together so that your claims are airtight and loophole-free.\n",
        "\n",
        "But as you learn real analysis (or other proof-heavy math subjects 😉), you'll notice that some blocks of proof (like code blocks) are so often used that it would be tedious to write them out for every single proof you need to make (Like do you always need to show that the sum of two integers is odd whenever you make that assertion in a proof? Nah.).\n",
        "\n",
        "Normally those blocks of proof would be packaged into \"little\" theorems which you can then use to prove \"bigger\" theorems.\n",
        "\n",
        "What you're learning now is convincing youself of those little connections so that you can use them to build much larger ones later.\n",
        "\n",
        "And once you've gotten the hang of using the strategies here, making those connections will be a _lot_ easier.\n",
        "\n",
        "Good luck and have fun!"
      ]
    }
  ]
}