linear_algebra-1-homework.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic setup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create anaconda environment\n",
    "<br>\n",
    "```bash\n",
    "conda create -n ml python=3.7.4 jupyter\n",
    "```\n",
    "Install fastai library\n",
    "<br>\n",
    "```bash\n",
    "conda install -c pytorch -c fastai fastai\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Set theory basics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. Prove that:\n",
    "<br>\n",
    "$A \\subseteq A$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\forall x : (x \\in A \\implies x \\in A )$             Identity law\n",
    "<br>\n",
    "$A \\subseteq A$ subset definition\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. Prove that:\n",
    "<br>\n",
    "If $A \\subseteq B$ and $B \\subseteq A$ $\\to$ $A = B$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. Prove that:\n",
    "<br>\n",
    "if $B \\subset A$ then $A \\cap B = B$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$B \\subset A \\iff \\forall x: (x \\in B \\implies x \\in A)$\n",
    "<br>\n",
    "Prove by contradiction, let:\n",
    "$A \\cap B = B', B'\\neq B$\n",
    "<br>\n",
    "$B'\\neq B \\implies \\exists x: (x\\in B' \\land x \\notin B \\lor x \\in B \\land x \\notin B')$\n",
    "<br>\n",
    "$ x\\in B' \\implies x \\in A \\land x \\in B$ from intersection definition\n",
    "<br>\n",
    "Than $x\\in B' \\land x \\notin B$ is impossible\n",
    "<br>\n",
    "$x \\in B \\land x \\notin B' \\implies x \\in B \\land x \\in A \\land x \\notin B'$\n",
    "<br>\n",
    "$ \\exists x: (x \\in B \\land x \\in A \\land x \\notin A \\cap B)$ which is against intersection definition, because $B'$ would not be largest set whose elements belong both to $A$ and $B$ (it's possible to add $x$ to  $B'$)\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4. Prove that:\n",
    "<br>\n",
    "$A \\cap B = B \\cap A$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ x \\in A \\cap B \\iff x \\in A \\land x \\in B$\n",
    "<br>\n",
    "$a \\land b \\iff b \\land a$\n",
    "<br>\n",
    "$ x \\in A \\cap B \\implies x \\in B \\land x \\in A$\n",
    "<br>\n",
    "$B \\cap A \\iff { x: x \\in B \\land x \\in A }$ intersection definition\n",
    "<br>\n",
    "$x \\in B \\cap A$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5. Prove that:\n",
    "<br>\n",
    "if $B \\subset A$ then $A \\cup B = A$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prove by contradiction, let: $B \\subset A, A \\cup B = A', A' \\neq A$\n",
    "<br>\n",
    "$\\exists x: (x \\in A' \\land x \\notin A \\lor x \\in A \\land x \\notin A'$\n",
    "<br>\n",
    "check first case: $x \\in A' \\land x \\notin A$\n",
    "<br>\n",
    "$ x\\in A' \\implies x \\in A \\lor x \\in B$ from union definition\n",
    "<br>\n",
    "$x \\notin A$ from our assumption\n",
    "<br>\n",
    "$x \\in B$\n",
    "<br>\n",
    "$B \\subset A \\iff x \\in B \\implies x \\in A$ subset definition\n",
    "<br>\n",
    "$x \\in A$ against our assumption\n",
    "<br>\n",
    "check second case: $x \\in A \\land x \\notin A'$\n",
    "<br>\n",
    "$ x\\notin A' \\implies x \\notin A \\land x \\notin B$\n",
    "<br>\n",
    "$ x \\notin A$ against our assumption\n",
    "<br>\n",
    "$\\blacksquare$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6. Prove that:\n",
    "<br>\n",
    "$A \\cup B = B \\cup A$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ x \\in A \\cup B \\iff x \\in A \\lor  x \\in B$\n",
    "<br>\n",
    "$a \\lor b \\iff b \\lor a$\n",
    "<br>\n",
    "$ x \\in A \\cup B \\implies x \\in B \\lor x \\in A$\n",
    "<br>\n",
    "$B \\cap A \\iff { x: x \\in B \\lor x \\in A }$ union definition\n",
    "<br>\n",
    "$x \\in B \\cup A$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7 Prove that:\n",
    "- 7.1.1, 7.1.2 for every injection $m:A \\to B$ and pair of functions $f, g :C \\to A$: if $m \\circ f = m \\circ g$ then $f = g$ and vice-versa\n",
    "- 7.2.1, 7.2.2 for every surjection $e:A \\to B$ and every pair of functions $f, g :B \\to C$: if $f \\circ e = g \\circ e$ then $f = g$ and vice-versa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7.1.1 Prove by contradiction, let $f \\neq g$<br>\n",
    "\n",
    "$\\exists (c,a, a'): c \\in C, a \\in A, f(c) = a, g(c) = a', a \\neq a'$\n",
    "<br>\n",
    "$m \\circ f = m \\circ g$\n",
    "<br>\n",
    "$m(a) = m(a')$\n",
    "<br>\n",
    "$a = a'$ from injection definition, which is against our assumption\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7.1.2 დავამტკიცოთ საწინააღმდეგოდან, დავუშვათ $m \\circ f \\neq m \\circ g$:\n",
    "<br>\n",
    "$\\exists (c,a, a', b, b'): c \\in C, a \\in A, f(c) = a, g(c) = a', m(a)=b, m(a')=b', b \\neq b'$\n",
    "<br>\n",
    "$f=g \\implies f(c) = g(c)$\n",
    "<br>\n",
    "$a = a' \\implies m(a)=m(a')$ mapping-ის განსაზღვრებიდან გამომდინარე\n",
    "<br>\n",
    "$b=b'$ რაც ეწინააღმდეგება ჩვენს დაშვებას\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7.2.1 დავამტკიცოთ საწინააღეგოდან, დავუშვათ $f \\neq g$<br>\n",
    "\n",
    "$\\exists (a,b,c,c'): a \\in A, b \\in B, c \\in C, e(a)=b, f(b) = c, g(b) = c', c \\neq c'$\n",
    "<br>\n",
    "$f \\circ e = g \\circ e$\n",
    "<br>\n",
    "$f(e(a)) = g(e(a))$\n",
    "<br>\n",
    "$f(b) = g(b)$\n",
    "<br>\n",
    "$c = c'$ რაც ეწინააღმდეგება ჩვენს დაშვებას\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7.2.2 დავამტკიცოთ საწინააღეგოდან, დავუშვათ $f \\circ e \\neq g \\circ e$<br>\n",
    "\n",
    "$\\exists (a,b,c,c'): a \\in A, b \\in B, c \\in C, e(a)=b, f(b) = c, g(b) = c', c \\neq c'$\n",
    "<br>\n",
    "$f = g \\implies f(b) = g(b)$ mapping-ის განსაზღვრებიდან გამომდინარე\n",
    "<br>\n",
    "$c = c'$ რაც ეწინააღმდეგება ჩვენს დაშვებას\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8 Prove that \n",
    "- 8.1 composition of injections is injection itself\n",
    "- 8.2 composition of surjections is surjection itself\n",
    "- 8.3 composition of bijections is bijection itself\n",
    "<br>\n",
    "or give a counterexamples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8.1 let $f, g$ be surjections\n",
    "<br>\n",
    "$f \\circ g(a) = f \\circ g(b)$\n",
    "<br>\n",
    "$f(g(a)) = f(g(b))$\n",
    "<br>\n",
    "$g(a) = g(b)$ because f is injection\n",
    "<br>\n",
    "$a = b$ because g is injection\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8.2 let $f : A \\to B, g: B \\to C$ be surjections\n",
    "<br>\n",
    "$\\exists c \\in C: \\exists b \\in B: g(b) = c$ surjection definition\n",
    "<br>\n",
    "$\\exists a \\in A: f(a) = b$ surjection definition\n",
    "<br>\n",
    "$g \\circ f(a) = g(f(a)) = g(b) = c$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "let f and g be bijections. From bijection definition f and g are also injections and surjections. Because injection composition is injection and surjection composition is surjection $f\\circ g$ is injjection and surjection simultaneously, which means it is bijection\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 9 Prove that for each set $A$:\n",
    "- 9.1 $A \\cong A$\n",
    "- 9.2 if $B \\cong A$ then $B \\cong A$ for every pair of sets $A$ and $B$\n",
    "- 9.3 if $A \\cong B$ and $B \\cong C$ then $A \\cong C$ for every triplet $A$, $B$ and $C$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9.1 \n",
    "$I_S: A \\to A$ არის ბიექცია (Identity mapping), რადგან ბიექცია არსებობს შესაბამისად:\n",
    "<br>\n",
    "$A \\cong A$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9.2 \n",
    "$A \\cong B \\implies \\exists \\phi : A \\to B$ სადაც $\\phi$ ბიექციაა, ესეიგი:\n",
    "<br>\n",
    "$ \\exists \\phi^{-1}: B \\to A$ \n",
    "<br>ბიექციის თვისებიდან გამომდინარე: inverse bijections is bijection itself\n",
    "<br>\n",
    "$B \\cong A$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9.3 $A \\cong B$ and $B \\cong C$\n",
    "<br>\n",
    "$\\exists \\phi_1: A \\to B \\land \\exists \\phi_2: B \\to C$ სადაც $\\phi_1, \\phi_2$ ბიექციებია\n",
    "<br>\n",
    "$\\phi_1 \\circ \\phi_2 : A \\to C$\n",
    "<br>\n",
    "$\\phi_1 \\circ \\phi_2$ ბიექციაა, რადგან ბიექციების კომპოზიცია ასევე ბიექციაა\n",
    "<br>\n",
    "$A \\cong C$ ეკვივალენტურობის განსაზღრებიდან გამომდინარე (არსებობს ბიექცია A-ს და C-ს შორის)\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 10 Prove that:\n",
    "<br>\n",
    "there exists a bijection between set of natural and even numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 11 Prove that:\n",
    "<br>\n",
    "if we have a bijection between two finite sets than they have an equal number of elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 12 Prove that:\n",
    "<br>\n",
    "$A \\times B \\cong B \\times A$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$f: A \\times B \\to B \\times A, f: (a, b) \\mapsto (b, a)$\n",
    "<br>\n",
    "f ბიექციაა\n",
    "<br>\n",
    "$A \\times B \\cong B \\times A$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "14. $\\cap_{i\\in I}A_i$ and $\\cup_{i\\in I}A_i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1}\n",
      "{1, 2, 3}\n"
     ]
    }
   ],
   "source": [
    "# Inplement in python\n",
    "def intersect_many(set1, *sets):\n",
    "    result = set1.intersection(*sets)\n",
    "    return result\n",
    "\n",
    "def union_many(set1, *sets):\n",
    "    result = set1.union(*sets)\n",
    "    return result\n",
    "print(intersect_many({1, 2, 3}, {1, 3}, {1, 2}))\n",
    "print(union_many({1, 2, 3}, {1, 3}, {1, 2}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "15 We can also define cartesian product of any \"number\" of sets $\\prod_{i \\in I}{A_i}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 4, 8),\n",
       " (1, 4, 7),\n",
       " (1, 5, 8),\n",
       " (1, 5, 7),\n",
       " (1, 6, 8),\n",
       " (1, 6, 7),\n",
       " (2, 4, 8),\n",
       " (2, 4, 7),\n",
       " (2, 5, 8),\n",
       " (2, 5, 7),\n",
       " (2, 6, 8),\n",
       " (2, 6, 7),\n",
       " (3, 4, 8),\n",
       " (3, 4, 7),\n",
       " (3, 5, 8),\n",
       " (3, 5, 7),\n",
       " (3, 6, 8),\n",
       " (3, 6, 7)]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Inplement in python\n",
    "from itertools import product\n",
    "\n",
    "list(product({1, 2, 3}, {4, 5, 6}, {7, 8}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 16 Prove that:\n",
    "<br>\n",
    "16.1 $$A \\cap (B \\cup C)=(A \\cap B) \\cup (A\\cap C)$$\n",
    "16.2 $$A \\cup (B \\cap C)=(A \\cup B) \\cap (A\\cup C)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "16.1\n",
    "<br>\n",
    "$x\\in A \\cap (B \\cup C) \\implies x \\in A \\land x \\in (B \\cup C) $\n",
    "<br>\n",
    "$x \\in (B \\cup C) \\implies x \\in B \\lor x \\in C$\n",
    "<br>\n",
    "$x\\in A \\cap (B \\cup C) \\implies x \\in A \\land (x \\in B \\lor x \\in C)$\n",
    "<br>\n",
    "$x\\in A \\cap (B \\cup C) \\implies x \\in A \\land x \\in B \\lor x \\in A \\land x \\in C $\n",
    "<br>\n",
    "<br>\n",
    "$x \\in (A \\cap B) \\cup (A\\cap C) \\implies x \\in (A \\cap B) \\lor x \\in (A \\cap C)$\n",
    "<br>\n",
    "$x \\in (A \\cap B) \\implies x \\in A \\land x \\in B$\n",
    "<br>\n",
    "$x \\in (A \\cap C)\\implies x \\in A \\land x \\in C$\n",
    "<br>\n",
    "$x \\in (A \\cap B) \\cup (A\\cap C) \\implies x \\in A \\land x \\in B \\lor x \\in A \\land x \\in C$\n",
    "<br>\n",
    "\n",
    "$A \\cap (B \\cup C)=(A \\cap B) \\cup (A\\cap C)$\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "16.2\n",
    "<br>\n",
    "$ x \\in A \\cup (B \\cap C) \\implies x \\in A \\lor x \\in (B \\cap C)$\n",
    "<br>\n",
    "$x \\in x \\in (B \\cap C) \\implies x \\in B \\land x \\in C$\n",
    "<br>\n",
    "$x \\in A \\cup (B \\cap C) \\implies  x \\in A \\lor x \\in B \\land x \\in C$\n",
    "<br>\n",
    "<br>\n",
    "$x \\in (A \\cup B) \\cap (A\\cup C) \\implies x \\in (A \\cup B) \\land x \\in (A \\cup C)$\n",
    "<br>\n",
    "$x \\in (A \\cup B) \\implies x \\in A \\lor x \\in B$\n",
    "<br>\n",
    "$x \\in (A \\cup C) \\implies x \\in A \\lor x \\in C$\n",
    "<br>\n",
    "$x \\in (A \\cup B) \\cap (A\\cup C) \\implies (x \\in A \\lor x \\in B) \\land (x \\in A \\lor x \\in C)$\n",
    "<br>\n",
    "$(x \\in A \\lor x \\in B) \\land (x \\in A \\lor x \\in C) = x \\in A \\land x \\in A \\lor x \\in A \\land x \\in C \\lor x \\in B \\land x \\in A \\lor x \\in B \\land x \\in C = $\n",
    "<br>\n",
    "$ = x \\in A \\lor x \\in A \\land x \\in C \\lor x \\in B \\land x \\in A \\lor x \\in B \\land x \\in C = $\n",
    "<br>\n",
    "$ x\\in A \\land(1 \\lor x \\in C \\lor x \\in B) \\lor x \\in B \\land x \\in C = $\n",
    "<br>\n",
    "$ x \\in A \\lor x \\in B \\land x \\in C$\n",
    "<br>\n",
    "$x \\in (A \\cup B) \\cap (A\\cup C) \\implies x \\in A \\lor x \\in B \\land x \\in C $\n",
    "<br>\n",
    "$ A \\cup (B \\cap C) = (A \\cup B) \\cap (A\\cup C) $\n",
    "<br>\n",
    "$\\blacksquare$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Algebra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 17 Prove that:\n",
    "<br>\n",
    "$(AB)^{T} = B^{T}A^{T}$ for each pair of matrices $A, B \\in \\mathbb{R}^{n \\times m}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$(ab)^{T}_{k,i} = ab_{i,k} = \\sum\\limits_{j=1}^na_{ij}b_{jk}$\n",
    "<br>\n",
    "$(b^{T}a^{T})_{ki} = \\sum\\limits_{j=1}^nb^{T}_{kj}a^{T}_ji$\n",
    "<br>\n",
    "$(b^{T}a^{T})_{ki} = \\sum\\limits_{j=1}^nb_{jk}a_{ij} = \\sum\\limits_{j=1}^na_{ij}b_{jk}$\n",
    "<br>\n",
    "$(ab)^{T}_{k,i} = (b^{T}a^{T})_{ki}$\n",
    "<br>\n",
    "$\\blacksquare$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions on tensors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Write combination for $XOR$ calculation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "\n",
    "bias = 1\n",
    "WA = np.array([20, 20, -30])\n",
    "WO = np.array([20, 20, -10])\n",
    "WNA = np.array([-10, -10, 15])\n",
    "\n",
    "s = lambda x: 1 / (1 + math.exp(-x))\n",
    "sig = np.vectorize(lambda x: 1 / (1 + math.exp(-x)))\n",
    "\n",
    "act = lambda X, W: np.around(sig(np.dot(W, X)), decimals=1)\n",
    "XI = [[0, 0, bias], [0, 1, bias], [1, 0, bias], [1, 1, bias]]\n",
    "\n",
    "def _XOR(XI, WA, WNA, WO):\n",
    "    t1 = act(XI, WNA)\n",
    "    t2 = act(XI, WO)\n",
    "    T = [t1, t2, bias]\n",
    "    # print(T)\n",
    "    result = act(T, WA)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 1] 0.0\n",
      "[0, 1, 1] 1.0\n",
      "[1, 0, 1] 1.0\n",
      "[1, 1, 1] 0.0\n"
     ]
    }
   ],
   "source": [
    "for bi in XI:\n",
    "    print(bi, _XOR(bi, WA, WNA, WO))"
   ]
  },
  {
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}