11
$\begingroup$

I'm reading through Asaf Karagila's answer to the question What is the Axiom of Choice and Axiom of Determinacy, and while reading the explanation of Bertrand Russell's analogy ("The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.") at the bottom, I realized I'm a little confused by what a function actually is in set-theoretic terms (and probably confused by some other things, too).

Basically, my confusion is this:

  • I thought that a function was specified by a finite string.
  • Thus, the reason that we need the Axiom of Choice to select a set from an infinite number of socks is that there's no way to define a choice function on an infinite number of socks using only a finite string.
  • However, if our universe is the set of natural numbers, aren't there an uncountable number of functions defined on our universe, but only a countable number of finite strings?

Where am I going wrong? What's the precise definition of a function, and what's the problem with my thinking in my last bullet point?

  • 0
    As Arturo gave a good answer, I'll only leave you with this comment: If everything is specified by finite strings, how can we define all the subsets of $\mathbb N$, how can we specify what is $\mathbb N$ to begin with? How can we specify the $\mathbb N$-th iteration of power sets of $\mathbb N$ (that is the limit of all finite iterations)? We can define how these things look like, and swipe them all off in one short definition. Not everything is definable, somethings just exist as a byproduct of a definable object (i.e. definable with parameters).2011-08-28

3 Answers 3

18

A common definition of function between two sets (or between two classes, when working in GBN) is based on the notion of "ordered pair". An ordered pair is some set-theoretic construction, denoted "$(a,b)$" where $a$ and $b$ are sets, with the property that $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$. There are many ways of achieving this; the most common is the Kuratowski definition of ordered pair:

Definition. If $a$ and $b$ are sets, then the ordered pair $(a,b)$ is the set $$(a,b) = \Bigl\{ \{a\}, \{a,b\}\Bigr\}.$$

Note that $(a,b)$ is a set if $a$ and $b$ are sets. The Axiom of Pairing guarantees the existence of a set $P$ that contains $a$ and $b$ as elements; and then both $\{a\}$ and $\{a,b\}$ are elements of the power set of $P$, so $(a,b)$ is an element of the power set of the power set of $P$. Also:

Theorem. $(a,b) = (c,d)$ if and only if $a=c$ and $b=d$.

Proof. If $a=c$ and $b=d$, then $(a,b)=(c,d)$. Assume now that $(a,b)=(c,d)$. Then $$\{a\} = \cap(a,b) = \cap(c,d) = \{c\},$$ so $a=c$. If $b=a$, then $(c,d) = (a,b) = \{\{a\}\}$, so $\{c,d\}=\{a\}$, hence $d=a=b=c$. Likewise, if $d=c$, then $a=b=c=d$.

If $a\neq b$ and $c\neq d$, then $\{b\} = \cup(a,b) - \cap(a,b) = \cup(c,d)-\cap(c,d) = \{d\}$, so $b=d$. QED

Now let $A$ and $B$ be sets (classes if you are in GBN). The cartesian product $A\times B$ of $A$ and $B$ is defined to be $$A\times B = \{ (a,b) \mid a\in A, b\in B\}.$$ If $A$ and $B$ are sets, then so is $A\times B$: it is an element of $\mathcal{P}(\mathcal{P}(\mathcal{P}(A\cup B)))$.

Now we are ready:

Definition. Let $A$ and $B$ be sets (or classes). A function $f\colon A\to B$ is a subset (or subclass) $f\subseteq A\times B$ such that:

  • For all $a\in A$ there exists $b\in B$ such that $(a,b)\in f$; and
  • For all $a\in A$ and $b,b'\in B$, if $(a,b)\in f$ and $(a,b')\in f$, then $b=b'$.

The idea is that $f$ "assigns" $a\in A$ to $b\in B$ if and only if $(a,b)\in f$. In that case, we write $f(a)=b$ (to mean $(a,b)\in f$).

The problem with your last bullet point is really the first bullet point. You seem to be confusing "function" with "function you can name".

