Set Theory Proofs

[Stochastic_Jimmy]

Hi all. I was hoping you guys/gals could take a look at the proofs I've done below. I think they are all valid, but sometimes it's hard to find small flaws (like unjustified assumptions, etc). The goal is to come up with several ways to prove the following:

For any two sets \(\displaystyle A, B\) let \(\displaystyle B^A\) denote the set of all functions from \(\displaystyle A\) to \(\displaystyle B\), and let \(\displaystyle \mathcal{P}(A \times B)\) denote the power set of \(\displaystyle A \times B\). Prove that \(\displaystyle \left|B^A\right| \leq \left|\mathcal{P}(A \times B)\right|\).

Here are three very brief proofs I've been working on:

Proof 1.

By definition we have that

\(\displaystyle B^A = \left\{f \subseteq A \times B \text{ s.t. } f \text{ is a function } A \to B \right\}.\)

And this is equivalent to saying that

\(\displaystyle B^A = \left\{f \in \mathcal{P} (A \times B) \text{ s.t. } \forall x \in A,\: \exists \text{ a unique } y \in B \text{ where } f(x) = y \right\}.\)

So then we have that for some arbitrary function \(\displaystyle f:\)

\(\displaystyle \begin{align*}
f \in B^A &\implies f \in \mathcal{P} \left(A \times B\right) \\
& \implies B^A \subseteq \mathcal{P} \left(A \times B\right) \\
& \implies \left|B^A\right| \leq \left| \mathcal{P} (A\times B) \right|
\end{align*}\)

End proof.



Proof 2.

Consider the set of all possible binary relations from \(\displaystyle A\) to \(\displaystyle B\).
Obviously \(\displaystyle B^A\), the set of all functions \(\displaystyle A \to B\), is a subset of the set of all binary relations from \(\displaystyle A\) to \(\displaystyle B\) since functions are relations.

We know that, by definition, a binary relation from \(\displaystyle A\) to \(\displaystyle B\) is a subset of \(\displaystyle A \times B\).
And so, using the definition of a power set, the elements of the set of all possible relations from \(\displaystyle A \times B\) are therefore the elements of \(\displaystyle \mathcal{P} (A \times B)\).

It follows immediately that \(\displaystyle \left|B^A\right| \leq \left| \mathcal{P} (A\times B) \right|\).

End proof.



Proof 3.

Consider for an arbitrary function \(\displaystyle f: A \to B\) its graph

\(\displaystyle \qquad G_f = \left\{(x,y) \in A \times B \:\big|\: y = f(x)\right\}.\)

Now, consider a mapping \(\displaystyle F : f \to G_f.\)

Claim: This mapping \(\displaystyle F\) is one-to-one. That is, \(\displaystyle F\) is an injection \(\displaystyle B^A \to A \times B\).

