In FOL, we often have functions which take as input some elements from the domain of discourse and give us another element from the domain of discourse. I'm looking into how to use FOL in the context of mathematics: set theory, arithmetic, etc.

The problem that I've noticed is that in mathematics, we often have functions (in the sense of FOL) which only output another element in the domain of discourse for certain inputs. For example, the function sqrt(x) will give another element in the domain when x is a nonnegative number, but not when x is negative.

I've only taken logic class and we used the book Language, Proof, and Logic. In this book they said that when constructing FOL languages, we should try to make functions refer to elements in the domain of discourse for any inputs.

How does FOL handle functions that don't produce an output for certain inputs?

  • Duplicate question on math.se: math.stackexchange.com/questions/845450/… – Not_Here Jul 29 '17 at 19:31
  • 1
    There are multiple ways to do what you're asking as are outlined in the question on math.se. Personally I would follow the suggestion of defining a predicate instead of a function. (It's a result due to Bertrand Russell that functions can be rewritten as predicates, e.g. F(x)=y is rewritten to Pxy=True) – Not_Here Jul 29 '17 at 19:45
  • The usual one-sorted FOL doesn't, but many-sorted FOL does. However, since any many-sorted FOL theory can be translated to a one-sorted FOL theory, textbooks tend not to mention the many-sorted version, since they are focused on studying FOL (it's easier to study a simpler system) rather than using FOL. Sadly, even textbooks that aim to teach beginners (of which LPL is a good one) end up pandering to the higher-level preference for one-sorted FOL, despite the reality that many-sorted FOL is more user-friendly. – user21820 Jun 7 at 7:53

Any function or relation symbol in any FOL is removable by expressing it as a predicate and adding a free variable for the output.

If we are using f(x, y, z) we can instead express it as F(x, y, z, o), where F is a predicate equivalent to o = f(x, y, x) and o is a free variable (which will be bound to the output).

So they are, in effect, present only as short-hand. Therefore, it does not matter what their semantics is -- whether we look at them as single-valued, whether they cover their domain, etc.

We don't need to fuss with the distinction between the function sqrt(x) and the relation x * x = y unless we really want to, if they are meant to be logically equivalent. We can easily allow the square root to be a function that simply has no output for negative numbers and even have it return both roots for positive values.

The function ultimately represents a reducible formula, and some formulas simply are true for no values in the domain. In that case, the free variable equivalent to the function's output can remain unbound, and no expressive power is lost.

  • Of course, if we have functionality but not totality, we can always add the axiom ∀x∀y∀z∀o∀o' F(x, y, z, o) ∧ F(x, y, z, o') → o = o' to enforce that the predicate F encodes indeed a partial function. – Uwe Aug 1 '17 at 21:42
  • That is the point of the 'even'. Yeah, all of these aspects are independent, if that was not clear enough. – user9166 Aug 2 '17 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.