lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

sets.html (3607B)

      1 <html>
      2 <head>
      3     <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.15.6/highlight.min.js"></script>
      4     <script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
      5     <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.15.6/styles/default.min.css">
      6     <link rel="Stylesheet" type="text/css" href="style.css" />
      7     <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
      8     <script>
      9       document.addEventListener('DOMContentLoaded', function() {
     10         document.querySelectorAll('pre.code').forEach(function(item) {
     11           hljs.highlightBlock(item)
     12         })
     13       });
     14     </script>
     15     <title>sets</title>
     16 </head>
     17 <body>
     18 <style type="text/css">
     19 nav a {
     20     text-align: left;
     21 }
     22 nav #name {
     23     text-align: right;
     24     float: right;
     25     font-style: italic;
     26 }
     27 </style>
     28     <nav>
     29     <a href="index.html">Index</a>
     30     <span id="name">Alex Balgavy</span>
     31     </nav>
     32     <hr>
     33     <div class="content">
     34     
     35 <div id="Sets"><h2 id="Sets" class="header"><a href="#Sets">Sets</a></h2></div>
     36 <p>
     37 Recap from logic and sets:
     38 </p>
     39 <ul>
     40 <li>
     41 empty set Ø = {x | false}
     42 
     43 <li>
     44 universal set U = {x | true}
     45 
     46 <li>
     47 union A ∪ B = {x | x ∈ A or x ∈ B}
     48 
     49 <li>
     50 intersection A ∩ B = {x | x ∈ A and x ∈ B}
     51 
     52 <li>
     53 complement Ā = {x | x ∉ A}
     54 
     55 <li>
     56 difference A \ B = {x | x ∈ A and x ∉ B}
     57 
     58 </ul>
     59 
     60 <p>
     61 Theorems:
     62 </p>
     63 <ul>
     64 <li>
     65 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
     66 
     67 <li>
     68 (A \ B) \ C = A \ (B ∪ C)
     69 
     70 </ul>
     71 
     72 <div id="Sets-Relations"><h3 id="Relations" class="header"><a href="#Sets-Relations">Relations</a></h3></div>
     73 <p>
     74 definitions of properties:
     75 </p>
     76 <ul>
     77 <li>
     78 reflexive: ∀x R(x,x)
     79 
     80 <li>
     81 symmetric: ∀x ∀y (R(x,y) → R(y,x))
     82 
     83 <li>
     84 transitive: ∀x ∀y ∀z ((R(x,y) ∧ R(y,z)) → R(x,z))
     85 
     86 <li>
     87 serial: ∀x ∃y R(x,y)
     88 
     89 <li>
     90 functional: ∀x ∃y (R(x,y) ∧ ∀z (R(x,z) → z=y))
     91 
     92 </ul>
     93 
     94 <div id="Sets-Relations-Order types"><h4 id="Order types" class="header"><a href="#Sets-Relations-Order types">Order types</a></h4></div>
     95 <p>
     96 partial order:
     97 </p>
     98 <ul>
     99 <li>
    100 reflexive
    101 
    102 <li>
    103 transitive
    104 
    105 <li>
    106 antisymmetric
    107 
    108 </ul>
    109 
    110 <p>
    111 total order:
    112 </p>
    113 <ul>
    114 <li>
    115 partial order
    116 
    117 <li>
    118 ∀ a,b (R(a,b) ∨ R(b,a))
    119 
    120 </ul>
    121 
    122 <p>
    123 strict partial order: partial order but irreflexive
    124 </p>
    125 
    126 <p>
    127 strict total order:
    128 </p>
    129 <ul>
    130 <li>
    131 strict partial order
    132 
    133 <li>
    134 ∀ a,b (R(a,b) ∨ (a=b) ∨ R(b,a))
    135 
    136 </ul>
    137 
    138 <p>
    139 equivalence relation:
    140 </p>
    141 <ul>
    142 <li>
    143 reflexive (∀a, a ≡ A)
    144 
    145 <li>
    146 symmetric
    147 
    148 <li>
    149 transitive
    150 
    151 </ul>
    152 
    153 <div id="Sets-Natural numbers &amp; induction"><h3 id="Natural numbers &amp; induction" class="header"><a href="#Sets-Natural numbers &amp; induction">Natural numbers &amp; induction</a></h3></div>
    154 <p>
    155 Set of natural numbers is N ∈ (0,∞)
    156 </p>
    157 
    158 <p>
    159 Principle of induction: let P be a property of natural numbers. Suppose P holds for zero, and whenever P holds for a natural number n, then it holds for its successor n+1. Then P holds for every natural number.
    160 </p>
    161 
    162 <p>
    163 As a natural deduction rule:
    164 </p>
    165 
    166 <p>
    167 <img src="img/induction-natural-deduction-rule.png" alt="Induction natural deduction rule" />
    168 </p>
    169 
    170 <div id="Sets-Recursive definitions"><h3 id="Recursive definitions" class="header"><a href="#Sets-Recursive definitions">Recursive definitions</a></h3></div>
    171 <p>
    172 Let A be any set, suppose a is in A, and g: N × A → A. Then there is a unique function f satisfying:
    173 </p>
    174 <ul>
    175 <li>
    176 f(0) = a
    177 
    178 <li>
    179 f(n+1) = g(n, f(n))
    180 
    181 </ul>
    182 
    183 <p>
    184 Typically to prove something about a recursively defined function is to use induction.
    185 </p>
    186 
    187     </div>
    188 </body>
    189 </html>