Timeline for Embedding of consistent subset in first order logic (finitely many variables)
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 23, 2013 at 17:13 | comment | added | Noel Vaillant | Regarding the fact that satisfiability of $\Gamma$ is preserved through $f:V\to W$, apart from the variable capture/essential caveats, i should have assumed $f$ injective there too. I simply need to find a variable assignment $b:W\to M$ such that $a=b\circ f$ and apply the substitution lemma $\beta(f(\phi))(b)=\beta(\phi)(b\circ f)$ ($f$ avoids capture in $\phi$) (the truth value of $f(\phi)$ in model $M$ under assignment $b$ is the same as truth value of $\phi$ in model $M$ under assignment $b\circ f$. | |
| Aug 23, 2013 at 13:23 | comment | added | Noel Vaillant | The real issue is that my question is precisely motivated by Godel's completeness theorem which I want to establish in this setting, and for which I need consistency to be preserved through embedding. So I do have satisfiable => consistent (from soundness) but not the other side of the implication. So it is too early to attempt a semantic argument :) Needless to say I am still very grateful for the time you have spent thinking about this. | |
| Aug 23, 2013 at 13:18 | comment | added | Noel Vaillant | @ Noah on the second part, I agree with your conclusion that if $\Gamma$ is satisfiable (There is an $(M,r)$ $r$ binary on $M$ and a variable assignment $a:V\to M$ such that $M\vDash\phi[a]$ for all $\phi\in\Gamma$), then so is $f(\Gamma)$, for all $f:V\to W$, provided the associated $f:{\bf P}(V)\to{\bf P}(W)$ avoids capture on every element of $\Gamma$ (or is regarded as 'essential' which is what you implicitly assume, and which works fine when $W$ is infinite set or $|V|\leq|W|$). The real issue is.... | |
| Aug 23, 2013 at 12:53 | comment | added | Noel Vaillant | On the initial part of your answer, we do require $f:V\to W$ to be injective. However, formulas may have free variables so you could even choose $\Gamma=\{x E y, (y E y)\to\bot\}$ to make your point. Consistency cannot realistically be preserved without injectivity. More to come on your second part. | |
| Aug 23, 2013 at 6:20 | comment | added | Noah Schweber | It just occurred to me that most of my answer is vacuous: if we disallow negation, then we're looking at positive sentences only, and any set of positive sentences is consistent. :P | |
| Aug 23, 2013 at 4:29 | comment | added | Noel Vaillant | yes $V$ nonempty is fine, I can treat the case separately. Thank you very much for this. Will study your answer carefully and revert. | |
| Aug 23, 2013 at 1:11 | comment | added | Noah Schweber | I suppose I'm implicitly assuming, in the latter part, that $V$ is nonempty. But I don't imagine that we care about this. | |
| Aug 23, 2013 at 1:04 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 254 characters in body
|
| Aug 23, 2013 at 0:59 | history | answered | Noah Schweber | CC BY-SA 3.0 |