Tag Info

Hot answers tagged

4

The soundness property of a logical calculus means that if a formula $\phi$ is derivable form the set $\Gamma$ of premises (or assumptions) : $\Gamma \vdash \phi$, then $\phi$ is a logical consequence of the premises in $\Gamma$, according to the semantics suitable for that calculus : $\Gamma \vDash \phi$. The application of the said Lemma is ...


3

No theory containing at least the peano axioms can prove its own consistency (proven by Gödel). But there can be a stronger theory proving the consistency of the weaker theory. The catch is, to prove the consistency of the stronger theory, you need an even stronger one. ZFC is believed to be consistence and can be used to prove the consistency of PA. To be ...


1

A proof system is a Formal system with logical axiom (possibly none) and rules of inference (at least one). Some examples : Hilbert-style proof system : usually more than one (logical) axioms and few rules : modus ponens and generalization. See Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), page 109, for a system with few axioms ...


1

If you are going to bring in the question of bugs, then no: there is no way to use any program to prove any conjecture, ever. Even if it is open source, being able to look at the code doesn't insure it works properly. A bug could be inherent in the programming language even! If you are willing to trust software, then you need to make some theoretical ...


1

Mauro's answer is very helpful and clear. I'd just like to add to it one point. Granted the context of the lemma you mention, that lemma isn't just a restatement of soundness but a slight generalization. Recall that, roughly speaking, soundness says that derivability implies consequence. However, this rough statement is not strictly true for some ...


1

Just go back to the definition : $$ |x| = \left\{\begin{array} .x & \text{if} & x\geq 0 \\ -x & \text{if} & x< 0 \end{array} \right. $$ So if $x\geq 0, |x| = x \geq x $ if $x< 0, |x| = -x > 0 \geq x $ Hence $ \forall x \in \mathbb{R}, |x| \geq x$ Note that you can also define $|x| = \max\{ x, -x\}$ and the result is then ...


1

There are few natural examples of such theories, if any. This is because having enough constants is a very restrictive condition: for instance, any theory in a finite language with no finite models does not have enough constants. (By the way, things are a little better if we merely demand that whenever $T\vdash\exists x \varphi(x)$, there is a term $t$ such ...


1

It's nice question, and little hard too, and I think it's Olympiad question, I wounder from what Olympiad did you take this question?, This is my solution : Suppose that $f$ is reducible. Therefore it has a factor $g$ of degree $1$. Suppose that $g$ is symmetric. We may assume that $$g = x + y + z + k$$ for some constant $k.$ Now put $x = 0$, so $ y ...



Only top voted, non community-wiki answers of a minimum length are eligible