Timeline for Completeness of a set of propositional formulas [closed]
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2015 at 17:05 | history | closed |
Emil Jeřábek Carl Mummert Stefan Kohl♦ Peter Crooks Ricardo Andrade |
Not suitable for this site | |
| Feb 28, 2015 at 14:56 | comment | added | M a m a D | You are right, Fortunately their questions mostly relies on first order logic consistency and equivalence. Thank you | |
| Feb 28, 2015 at 14:48 | vote | accept | M a m a D | ||
| Feb 28, 2015 at 14:44 | comment | added | Emil Jeřábek | Well, your best bet then is to look at the kind of problems the entrance committee likes to give, and train how to solve them. There really isn’t a deterministic method. A case in point: let $\Sigma$ be the set of formulas in variables $p_n$, $n\ge2$, axiomatized by $\{p_n:n\text{ prime}\}\cup\{\neg p_n:n\text{ odd composite}\}\cup\{p_n\land p_m\to p_{n+m}:n,m\text{ odd}\}$. Is it complete? (This is a rhetorical question.) | |
| Feb 28, 2015 at 14:26 | comment | added | M a m a D | @EmilJeřábek I need to solve this problem in PhD entrance exam in the next week, I will have only 3 minutes to solve it that's why I was looking for a deterministic way. | |
| Feb 28, 2015 at 14:08 | comment | added | Emil Jeřábek | @Drupalist: The process is thinking. You have the set, you have the definition of completeness, so try to prove or disprove that the set satisfies the definition, or something equivalent. How to do that depends entirely on what you know about the set, there is no generally applicable answer. | |
| Feb 28, 2015 at 14:03 | comment | added | M a m a D | @JoelDavidHamkins that is right. | |
| Feb 28, 2015 at 14:01 | comment | added | Joel David Hamkins | @Drupalist For a consistent theory $\Sigma$, it is incomplete if and only if there are at least two rows in the truth table that satisfy $\Sigma$. Or, equivalently, if $\Sigma\cup\{p\}$ and $\Sigma\cup\{\neg p\}$ are both satisfiable for some propositional variable. In other words, it suffices to consider the case that $\phi$ in your statement is a propositional variable, since if $\Sigma$ settles the values of all variables, it settles all the sentences as well. | |
| Feb 28, 2015 at 13:55 | comment | added | M a m a D | @CarlMummert despite of being decidable or semi-decidable what is the process of determining the completeness of a set? | |
| Feb 28, 2015 at 13:44 | review | Close votes | |||
| Feb 28, 2015 at 17:05 | |||||
| Feb 28, 2015 at 13:35 | answer | added | Joel David Hamkins | timeline score: 3 | |
| Feb 28, 2015 at 13:35 | comment | added | Carl Mummert | I have voted to put this on-hold because it is not about research level mathematics - this question would be a better fit on mathematics.stackexchange.com. In any event: when we have a finite set of variables and a finite set of formulas, it is trivially decidable whether the set is complete, by using truth tables. When the set of formulas may be infinite, it is not decidable whether a given set is complete, by a simple diagonalization argument. | |
| Feb 28, 2015 at 13:31 | comment | added | M a m a D | How?! any inconsistent set of formulas is complete while it has no model | |
| Feb 28, 2015 at 13:29 | comment | added | Emil Jeřábek | Incompleteness is equivalent to having at least two satisfying assignment, hence it is NP-complete by a trivial reduction from SAT. | |
| Feb 28, 2015 at 13:17 | history | undeleted | M a m a D | ||
| Feb 28, 2015 at 13:09 | history | deleted | M a m a D | via Vote | |
| Feb 28, 2015 at 13:06 | review | First posts | |||
| Feb 28, 2015 at 13:07 | |||||
| Feb 28, 2015 at 13:01 | history | asked | M a m a D | CC BY-SA 3.0 |