3
$\begingroup$

Is it true that for all proofs $\forall x \exists y : R(x, y)$, then $y = y(x)$?

A while back I remember reading a book on functional programming that was leading into some questions about what exactly mathematical proofs were and how they were related to functions. In fact, I just found the book: link to PDF, page 16 (marked page 3).

The author mentions that if we have a proof that $\forall x \exists y : R(x, y)$, then, in a sense, because $x$ is bound before $y$, then $y$ is dependent on $x$, and therefore $y = y(x)$. There may be counterexamples. Perhaps $y$ is a constant itself, but then $y(x)$ can also just be a constant function. I'm trying to understand under what circumstances this is not true.

Example:

Let $f : \mathbb {R}^n \to \mathbb R$ be continuous at a point $\vec{v_0}$ and $f(\vec{v_0}) = A < 0$. Prove that there exists a number $\delta > 0$ such that if $\| \vec{v} - \vec{v_0} \| < \delta $ then $f(\vec{v}) < 0$.

My argument was simply to use the statement of continuity at $\vec{v_0}$ to prove this. That is, since $f$ is continuous, the following holds:

$ \forall \epsilon > 0 \quad \exists \delta > 0 : \quad \| \vec{v} - \vec{v_0} \| < \delta \Rightarrow \| f(\vec{v}) - f(\vec{v_0}) \| < \epsilon .$

So, as referred to above, we must have $\delta = \delta(\epsilon)$. Then we can make the replacement $\delta = \delta(|A|)$, and we have the necessary $\delta$ to prove that $f(\vec{v}) < 0$.

I have one main question (the one that closes this), and one side question.

  1. Under what conditions can we assume that $\forall x \exists y : R(x, y)$, then $y = y(x)$?

    Are there indirect ways to prove a proposition of the form $\forall x \exists y : R(x, y)$ where $y$ is somehow not dependent on $x$ and also not a constant? Perhaps it varies on $R$, but that is given, I suppose. Certainly all $\epsilon$-$\delta$ proofs that I've come across have been constructive in this way.

  2. Is there a canonical way to prove the proposition above?

    I actually struggled with a possible proof for a while before I came up with the technique above. I used this technique in a HW assignment and on my latest Advanced Calculus test. The HW was marked as correct although with the note that it was "indirect", while the test was marked as wrong. Granted, the HW was done by the TA, the test by my prof. I personally don't see a more "direct" way to prove this result.

  • 2
    @muad: $y=y(x)$ is not meaningless: it is the standard notation!2010-10-28

2 Answers 2

16

You seem to be asking: if for every $x$ there is a $y$ for which $R(x,y)$ holds, can we then define a function $f$ (in the usual sense) such that for every $x$, $R(x,f(x))$ holds?

From a set-theoretic point of view, that statement is in fact none other than the Axiom of Choice.

The Axiom of Choice has many forms, but one form is the following: given a nonempty family of nonempty sets, $S_i$ with $i\in I$ ("nonempty family" means that $I$ is not empty, so we have some sets; "nonempty sets" means that each $S_i$ is not empty), there exists a "choice function": a way to select for each $i\in I$ an element of the corresponding $S_i$. Formally, there exists a function $f\colon I\to \cup S_i$ from the index set to the union of the sets, with the property that $f(i)\in S_i$ for each $i$.

Suppose that by assumption, for every $x$ in our universe $X$, the set $S_x = \{y\mid R(x,y)\}$ is nonempty, and you have a function $f$ with the desried property. The function $f$ will be a "choice function": a function $f:X \to \cup_{x\in U}S_x$ such that for each $x\in X$, $f(x)\in S_x$. Conversely, a choice function for the family $\{S_x\}_{x\in X}$ will yield and $f$ with the desired property. The existence of such functions for every nonempty family of nonempty sets is precisely the Axiom of Choice. Conversely, suppose that the Axiom of Choice fails, and let $\{S_x\}_{x\in X}$ be a nonempty family of nonempty sets for which no choice function exists. Then let $R(x,y)$ be "$y$ is in $S_x$". For every $x$ there exists a $y$ such that $R(x,y)$, since $S_x\neq\emptyset$. But since we are assuming that the family has no choice function, there does not exist any function $f$ such that for every $x$, $f(x)$ is in $S_x$. Thus, the question not only depends on the Axiom of Choice, but is equivalent to the Axiom of Choice.

