Dtjytyk

Co-worker team leader wants to inject his friend's awful software into our development. What should I say to our common boss?

Why doesn't the EU now just force the UK to choose between referendum and no-deal?

Does splitting a potentially monolithic application into several smaller ones help prevent bugs?

Professor being mistaken for a grad student

2D counterpart of std::array in C++17

Official degrees of earth’s rotation per day

Counting certain elements in lists

Unreachable code, but reachable with exception

How to deal with a cynical class?

Where is the 1/8 CR apprentice in Volo's Guide to Monsters?

How to explain that I do not want to visit a country due to personal safety concern?

RegionDifference for Cylinder and Cuboid

Know when to turn notes upside-down(eighth notes, sixteen notes, etc.)

How can I change step-down my variable input voltage? [Microcontroller]

Who is our nearest planetary neighbor, on average?

Replacing Windows 7 security updates with anti-virus?

Welcoming 2019 Pi day: How to draw the letter π?

When do we add an hyphen (-) to a complex adjective word?

Can hydraulic brake levers get hot when brakes overheat?

Theorems like the Lovász Local Lemma?

Why would a flight no longer considered airworthy be redirected like this?

Identifying the interval from A♭ to D♯

PlotLabels with equations not expressions

How to simplify this time periods definition interface?

Gödel's Incompleteness Theorem - Diagonal Lemma

Proving and understanding the Fixed point lemma (Diagonal Lemma) in Logic - used in proof of Godel's incompleteness theoremUnpacking the Diagonal LemmaDifferences between between concepts related to Gödel's Incompleteness theorems: self-referencing, diagonalization and fixed point theorem?Diagonal Lemma justificationDiagonal lemma in Godel Incompleteness TheoremAbout Gödel's Incompleteness TheoremGödel's Incompleteness Theorem in “Gödel, Escher, Bach”Proving $square(forall v_1negpsi(v_1))rightarrowforall v_1negpsi(v_1)$ for a particular $psi$.Alternative approach in self-referential step of the proof of Gödel's first incompleteness theoremCan an error be found in this proof of Gödel's incompleteness theorem?Gödel diagonalization and formulas not holding for themselves

2

1

$begingroup$

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $phi$ that spoke about itself? Can't this formula be built this way:

Diagonal Function. Let $D(x, y)$ be the diagonal function, such that $D$ returns the result obtained by replacing the formula with Gödel number $y$ for all free occurrences of $a$ in the formula with Gödel number $x$.

Example. Let $psi(a)$ be a formula that affirms that some formula with the Gödel number of $a$ is closed (has no free variables) and $k$ be it's Gödel number. Using Diagonal Function to construct a formula, by applying $D(k, k) = j$, the Gödel number $j$ will already be the Gödel number of a formula affirming that the formula itself has no free variables. I mean, $ulcorner psi(ulcorner psi(a) urcorner) urcorner = j$, or $ulcorner psi(overline{k}) urcorner = j$.

What i am missing here?

logic incompleteness

share|cite|improve this question

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you referring to a particular exposition of Gödel's work? His own original article does not name any "Diagonal Lemma" or "Fixed Point Theorem" -- its lemmas and theorems are simply numbered.
  $endgroup$
  – Henning Makholm
  Jun 2 '12 at 15:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are right, i'm referring to Mendelson's (Introduction to Mathematical Logic) exposition on the subject.
  $endgroup$
  – felipegf
  Jun 2 '12 at 15:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So you're using $D(u,u)$ for what Mendelson (fourth edition, section 3.5) just calls $D(u)$?
  $endgroup$
  – Henning Makholm
  Jun 2 '12 at 15:10
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I didn't wanted to define $sub$, but i wanted everyone to see that in fact $D(x,y)$ just replaces all free occurrences of a free variable $a$ (in the $sub$ predicate the Gödel number of the free variable is passed as an argument) in the Gödel number of a formula $x$ for the formula (whose Gödel number is) $y$. In fact, $D(u, u)$ is equivalent to $D(u)$.
  $endgroup$
  – felipegf
  Jun 2 '12 at 15:18
  
  
  

  
  
  
  

add a comment | 

2

1

$begingroup$

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $phi$ that spoke about itself? Can't this formula be built this way:

Diagonal Function. Let $D(x, y)$ be the diagonal function, such that $D$ returns the result obtained by replacing the formula with Gödel number $y$ for all free occurrences of $a$ in the formula with Gödel number $x$.

Example. Let $psi(a)$ be a formula that affirms that some formula with the Gödel number of $a$ is closed (has no free variables) and $k$ be it's Gödel number. Using Diagonal Function to construct a formula, by applying $D(k, k) = j$, the Gödel number $j$ will already be the Gödel number of a formula affirming that the formula itself has no free variables. I mean, $ulcorner psi(ulcorner psi(a) urcorner) urcorner = j$, or $ulcorner psi(overline{k}) urcorner = j$.

What i am missing here?

logic incompleteness

share|cite|improve this question

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you referring to a particular exposition of Gödel's work? His own original article does not name any "Diagonal Lemma" or "Fixed Point Theorem" -- its lemmas and theorems are simply numbered.
  $endgroup$
  – Henning Makholm
  Jun 2 '12 at 15:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are right, i'm referring to Mendelson's (Introduction to Mathematical Logic) exposition on the subject.
  $endgroup$
  – felipegf
  Jun 2 '12 at 15:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So you're using $D(u,u)$ for what Mendelson (fourth edition, section 3.5) just calls $D(u)$?
  $endgroup$
  – Henning Makholm
  Jun 2 '12 at 15:10
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I didn't wanted to define $sub$, but i wanted everyone to see that in fact $D(x,y)$ just replaces all free occurrences of a free variable $a$ (in the $sub$ predicate the Gödel number of the free variable is passed as an argument) in the Gödel number of a formula $x$ for the formula (whose Gödel number is) $y$. In fact, $D(u, u)$ is equivalent to $D(u)$.
  $endgroup$
  – felipegf
  Jun 2 '12 at 15:18
  
  
  

  
  
  
  

add a comment | 

$begingroup$

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $phi$ that spoke about itself? Can't this formula be built this way:

Diagonal Function. Let $D(x, y)$ be the diagonal function, such that $D$ returns the result obtained by replacing the formula with Gödel number $y$ for all free occurrences of $a$ in the formula with Gödel number $x$.

Example. Let $psi(a)$ be a formula that affirms that some formula with the Gödel number of $a$ is closed (has no free variables) and $k$ be it's Gödel number. Using Diagonal Function to construct a formula, by applying $D(k, k) = j$, the Gödel number $j$ will already be the Gödel number of a formula affirming that the formula itself has no free variables. I mean, $ulcorner psi(ulcorner psi(a) urcorner) urcorner = j$, or $ulcorner psi(overline{k}) urcorner = j$.

What i am missing here?

logic incompleteness

share|cite|improve this question

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

$endgroup$

share|cite|improve this question

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

share|cite|improve this question

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

asked Jun 2 '12 at 1:20

felipegffelipegf

8718

2 Answers
2

active

oldest

votes

1

$begingroup$

If I understand your notation correctly, the formula (whose Gödel number is) $j$ does not assert that $j$ itself has no free variables, merely that $psi(a)$ (which is different from $j$ itself) has no free variables. Which, incidentally, is false because it has $a$ as a free variable.

share|cite|improve this answer

edited Jun 2 '12 at 15:12

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are right, thank you very much. Do you have any reference on why the diagonal lemma is named after Cantor's diagonal argument?
  $endgroup$
  – felipegf
  Jun 4 '12 at 4:05
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

