There is a bijection between the natural numbers (including 0) and the integers (positive, negative, 0). The bijection from N -> Z is n -> k if n = 2k OR n -> -k if n = 2k + 1.
For example, if n = 4, then k = 2 because 2(2) = 4. If n = 3, then k = -1 because 2(1) + 1 = 3.
My problem...
Let me elaborate on my question. Say that we have T l- S. In order to infer l- T -> S, what restrictions must be placed on the formulas? How does the deduction theorem for first order logic depend upon the rules of inference that are allowed?
When I said 'PA' I was referring to Presburger Arithmetic. As for the other point, what I meant is that an arbitrary sentence formulated in the language of Presburger Arithmetic is not decidable in first order logic with no assumptions, although it is decidable whether or not it follows from...
If I have P l- Q in FOL and P is closed, can I infer l- P -> Q. IIRC, this is valid as long as P is closed, but my memory is a little hazy. Is that how it works?
Let *PA* represent the conjunction of the non-logical axioms of Presburger arithmetic. So, what you're saying is that we have a way of determining for an arbitrary sentence S whether *PA* l- S. However, we can't determine for an arbitrary S whether or not l- S in first order logic with a...
There is another point that I don't get. The page says: "The set of first-order logical validities in a signature with equality and one unary function" is decidable. But isn't any theory with an n-ary function logically equivalent to a theory with an n+1-ary relation? For example, take some...
I always thought that first order logic with identity was undecidable if it had either a 2-place relation or a 2-place function. Wikipedia seems to confirm what I'd thought: "The set of logical validities in any first-order signature with equality and either: a relation symbol of arity no less...