In some circumstances, the exact nature of the sets $S_x$ mean that you do not need to invoke the Axiom of Choice, because we have some "natural way" of defining the choice. For instance, if every set $S_x$ is a subset of the natural numbers, then you can define $f(x)$ to be "the least element of $S_x$". Another standard example is when $S_x$ is a singleton for every $x$; that is, for each $x$ there exists one and only one $y$ for which $R(x,y)$ holds. In that case, you can define your function $f$ to be "$f(x)$ is the unique $y$ for which $R(x,y)$ holds".

But in general, the Axiom of Choice is, in some sense, "inherently non-constructive". And the thing is, the Axiom of Choice is independent of the usual axioms of set theory. Like the parallel postulate in geometry, you can accept it or not at your taste (the consequences of accepting and of not accepting it are different; for example, if you accept the Axiom of Choice, then that means that there is a way to slice a ball of radius 1 into a finite number of parts, and then rearrange the parts without changing their shape or size, into two balls of radius of 1; this is called the Banach-Tarski paradox; on the other hand, if you want all your vector spaces to have bases, then you must accept the Axiom of Choice. In short, it has good consequences and weird/bad consequences).

Edit: In the situation you have, it is possible to describe a function that will work; however, the "description" is a bit like cheating, in the sense that you can give an explicit rule for what the value of the function will be, but in practice it would be difficult to actually find the value. Namely, for every $\epsilon\gt 0$ you know that the set of $\delta\gt 0$ for which the implication $||v-v_0||\lt\delta\Rightarrow ||f(v)-f(v_0)||\lt\epsilon$ holds is nonempty. In particular, by the Archimedean property, the set $A_{\epsilon}=\{n\in\mathbb{N}| ||v-v_0||\lt\frac{1}{n} \Rightarrow ||f(v)-f(v_0)||\lt\epsilon\}$ is nonempty. This is a nonempty set of positive integers, so it has a least element. You can then define your function $\mathbf{f}\colon (0,\infty)\to(0,\infty)$ by the "formula" $\mathbf{f}(\epsilon)=1/\min(A_{\epsilon})$, the reciprocal of the smallest $n$ in the set. This definition would not require you to invoke the Axiom of Choice.

As to your question 2: you almost had it, I think, but you should not invoke (implicitly) the Axiom of Choice: pick a specific $\epsilon$ (for example, $|A|/2$). You know that there exists a $\delta\gt 0$ that works for that epsilon, so you pick any $\delta_0$ that works and use that. That would be the standard way of proving the proposition at hand. If you assume you have some kind of "black-box function" that will hand you a $\delta$ whenever you hand it an $\epsilon$, you are invoking the Axiom of Choice and you are making your proof somewhat non-constructive.

  • 0
    @robinhoode: As I point out in the text, at least in standard set theory this proposition *is* AC (it is *equivalent* to AC). It cannot be proven without AC unless you are working in a different set theory; in which case, many of the things you think you know about the reals might turn out to not hold in that theory.2010-10-29
2

Some texts define a relation as simply a set of ordered pairs and a function as a set of ordered pairs in which every first element is unique. So if for all $x$ there is a unique $y$ such that $R(x,y)$, then you can say you have a function $y(x)$. You have not specified that y has to be unique.

I'm not sure what you mean by "prove a relation" under question 1. Your proof seems fine to me.

  • 0
    @Srivatsan: Thanks2011-11-04