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.

Definition: F is a function iff F is a relation and $(x,y) \in F$ and $(x,z) \in F \implies y=z$.

I'm reading Introduction to Set Theory by Monk, J. Donald (James Donald), 1930 and i came across a theorem 4.10.

Theorem 4.10

(ii)$0:0 \to A$, if $F : 0 \to A$, then $F=0$.

(iii) If $F:A\to 0$, then $A=F=0$.

Where the book just explain the concept of function and now is stating its function property. I am stuck on what actually does it mean and how to prove it. May be can give me a hint.

Thanks ahead.

share|improve this question
So... $f: \mathbb{R} \to \mathbb{R}$ where $f(x)$ isn't defined for any $x$ is a function? And by $0$ I presume you mean the empty set (\emptyset). And (iii) just looks wrong. Why would $A$ have to be $0$?! –  kahen Feb 17 '11 at 9:44
@kahen: In your example, f(x) is indeed a function the source of which is not $\mathbb{R}$, and I agree with you that $A$ does not have to be $0$ as well. –  awllower Feb 17 '11 at 12:37
@awllower: I would say that my example is a partial function. I've never seen a set-theoretic definition of function that doesn't require that for all $x$ in the domain of $f$ there must be a $y$ in the codomain such that $(x,y) \in f$ –  kahen Feb 17 '11 at 12:58
@kahen: I've seen it from time to time. You define "relation" simply as a set $R$ of ordered pairs, and then you let $\mathrm{dom}(R) = \{x\mid \exists y (x,y)\in R\}$, and similarly for $\mathrm{codom}(R)$. You define "function" as Seoral does, and then it becomes a function from $\mathrm{dom}(F)$ to $\mathrm{codom}(F)$. Then you say that the notation $F\colon A\to B$ means that $A=\mathrm{dom}(F)$ and $\mathrm{codom}(F)\subseteq B$. I don't much like it, but I've certainly seen it done. –  Arturo Magidin Feb 17 '11 at 16:27
@awllower, @kahen: The only set $A$ for which there is a function from $A$ into the empty set is the empty set; so if $F$ is a function, $F\colon A\to\emptyset$, then $A=\emptyset$. Because for every $a\in A$ there must exist $b\in\emptyset$ such that $F(a)=b$, so $A$ cannot be nonempty. –  Arturo Magidin Feb 17 '11 at 19:08

2 Answers 2

up vote 4 down vote accepted

Consider the function $F\colon 0\to A$, suppose there is some $\langle x,y\rangle\in F$. This means that $x\in dom F$, since we have $dom F = 0$ then $x\in 0$ which is a contradiction. Therefore there are no ordered pairs in $F$, from the fact that it is a function we know that there are not other elements in $F$.

If so, we proved $F=0$.

The same proof goes for the other statement.

An alternative method is by cardinal arithmetic: $|F|=|dom F| \le |dom F|\times|rng F|$

The first equality is simply by projection $\langle x,F(x)\rangle \mapsto x$, where the second is by the identity map.

From this, suppose $dom F = 0$ then $F=0$ and suppose $rng F=0$ then $F=0$ and $dom F=0$.

share|improve this answer

I assume that by $0$ you mean the empty set ($\varnothing$). I don't know how the book defines a relation (the usual definition is that it's a subset of the Cartesian product of two sets). But unless it mentions that the domain of a relation $R\subset A\times B$ is $A$ then the definition of a function as you present it is different from the standard set theoretic definition of the function and furthermore (iii) is not correct. Under the standard definition of a function (namely that if $F\subset A\times B$ then the $dom(F)=A$) both (ii) and (iii) are correct. To see this you have to carefully examine whether they fall into the definition of a function:

Observe that $\varnothing\subset A\times B$. Also note that for any set $A$, $\varnothing\times A= A\times\varnothing=\varnothing$ and thus its only subset (and possible function) is the empty set. So $\varnothing$ is by definition a relation of $A\times B$ for any $A$ and $B$ and furthermore the only relation if one of the $A$ or $B$ is empty.

Now if $F\subset \varnothing\times B$ then $F=\varnothing$ and there cannot be $(x,y)\in F$, $(x,z)\in F$ and $y\neq z$ (since $F$ is empty). Thus $F$ is a function. Note here that if we assume that for a function $F\subset A\times B$ we have $dom(F)\subset A$, then with a similar argument we show that given arbitrary sets $A$ and $B$ the empty set is always a function between $A$ and $B$ (and thus (iii) is wrong).

Now for (iii) under the standard definition, if $A$ is not empty then $F$ has to be non-empty since its domain is not empty, but on the other hand $F=\varnothing$ (as a subset of the empty set). Thus $F=A=\varnothing$.

share|improve this answer
You can define "function" as Seoral does; but these are not functions-as-triples (domain, codomain, relation), but merely functions-as-special-kinds-of-relations. A relation is defined to be a set of ordered pairs, a function a relation with the extra property. Then the notions of domain and codomain (of functions and relation) are defined in terms of the projections onto first and second components. Some set-theory books do that, though you automatically lose things like the notion of "surjective". –  Arturo Magidin Feb 17 '11 at 16:24
@Arturo: I hadn't come across that definition before, thank you. :) –  Apostolos Feb 17 '11 at 16:43
what Arturo says was right. Here the definition of a relation is just any ordered pair,i.e, $(x,y)=\{\{x\},\{x,y\}\}$ and a function is a special types of relation with the above mention property,i.e, $F$ is a function iff $F$ is a relation and $(x,y) \in F$ and $(x,z)\in F \implies y=z$. Also, the book defined this: $F$ is a function of $A$ onto $B$ iff F is a function from A into B and Rng $F=B$. –  Seoral Feb 18 '11 at 6:38

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.