The "diagonal lemma" (also called "diagonalization lemma", "self-referential lemma” and “fixed-point lemma”) is a generalization (see below (Carnap 1934)) of Gödel's argument. Gödel attributed that generalization to Carnap in the references (Gödel 1934) and (Gödel 1986) given below. Gödel proved the special case of that lemma where the unary relation is "not Bew(x)".

R. Carnap: Logische Syntax der Sprache, Vienna: Julius Springer, 1934

K. Gödel: On Undecidable Propositions of Formal Mathematical Systems, lecture notes taken by S. Kleene and J. Rosser, 1934

K. Gödel: Review of Carnap 1934, in: Gödel: Collected Works I. Publications 1929–1936, S. Feferman et al. editors, Oxford University Press, 1986 p. 389

share|cite|improve this answer

answered Mar 10 at 13:54

François BryFrançois Bry

437

New contributor

François Bry is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure that I see how this answers the question---could you perhaps clarify that a bit? By my reading, the original asker wants to understand why the diagonal lemma is needed. As far as I can tell, you have provided references which explain what the diagonal lemma is. The references may be relevant, but they seem orthogonal to the question itself.
  $endgroup$
  – Xander Henderson
  Mar 10 at 14:15
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f152703%2fg%25c3%25b6dels-incompleteness-theorem-diagonal-lemma%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

If I understand your notation correctly, the formula (whose Gödel number is) $j$ does not assert that $j$ itself has no free variables, merely that $psi(a)$ (which is different from $j$ itself) has no free variables. Which, incidentally, is false because it has $a$ as a free variable.

share|cite|improve this answer

edited Jun 2 '12 at 15:12

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are right, thank you very much. Do you have any reference on why the diagonal lemma is named after Cantor's diagonal argument?
  $endgroup$
  – felipegf
  Jun 4 '12 at 4:05
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

If I understand your notation correctly, the formula (whose Gödel number is) $j$ does not assert that $j$ itself has no free variables, merely that $psi(a)$ (which is different from $j$ itself) has no free variables. Which, incidentally, is false because it has $a$ as a free variable.

share|cite|improve this answer

edited Jun 2 '12 at 15:12

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are right, thank you very much. Do you have any reference on why the diagonal lemma is named after Cantor's diagonal argument?
  $endgroup$
  – felipegf
  Jun 4 '12 at 4:05
  
  
  

  
  
  
  

add a comment | 

$begingroup$

If I understand your notation correctly, the formula (whose Gödel number is) $j$ does not assert that $j$ itself has no free variables, merely that $psi(a)$ (which is different from $j$ itself) has no free variables. Which, incidentally, is false because it has $a$ as a free variable.

share|cite|improve this answer

edited Jun 2 '12 at 15:12

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

$endgroup$

share|cite|improve this answer

edited Jun 2 '12 at 15:12

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

answered Jun 2 '12 at 15:05

Henning MakholmHenning Makholm

242k17308549

1

$begingroup$

The "diagonal lemma" (also called "diagonalization lemma", "self-referential lemma” and “fixed-point lemma”) is a generalization (see below (Carnap 1934)) of Gödel's argument. Gödel attributed that generalization to Carnap in the references (Gödel 1934) and (Gödel 1986) given below. Gödel proved the special case of that lemma where the unary relation is "not Bew(x)".

R. Carnap: Logische Syntax der Sprache, Vienna: Julius Springer, 1934

K. Gödel: On Undecidable Propositions of Formal Mathematical Systems, lecture notes taken by S. Kleene and J. Rosser, 1934

K. Gödel: Review of Carnap 1934, in: Gödel: Collected Works I. Publications 1929–1936, S. Feferman et al. editors, Oxford University Press, 1986 p. 389

share|cite|improve this answer

answered Mar 10 at 13:54

François BryFrançois Bry

437

New contributor

François Bry is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure that I see how this answers the question---could you perhaps clarify that a bit? By my reading, the original asker wants to understand why the diagonal lemma is needed. As far as I can tell, you have provided references which explain what the diagonal lemma is. The references may be relevant, but they seem orthogonal to the question itself.
  $endgroup$
  – Xander Henderson
  Mar 10 at 14:15
  

  
  
  
  

add a comment | 

1

$begingroup$

The "diagonal lemma" (also called "diagonalization lemma", "self-referential lemma” and “fixed-point lemma”) is a generalization (see below (Carnap 1934)) of Gödel's argument. Gödel attributed that generalization to Carnap in the references (Gödel 1934) and (Gödel 1986) given below. Gödel proved the special case of that lemma where the unary relation is "not Bew(x)".

R. Carnap: Logische Syntax der Sprache, Vienna: Julius Springer, 1934

K. Gödel: On Undecidable Propositions of Formal Mathematical Systems, lecture notes taken by S. Kleene and J. Rosser, 1934

K. Gödel: Review of Carnap 1934, in: Gödel: Collected Works I. Publications 1929–1936, S. Feferman et al. editors, Oxford University Press, 1986 p. 389

share|cite|improve this answer

answered Mar 10 at 13:54

François BryFrançois Bry

437

New contributor

François Bry is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure that I see how this answers the question---could you perhaps clarify that a bit? By my reading, the original asker wants to understand why the diagonal lemma is needed. As far as I can tell, you have provided references which explain what the diagonal lemma is. The references may be relevant, but they seem orthogonal to the question itself.
  $endgroup$
  – Xander Henderson
  Mar 10 at 14:15
  

  
  
  
  

add a comment | 

$begingroup$

The "diagonal lemma" (also called "diagonalization lemma", "self-referential lemma” and “fixed-point lemma”) is a generalization (see below (Carnap 1934)) of Gödel's argument. Gödel attributed that generalization to Carnap in the references (Gödel 1934) and (Gödel 1986) given below. Gödel proved the special case of that lemma where the unary relation is "not Bew(x)".

R. Carnap: Logische Syntax der Sprache, Vienna: Julius Springer, 1934

K. Gödel: On Undecidable Propositions of Formal Mathematical Systems, lecture notes taken by S. Kleene and J. Rosser, 1934

K. Gödel: Review of Carnap 1934, in: Gödel: Collected Works I. Publications 1929–1936, S. Feferman et al. editors, Oxford University Press, 1986 p. 389

share|cite|improve this answer

answered Mar 10 at 13:54

François BryFrançois Bry

437

New contributor

François Bry is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

answered Mar 10 at 13:54

François BryFrançois Bry

437

New contributor

François Bry is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Mar 10 at 13:54

François BryFrançois Bry

437

New contributor

François Bry is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Mar 10 at 13:54

François BryFrançois Bry

437