The problem with the Axiom of Choice is more subtle than the notion of "being able to write down something". For example, if you restrict your universe to the "constructible sets" (see Wikipedia's article) of ZF (without assuming AC), then the Axiom of Choice is true for the constructible sets.

  • 5
    How do you come up with these well formatted and written answers in under 15 minutes??2011-08-28
  • 6
    @Asaf: I touch-type, and I've been using $\TeX$ since 1987, so it's almost second nature by now.2011-08-28
  • 0
    Hmm, I think I kind of see -- there are a countable number of definable functions on the naturals, but an uncountable number of possibly un-definable ones. However, now I don't see why AoC is required to select from an infinite pair of socks. Could you elaborate on how that follows from this definition of a function? Asaf wrote "It means that you may not be able to write a finite sentence to help you choose from infinitely many pairs without the axiom of choice" -- was the mention of finiteness more to provide a layman's answer, or can it be rigorized?2011-08-28
  • 0
    @grautur: Could you explain what in my answer is missing? I would very much like it to be complete and better understood.2011-08-28
  • 2
    @grautur: The problem is that of *proving* that a function exists from $\mathbb{N}$ to the set of all socks in the pairs with the desired properties. AoC is required to be able to write down a proof that such a function exists. Again: it's subtle, and it *is* connected to infinity in some sense, but not simply in the sense of "naming". We can *prove* that there are uncountably many subsets of $\mathbb{N}$, and we can *prove* that we can only name countably many; the "un-nameable ones" don't cease to exist, we just can't name them.2011-08-28
  • 1
    @Asaf: I think your answer was excellent for a high-level understanding. The part where it breaks down for me is why we can make a choice function on a finite number of pairs of socks, but not an infinite number. (It makes sense if we have to define the choice function with a finite string, but I don't see how it follows if the function can be undefinable. Or maybe therein lies my confusion? -- I've never really understood what Russell's analogy is saying, so is there in fact an (undefinable) choice function on the infinite socks? I guess I need a rigorous explanation of the connection =).)2011-08-28
  • 2
    @grautur: That might make a very fine separate question...2011-08-28
  • 0
    @grautur: If you didn't understand it wholly, then how you can be certain it was excellent on the high level? Anyway, I guess you cannot capture everything in one answer. If the answers to this question do clarify the missing points do let me know what you think of my answer *after* reading it again. Worst case scenario, I can always add more... (I mean, it is already infinitely long, what's a couple more lines? :-))2011-08-28
  • 0
    @Arturo: Cool, yeah, I'll make a separate question after thinking about this a bit more. One last thing: can we prove that AoC is required to prove that such a function exists?2011-08-28
  • 0
    @Asaf: Ha, you got me there! I guess I've seen similar explanations before and yours was better :-), and you gave me at least a partial understanding (though for all I know it's an incorrect partial understanding ;-)).2011-08-28
  • 2
    @grautur: It is possible to construct a model in which there is a countable set of pairs and you cannot choose from them. Of course the axiom of choice does not hold in this model, but it shows that we really do need AC to prove the existence of choice functions.2011-08-28
4

A function $f$ from $A$ to $B$ is usually defined as a subset of $A \times B$ with the property that for each $a \in A$ there is a unique $b \in B$ such that $(a,b)$ is in the subset. In symbols: $$f \colon A \longrightarrow B \Leftrightarrow f \subset A \times B \land \forall a \in A \exists ! b \in B . (a,b) \in f.$$ In fact, sometimes a function is defined as a triple $(f,A,B)$ where $f$ is as before, i.e. it comes tagged with its domain and range; but this is not the usual definition in set theory.

If $A,B$ are proper sets then the set of all functions from $A$ to $B$ exists (axiom chase).

A definable function (in some context) is given by a "textual" definition, and there are only countably many of those. There are different definitions of definability, e.g. Gödel's one, computable functions (when it applies) and so on.

2

Some authors say that the subset of $A\times B$ is the graph of a function and define a function to be an object with three parts as follows.

  • A set $D$ called the domain
  • A set $R$ called the range
  • A rule f tying each element $x\in D$ to a specific $f(x)\in R$

In this case we write $f:D\rightarrow R$.