Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I apologize for asking yet another trivial question, but here it goes i am interested in formulating a proof to show that the set $L$ of all functions on $A$ into $B$ exists. Now as per my readings i believe proofs of existence only require us to show one such case.

Now clearly such a set L is a subset(may be a proper subset) of $P(A \times B)$.

I can create a trivial example say if $A = \{a_1, a_2\}$ and B={b1, b2} then (A X B) = {(a1, b1), (a2, b1), (a1, b2), (a2, b2)}, and the Power Set $P(A \times B)$ = {{}, {(a1, b1)}, {(a2, b1)}, {(a1, b2)}, {(a2, b2)}, ..., $A \times B$}.

Since a function is simply a binary relation such that if (a1,b1) and (a1,b2) exist in it then b1 = b2. Hence as long as we satisfy this property we can pick ordered pairs from (A X B) to form our function and various permutations of such pickings would give us our set L of our functions, so such a set L must exist ?

Would this be considered a valid existence proof ? Any help or guidance would be appreciated.

share|cite|improve this question
Proof from what assumptions? What axioms? – Asaf Karagila Feb 9 '12 at 18:48
@AsafKaragila Hi bud, I am not so sure if there is a name for this set of axioms, I can give names here maybe u can recognise, The Axiom of Existence(null set exists), The axiom of extensionality, The axiom schema of Comprehension, The axiom of Pair, The axiom of Union and The axiom of Power Set. – Comic Book Guy Feb 9 '12 at 18:57
I changed A X B to $A \times B$ and did some other TeX edits. The rest of the typesetting is left as an exercise. – Michael Hardy Feb 9 '12 at 19:14
It appears you're working within the Zermelo--Fraenkel axiom system. – Michael Hardy Feb 9 '12 at 19:15
Your procedure will not yield the proof that the set of all functions from $A$ to $B$ exists. You seem to say that you will be done if you can prove that a single function exists. That is not true. What you need to do is to do is first to identify a set that contains all the functions from $A$ to $B$. For that, we must first show $A\times B$ exists. Then produce a formula $\phi(z,x,y)$ that "says" $z$ is a function from $x$ to $y$. (The usual every element of $z$ is an ordered pair $(s,t)$ such that $s\in x$ and $t\in y$ and (Cont) – André Nicolas Feb 9 '12 at 19:43
up vote 1 down vote accepted

If you want to show that for all sets $A$ and $B$, the set of functions from $A$ into $B$ (written $^AB$) exists, you have to show exactly that; one example isn’t enough.

Do it in small steps. First define the ordered pair $\langle a,b\rangle$ to be $\{\{a\},\{a,b\}\}$; this is an element of $\wp(\wp(A\cup B))$, which exists by the union and power set axioms. Then you can define the Cartesian product of $A$ and $B$ as

$$A\times B\triangleq\{\langle a,b\rangle\in\wp(\wp(A\cup B)):a\in A\land b\in B\}\;,\tag{1}$$

using the comprehension schema. Finally, $^AB$ is then

$$^AB=\left\{F\in\wp(A\times B):\forall a\in A\exists b\in B\Big(\langle a,b\rangle\in F\land\forall x\in B\big(\langle a,x\rangle\in F\to x=b\big)\Big)\right\}\;,$$

using the power set axiom and the comprehension schema.

Note that although the important details are there, what I wrote is all actually quite informal. For example, $\exists x\in X\big(\varphi(x)\big)$ is ‘really’ $\exists x\big(x\in X\to\varphi(x)\big)$, and the set in $(1)$ is

$$\left\{x\in\wp(\wp(A\cup B)):\exists a,b\Big(a\in A\land b\in B\land x=\big\{\{a\},\{a,b\}\big\}\Big)\right\}\;,$$

where $x=\big\{\{a\},\{a,b\}\big\}$ is itself already an abbreviation.

share|cite|improve this answer
Thanks for your help. I appreciate it. – Comic Book Guy Feb 9 '12 at 19:57

As you already mention $L\subset P(A\times B)$. Now $L=\{f\in P(A\times B): \forall a\in A \exists b\in B\ ((a,b)\in f, \text{and} \ \forall (a,b), (c,d)\in f\ (a=c \ \text{implies}\ b=d\} $

$L$ is a set by comprehension.

share|cite|improve this answer
Thanks for your help buddy, your proof was very slick and concise. – Comic Book Guy Feb 9 '12 at 19:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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