1
$\begingroup$

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.

  • 0
    I edited/changed ordered pairs into singletons in P(A×B)2012-02-24

2 Answers 2

1

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.

2

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.

  • 0
    Thanks for your help buddy, your proof was very slick and concise.2012-02-09