1
$\begingroup$

Suppose we want to formalise some parts of mathematics within set theory, which is itself formalised in a first-order language (in the standard way). Logic is assumed to be classical. In particular, this means that – at the level of semantics – every term must have a denotation, which in turn means that every function must have as its domain the entire universe of the model (or its Cartesian product, if it has more than one argument). Let’s say that we construct within our set theory natural numbers, then integers, rational numbers and real numbers (in the standard way). At some point we would like to consider, for example, functions from real numbers to real numbers. However, if we just introduce a functional symbol to the language, then the corresponding function has to have as its domain the entire universe of set theory, not just real numbers. How to deal with this issue? Here are some options that I find unsatisfactory:

(1) Consider the theory of real numbers only, not the entire set theory – then every model of this theory will be just a set of all real numbers. This is fine if we are interested in real numbers only. However, if we are going to consider other set-theoretic constructions that are not real numbers, then we should better stay within full set theory. And even if we want to restrict to real numbers only, there will be functions that are not defined on all real numbers, such as division, which is not defined if the second argument is $0$.

(2) Change classical logic into free logic (which allows terms without denotation; cf. here and here) or many-sorted logic (which allows functions with different domains, depending on the type of a function). This is unsatisfactory mainly because using functions with domain that is not the entire universe of the model is commonplace in mathematics but the official logic of mathematics seems to be classical first-order logic, so there should be some solution within it. In any case, I am just interested in solutions within classical first-order logic.

(3) Choose some arbitrary object as the value of the function for the arguments for which we want it to be ill-defined (cf. here). This is unsatisfactory because it is commonplace in mathematics to talk about functions on some restricted domain, not about functions that work as we want on the intended domain and arbitrarily elsewhere. For example, when we write $f : \mathbb{N} \to \mathbb{R}$, we really mean a function whose domain is exactly $\mathbb{N}$.

(4) Use relational symbols to simulate functions (cf. here). This sounds promising because this is in agreement with how functions are defined in set theory. However, this also is unsatisfactory because when we write mathematical formulas, we use functional symbols and we use terms such as $f(x)$.

Perhaps we can think about functional notation as an abbreviation for relational notation. For example, if we write $f(x)=y$, we really mean $R_f (x, y)$ for some relation $R_f$ satisfying $\forall_x \left[\left( \forall_y \neg R(x,y) \right) \vee \left(\exists!_y R(x,y)\right)\right]$. However, it is not clear to me how then should we think about formulas of a more complex form, such as $g(f(x), f(y)) = z$.

I believe that there should be some solution that is both fully correct formally and does justice to the usual practice. Perhaps some variant of option (4) would work but more details are needed.

$\endgroup$
5
  • 3
    $\begingroup$ When you formalise maths in set theory and you want to talk about a function $f: \Bbb R \to \Bbb R$ there's no essential need to do any 1-4. This is because functions can be implemented as sets of ordered pairs, so $f$ doesn't need to be a "genuine function" on the level of the meta-theory - it's just an element of $V$. Note that when I make a statement $\phi(f(x))$ this is really shorthand for $(\exists y)((x, y) \in f \land \phi(y))$, which it seems like you're worried about. I'm not totally sure what you find so unsatisfactory about 3, though. What problems do you think it causes? $\endgroup$ Commented Mar 28 at 11:26
  • 1
    $\begingroup$ You may want to read math.stackexchange.com/q/3727287/473276 and math.stackexchange.com/a/2103894/473276. I think maybe a key insight for you is that the implementation of "function" is separate from what a function "actually is". So if you really want to introduce a single function symbol referring to a specific function on the reals, you can do that. I think the real problem is that we'd like to be able to talk about "the set of all functions from $A$ to $B$" sometimes. $\endgroup$ Commented Mar 28 at 11:29
  • 2
    $\begingroup$ A compromise can be "many-sorted logic" like that used informally by T.Tao's Analysis textbook. $\endgroup$ Commented Mar 28 at 12:22
  • $\begingroup$ I suggest formally introducing a function f mapping elements of set A to the elements of set B as follows: ∀x:[x∈A⟹f(x)∈B] , or equivalently, ∀ x:[x∈A⟹∃y:[y∈B∧y=f(x)]] . $\endgroup$ Commented Mar 28 at 18:00
  • 1
    $\begingroup$ Many-sorted logic is the best way forward and I don't understand your objections to it. It is much closer to standard mathematical practice than untyped set theory. Large parts of mathematics have been formalised in mechanized theorem proving systems like Coq, Isabelle, HOL and Mizar, and of these only Mizar is untyped. $\endgroup$
    – Rob Arthan
    Commented Mar 29 at 20:30

1 Answer 1

1
$\begingroup$

If you are working within set theory, "function" does not mean the same as "function-symbol". (Dan Christensen's suggestion is wrong.) If you work within any reasonable foundational system based on ZFC (e.g. this one), a function f ∈ ℝ→ℝ is simply a set of a certain kind that encodes the mappings. One common encoding is that it is a set of pairs from ℝ×ℝ where each pair ⟨x,y⟩ ∈ f means that f(x) = y. Division on ℝ is a function from ℝ∖{0}→ℝ; nothing problematic with that.

By the way, if you want to learn proper mathematics, you need to stop trying to rely on anything from philosophy such as "every term must have a denotation", as that would simply be detrimental to your learning and useless for genuine mathematics.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .