Take the 2-minute tour ×
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.

Let $A$ to be a nonempty set and $B= \emptyset$; then $ A \times B$ is a set. And let $F$ be a function $A \to B$. Then $F \subseteq A \times B$. By the axiom of specification, $F$ must exists (if I didn't mess up something).

But the book I'm reading, Elements of Set Theory by Enderton, says that no function could have a nonempty domain and an empty range, and no more detail is given.

So my confusion arises. His statement against my proof. The only axiom as far as I know to prove such a set does not exist is the axiom of regularity. But I can't give such a proof. So I need help. I hope someone could clearly explain why such a function doesn't exist, and why this doesn't contradict the axiom of specification.


Let me explain my confusion in more detail:

First of all, I know that $A \times \emptyset$ is empty. But $ \emptyset \times A$ is also an empty set, yet there is no problem with functions with an empty domain.

The book I'm reading defines a function as:

"A function is a relation such that for each $x$ in $\operatorname{dom} F$ there is only one $y$ such that $x \mathop F y$."

and a relation as:

"A relation is a set of ordered pairs."

Now, let me define the function $F$ as: $$F = \{\langle x,y \rangle \mid x \in A \text{ and } y \in B \text{ and ... other conditions} \}$$ so it's equal to: $$F = \{ \langle x,y \rangle \in A \times B \mid \text{... other conditions} \}.$$

Doesn't that mean that $F$ meets the conditions of the axiom of specification, and therefore exists?


What I would specifically like to ask is:

  1. How do you define a function $F$ (as precisely as possible)?

  2. Why does the argument above not imply that a function $F: A \to B$ always exists?

  3. Does $F \subseteq A \times B$ still hold when $B = \emptyset$?

(The answer to #2 cannot simply be that $A \times B = \emptyset$, because $ B \times A = \emptyset$ as well, but a function $B \to A$ does exist.)

share|improve this question
3  
How precisely are you using the axiom of specification? The set $\mathcal C$ of functions from $A$ to $B$ certainly exists, and specification may be used to verify this. But the existence of $\mathcal C$ does not imply the existence of any functions $F:A\to B$. In fact, $\mathcal C=\emptyset$. –  Andres Caicedo May 10 at 14:31
1  
For every $a \in A$, there must exist a unique $b \in B$ so that $(a, b) \in F$. Can you see the problem with this restriction if $A$ is nonempty and $B$ is empty? –  Dustan Levenstein May 10 at 14:31
1  
@DetectiveKing Stop being vague and write down your proof. How is anybody going to help you if you keep your proof hidden. –  Andres Caicedo May 10 at 14:52
1  
Your definition of $S$ makes no sense. Your definition of $F$ makes no sense either. Perhaps you meant $S=\{\langle x,y\rangle \mid x\in A,y\in B\}$? Then $S$ is just $A\times B$, which in this case is indeed $\emptyset$. Saying $S=\{\langle x,y\rangle \mid \exists x\in A\dots\}$ makes no sense. The $x$ on the left of the $\mid$ won't be the same as the one on the right, which is now quantified. You then "proceed" to write what $F$ is, but you don't. You wrote some ellipses, and have the incorrect $\exists x\in A$ and $\exists y\in B$ there as well. It is still not precise enough. –  Andres Caicedo May 10 at 15:35
1  
@DetectiveKing: I just edited your question to clarify it and eliminate some repetition. Feel free to fix anything that doesn't match what you intended to ask (and to simplify the question further, if there's anything unnecessary left). (Ps. For future reference, when improving your question based on comments, it's generally considered better style to edit your question "in place" to clarify it than to just append further questions at the end.) –  Ilmari Karonen May 10 at 21:40

5 Answers 5

up vote 17 down vote accepted
+50

The standard set-theoretic way to define functions is that:

  1. The cartesian product of the sets $A$ and $B$, written as $A \times B$, is the set of all ordered pairs where the first element of the pair is in $A$ and the second in $B$: $$A \times B = \{(a,b): a \in A, b \in B\}.$$

    (Representing these ordered pairs as sets, and showing that the cartesian product of two sets is indeed a set under the axioms of set theory, are details that we may safely skip here.)

  2. A relation $R$ between the sets $A$ and $B$ is any subset of their cartesian product: $R \subset A \times B$.

    (Often, by convention, we write $a \mathop R b$ as a shorthand for $(a,b) \in R$; this is particularly common when the symbol chosen for the relation is not a letter like $R$, but something abstract like $\sim$ or $\odot$.)

  3. A function $f$ from $A$ to $B$ is a relation between $A$ and $B$ (i.e. a subset of their cartesian product) satisfying the following two extra conditions:

    • existence of images: for all $a \in A$, there is a $b \in B$ such that $(a,b) \in f$.

    • uniqueness of images: if $(a,b) \in f$ and $(a,b') \in f$, then $b = b'$.

    If the relation $f$ is a function, then, for each $a \in A$, there exists exactly one $b \in B$ satisfying $(a,b) \in f$. We call this $b$ the image of $a$ under $f$, written $f(a)$, so that: $$f(a) = b \iff (a,b) \in f.$$


So, what about when $B = \varnothing$? In that case, for any $A$, the cartesian product $A \times B = \varnothing$, since there exist no pairs $(a,b)$ such that $a \in A$ and $b \in B$. (The same, of course, is also true whenever $A = \varnothing$.)

Since the only subset of $\varnothing$ is $\varnothing$, the only relation between $A$ and $B$ is the empty relation $\varnothing$. The question, then, is: is the empty relation a function from $A$ to $B$?

  • If $A \ne \varnothing$, no, it is not, because there exists at least one $a \in A$, but there can be no $b$ such that $(a,b) \in \varnothing$.

  • If $A = \varnothing$, yes, it is. In this case, both the existence and uniqueness conditions are vacuously true, since there is no $a \in A$ for which they could fail.

Thus, there is a (single) function from the empty set to any set (including the empty set itself), but there is no function from a non-empty set to the empty set.

share|improve this answer
    
Thanks for the answer.It's comprehensive and helpful.I'll give you a bounty as long as I can. –  Detective King May 10 at 19:17

You messed up because $A\times\varnothing$ is the empty set. So only if $A$ is empty as well such function exists.

share|improve this answer
    
Hi,in my opnion it's not about whether $A \times B$ is empty or not.Thing comes difference when $B \times A = \varnothing$ .I've updated my post give more explain about the issue.Hope you could have a look. –  Detective King May 10 at 17:06
    
Detective King, $F\colon A\to B$ means that (1) $F$ is a function (a set of ordered pairs with a particular property); (2) the domain of $F$ is all of $A$. So if $F\subseteq\varnothing$ it is necessarily the case that the domain of $F$ is empty, so if $A$ is not empty, $F$ is not a function whose domain is $A$ itself; but if $A$ is empty (regardless to what $B$ is), then it is a function whose domain is $A$. So $\varnothing\subseteq\varnothing\times A$ is a function from $\varnothing$ to $A$; but $\varnothing\subseteq A\times\varnothing$ need not be a function from $A$ to $\varnothing$. –  Asaf Karagila May 10 at 17:10
    
@AsafKragila I think I get some idea in your comment.So if let $F$ to be a set with some property to describe a function about the set with condition given in the post.The set is exist and it's empty.But the set $F$ doesn't fit the property in the set $B^A$, is that right? –  Detective King May 10 at 17:30
    
After a careful re-reading of your question, it seems that you want to argue that by the axiom of specification $B^A$ exists, but you don't understand why it's not empty. But you wrote $F$ for both that set and its elements. Yes, specification implies that $B^A$ exists, but we can prove that no $F\subseteq A\times B$ satisfies the conditions required to be a member $B^A$, therefore that set is empty. –  Asaf Karagila May 10 at 17:33
1  
@AsafKragila Thanks for the explaination.I think I know what's going on here.And I'm quite shocked is that thing described its property in its own body can't describe its existence . –  Detective King May 10 at 17:55

A function $f\colon A\to B$ is a subset of $A\times B$ such that

  1. for every $a\in A$, there exists $b\in B$ such that $(a,b)\in f$;

  2. for every $b,b'\in B$, if there exists $a\in A$ with $(a,b)\in f$ and $(a,b')\in f$, then $b=b'$.

The first condition expresses the fact that every element in $A$ has an image in $B$. The second condition expresses the fact that such image is uniquely determined by the element in the domain. Thus, if $a\in A$, we can write $f(a)$ to denote the unique element in $B$ such that $(a,f(a))\in f$.

Now, if $B=\emptyset$, we have $f\subset A\times\emptyset=\emptyset$, so $f$ is empty. Thus every element of $A$ fails to have an image in $B$ under $f$, and so a function $f\colon A\to\emptyset$ can exist only when also $A$ is empty.

On the contrary, if $A=\emptyset$, condition 1 cannot fail for any element of $\emptyset$, which has no elements; also condition 2 cannot fail, so there is indeed a function $f\colon \emptyset\to B$. It's unique, because $f\subseteq \emptyset\times B=\emptyset$, so $f=\emptyset$.

share|improve this answer

Given sets $A$ and $B$, a function from $A$ to $B$ is a subset $f\subseteq A\times B$ such that $$\forall a\in A\ \exists ! b\in B\ ((a,b)\in f).$$

Thus, if $A\neq\emptyset$ and $B=\emptyset$, no function $f$ exists, since, given any $a\in A$ you can not find any $b\in B$ with $(a,b)\in A\times B$, as $A\times B$ is empty.

share|improve this answer
    
I think the problem is here.If you say $f$ is a subset then the problem occur.I've update my post. –  Detective King May 10 at 16:58

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\notag \\ #1 \quad & \quad \text{"#2"} \notag \\ \quad & } \newcommand{\endcalc}{\notag \end{align}} $In essence, Enderton is saying that $$ \tag{0} F\text{ is a function} \;\land\; \text{dom }F \not= \emptyset \;\land\; \text{ran }F = \emptyset $$ is false. And from what I read in the question, and from snippets on the interwebs (e.g., http://tedsider.org/teaching/st/st_notes.pdf), his definitions for domain and range are \begin{align} \text{dom }F & \;=\; \{x \mid \langle \exists y :: xFy \rangle \} \\ \text{ran }F & \;=\; \{y \mid \langle \exists x :: xFy \rangle \} \\ \end{align}

Now, what does it mean that $\;\text{dom }F \not= \emptyset\;$?

$$\calc \text{dom }F \not= \emptyset \calcop{\equiv}{basic property of $\;\emptyset\;$} \langle \exists x :: x \in \text{dom }F \rangle \calcop{\equiv}{the above definition of $\;\text{dom}\;$} \langle \exists x :: \langle \exists y :: xFy \rangle \rangle \endcalc$$

Similarly,

$$\calc \text{ran }F = \emptyset \calcop{\equiv}{basic property of $\;\emptyset\;$} \lnot\langle \exists y :: y \in \text{ran }F \rangle \calcop{\equiv}{the above definition of $\;\text{ran}\;$} \lnot\langle \exists y :: \langle \exists x :: xFy \rangle \rangle \rangle \endcalc$$

Therefore we have a contradiction:

$$\calc \text{dom }F \not= \emptyset \;\land\; \text{ran }F = \emptyset \calcop{\equiv}{the above calculations} \langle \exists x, y :: xFy \rangle \;\land\; \lnot \langle \exists x, y :: xFy \rangle \calcop{\equiv}{logic: contradiction} \text{false} \endcalc$$

and it directly follows that $(0)$ is false, regardless of the definition of 'function'.

So (using Enderton's definitions) there is not even a relation $\;F\;$ with a non-empty domain and an empty range, and therefore (since every function is a relation) there is also no function with a non-empty domain and an empty range.

Note how no fixed sets $\;A\;$ or $\;B\;$ have been mentioned so far.

Enderton then abbreviates $$ F : A \to B \;\equiv\; F\text{ is a function} \;\land\; \text{dom }F = A \;\land\; \text{ran }F \subseteq B $$ Note how this definition is asymmetrical w.r.t. domain and range: $\;F : A \to \emptyset\;$ is false for non-empty $\;A\;$ (as we've just proved above), but $\;F : \emptyset \to B\;$ is true iff $\;F = \emptyset\;$ (since $\;\emptyset\text{ is a function}\;$), regardless of the value of $\;B\;$. This is exactly the asymmetry noted in the question.

share|improve this answer

Your Answer

 
discard

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.