<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@1bb4d25d9784494481ddc5946e06f1e8" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="51065c55fe2711ee9b7116fff75c5923">
<h2 class="hd hd-2 unit-title">Symbols</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@558f6fa6d9a7477bbf5783ed4178f41a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@558f6fa6d9a7477bbf5783ed4178f41a" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="51065c55fe2711ee9b7116fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4 class="MsoNormal">Basic set theoretic symbols</h4>
<ul>
<li>\(x \in A\)<br />\(x\) is a member of set \(A\)<br /><br /></li>
<li>\(\{a_1,\dots,a_n\}\)<br />the set whose members are \(a_1,\dots,a_n\)<br /><br /></li>
<li>\(\{x : \phi(x)\}\)<br />the set whose members are all and only the individuals satisfying condition \(\phi\)<br /><br /></li>
<li>\(A \subset B\)<br />\(A\) is a subset of \(B\); in other words: everything in \(A\) is also in \(B\)<br /><br /></li>
<li>\(A \subsetneq B\)<br />\(A\) is a proper subset of \(B\); in other words: \(A\) is a subset of \(B\) and the two are distinct.<br /><br /></li>
<li>\(A \cup B\)<br />the union of \(A\) and \(B\); in other words: \(A \cup B = \{x : x \in A \text{ or } x \in B\}\)<span style="mso-spacerun: yes;"> <br /><br /></span></li>
<li>\(A \cap B\)<br />the intersection of \(A\) and \(B\);<span style="mso-spacerun: yes;"> </span>in other words: \(A \cap B = \{x : x \in A \text{ and } x \in B\}\)<br /><br /></li>
<li>\(A - B\)<br />the set of elements in \(A\) but not in \(B\);<span style="mso-spacerun: yes;"> </span>in other words: \(A - B = \{x : x \in A \text{ and not-\((x \in B\))}\}\)<br /><br /></li>
<li>\(\mathscr{P}(A)\)<br />\(A\)'s powerset<br /><br /></li>
<li>\(\mathscr{P}^n(A)\)<br />\(\underbrace{\mathscr{P}(\mathscr{P}(\ldots\mathscr{P}(A)\ldots))}_{\text{\(n\) times}}\)<br /><br /></li>
<li>\(A\times B\)<br />the Cartesian product of \(A\) and \(B\)<br /><br /></li>
<li>\(|A|\)<br />the cardinality of set \(A\)<br /><br /></li>
<li>\(\bigcup A\)<br />the set of individuals \(x\) such that \(x\) is a member of some member of \(A\)<br /><br /></li>
<li>\(\overline{A}\)<br />When \(A\) is a <em>set</em>, \(\overline{A}\) is the complement of \(A\) relative to a suitable universal set \(U\); in other words: \(\overline{A} = U - A\); when \(A\) is a <em>proposition</em>, \(\overline{A}\) is the negation of \(A\). (The abuse of notation makes sense because it is sometimes useful to think of propositions as sets of "possible worlds" and in this context the negation of a proposition is its complement.)</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Symbols for functions</h4>
<p class="MsoNormal"></p>
<ul>
<li>\(f^{-1}\)<br />When \(f\) is a bijection from \(A\) to \(B\), \(f^{-1}\) is \(f\)'s {inverse}, i.e. the function \(g\) such that for each \(b\in B\), \(g(b)\) is the \(a \in A\) such that \(f(a) = b\).<br /><br /></li>
<li>\(g \circ f\)<br />the function \(g(f(x))\))<br /><br /></li>
<li>\(H(n,m)\)<br />\(H(n,m)\) is the two-place Halting function. In general, \(H(n,m) = 1\) if the \(n\)th Turing Machine (on a given coding scheme) halts on input \(m\); otherwise, \(H(n,m) = 0\).<br /><br /></li>
<li>\(H(n)\)<br />\(H(n,m)\) is the one-place Halting function. In general, \(H(n) = H(n,n)\).<br /><br /></li>
<li>\(BB(n)\)<br />\(BB(n)\) is the Busy Beaver function. In general, \(BB(n)\) is the productivity of the most productive (one-symbol) Turing Machine with \(n\) states or fewer.</li>
</ul>
<p></p>
<hr />
<p class="MsoNormal"> </p>
<h4 class="MsoNormal">Symbols for sets of numbers</h4>
<p class="MsoNormal"></p>
<ul>
<li>\(\mathbb{N}\)<br />the set of natural numbers<br /><br /></li>
<li>\(\mathbb{Z}\)<br />the set of integers<br /><br /></li>
<li>\(\mathbb{Z^+}\)<br />the set of positive integers<br /><br /></li>
<li>\(\mathbb{Q}\)<br />the set of rational numbers<br /><br /></li>
<li>\(\mathbb{Q}^{\geq 0}\)<br />the set of non-negative rational numbers<br /><br /></li>
<li>\(\mathbb{Q}^{[0,1)}\)<br />the set a rational numbers in \([0,1)\)<br /><br /></li>
<li>\(\mathbb{R}\)<br />the set of real numbers<br /><br /></li>
<li>\(\mathfrak{F}\)<br />the set of finite sequences of natural numbers<br /><br /></li>
<li>\((a,b)\)<br />the set of real numbers \(x\) such that \(a < x < b\)<br /><br /></li>
<li>\([a,b]\)<br />the set of real numbers \(x\) such that \(a \leq x \leq b\)<br /><br /></li>
<li>\([a,b)\)<br />the set of real numbers \(x\) such that \(a \leq x < b\)<br /><br /></li>
<li>\((-\infty,\infty)\)<br />the set of real numbers<br /><br /></li>
<li>\([0,\infty)\)<br />the set of non-negative real numbers</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Symbols for ordinals and cardinals</h4>
<p class="MsoNormal"></p>
<ul>
<li>\(0\)<br />\(0\) is the smallest ordinal and is defined as the set \(\{\}\).<br /><br /></li>
<li>\(\alpha'\)<br />\(\alpha'\) is the successor of ordinal \(\alpha\), and is defined as \(\alpha \cup \{\alpha\}\).<br /><br /></li>
<li>\(\omega\)<br />\(\omega\) is the smallest infinite ordinal and is defined as the set \(\{0,0',0'',\ldots\}\).<br /><br /></li>
<li>\(\alpha + \beta\)<br />the result of applying the operation of ordinal addition to ordinals \(\alpha\) and \(\beta\)<br /><br /></li>
<li>\(\alpha \times \beta\)<br />the result of applying the operation of ordinal multiplication to ordinals \(\alpha\) and \(\beta\)<br /><br /></li>
<li>\(\alpha^\beta\)<br />the result of applying the operation of ordinal exponentiation to ordinals \(\alpha\) and \(\beta\)<br /><br /></li>
<li>\(|A| \oplus |B|\)<br />the result of applying the operation of cardinal addition to the cardinalities of sets \(A\) and \(B\)<br /><br /></li>
<li>\(|A| \otimes |B|\)<br />the result of applying the operation of cardinal multiplication to the cardinalities of sets \(A\) and \(B\)<br /><br /></li>
<li>\(\mathfrak{B}_\alpha\)<br />\[\mathfrak{B}_\alpha = \begin{cases} \mathbb{N}, \text{ if \(\alpha = 0\)}\\ \mathscr{P}(\mathfrak{B}_\beta), \text{ if \(\alpha = \beta'\)}\\ \bigcup \{\mathfrak{B}_\gamma : \gamma <_o \alpha\} \text{ if \(\alpha\) is a limit ordinal greater than \(0\) \quad (p. \pageref{gloss:frak-B})} \end{cases}\]</li>
<li>\(\aleph_\alpha\)<br />the first infinite ordinal of cardinality greater than every \(\aleph_\beta\), for \(\beta <_o \alpha\)<br /><br /></li>
<li>\(\beth_\alpha\)<br />the first ordinal of cardinality \(|\mathfrak{B}_\alpha|\) (p. \pageref{gloss:beth}).</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal">Probabilistic Symbols</h4>
<ul>
<li>\(p(A)\)<br />the probability of \(A\)<br /><br /></li>
<li>\(p(A|B)\)<br />the conditional probability of \(A\), given \(B\)</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal">Symbols in Banach-Tarski Construction</h4>
<p class="MsoNormal"></p>
<ul>
<li>\(X^e\)<br />When \(X\) is a set of Cayley Paths, \(X^e\) is the set of endpoints of paths in \(X\) <br /><br /></li>
<li>\(\stackrel{\leftarrow}{X}\) <br />When \(X\) is a set of Cayley Paths, \(\stackrel{\leftarrow}{X}\) is the set that results from eliminating the first step from each of the Cayley Paths in \(X\)</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Logical Symbols</h4>
<p class="MsoNormal"></p>
<ul>
<li>\(=\)<br />identity<br /><br /></li>
<li>\(\neg\)<br />negation</li>
<li>\(\&\)<br />conjunction<br /><br /></li>
<li>\(\vee\)<br />disjunction<br /><br /></li>
<li>\(\supset\)<br />conditional<br /><br /></li>
<li>\(\forall\)<br />universal quantification<br /><br /></li>
<li>\(\exists\)<br />existential quantification<br /><br /></li>
<li>\( \exists !\)<br /><span style="mso-spacerun: yes;"> </span>"\( \exists ! x_i (\phi(x_i))\)'' is true if and only if there is exactly one object \(x\) such that \(\phi(x)\)</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal">Arithmetical Symbols</h4>
<p class="MsoNormal"></p>
<ul>
<li>\(+\)<br />addition<br /><br /></li>
<li>\(\times\)<br />multiplication<br /><br /></li>
<li>\(\wedge\)<br />exponentiation<br /><br /></li>
<li>\(n|m\)<br />\(n\) divides \(m\) with no remainder</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal">Miscellaneous Symbols</h4>
<ul>
<li>\(\mathring{M}\)<br />When \(M\) is a Turing Machine, \(\mathring{M}\) is the number of states in \(M\)'s program.<br /><br /></li>
<li>\(\leftrightarrow_{\text{df}}\)<br />The symbol "\(\leftrightarrow_{df}\)'' is used to indicate that the expression to its left is to be treated as a syntactic abbreviation for the expression to its right.</li>
</ul>
<p></p>
<p class="MsoNormal"> </p>
<p></p>
<p class="MsoNormal"> </p>
<p></p>
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;
mso-font-charset:0;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:-536870145 1107305727 0 0 415 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;
mso-font-charset:0;
mso-generic-font-family:swiss;
mso-font-pitch:variable;
mso-font-signature:-536859905 -1073732485 9 0 511 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-unhide:no;
mso-style-qformat:yes;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;}
.MsoChpDefault
{mso-style-type:export-only;
mso-default-props:yes;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection1
{page:WordSection1;}
--></style>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@b0fa441ceb694dd785b4cb272f021fe4" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="51065c55fe2711ee9b7116fff75c5923">
<h2 class="hd hd-2 unit-title">Concepts</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@73ef9f1e4dde489aa5909e2c92e90bdb">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@73ef9f1e4dde489aa5909e2c92e90bdb" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="51065c55fe2711ee9b7116fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4 class="MsoNormal">Set theory</h4>
<ul>
<li><strong>subset</strong><br />Set \(A\) is a subset of set \(B\) if and only if every member of \(A\) is also a member of \(B\).<br /><br /></li>
<li><strong>proper subset</strong><br />Set \(A\) is a proper subset of set \(B\) if and only if every member of \(A\) is also a member of \(B\), but not vice-versa.<br /><br /></li>
<li><strong>union</strong><br />The union of set \(A\) and set \(B\) is the set of everything in either in \(A\) or \(B\): \(\{x : x \in A \text{ or } x \in B\}\). The union of the countable family of sets \(A_1, A_2, A_3, \ldots\) is the set of everything in at least one of the \(A_1, A_2, A_3, \ldots\).<br /><br /></li>
<li><strong>intersection</strong><br />The intersection of set \(A\) and set \(B\) is the set of everything in both \(A\) and \(B\): \(\{x : x \in A \text{ and } x \in B\}\). The intersection of the countable family of sets \(A_1, A_2, A_3, \ldots\) is the set of everything in each of the \(A_1, A_2, A_3, \ldots\).<br /><br /></li>
<li><strong>complement</strong><br />The complement of set \(A\) and set \(B\) is the set of everything in both \(A\) and \(B\): \(\{x : x \in A \text{ and } x \in B\}\).<br /><br /></li>
<li><strong>powerset</strong><br />The powerset of a set \(A\) is the set of all and only \(A\)'s subsets.<br /><br /></li>
<li><strong>cardinality</strong><br />The cardinality (or size) of a set is a measure of how many objects it has.<br /><br /></li>
<li><strong>infinity</strong><br />A set \(A\) is infinite if \(|\mathbb{N}| \leq |A|\).<br /><br /></li>
<li><strong>countability<br /></strong>A set \(A\) is {countable} if \(|A| \leq |\mathbb{N}|\).<br /><br /></li>
<li><strong>cartesian product</strong><br />The Cartesian product of \(A\) and \(B\) is the set of pairs \(\langle a,b\rangle\) such that \(a \in A\) and \(b\in B\).<br /><br /></li>
<li><strong>disjoint</strong><br />For the family of sets \(A_1,A_2,\dots\)<span style="mso-spacerun: yes;"> </span>to be {disjoint} is for \(A_i\) and \(A_j \) to have no members in common whenever \(i \neq j\).<br /><br /></li>
<li><strong>partition</strong><br />A partition of a set \(A\) is a set \(P\) of non-empty subsets of \(A\) such that: (1) \(\bigcup P = A\), and (2) \(a \cap b = \{\}\) for any distinct \(a,b \in P\). One way to generate a partition \(P\) of \(A\) is to define an equivalence relation \(R\) on \(A\) and let \(P = \{S : S = \{x : xRa\} \text{ for } a \in A\}\).</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Sets of numbers</h4>
<p class="MsoNormal"></p>
<ul>
<li><strong>natural</strong><br />A natural number is one of the non-negative finite integers \(0,1,2,\dots\).<br /><br /></li>
<li><strong>square<br /></strong>A square number is a number of the form \(n^2\), for \(n\) a positive integer.<br /><br /></li>
<li><strong>integer</strong><br />An integer is one of \(\dots-2, -1, 0,1,2,\dots\).<br /><br /></li>
<li><strong>rational</strong><br />A rational number is a number \(a/b\), where \(a\) and \(b\) are integers and \(b \neq 0\).<br /><br /></li>
<li><strong>real</strong><br />A real number is a number that can be written down in decimal notation by starting with a numeral (e.g. "17''), adding a decimal point ("17.''), and then an infinite sequence of digits (e.g. "17.8423\dots'').<br /><br /></li>
<li><strong>infinitesimal</strong><br />An infinitesimal number is a number that is greater than zero but smaller than every positive real number.<br /><br /></li>
<li><strong>line segment</strong><br />Where \(a\) and \(b\) are real numbers, the line segment \([a,b]\) is the set of real numbers \(x\) such that \(a \leq x \leq b\).<br /><br /></li>
<li><strong>borel</strong><br />A {Borel Set} is any member of the smallest set \(\mathscr{B}\) such that: \((i)\) every line segment is in \(\mathscr{B}\), \((ii)\) if a set is in \(\mathscr{B}\), then so is its complement, and \((iii)\) if a countable family of sets is in \(\mathscr{B}\), then so is its union.<br /><br /></li>
<li><strong>translation</strong><br />If \(A\) is a set of real numbers, the {translation} of \(A\) by \(c\) is the result of adding \(c\) to each member of \(A\).</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Numerical systems</h4>
<p class="MsoNormal"></p>
<ul>
<li><strong>decimal</strong><br />A number's decimal expansion is a name for that number in decimal notation. One names a number in decimal notation by writing out a finite sequence of decimal digits (which are the symbols "0'', "1'', \dots "9''), followed by a point, followed by an infinite sequence of decimal digits.<span style="mso-spacerun: yes;"> </span>The decimal expansion "\(a_n a_{n-1}\dots a_0.b_1b_2b_3\ldots\)'' represents the number: \(a_n 10^n + a_{n-1} 10^{n-1} + \dots + a_0<span style="mso-spacerun: yes;"> </span>10^0 + {b_1 10^{-1}}+{b_2 10^{-2}}+{b_3 10^{-3}}+\ldots\). The number 17, for example, has two decimal expansions: "\(17.0000\dots\)'' and "\(16.9999\dots\)''.<br /><br /></li>
<li><strong>binary<br /></strong>A number's binary expansion is a name for that number in binary notation. One names a number in decimal notation by writing out a finite sequence of binary digits (which are the symbols "0'' and "1''), followed by a point, followed by an infinite sequence of decimal digits. The decimal expansion "\(a_n a_{n-1}\dots a_0.b_1b_2b_3\ldots\)'' represents the number: \(a_n 2^n + a_{n-1} 2^{n-1} + \dots + a_0<span style="mso-spacerun: yes;"> </span>2^0 + {b_1 2^{-1}}+{b_2 2^{-2}}+{b_3 2^{-3}}+\ldots\). The number \(3/2\), for example, has two decimal expansions: "\(1.1000\dots\)'' and "\(1.0111\dots\)''.</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Functions</h4>
<p></p>
<ul>
<li><strong>function</strong><br />A function from \(A\) to \(B\) is an assignment of one member of \(B\) to each member of \(A\).<br /><br /></li>
<li><strong>domain<br /></strong>If \(f\) is a function from \(A\) to \(B\), then \(A\) is the domain of \(f\).<br /><br /></li>
<li><strong>range</strong><br />If \(f\) is a function from \(A\) to \(B\), then the range of \(f\) is the subset \(\{f(x) : x \in A\}\) of \(B\).<br /><br /></li>
<li><strong>bijection<br /></strong>A bijection from set \(A\) to set \(B\) is a function from \(A\) to \(B\) such that: \((i)\) each member of \(A\) is assigned to a different member of \(B\), and \((ii)\) no member of \(B\) is left without an assignment from \(A\).<br /><br /></li>
<li><strong>injection</strong><br />An injection from \(A\) to \(B\) is a bijection from \(A\) to a subset of \(B\).<br /><br /></li>
<li><strong>surjection</strong><br />A surjection from \(A\) to \(B\) is a function \(f\) from \(A\) to be \(B\) such that there is no member of \(B\) to which \(f\) fails to assign some member of \(A\).<br /><br /></li>
<li><strong>inverse</strong><br />When \(f\) is a bijection from \(A\) to \(B\), \(f\)'s {inverse} function \(f^{-1}\) is the function \(g\) such that for each \(b\in B\), \(g(b)\) is the \(a \in A\) such that \(f(a) = b\).<br /><br /></li>
<li><strong>composition</strong><br />The composite function \(g \circ f\) is the function \(g(f(x))\)).</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<h4 class="MsoNormal">Relations</h4>
<p class="MsoNormal"></p>
<ul>
<li><strong>relation<br /></strong>A relation \(R\) on set \(A\) is a subset of \(A \times A\). If \(R\) is a relation on \(A\) and \(a,b \in A\), we say that \(aRb\) holds (or that \(Rab\) holds) if and only if \(\langle a,b\rangle \in R\). }<br /><br /></li>
<li><strong>reflexivity<br /></strong>A relation \(R\) on \(A\) is reflexive if and only if, for each \(a \in A\), \(aRa\).<br /><br /></li>
<li><strong>symmetry</strong><br />A relation \(R\) on \(A\) is symmetric if and only if, for each \(a,b\in A\),<span style="mso-spacerun: yes;"> </span>if \(aRb\) then \(bRa\).<br /><br /></li>
<li><strong>transitivity</strong><br />A relation \(R\) on \(A\) is transitive if and only if, for each \(a,b\in A\), it satisfies \(aRc\) whenever it satisfies \(aRb\) and \(bRc\).<br /><br /></li>
<li><strong>equivalence</strong><br />A two-place relation \(R\) on \(A\) is an equivalence if and only if it is reflexive, symmetric and transitive.<br /><br /></li>
<li><strong>irreflexivity</strong><br />A relation \(R\) on \(A\) is irreflexive if and only if, for each \(a \in A\), not-(\(aRa\)).<br /><br /></li>
<li><strong>asymmetry</strong><br />A relation \(R\) on \(A\) is asymmetric if and only if, for each \(a,b\in A\), if \(aRb\), then not-(\(bRa\)).<br /><br /></li>
<li><strong>anti-symmetry</strong><br />A relation \(R\) on \(A\) is anti-symmetric if and only if, for each \(a,b\in A\), if \(a R b\) and \(b R a\), then \(a = b\).<br /><br /></li>
<li><strong>totality</strong><br />A relation \(R\) on \(A\) is total if and only if, for each \(a,b\in A\), one of \(aRb\) or \(bRa\) or \(a = b\).<br /><br /></li>
<li><strong>isomorphism</strong><br />Let \(R_A\) be a relation on \(A\) and \(R_B\) be a relation on \(B\). Then<span style="mso-spacerun: yes;"> </span>\(R_A\) is isomorphic to \(R_B\) if and only if there is a bijection \(f\) from \(A\) to \(B\) such that, for every \(x\) and \(y\) in \(A\), \(xR_Ay\) if and only if \(f(x)R_Bf(y)\).</li>
</ul>
<p></p>
<hr />
<p></p>
<h4>Orderings</h4>
<p></p>
<ul>
<li><strong>ordering</strong><br />A set \(A\) is ordered by the two-place relation \(R\) if \(R\) satisfies asymmetry and transitivity for every member of \(A\).<br /><br /></li>
<li><strong>partial ordering</strong><br />A set \(A\) is (non-strictly) partially ordered by the two-place relation \(R\) if \(R\) satisfies reflexivity, anti-symmetry and transitivity for every member of \(A\).<br /><br /></li>
<li><strong>total ordering</strong><br />A set \(A\) is (strictly) totally ordered by the two-place relation \(R\) if \(A\) is ordered by \(R\) and \(R\) satisfies totality for every member of \(A\).<br /><br /></li>
<li><strong>well-ordering</strong><br />A set \(A\) is well-ordered by the two-place relation \(R\) if \(A\) is totally ordered<span style="mso-spacerun: yes;"> </span>by \(R\) and \(R\) satisfies the following additional condition: Every non-empty subset \(S\) of \(A\) has some member \(x\) with the property that \(x R y\) for for every \(y\) in \(S\) other than \(x\).<br /><br /></li>
<li><strong>well-order type</strong><br />a class that consists of an ordering \(<\) and every ordering \(<\) is isomorphic to.<br /><br /></li>
<li><strong>\(\omega\)-sequence</strong><br />a sequence of items whose ordering is isomorphic to the natural ordering of the natural numbers: \({0 < 1 < 2 < 3 < 4 <\dots}\).<br /><br /></li>
<li><strong>reverse \(\omega\)-sequence</strong><br />a sequence of items whose ordering is isomorphic to the reverse of the natural ordering of the natural numbers:<span style="mso-spacerun: yes;"> </span>\(\dots 4 < 3 < 2 <1 < 0\).</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<p class="MsoNormal"> </p>
<h4 class="MsoNormal">Ordinals</h4>
<p></p>
<ul>
<li><strong>ordinal</strong><br />Ordinals are sets that are used to represent types of well-orderings. Informally, the ordinals are build in stages, in accordance with the Open-Endedness Principle and the Construction Principle. Formally, an ordinal is a (pure) set that is set-transitive and well-ordered by \(<_o\).<br /><br /></li>
<li><strong>successor ordinal</strong><br />A successor ordinal is an ordinal \(\alpha\) such that \(\alpha = \beta'\) for some ordinal \(\beta\).<br /><br /></li>
<li><strong>limit ordinal</strong><br />A limit ordinal is an ordinal that is not a successor ordinal.<br /><br /></li>
<li><strong>ordinal addition</strong><br />Ordinal addition is an operation that takes two ordinals as input and yields an ordinal as output. Here is the intuitive idea: a well-ordering of type \((\alpha+\beta)\) is the result of starting with a well-ordering of type \(\alpha\) and appending a well-ordering of type \(\beta\) at the end.<br /><br /></li>
<li><strong>ordinal multiplication</strong><br />Ordinal multiplication is an operation that takes two ordinals as input and yields an ordinal as output.<span style="mso-spacerun: yes;"> </span>Here is the intuitive idea: a well-ordering of type \((\alpha\times\beta)\) is the result of starting with a well-ordering of type \(\beta\) and replacing each position in the ordering with a well-ordering of type \(\alpha\).<br /><br /></li>
<li><strong>cardinal addition</strong><br />Cardinal addition is an operation that takes two cardinalities as input and yields a cardinality as output. It is defined as follows: \(|A| \oplus |B| = |A \cup B|\), assuming \(A\) and \(B\) have no members in common. If they do, find sets \(A'\) and \(B'\) with no members in common such that \(|A| = |A'|\) and \(|B| = |B'|\), and let \(|A| \oplus |B| = |A' \cup B'|\).<br /><br /></li>
<li><strong>cardinal multiplication</strong><br />Cardinal multiplication is an operation that takes two cardinalities as input and yields a cardinality as output. It is defined as follows: \(|A| \otimes |B| = |A \times B|\).<br /><br /></li>
<li><strong>initial ordinal</strong><br />An initial ordinal is an ordinal that precedes all other ordinals of the same cardinality.<br /><br /></li>
<li><strong>cardinal</strong><br />An initial ordinal, which is used to represent its own cardinality.<br /><br /></li>
<li><strong>beth hierarchy</strong><br />The hierarchy of sets \(\beth_\alpha\), for \(\alpha\) an ordinal, where \(\beth_\alpha\) is the smallest ordinal of cardinality \(|\mathfrak{B}_\alpha|\).</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<h4 class="MsoNormal"> Determinism</h4>
<p></p>
<ul>
<li><strong>determinism<br /></strong>For a system of laws to be determinisitic is for it to entail, on the basis of a full specification of the state of the world at any given time, a full specification of the state of the world at any later time.</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<h4 class="MsoNormal"> Conditionals</h4>
<p></p>
<ul>
<li><strong>indicative</strong><br />An indicative conditional is a conditional of the form <em>if \(A\), then \(B\)</em>; its probability is the conditional probability of its consequent on its .<br /><br /></li>
<li><strong>subjunctive</strong><br />A subjunctive conditional is a conditional of the form <em>if it were that A, it would be that B</em>. There is a connection between subjunctive conditionals and causal dependence, but it is fairly subtle.</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Decision Theory</h4>
<p></p>
<ul>
<li><strong>expected value</strong><br />According to evidential decision theory, the expected value of an option \(A\) is the weighted average of the value of the outcomes that \(A\) might lead to, with weights determined by the conditional probability of the relevant state of affairs, given that you choose \(A\). According to causal decision theory, the expected value of an option \(A\) is the weighted average of the value of the outcomes that \(A\) might lead to, with weights determined by the probability of the subjunctive conditional: <em>were you to do \(A\), the relevant outcome would come about</em>.<br /><br /></li>
<li><strong>maximization</strong><br />Expected Value Maximization is the principle that one should choose an option whose expected value is at least as high as that of any rival option.<br /><br /></li>
<li><strong>dominance</strong><br />Option \(A\) (strictly) dominates option \(B\) if however matters you have no control over turn out, you'll be better off choosing \(A\) than choosing \(B\).<br /><br /></li>
<li><strong>probabilistic dependence</strong><br />Two events are probabilistically independent of one another if the assumption that one of them occurs does not affect the probability that the other one will occur; otherwise, each of them is probabilistically dependent on the other.<br /><br /></li>
<li><strong>causal dependence</strong><br />Two events are causally independent of one another if neither of them is a cause of the other; otherwise, the effect is causally dependent on the cause.</li>
</ul>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Probability</h4>
<p></p>
<ul>
<li><strong>subjective</strong><br />\(S\)'s subjective probability in \(p\) is the degree to which \(S\) believes that \(p\).<br /><br /></li>
<li><strong>objective</strong><br />The objective probability of \(p\) is meant to be a fact about the probability that \(p\) which is independent of the beliefs of any particular subject. There are many different views about what objective probability consists in.<br /><br /></li>
<li><strong>credence</strong><br />a degree of belief<br /><br /></li>
<li><strong>credence function</strong><br />a function that assigns to each proposition in a suitable range a real number between \(0\) and \(1\), representing the degree to which \(S\) believes that proposition<br /><br /></li>
<li><strong>probability function</strong><br />A probability function is an assignment of real numbers between \(0\) and \(1\) to propositions that satisfies Necessity and Additivity.<br /><br /></li>
<li><strong>necessity<br /></strong>A probability function \(p\) satisfies Necessity if and only if: \(p(A) = 1\) whenever \(A\) is a necessary truth.<br /><br /></li>
<li><strong>additivity</strong><br />A probability function \(p\) satisfies Additivity if and only if: \(p(A \text{ or } B) = p(A) + p(B)\) whenever \(A\) and \(B\) are incompatible propositions. Further, \(p\) satisfies Countable Additivity if and only if:<span style="mso-spacerun: yes;"> </span>for \(A_1,A_2,A_3,\dots\) a countable list of propositions, \(p\left(A_1 \mbox{ or } A_2 \mbox{ or } A_3 \mbox{ or } \ldots\right) = p(A_1) + p(A_2) + p(A_3) + \ldots\), assuming \(A_i\) and \(A_j\) are incompatible whenever \(i \neq j\).<br /><br /></li>
<li><strong>frequentism</strong><br />the view that what it is for the objective probability that an event of type \(E\) yields outcome \(O\) to be \(n\%\) is for \(n\%\) of events of type \(E\) to yield outcome \(O\)<br /><br /></li>
<li><strong>rationalism</strong><br />the view that there is nothing more to objective probability than the Objective-Subjective Connection<br /><br /></li>
<li><strong>localism</strong><br />a variety of rationalism according to which the notion of perfect rationality is only well-defined in certain special circumstances; for example, circumstances in which there is an unproblematic way of deploying a Principle of Indifference<br /><br /></li>
<li><strong>primitivism</strong><br />the view that the notion of objective probability resists full elucidation and is best regarded as a theoretical primitive</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<h4 class="MsoNormal"> Measure</h4>
<h4></h4>
<ul>
<ul>
<li><strong>measure</strong><br />A function on the Borel Sets is a {measure} if and only if it satisfies Countable Additivity, satisfies Non-Negativity, and assigns the value 0 to the empty set.<br /><br /></li>
<li><strong>lebesgue measure<br /></strong>The Lebesgue Measure is a measure. It is the unique measure satisfying Length on Line Segments and the unique function on the Borel Sets that satisfies all three of Length on Line Segments, Countable Additivity and Non-Negativity.<br /><br /></li>
<li><strong>lebesgue measurable</strong><br />A set \(A \subset \mathbb{R}\) is Lebesgue Measurable if and only if: \(A = A^B \cup A^0\), for \(A^B\) a Borel Set and \(A^0\) a subset of some Borel Set of Lebesgue Measure zero.<br /><br /></li>
<li><strong>length on line segments</strong><br />A function \(\mu\) satisfies Length on Line Segments if and only if \(\mu([a,b]) = b-a\) for every \(a,b \in \mathbb{R}\).<br /><br /></li>
<li><strong>countable additivity</strong><br /><span style="mso-spacerun: yes;"> </span>A function \(\mu\) is countably additive if and only if \(\mu\left(\bigcup\{A_1,<span style="mso-spacerun: yes;"> </span>A_2 , A_3,\ldots\}\right) = \mu(A_1) + \mu(A_2) + \mu(A_3) + \ldots\) whenever \(A_1,A_2,\dots\) is a countable family of disjoint sets for each of which \(\mu\) is defined.<br /><br /></li>
<li><strong>non-negativity</strong><br />A function \(\mu\) satisfies Non-Negativity if and only if \(\mu(A)\) is either a non-negative real number or the infinite value \(\infty\), for any set \(A\) in the domain of \(\mu\).<br /><br /></li>
<li><strong>uniformity</strong><br />A function \(\mu\) satisfies Uniformity if and only if \(\mu(A^c) = \mu(A)\), whenever \(\mu(A)\) is well-defined and \(A^c\) is the result of adding \(c \in \mathbb{R}\) to each member of \(A\).</li>
</ul>
</ul>
<p></p>
<p></p>
<hr />
<p></p>
<h4 class="MsoNormal"> Banach-Tarski Construction</h4>
<p></p>
<ul>
<li><strong>cayley graph</strong><br />the set of Cayley Paths<br /><br /></li>
<li><strong>cayley path</strong><br />A Cayley Path is a finite sequence of steps, starting from a given point, referred to as the Cayley Graph's "center''. Each step is taken in one of four directions: up, down, right or left, with the important restriction that one is forbidden from following opposite directions in adjacent steps.<br /><br /></li>
<li><strong>endpoint</strong><br />The endpoint of a Cayley Path is the result of starting from the Cayley Graph's "center'' and taking each step in the path. An {endpoint} of the Cayley Graph is the endpoint of some Cayley Path.</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<h4 class="MsoNormal">Computability</h4>
<p></p>
<ul>
<li><strong>turing machine</strong><br />A Turing Machine is a computer of a particularly simple sort. Its hardware consists of a memory tape and a tape-reader. The tape is divided into cells and is assumed to be infinite in both directions. The reader is able to read and write symbols on the tape and move between cells. The machine's software consists of a finite list of command lines. Each command line is a sequence of five symbols: \[\langle\text{current state}\rangle \langle\text{current symbol}\rangle \langle\text{new symbol}\rangle \langle\text{direction}\rangle \langle\text{new state}\rangle\].</li>
<li><strong>compute</strong><br />For a computer to compute a function \(f\), from natural numbers to natural numbers, is for the computer to be such that it always returns \(f(n)\) as output when given \(n\) as input.<br /><br /></li>
<li><strong>computable</strong><br />For a function to be computable is for there to be a (possible) computer that computes it. For a function to be Turing-computable is for there to be a (possible) Turing Machine that computes it. It can be shown that a function is Turing-computable if and only if it is computable by an ordinary computer (i.e. a register machine), assuming unlimited memory and running time.<br /><br /></li>
<li><strong>algorithm</strong><br />An algorithm is a finite list of instructions for solving a given problem such that: \((1)\) following the instructions is guaranteed to yield a solution to the problem in a finite amount of time, and \((2)\)<span style="mso-spacerun: yes;"> </span>the instructions are specified in such a way that carrying them out requires no ingenuity, special resources, or physical conditions. For a problem to be algorithmically computable is for there to be an algorithm for that problem.<br /><br /></li>
<li><strong>one-symbol</strong><br />A {one-symbol} Turing Machine is a machine in which the only symbol allowed on the tape (not counting blanks) is "1''. One can show that every function computed by a many-symbol Turing Machine can also be computed by some one-symbol machine.<br /><br /></li>
<li><strong>oracle</strong><br />In the context of Turing Machines, an oracle is a primitive operation that allows a Turing Machine to instantaneously determine the answer to a given question. For example, a {halting oracle} is a primitive operation that allows a Turing Machine to instantaneously determine whether a given Turing Machine would halt on an empty input.</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<p class="MsoNormal"> </p>
<h4 class="MsoNormal">Logic and Arithmetic</h4>
<p></p>
<ul>
<li> <strong>arithmetical language</strong><br />An arithmetical language is a language in which one can talk about the natural numbers and their two basic operations, addition and multiplication.<br /><br /></li>
<li><strong>axiomatization</strong><br />An axiomatization is system of axioms and rules of inference for proving claims within a suitable language. Axiomatizations are assumed to be Turing-computable; in other words, it must be possible to program a Turing Machine to determine what counts as an axiom and when one sentence follows from another by a rule of inference.<br /><br /></li>
<li><strong>axiom</strong><br />a sentence on the basis of which other sentences are to be proved<br /><br /></li>
<li><strong>rule of inference<br /></strong>a rule for inferring some sentences from others<br /><br /></li>
<li><strong>provable<br /></strong>A sentence \(S\) is {provable} on the basis of a given axiomatization if and only if there is a finite sequence of sentences of the language such that: (1) every member of the sequence is either an axiom, or something that results from previous members of the sequence by applying a rule of inference, and (2) the last member of the sequence is \(S\).<br /><br /></li>
<li><strong>complete</strong><br />In the sense of completeness that is presupposed in Lecture 10, an axiomatization is said to be complete if and only if every true sentence of the language is provable on the basis of that axiomatization. There is a different sense of completeness according to which an axiomatization is said to be complete if and only if it proves every sentence or its negation.<br /><br /></li>
<li><strong>consistent</strong><br />An axiomatization is consistent if and only if it is never the case that both a sentence of the relevant language and its negation are provable on the basis of that axiomatization.</li>
</ul>
<p></p>
<hr />
<p></p>
<p></p>
<p class="MsoNormal"> </p>
<h4 class="MsoNormal">Other</h4>
<p></p>
<ul>
<li> <strong>paradox</strong><br />an argument that appears to be valid, and goes from seemingly true premises to a seemingly false conclusion<br /><br /></li>
<li><strong>logical impossibility</strong><br />For a hypothesis to be logically impossible is for it to contain an absurdity.</li>
</ul>
<p></p>
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;
mso-font-charset:0;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:-536870145 1107305727 0 0 415 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;
mso-font-charset:0;
mso-generic-font-family:swiss;
mso-font-pitch:variable;
mso-font-signature:-536859905 -1073732485 9 0 511 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-unhide:no;
mso-style-qformat:yes;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;}
.MsoChpDefault
{mso-style-type:export-only;
mso-default-props:yes;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection1
{page:WordSection1;}
--></style>
</div>
</div>
</div>
</div>
© All Rights Reserved