4
$\begingroup$

I had a lecture concerning axiom of choice, and the teacher says that an equivalent property is that surjective maps are invertible at right. After, as an example, we had the function $\sqrt x$. The example goes as follow : $x\mapsto x^2$ is surjective $\mathbb R\to \mathbb R^+$. We are looking for function $f:\mathbb R^+\to \mathbb R$ s.t. $f(x)^2=x$. There are infinitely many such function, and there existence require axiom of choice. Strictly speaking, $x\mapsto \sqrt x$ is rather a representative of the class of the function $f$ s.t. $f(x)^2=x$ than a function

Question : For fix $x$, the equation $y^2=x$ has always $2$ solutions. Let denote $A_x=\{y\mid y^2=x\}$. Let $g(x)=\max A_x$. Then, $g(x)$ is really a function and not a representative. Moreover, I didn't need axiom of choice, right ? So why should we see an inverse as a representative class rather than as a function ?

$\endgroup$
  • $\begingroup$ I think you make things very complicated. $\sqrt{\cdot }:\mathbb R^+\to \mathbb R^+$ is the unique inverse of $x^2$. Why do you need axiom of choice ? $\endgroup$ – user657324 Apr 10 at 7:48
  • $\begingroup$ @user657324: First, the inverse should go from $\mathbb R^+\to \mathbb R$. And why did you that $\sqrt{\cdot }$ as the inverse of $x^2$ on $\mathbb R^+\to \mathbb R^+$ ? (I guess you then prolonge the do-domain to $\mathbb R$). There is at my opinion no reason to talk this inverse rather an other one... $\endgroup$ – user659895 Apr 10 at 7:50
  • $\begingroup$ It's by definition ! $\sqrt \cdot : \mathbb R^+\to \mathbb R^+$... no need axiom of choice for that. I don't get what is not clear for you... $\endgroup$ – user657324 Apr 10 at 7:52
  • $\begingroup$ @user657324 : No. The problem comes from the infinitely many choices of inverses for the function $\sqrt{}: \mathbb{R^+} \rightarrow \mathbb{R}$. For each $y \in \mathbb{R}$, there are two choices $\pm x \in \mathbb{R}$ for preimages. Selecting a full collection of preimages requires infinitely many choices (if the elements of each set of preimages are "indistinguishable": paraphrasing Bertrand Russell: "To choose one sock from each of infinitely many pairs of socks requires the Axiom of Choice. For one from each of infinitely many pairs of shoes, the Axiom is not needed.") $\endgroup$ – Eric Towers Apr 10 at 7:53
4
$\begingroup$

We can prove, without the axiom of choice, that $A_x=\{y\in\Bbb R\mid y^2=x\}$ has at most $2$ elements for every $x\geq 0$.

Since $\Bbb R$ is linearly ordered, there is a "largest" and "smallest" of these two elements, so we can choose the largest. The axiom of choice is not needed.

Well, you might say, what happens when we want to consider $\Bbb C$ instead? Since there is no order on $\Bbb C$, then how do we do that? Well. There is no order which is compatible with the field, but there is an order on the set $\Bbb C$ (e.g. the lexicographic ordering) which we can fix and use to make our choices, of course there is some algebraic issue there with choosing a root for $-1$, but this is a single additional choice we need to make.

This works for any $\sqrt[n]x$ function as well, since there are at most $n$ roots in $\Bbb R$.


To your other question, choosing a representative is in fact a function. It might not be spelled out in fancy formulas like $f(x)=x^2$ is given. But it is a function. That is the whole point of a representative, that it is unique for any two equivalent objects (in this case, any set of numbers with the same square).

