https://machinelearning.subwiki.org/w/index.php?action=history&feed=atom&title=User%3AIssaRice%2FComputability_and_logic%2FDiagonalization_lemma_%28Yanofsky_method%29
User:IssaRice/Computability and logic/Diagonalization lemma (Yanofsky method) - Revision history
2026-05-22T22:23:07Z
Revision history for this page on the wiki
MediaWiki 1.41.2
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3371&oldid=prev
IssaRice: /* Theorem statement and proof */
2021-07-29T03:32:06Z
<p><span dir="auto"><span class="autocomment">Theorem statement and proof</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:32, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l5">Line 5:</td>
<td colspan="2" class="diff-lineno">Line 5:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Theorem (Diagonalization lemma).''' Let <math>T</math> be some nice theory (I don't remember the exact conditions, but Peano Arithmetic or Robinson Arithmetic would work). For any single-place formula <math>\mathcal E(x)</math> with <math>x</math> as its only free variable, there exists a sentence (closed formula) <math>\mathcal C</math> such that <math>T \vdash \mathcal C \leftrightarrow \mathcal E(\ulcorner \mathcal C \urcorner)</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''Theorem (Diagonalization lemma).''' Let <math>T</math> be some nice theory (I don't remember the exact conditions, but Peano Arithmetic or Robinson Arithmetic would work). For any single-place formula <math>\mathcal E(x)</math> with <math>x</math> as its only free variable, there exists a sentence (closed formula) <math>\mathcal C</math> such that <math>T \vdash \mathcal C \leftrightarrow \mathcal E(\ulcorner \mathcal C \urcorner)</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>''Proof.'' We will use what's called the [[wikipedia:Lindenbaum–Tarski algebra]] in our proof, which the Yanofsky paper just calls Lindenbaum classes. The idea is to define an equivalence an equivalence relation on formulas, so that <math>A \sim B</math> iff our theory <math>T</math> can prove that <math>A</math> and <math>B</math> are logically equivalent. In other words, we define <math>A \sim B</math> iff <math>T \vdash A \leftrightarrow B</math>. This is easily verified to be an equivalence relation. One twist is that it doesn't make sense to compare two formulas with differing arity. For instance, what does it even mean to say "2+2=5" and "x+5=7" are or are not provably equivalent? For this reason, we make a separate equivalence relation for each arity, and so we end up with separate quotients for each arity. For <math>i=0,1,2,\ldots</math>, we let <math>\mathit{Lind}^i</math> be the set of Lindenbaum classes of formulas with <math>i</math> free variables.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>''Proof.'' We will use what's called the [[wikipedia:Lindenbaum–Tarski algebra]] in our proof, which the Yanofsky paper just calls Lindenbaum classes. The idea is to define an equivalence an equivalence relation on formulas, so that <math>A \sim B</math> iff our theory <math>T</math> can prove that <math>A</math> and <math>B</math> are logically equivalent. In other words, we define <math>A \sim B</math> iff <ins style="font-weight: bold; text-decoration: none;"><math>T \vdash A \leftrightarrow B</math>. Thus below if we say <math>[A]_\sim = [B]_\sim</math> this means <math>T \vdash A \leftrightarrow B</math>, and similarly if we say <math>A \in [B]_\sim</math> this also means </ins><math>T \vdash A \leftrightarrow B</math>. This is easily verified to be an equivalence relation. One twist is that it doesn't make sense to compare two formulas with differing arity. For instance, what does it even mean to say "2+2=5" and "x+5=7" are or are not provably equivalent? For this reason, we make a separate equivalence relation for each arity, and so we end up with separate quotients for each arity. For <math>i=0,1,2,\ldots</math>, we let <math>\mathit{Lind}^i</math> be the set of Lindenbaum classes of formulas with <math>i</math> free variables.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>That means that e.g. each element of <math>\mathit{Lind}^0</math> is not a sentence, but rather a set of sentences that are all provably equivalent. But every sentence is either true or false, so doesn't this mean <math>\mathit{Lind}^0</math> has just two element, <math>[\top]_{\sim}</math> and <math>[\bot]_{\sim}</math> (i.e. the class of true sentences and the class of false sentences)? No! That's because even if two sentences are both true, our theory may be unable to prove that it is so! That's the whole point of Gödel's first incompleteness theorem, which shows us that there can be true sentences (such as the famous "I am not provable" sentence <math>G</math>) which are not provable (so that even though <math>G</math> is true, <math>G \notin [2+2=5]_\sim</math>).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>That means that e.g. each element of <math>\mathit{Lind}^0</math> is not a sentence, but rather a set of sentences that are all provably equivalent. But every sentence is either true or false, so doesn't this mean <math>\mathit{Lind}^0</math> has just two element, <math>[\top]_{\sim}</math> and <math>[\bot]_{\sim}</math> (i.e. the class of true sentences and the class of false sentences)? No! That's because even if two sentences are both true, our theory may be unable to prove that it is so! That's the whole point of Gödel's first incompleteness theorem, which shows us that there can be true sentences (such as the famous "I am not provable" sentence <math>G</math>) which are not provable (so that even though <math>G</math> is true, <math>G \notin [2+2=5]_\sim</math>).</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3370&oldid=prev
IssaRice at 00:57, 29 July 2021
2021-07-29T00:57:30Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:57, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l20">Line 20:</td>
<td colspan="2" class="diff-lineno">Line 20:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:<math>f([\mathcal B(x)]_\sim, [\mathcal H(y)]_\sim) := [\mathcal H(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \})]_\sim</math></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:<math>f([\mathcal B(x)]_\sim, [\mathcal H(y)]_\sim) := [\mathcal H(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \})]_\sim</math></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">But actually, this notation is quite unwieldy especially as we start to nest more and more expressions, so let's define a min operator for sets of sentences. Formally, we define <math>\min [\mathcal B(x)]_\sim := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>. A little confusing perhaps, but we are not finding the formula with the least godel number, but instead the godel number of the formula with the least godel number.</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now each single-place formula <math>\mathcal E(x)</math> induces a mapping <math>\Phi_{\mathcal E} : \mathit{Lind}^0 \to \mathit{Lind}^0</math> by <math>\mathcal [\mathcal P]_\sim \mapsto \mathcal [\mathcal E(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal P]_\sim\})]_\sim</math>. We again have to standardize by taking the smallest Gödel number in the class in order to ensure the mapping is well-defined.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now each single-place formula <math>\mathcal E(x)</math> induces a mapping <math>\Phi_{\mathcal E} : \mathit{Lind}^0 \to \mathit{Lind}^0</math> by <math>\mathcal [\mathcal P]_\sim \mapsto \mathcal [\mathcal E(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal P]_\sim\})]_\sim</math>. We again have to standardize by taking the smallest Gödel number in the class in order to ensure the mapping is well-defined.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3369&oldid=prev
IssaRice at 00:42, 29 July 2021
2021-07-29T00:42:45Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:42, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l56">Line 56:</td>
<td colspan="2" class="diff-lineno">Line 56:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[TODO] so actually to get the proof to work, we need <math>D(\ulcorner \varphi \urcorner) = \min [\varphi(\ulcorner \varphi \urcorner)]_\sim</math>. But doesn't this make D uncomputable?</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[TODO] Here we need to explain what D(x) means and why it's valid.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[TODO] Here we need to explain what D(x) means and why it's valid.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3368&oldid=prev
IssaRice at 00:18, 29 July 2021
2021-07-29T00:18:21Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:18, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l47">Line 47:</td>
<td colspan="2" class="diff-lineno">Line 47:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>. Note that <math>T \vdash \<del style="font-weight: bold; text-decoration: none;">varphi </del>\leftrightarrow \mathcal B(x)</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>. Note that <math>T \vdash \<ins style="font-weight: bold; text-decoration: none;">varphi_n </ins>\leftrightarrow \mathcal B(x)</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). Using our new notation, this is <math>D(n) = \ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). Using our new notation, this is <math>D(n) = \ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3367&oldid=prev
IssaRice at 00:17, 29 July 2021
2021-07-29T00:17:56Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:17, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l47">Line 47:</td>
<td colspan="2" class="diff-lineno">Line 47:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n<ins style="font-weight: bold; text-decoration: none;"></math>. Note that <math>T \vdash \varphi \leftrightarrow \mathcal B(x)</ins></math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). Using our new notation, this is <math>D(n) = \ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). Using our new notation, this is <math>D(n) = \ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3366&oldid=prev
IssaRice at 00:17, 29 July 2021
2021-07-29T00:17:10Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:17, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l50">Line 50:</td>
<td colspan="2" class="diff-lineno">Line 50:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). Using our new notation, this is <math>D(n) = \ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). Using our new notation, this is <math>D(n) = \ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">So in the end we get <math>[\mathcal E(\ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner)]_\sim</math>.</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3365&oldid=prev
IssaRice at 00:15, 29 July 2021
2021-07-29T00:15:36Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:15, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l49">Line 49:</td>
<td colspan="2" class="diff-lineno">Line 49:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). <del style="font-weight: bold; text-decoration: none;">This </del>is <math>\ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>So we want to compute D(n). <ins style="font-weight: bold; text-decoration: none;">Using our new notation, this </ins>is <math><ins style="font-weight: bold; text-decoration: none;">D(n) = </ins>\ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3364&oldid=prev
IssaRice at 00:15, 29 July 2021
2021-07-29T00:15:09Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:15, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l48">Line 48:</td>
<td colspan="2" class="diff-lineno">Line 48:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>.</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">So we want to compute D(n). This is <math>\ulcorner \varphi_n(\ulcorner \varphi_n \urcorner) \urcorner</math>.</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3363&oldid=prev
IssaRice at 00:13, 29 July 2021
2021-07-29T00:13:47Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:13, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l46">Line 46:</td>
<td colspan="2" class="diff-lineno">Line 46:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">To do the next step, it is convenient to put <math>n := \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}</math>, and let <math>\varphi_n</math> be the formula such that <math>\ulcorner \varphi_n \urcorner = n</math>.</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(\mathcal B( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td></tr>
</table>
IssaRice
https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_lemma_(Yanofsky_method)&diff=3362&oldid=prev
IssaRice at 00:09, 29 July 2021
2021-07-29T00:09:06Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:09, 29 July 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l47">Line 47:</td>
<td colspan="2" class="diff-lineno">Line 47:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>expanding the definition of G, we get <math>[\mathcal E(D(\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \}))]_\sim</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(<del style="font-weight: bold; text-decoration: none;">?</del>(<del style="font-weight: bold; text-decoration: none;">\ulcorner </del>\min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} <del style="font-weight: bold; text-decoration: none;">\urcorner</del>))]_\sim</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Now by definition of D, we get <math>[\mathcal E(<ins style="font-weight: bold; text-decoration: none;">\mathcal B</ins>( \min \{\ulcorner \varphi \urcorner : \varphi \in [\mathcal B(x)]_{\sim} \} ))]_\sim</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[TODO] Here we need to explain what D(x) means and why it's valid.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[TODO] Here we need to explain what D(x) means and why it's valid.</div></td></tr>
</table>
IssaRice