What are the basic ideas behind the standard proof of the Lindenbaum's Lemma?

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

1

I have a question about Lindenbaum's Lemma for Propostitional Logic:

Any consistent set $Gamma$ of formulas is a subset of a maximal consistent set $Gamma^prime$ of formulas.

The outline of the proof (by Hunter's book) is the following:

1. By enumeration theorem, a machine can map the whole set of propositional formulas onto the set of natural numbers; let $phi_n$ the $n^th$ formula in this sense.



2. 
   

   Let recursively define the function $Gamma_n$ as

   
   
   
   • $Gamma_0=Gamma$,
   
   
   • $Gamma_n+1=Gamma_ncup phi_n+1$ if $Gamma_nnotvdashnegphi_n+1$ and $Gamma_n+1=Gamma_n$ otherwise.
   
   



3. Let $Gamma'$ be the union of $Gamma_0, Gamma_1, ..., Gamma_n, ...$



4. etc.

Ok! I understood it. But here is my trouble:

1. 
   

   It would be better if we could directly define $Gamma^prime$ like any set s.t. for any formula $phi$:

   
   
   
   • if neither $phi$ nor in $negphi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$;
   
   
   • if $phi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$
   
   
   • if $negphi$ can be deduced by $Gamma$ then $negphi$ is in $Gamma^prime$
   
   

   In fact with this definition the claim of the lemma is automatically verified! But, I know, something is wrong. However, in order to "accept" this proof, I need to find motivations to why one cannot shorten/simplify it.

   
   


2. Are steps 1-3 necessary because we cannot ensure otherwise the existence of the set $Gamma^'$?


3. If yes, are we using replacement axiom scheme in step 2 and union axiom in step 3?


4. If yes, what is the particular instance of the replacement axiom scheme that we are using? Namely, which is the actual, exact first-order formula we are considering?

Remark. I know that this is a metatheorem, and therefore its metaproof does not strictly depend by any formal theory (like ZFC is), however it is the current best justification for steps 1-3 that I found.
But I'm absolutely not conviced by this, I really need your help to understand.

Thank you!

logic set-theory

share|cite|improve this question

asked Jul 14 at 23:34

Michele Cirillo

393

add a comment | 

up vote
4
down vote

favorite

1

I have a question about Lindenbaum's Lemma for Propostitional Logic:

Any consistent set $Gamma$ of formulas is a subset of a maximal consistent set $Gamma^prime$ of formulas.

The outline of the proof (by Hunter's book) is the following:

1. By enumeration theorem, a machine can map the whole set of propositional formulas onto the set of natural numbers; let $phi_n$ the $n^th$ formula in this sense.



2. 
   

   Let recursively define the function $Gamma_n$ as

   
   
   
   • $Gamma_0=Gamma$,
   
   
   • $Gamma_n+1=Gamma_ncup phi_n+1$ if $Gamma_nnotvdashnegphi_n+1$ and $Gamma_n+1=Gamma_n$ otherwise.
   
   



3. Let $Gamma'$ be the union of $Gamma_0, Gamma_1, ..., Gamma_n, ...$



4. etc.

Ok! I understood it. But here is my trouble:

1. 
   

   It would be better if we could directly define $Gamma^prime$ like any set s.t. for any formula $phi$:

   
   
   
   • if neither $phi$ nor in $negphi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$;
   
   
   • if $phi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$
   
   
   • if $negphi$ can be deduced by $Gamma$ then $negphi$ is in $Gamma^prime$
   
   

   In fact with this definition the claim of the lemma is automatically verified! But, I know, something is wrong. However, in order to "accept" this proof, I need to find motivations to why one cannot shorten/simplify it.

   
   


2. Are steps 1-3 necessary because we cannot ensure otherwise the existence of the set $Gamma^'$?


3. If yes, are we using replacement axiom scheme in step 2 and union axiom in step 3?


4. If yes, what is the particular instance of the replacement axiom scheme that we are using? Namely, which is the actual, exact first-order formula we are considering?

Remark. I know that this is a metatheorem, and therefore its metaproof does not strictly depend by any formal theory (like ZFC is), however it is the current best justification for steps 1-3 that I found.
But I'm absolutely not conviced by this, I really need your help to understand.

Thank you!

logic set-theory

share|cite|improve this question

asked Jul 14 at 23:34

Michele Cirillo

393

add a comment | 

up vote
4
down vote

favorite

1

up vote
4
down vote

favorite

1

1

I have a question about Lindenbaum's Lemma for Propostitional Logic:

Any consistent set $Gamma$ of formulas is a subset of a maximal consistent set $Gamma^prime$ of formulas.

The outline of the proof (by Hunter's book) is the following:

1. By enumeration theorem, a machine can map the whole set of propositional formulas onto the set of natural numbers; let $phi_n$ the $n^th$ formula in this sense.



2. 
   

   Let recursively define the function $Gamma_n$ as

   
   
   
   • $Gamma_0=Gamma$,
   
   
   • $Gamma_n+1=Gamma_ncup phi_n+1$ if $Gamma_nnotvdashnegphi_n+1$ and $Gamma_n+1=Gamma_n$ otherwise.
   
   



3. Let $Gamma'$ be the union of $Gamma_0, Gamma_1, ..., Gamma_n, ...$



4. etc.

Ok! I understood it. But here is my trouble:

1. 
   

   It would be better if we could directly define $Gamma^prime$ like any set s.t. for any formula $phi$:

   
   
   
   • if neither $phi$ nor in $negphi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$;
   
   
   • if $phi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$
   
   
   • if $negphi$ can be deduced by $Gamma$ then $negphi$ is in $Gamma^prime$
   
   

   In fact with this definition the claim of the lemma is automatically verified! But, I know, something is wrong. However, in order to "accept" this proof, I need to find motivations to why one cannot shorten/simplify it.

   
   


2. Are steps 1-3 necessary because we cannot ensure otherwise the existence of the set $Gamma^'$?


3. If yes, are we using replacement axiom scheme in step 2 and union axiom in step 3?


4. If yes, what is the particular instance of the replacement axiom scheme that we are using? Namely, which is the actual, exact first-order formula we are considering?

Remark. I know that this is a metatheorem, and therefore its metaproof does not strictly depend by any formal theory (like ZFC is), however it is the current best justification for steps 1-3 that I found.
But I'm absolutely not conviced by this, I really need your help to understand.

Thank you!

logic set-theory

share|cite|improve this question

asked Jul 14 at 23:34

Michele Cirillo

393

I have a question about Lindenbaum's Lemma for Propostitional Logic:

Any consistent set $Gamma$ of formulas is a subset of a maximal consistent set $Gamma^prime$ of formulas.

The outline of the proof (by Hunter's book) is the following:

1. By enumeration theorem, a machine can map the whole set of propositional formulas onto the set of natural numbers; let $phi_n$ the $n^th$ formula in this sense.



2. 
   

   Let recursively define the function $Gamma_n$ as

   
   
   
   • $Gamma_0=Gamma$,
   
   
   • $Gamma_n+1=Gamma_ncup phi_n+1$ if $Gamma_nnotvdashnegphi_n+1$ and $Gamma_n+1=Gamma_n$ otherwise.
   
   



3. Let $Gamma'$ be the union of $Gamma_0, Gamma_1, ..., Gamma_n, ...$



4. etc.

Ok! I understood it. But here is my trouble:

1. 
   

   It would be better if we could directly define $Gamma^prime$ like any set s.t. for any formula $phi$:

   
   
   
   • if neither $phi$ nor in $negphi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$;
   
   
   • if $phi$ can be deduced by $Gamma$ then $phi$ is in $Gamma^prime$
   
   
   • if $negphi$ can be deduced by $Gamma$ then $negphi$ is in $Gamma^prime$
   
   

   In fact with this definition the claim of the lemma is automatically verified! But, I know, something is wrong. However, in order to "accept" this proof, I need to find motivations to why one cannot shorten/simplify it.

   
   


2. Are steps 1-3 necessary because we cannot ensure otherwise the existence of the set $Gamma^'$?


3. If yes, are we using replacement axiom scheme in step 2 and union axiom in step 3?


4. If yes, what is the particular instance of the replacement axiom scheme that we are using? Namely, which is the actual, exact first-order formula we are considering?

Remark. I know that this is a metatheorem, and therefore its metaproof does not strictly depend by any formal theory (like ZFC is), however it is the current best justification for steps 1-3 that I found.
But I'm absolutely not conviced by this, I really need your help to understand.

Thank you!

logic set-theory

share|cite|improve this question

asked Jul 14 at 23:34

Michele Cirillo

393

share|cite|improve this question

share|cite|improve this question

asked Jul 14 at 23:34

Michele Cirillo

393

asked Jul 14 at 23:34

Michele Cirillo

393

asked Jul 14 at 23:34

Michele Cirillo

393

393

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
8
down vote



accepted

Your set $Gamma'$ does not work. Consider a formula $phi$ such that neither $phi$ nor $neg phi$ can be deduced from $Gamma$. Then, by your definition, $phi$ will be in $Gamma'$. But letting $psi=negphi$, it is also true that neither $psi$ nor $negpsi$ can be deduced from $Gamma$. So $psi$ will also be in $Gamma'$. So both $phiinGamma'$ and $negphiinGamma'$, and $Gamma'$ is not consistent.

More generally, even if you modify your definition to avoid this specific issue, there is no guarantee that your set $Gamma'$ will be consistent. Each individual new formula you added is consistent with $Gamma$, but they may not be consistent with each other. That is why the recursive procedure of steps 1-3 is important, to guarantee that the set $Gamma'$ is actually consistent. It has nothing to do with being able to formally construct the set.

In detail, here is how you prove the set $Gamma'$ given by steps 1-3 is consistent. If it were inconsistent, some finite subset $FsubseteqGamma'$ would be inconsistent. Then for some $n$, $Fsubseteq Gamma_n$. But we can prove by induction on $n$ that $Gamma_n$ is consistent for all $n$ (since if $Snotvdash negphi$ then $Scupphi$ is consistent). This is a contradiction, and thus $Gamma'$ is consistent.

share|cite|improve this answer

edited Jul 15 at 9:08

Max

10.4k1836

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852053%2fwhat-are-the-basic-ideas-behind-the-standard-proof-of-the-lindenbaums-lemma%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
8
down vote



accepted

Your set $Gamma'$ does not work. Consider a formula $phi$ such that neither $phi$ nor $neg phi$ can be deduced from $Gamma$. Then, by your definition, $phi$ will be in $Gamma'$. But letting $psi=negphi$, it is also true that neither $psi$ nor $negpsi$ can be deduced from $Gamma$. So $psi$ will also be in $Gamma'$. So both $phiinGamma'$ and $negphiinGamma'$, and $Gamma'$ is not consistent.

More generally, even if you modify your definition to avoid this specific issue, there is no guarantee that your set $Gamma'$ will be consistent. Each individual new formula you added is consistent with $Gamma$, but they may not be consistent with each other. That is why the recursive procedure of steps 1-3 is important, to guarantee that the set $Gamma'$ is actually consistent. It has nothing to do with being able to formally construct the set.

In detail, here is how you prove the set $Gamma'$ given by steps 1-3 is consistent. If it were inconsistent, some finite subset $FsubseteqGamma'$ would be inconsistent. Then for some $n$, $Fsubseteq Gamma_n$. But we can prove by induction on $n$ that $Gamma_n$ is consistent for all $n$ (since if $Snotvdash negphi$ then $Scupphi$ is consistent). This is a contradiction, and thus $Gamma'$ is consistent.

share|cite|improve this answer

edited Jul 15 at 9:08

Max

10.4k1836

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

add a comment | 

up vote
8
down vote



accepted

Your set $Gamma'$ does not work. Consider a formula $phi$ such that neither $phi$ nor $neg phi$ can be deduced from $Gamma$. Then, by your definition, $phi$ will be in $Gamma'$. But letting $psi=negphi$, it is also true that neither $psi$ nor $negpsi$ can be deduced from $Gamma$. So $psi$ will also be in $Gamma'$. So both $phiinGamma'$ and $negphiinGamma'$, and $Gamma'$ is not consistent.

More generally, even if you modify your definition to avoid this specific issue, there is no guarantee that your set $Gamma'$ will be consistent. Each individual new formula you added is consistent with $Gamma$, but they may not be consistent with each other. That is why the recursive procedure of steps 1-3 is important, to guarantee that the set $Gamma'$ is actually consistent. It has nothing to do with being able to formally construct the set.

In detail, here is how you prove the set $Gamma'$ given by steps 1-3 is consistent. If it were inconsistent, some finite subset $FsubseteqGamma'$ would be inconsistent. Then for some $n$, $Fsubseteq Gamma_n$. But we can prove by induction on $n$ that $Gamma_n$ is consistent for all $n$ (since if $Snotvdash negphi$ then $Scupphi$ is consistent). This is a contradiction, and thus $Gamma'$ is consistent.

share|cite|improve this answer

edited Jul 15 at 9:08

Max

10.4k1836

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

add a comment | 

up vote
8
down vote



accepted

up vote
8
down vote



accepted

Your set $Gamma'$ does not work. Consider a formula $phi$ such that neither $phi$ nor $neg phi$ can be deduced from $Gamma$. Then, by your definition, $phi$ will be in $Gamma'$. But letting $psi=negphi$, it is also true that neither $psi$ nor $negpsi$ can be deduced from $Gamma$. So $psi$ will also be in $Gamma'$. So both $phiinGamma'$ and $negphiinGamma'$, and $Gamma'$ is not consistent.

More generally, even if you modify your definition to avoid this specific issue, there is no guarantee that your set $Gamma'$ will be consistent. Each individual new formula you added is consistent with $Gamma$, but they may not be consistent with each other. That is why the recursive procedure of steps 1-3 is important, to guarantee that the set $Gamma'$ is actually consistent. It has nothing to do with being able to formally construct the set.

In detail, here is how you prove the set $Gamma'$ given by steps 1-3 is consistent. If it were inconsistent, some finite subset $FsubseteqGamma'$ would be inconsistent. Then for some $n$, $Fsubseteq Gamma_n$. But we can prove by induction on $n$ that $Gamma_n$ is consistent for all $n$ (since if $Snotvdash negphi$ then $Scupphi$ is consistent). This is a contradiction, and thus $Gamma'$ is consistent.

share|cite|improve this answer

edited Jul 15 at 9:08

Max

10.4k1836

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

Your set $Gamma'$ does not work. Consider a formula $phi$ such that neither $phi$ nor $neg phi$ can be deduced from $Gamma$. Then, by your definition, $phi$ will be in $Gamma'$. But letting $psi=negphi$, it is also true that neither $psi$ nor $negpsi$ can be deduced from $Gamma$. So $psi$ will also be in $Gamma'$. So both $phiinGamma'$ and $negphiinGamma'$, and $Gamma'$ is not consistent.

More generally, even if you modify your definition to avoid this specific issue, there is no guarantee that your set $Gamma'$ will be consistent. Each individual new formula you added is consistent with $Gamma$, but they may not be consistent with each other. That is why the recursive procedure of steps 1-3 is important, to guarantee that the set $Gamma'$ is actually consistent. It has nothing to do with being able to formally construct the set.

In detail, here is how you prove the set $Gamma'$ given by steps 1-3 is consistent. If it were inconsistent, some finite subset $FsubseteqGamma'$ would be inconsistent. Then for some $n$, $Fsubseteq Gamma_n$. But we can prove by induction on $n$ that $Gamma_n$ is consistent for all $n$ (since if $Snotvdash negphi$ then $Scupphi$ is consistent). This is a contradiction, and thus $Gamma'$ is consistent.

share|cite|improve this answer

edited Jul 15 at 9:08

Max

10.4k1836

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

share|cite|improve this answer

share|cite|improve this answer

edited Jul 15 at 9:08

Max

10.4k1836

edited Jul 15 at 9:08

Max

10.4k1836

edited Jul 15 at 9:08

Max

10.4k1836

10.4k1836

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

answered Jul 14 at 23:50

Eric Wofsey

163k12189300

163k12189300

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852053%2fwhat-are-the-basic-ideas-behind-the-standard-proof-of-the-lindenbaums-lemma%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email