Midterm_Review.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4334f52c-5b89-450c-8af9-307c4fcd116f",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "# Quick Notes on Sets\n",
    "---\n",
    "1. Template for proving two sets are equal\n",
    "- Let A and B be the sets. To show that A = B, we have the following template:\n",
    "- Suppose $x \\in A$, therefore $x \\in B$.\n",
    "- Suppose $x \\in B$, therefore $x \\in A$.\n",
    "- Therefore, $A=B$.\n",
    "  \n",
    "2. Template for proving Subsets\n",
    "- Let $x$ be anything and let A be a set, then $x \\in A \\iff \\{x\\} \\subseteq A$.\n",
    "-  Proving one set is a subset of another:\n",
    "         To show $A \\subseteq B:$\n",
    "              Let $x \\in A$ threfore $x \\in B$, therefore $A \\subseteq B$.\n",
    "\n",
    "3. Do note that in some books set symmetric is denoted as $\\textbackslash$ in some books its $\\triangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a03f3d0-f649-46ce-8d8c-879b2ec4b764",
   "metadata": {},
   "source": [
    "# Sample Problems on Sets:\n",
    "---\n",
    "- For each of the folowing statements about sets A, B, C either prove the statement is true or give a counterexample to show that it is false:\n",
    "    1. If $A \\subseteq B$, and $B \\subseteq C$, then $A \\subseteq C$.\n",
    "    2. If $A \\in B$, and $B \\subseteq C$, then $A \\subseteq C$.\n",
    "    3. If $A \\in B$, and $B \\subseteq C$, then $A \\in C$.\n",
    "    4. If $A \\in B$, and $B \\in C$, then $A \\in C$.\n",
    "\n",
    "- Let A and B be sets, Prove that of $A = B \\iff A\\subseteq$ and $B \\subseteq A$.\n",
    "- Let A, B, and C be sets and suppose $A \\subseteq B, B \\subseteq C$ and $C \\subseteq A$. Prove that $A=C$.\n",
    "- Let a and b be integers and let $A = \\{x \\in \\mathbb{Z}:a|x\\}$ and $B = \\{x \\in \\mathbb{Z}:b|x\\}$, prove that $A \\subseteq B$.\n",
    "- If A and B are sets. Explain why $A \\cap B$ and $A \\textbackslash B$ are disjoint.\n",
    "- Is a Venn diagram illustration a proof?\n",
    "- Suppose A, B, and C are sets with $A \\cap B \\cap = \\emptyset$. Prove or disprove $|A \\cup B \\cup C| = |A| + |B| + |C|$.\n",
    "- Suppose A and B are sets. Prove or disprove $A \\cup B = A \\cap B \\iff A=B$.\n",
    "- Suppose A and B are sets. Prove or disprove $|A \\triangle B| = |A|+|B|-|A \\cap B|$.\n",
    "- Suppose A and B are sets. Prove or disprove $|A \\triangle B| = |A-B| + |B-A|$.\n",
    "- Suppose that A be a set. Prove that $A - \\emptyset = A$ and $\\emptyset - A = \\emptyset$.\n",
    "- Suppose that A be a set. Prove that $A \\triangle \\emptyset = A$ and $A \\triangle A = \\emptyset$.\n",
    "- Prove that $A \\subseteq B \\iff A-B = \\emptyset$.\n",
    "- Let A and B be nonempty sets. Prove that AxB = BxA $\\iff A=B$. Why do we need the condition that A and B are nonempty?.\n",
    "- Prove the following set complement. Here the letters A, B, and C denote subsets of a universal set $\\mathbb{U}$.\n",
    "  1. $A = B \\iff A^c = B^c$.\n",
    "  2. $(A^c)^c = A$\n",
    "  3. $(A \\cup B \\cup C)^c = A^c \\cap B^c \\cap C^c$.\n",
    "- Let A, B, abd C be sets, prove that: $|A \\cup B \\cup C| = |A|+|B|+|C|-|A \\cap B| - |A \\cap C| - |B \\cap C| + |A \\cap B \\cap C|$\n",
    "- Prove that set symmetric difference is commutative.\n",
    "- Prove that set symmetric difference is an associative operation.\n",
    "- Let A, B and C be sets, prove the following:\n",
    "  1. $A \\times (B \\cup C) =(A \\times B) \\cup (A \\times C)$\n",
    "  2. $A \\times (B \\cap C) =(A \\times B) \\cap (A \\times C)$\n",
    "  3. $A \\times (B - C) =(A \\times B) - (A \\times C)$\n",
    "  4. $A \\times (B \\triangle C) =(A \\times B) \\triangle (A \\times C)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "415493d4-e9d1-4e39-92b0-fa959adced2e",
   "metadata": {},
   "source": [
    "# Quick Notes on Relations\n",
    "---\n",
    "- If $\\forall x \\in A| (x,x) \\in A \\times A$ and $(x,x) \\in \\textbf{R}| x \\textbf{R} x$ then $\\textbf{R}$ is reflexive.\n",
    "- If $\\forall x \\in A| (x,x) \\in A \\times A$ but $(x,x) \\notin \\textbf{R}| x \\cancel{\\textbf{R}} x$ then $\\textbf{R}$ is irreflexive.\n",
    "- If $\\forall x,y \\in A| (x,y) \\wedge (y,x) \\in A \\times A$ and $(x,y) \\wedge (y,x) \\in \\textbf{R}| x \\textbf{R} y, y\\textbf{R}x$ then $\\textbf{R}$ is symmetric.\n",
    "- If $\\forall x,y \\in A| (x,y) \\wedge (y,x) \\in A \\times A$ and $(x,y) \\wedge (y,x) \\in \\textbf{R}| x \\textbf{R} y, y\\textbf{R}x$ but $x = y$ then $\\textbf{R}$ is anti-symmetric.\n",
    "- If $x\\textbf{R}y \\wedge y\\textbf{R}z \\wedge x\\textbf{R}z$ then $\\textbf{R}$ is transitive."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac2501c1-14bb-40a6-ae0b-05ddd76a6708",
   "metadata": {},
   "source": [
    "# Sample Problems on Relations\n",
    "---\n",
    "1. Prove that the equality relation on the set of integers is antisymmetric.\n",
    "2. Suppose that R and S are relations and $R=S^{-1}$. Prove that $S = R^{-1}$.\n",
    "3. Let R be a relation on set A. Prove or disprove that if R is anti-symmetric, then R is also irreflexive.\n",
    "4. Prove that a relation is symmetric if and inly if $R=R^{-1}$.\n",
    "5. Prove that a relation on set A is antisymmetric if and only id $R \\cap R^{-1} \\subseteq \\{(a,a:a \\in A)\\}$\n",
    "6. What is wrong with the following proof:\n",
    "   - Statement: \"If R is symmetric and transitive, then R is reflexive\".\n",
    "   - Proof: \"Suppose R is symmetric and transitive. Symmetric means $xRy$ implies $yRx$. We apply transitivity to $xRy$ and $yRx$ to give xRx. Therefore R is reflexive.\"\n",
    "7. Let R be an equivalence relations on a set A. Prove that the union of all of the R's equivalence class is A, that is $\\mathbb{\\cup}_{a\\in A}[a]=A$.\n",
    "8. Suppose R is an equivalence relation on a set A and suppose $a,b \\in A$. Prove that $a \\in [b] \\iff b \\in [a]$.\n",
    "9. Let R and S be an equivalence relation on a set, A. Prove that $R=S$ if and only if the equivalence classes of R are the same as the equivalence classes of S.\n",
    "10. Let A be a set, and let P be a partition, is it possible to have $A=P$?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec4f2d6b-21c1-4191-b1a3-c562e6b181bc",
   "metadata": {},
   "source": [
    "# Quick Notes on Functions\n",
    "---\n",
    "1. Template to prove two functions are equal:\n",
    "   - If you are given a problem which reads like \"Let f and g be functions, prove that f=g\". do the following:\n",
    "       - Prove that the domain of f = domain of g.\n",
    "       - Prove that $\\forall x$ in their common domain, $f(x) = g(x)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19a9f6e4-de2b-44e4-bf32-930e7f754014",
   "metadata": {},
   "source": [
    "# Sample Problems on Functions\n",
    "---\n",
    "- Consider a function $f:A \\to B$.\n",
    "  1. How do you prove that $f$ is not one-to-one?\n",
    "  2. How do you prove that $f$ is not onto?\n",
    " \n",
    "- Let $a,b \\in \\mathbb{R}$ and consider the function $f:\\mathbb{R}\\to\\mathbb{R}$ defined by $f(x)=ax+b$:\n",
    "  1. For which values of a and b is $f$ one-to-one?\n",
    "  2. For which values of a and b is $f$ onto?\n",
    " \n",
    "- Let $a,b,c \\in \\mathbb{R}$ and consider the function $f:\\mathbb{R}\\to\\mathbb{R}$ defined by $f(x)=ax^2+bx+c$:\n",
    "  1. For which values of a and b is $f$ one-to-one?\n",
    "  2. For which values of a and b is $f$ onto?\n",
    " \n",
    "- Consider the following sentences about a function, $f$:\n",
    "  1. $f$ is onto.\n",
    "  2. $f: A \\to B$ is onto.\n",
    "  Explain why the $1^{st}$ sentence does not make sense, while the $2^{nd}$ sentence does.\n",
    "\n",
    "- Let $A$ and $B$ be finite sets, and let $f: A \\to B$. Prove that any of the following statements being true implies the third:\n",
    "  1. $f$ is one-to-one.\n",
    "  2. $f$ is onto.\n",
    "  3. Cardinality of A is the same as cardinality of B.\n",
    " \n",
    "- Suppose that $f: A \\to B$ is a bijection. Prove that $f^{-1}: B \\to A$ is a bijection as well.\n",
    "\n",
    "- Suppose $A, B, C$ are sets and $f: A \\to B$ and $f:B \\to A$:\n",
    "  1. Prove that if $f$ and $g$ is one-to-one, then $f \\circ g$ is also one-to-one.\n",
    "  2. Prove that if $f$ and $g$ is onto then $f \\circ g$ is also onto.\n",
    "  3. Prove that if $f$ and $g$ is bijective, then $f \\circ g$ is also bijective.\n",
    " \n",
    "- Let A be a set and $f$ be a function with $f:A \\to A$:\n",
    "  1. Suppose $f$ is one-to-one, must $f$ be also onto?\n",
    "  2. SUppose that $f$ is onto, must $f$ be also one-to-one?\n",
    " \n",
    "- Suppose that $f: A \\to A$ and $g: A \\to A$ are both bijections:\n",
    "  1. Prove or disprove that if $g \\circ f$ is a bijection from A to itself.\n",
    "  2. Prove or disprove that if $(g \\circ f)^{-1}$ = $g^{-1} \\circ f^{-1}$\n",
    "  3. Prove or disprove that $(g \\circ f)^{-1}$ = $f^{-1} \\circ g^{-1}$\n",
    " \n",
    "- If $f$ is invertible, must it be that $(f^{-1})^n = (f^n)^{-1}$? Prove or disprove."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}