To see this, consider that for \(\displaystyle f, f' \in B^A\) we have:

\(\displaystyle \begin{align*}
F(f) = F(f') &\implies G_f = G_{f'} \\
&\implies \big(x, f(x)\big) \in G_f \:\text{ for each } x \in A\\
&\implies \big(x, f(x)\big) \in G_{f'} \:\text{ for each } x \in A \\
&\implies f(x) = f'(x).
\end{align*} \)

And since \(\displaystyle F\) is an injection we know that \(\displaystyle \left|\text{Domain}(F) \right| \leq \left|\text{Codomain}(F)\right|\).

It follows that \(\displaystyle \left|B^A\right| \leq \left| \mathcal{P} (A\times B) \right|\).


End proof.




Thanks a lot for any help. I really appreciate it. (And I'm enjoying the TeX functionality!!)

 

[lookagain]

For any two sets \(\displaystyle A, B\) let \(\displaystyle (A \to B)\) denote the set of all functions from \(\displaystyle A\) to \(\displaystyle B\), and let \(\displaystyle \mathcal{P}(A \times B)\) denote the power set of \(\displaystyle A \times B\). Prove that \(\displaystyle \left|(A \to B)\right| \leq \left|\mathcal{P}(A \times B)\right|\).

You had an error in the prove statement. In this quote box,
I show the correction as

\(\displaystyle \mathcal{P}(A\times B)\)

You could edit your post to reflect that.

 

[Stochastic_Jimmy]

You had an error in the prove statement. In this quote box,
I show the correction as

\(\displaystyle \mathcal{P}(A\times B)\)

You could edit your post to reflect that.

Thanks! You're right. I've made the edit.

 

[pka]

Thanks! You're right. I've made the edit.

Here is another point about standard notation.
You have said that \(\displaystyle (A\to B)\) denotes the set of all functions that map \(\displaystyle A\text{ to }B\).

One of the very few standard notations for that set is \(\displaystyle B^A\).
It is used almost universality in set theory textbooks.

 

[Stochastic_Jimmy]

Here is another point about standard notation.
You have said that \(\displaystyle (A\to B)\) denotes the set of all functions that map \(\displaystyle A\text{ to }B\).

One of the very few standard notations for that set is \(\displaystyle B^A\).
It is used almost universality in set theory textbooks.

Yeah, that's the notation I'm familiar with. However, in the book where I found the problem the author uses \(\displaystyle (A \to B)\).

But, to avoid any confusion, I will update my original post to use the more common notation you suggest. Thanks.

Any thoughts on the actual proofs?

 

[pka]

Yeah, that's the notation I'm familiar with. However, in the book where I found the problem the author uses \(\displaystyle (A \to B)\).

Which author is that? I have never seen that notation.

I have seen a variation \(\displaystyle ^AB\) used. (Enderton)

 

[Stochastic_Jimmy]

Which author is that? I have never seen that notation.

I have seen a variation \(\displaystyle ^AB\) used. (Enderton)

It's Moschovakis (coincidentally also at UCLA). I hadn't seen the notation before either.

 

[daon2]

Hi Jimmy. What you did in proofs 1 and 2 look the same to me. But The notation in the first proof looks funny to me. You also state, without proof, the following:

\(\displaystyle \qquad B^A = \left\{f \subseteq A \times B \text{ s.t. } f \text{ is a function } A \to B \right\}.\)

And this is equivalent to saying that

\(\displaystyle \qquad B^A = \left\{f \in \mathcal{P} (A \times B) \text{ s.t. } \forall x \in A,\: \exists \text{ a unique } y \in B \text{ where } f(x) = y \right\}.\)

You quantify \(\displaystyle f\) as a subset of \(\displaystyle A\times B\), but it is not at all clear what \(\displaystyle "f(x)"\) is. I believe you mean: \(\displaystyle B^A = \{A\times Y \in \mathcal{P}(A\times B)\,|\, a\in A, y,y'\in Y\implies [(a,y)=(a,y') \iff y=y']\}\)

As an easy method of proof, you can just note that \(\displaystyle B^A\) is a proper subset of \(\displaystyle \mathcal{P}(A\times B)\) since we only consider certain subsets contained in \(\displaystyle A\times \mathcal{P}(B)\).

You might also consider a cardinality argument: \(\displaystyle |B|^{|A|} \le \left(2^{|B|}\right)^{|A|}\)

 

[Stochastic_Jimmy]

Hi Jimmy. What you did in proofs 1 and 2 look the same to me. But The notation in the first proof looks funny to me. You also state, without proof, the following:




You quantify \(\displaystyle f\) as a subset of \(\displaystyle A\times B\), but it is not at all clear what \(\displaystyle "f(x)"\) is. I believe you mean: \(\displaystyle B^A = \{A\times Y \in \mathcal{P}(A\times B)\,|\, a\in A, y,y'\in Y\implies [(a,y)=(a,y') \iff y=y']\}\)

As an easy method of proof, you can just note that \(\displaystyle B^A\) is a proper subset of \(\displaystyle \mathcal{P}(A\times B)\) since we only consider certain subsets contained in \(\displaystyle A\times \mathcal{P}(B)\).

You might also consider a cardinality argument: \(\displaystyle |B|^{|A|} \le \left(2^{|B|}\right)^{|A|}\)

Thanks daon2! Really appreciate the response.

My statement in the first proof:

\(\displaystyle B^A = \left\{f \subseteq A \times B \text{ s.t. } f \text{ is a function } A \to B \right\}.\)

And this is equivalent to saying that

\(\displaystyle B^A = \left\{f \in \mathcal{P} (A \times B) \text{ s.t. } \forall x \in A,\: \exists \text{ a unique } y \in B \text{ where } f(x) = y \right\}.\)

actually comes straight from the definition of a function given in the book Notes on Set Theory by Yiannis Moschovakis which you can see here:

​

and his subsequent definition of the set of all functions \(\displaystyle A \to B \) (although he uses the notation \(\displaystyle (A\to B)\) rather than \(\displaystyle B^A\)), which he gives as:

​

So, what I then tried to do in proof 1 was simply to say that if some function \(\displaystyle f \) is a member of \(\displaystyle B^A\) then that also implies that it is a member of \(\displaystyle \mathcal{P}(A \times B)\), which shows that the former is a subset of the latter and thus the conclusion that its cardinality less than or equal.

Does that make sense?


But, you're right, this first proof and the second are essentially saying the same exact thing I believe.​

 

[daon2]

Thanks daon2! Really appreciate the response.

My statement in the first proof:




actually comes straight from the definition of a function given in the book Notes on Set Theory by Yiannis Moschovakis which you can see here:

View attachment 2578​

and his subsequent definition of the set of all functions \(\displaystyle A \to B \) (although he uses the notation \(\displaystyle (A\to B)\) rather than \(\displaystyle B^A\)), which he gives as:

View attachment 2579


​

So, what I then tried to do in proof 1 was simply to say that if some function \(\displaystyle f \) is a member of \(\displaystyle B^A\) then that also implies that it is a member of \(\displaystyle \mathcal{P}(A \times B)\), which shows that the former is a subset of the latter and thus the conclusion that its cardinality less than or equal.

Does that make sense?


But, you're right, this first proof and the second are essentially saying the same exact thing I believe.​

I did understand what you meant, but to be rigorous, \(\displaystyle (\forall x \in A)(\exists ! y\in B)[(x,y)\in f]\) is not the same thing as \(\displaystyle \forall x\in A, \exists ! y\in B \,s.t.\, f(x)=y\). Yes, they do mean the same thing intuitively, but in your definition, \(\displaystyle f(x)\) is not defined. It should be stated what the the notation means: \(\displaystyle (x,y)\in f \iff f(x)=y\), and it very well might be in your text. I'm just nitpicking, but that is my professors fault, who exclaimed to our class that if an alien being, whose only language is set theory, cannot understand what you've written then it's wrong.

 

[Stochastic_Jimmy]

I did understand what you meant, but to be rigorous, \(\displaystyle (\forall x \in A)(\exists ! y\in B)[(x,y)\in f]\) is not the same thing as \(\displaystyle \forall x\in A, \exists ! y\in B \,s.t.\, f(x)=y\). Yes, they do mean the same thing intuitively, but in your definition, \(\displaystyle f(x)\) is not defined. It should be stated what the the notation means: \(\displaystyle (x,y)\in f \iff f(x)=y\), and it very well might be in your text. I'm just nitpicking, but that is my professors fault, who exclaimed to our class that if an alien being, whose only language is set theory, cannot understand what you've written then it's wrong.

Ah yes. That makes sense. I see what you mean. Thank you. (And I like your professor's philosophy.)