I guess that whomever said "representative" to you was trying to point out that this is not somehow a unique choice, and to some extent we could also require the root to be the negative root. Although there are algebraic arguments against that (for example, you can't take $\sqrt{\sqrt 4}$ since $-\sqrt2$ does not have a real root).

$\endgroup$
  • 1
    $\begingroup$ I have just a small question : Indeed, $\mathbb C$ is not ordered, but can't we choose $\sqrt[n]{z}$ as $\sqrt{n}r e^{i\theta /n}$ with $\theta $ the smallest in $[0,2\pi]$ ? $\endgroup$ – user657324 Apr 10 at 8:45
  • $\begingroup$ Nice answer. I'm not sure with what you mean in "That is the whole point of a representative, that it is unique for any two equivalent objects". For example, a representative for $[2]$ can be $2$ or $-2$. But it's not unique... I can choose $2$ or $-2$. But if I choose one, it will represent all element of $[2]$. I always see an equivalence class as : "painting all ball of the same class of the same color", and a representative as "taking a ball among all ball of the same color, but I can't see the number of the ball behind the color, so I can't choose the number. " $\endgroup$ – user659895 Apr 10 at 8:51
  • $\begingroup$ And when I took my painted ball, I erase the paint on it, an the number that will appear will be my representative. Is that correct ? $\endgroup$ – user659895 Apr 10 at 8:52
  • $\begingroup$ @user657324: That is a way of ordering of $\Bbb C$, first by $\theta$ and then by the argument. Yes. $\endgroup$ – Asaf Karagila Apr 10 at 9:17
  • $\begingroup$ @user659895: Yes, it's not unique, there are two. But we have a good argument to choosing always the non-negative one (for example $\sqrt{\sqrt 4}$). But once you make a choice of representatives then it is a function. $\endgroup$ – Asaf Karagila Apr 10 at 9:18
2
$\begingroup$

"For fix x, the equation $y^2=x$ has always 2 solutions.": Not true for $x = 0$. This is the only defect of the statement.

There is a minor defect in the example of choosing the sign of each preimage of the square root function. As you have observed, the elements of the preimage sets are distinguishable and there is a finitely specifiable function that selects one element from each preimage set to be the image of the inverse function.

Nevertheless, the example is useful in that it describes a natural setting in which you have an infinite collection of sets and a need to select an element from each member of the collection. It would be better if we could make these preimages lie in some abstract set, so that you could not "sneak in" other things you know about $\mathbb{R}$, but that can be too abstract to get started with these ideas.

Suppose for each real number there is a two element set and all those sets are pairwise disjoint. Can you make a set containing one element from each of those two element sets? (To really attack this, we have to be clear about what our rules for making new sets from old sets are. This is why one talks about AC in the context of a particular set theory, like ZF.) The short version is: One can write down a string of choices for finitely many sets (by literally writing them down), but you can't write down infinitely long strings of choices, so either you can't make the set, or you have to have a new axiom that lets you make that set. AC is a new axiom that lets you make that set.

There are several choice axioms an addition to AC. Two well studied ones are:

  • The axiom of dependent choice is weaker than AC. This can be used, for instance, to make a sequence of points, one from each of a sequence of nested open intervals (in, for example, $\mathbb{R}$).
  • The axiom of countable choice is weaker than dependent choice. It allows the selection of an element from each set in a countable collection of sets, so can be seen as the "limited to countable collections" version of AC.

All of these allow us to write down infinitely long strings of choices, with variations on how long and whether the choices can be interdependent. For the example above of continuum-many choices without interdependence, we can use the axiom of choice restricted to collections having cardinality no greater than that of the reals. This is much weaker than full AC. (For instance, this would not be strong enough to choose an element from each set in the powerset of $\mathbb{R}$.)

$\endgroup$
  • $\begingroup$ What I wanted to point is that $\sqrt x$ is not any inverse of $x^2$, is precisely a convention that refer to the inverse on $\mathbb R^+\to \mathbb R^+$. $\endgroup$ – user657324 Apr 10 at 8:40
  • $\begingroup$ In many ways, the question also has the issue of "do we need choice for this specific set", to which the answer is always "not full choice", in which case it becomes a question of what it means to "need" choice. $\endgroup$ – Tobias Kildetoft Apr 10 at 8:40

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.