4
$\begingroup$

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.

  • 0
    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$?!2011-02-17
  • 0
    @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.2011-02-17
  • 0
    @awllower: I would say that my example is a [partial function](http://en.wikipedia.org/wiki/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$2011-02-17
  • 0
    @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.2011-02-17
  • 0
    @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.2011-02-17

2 Answers 2

4

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.

Edit:
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$.

2

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$.

  • 2
    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".2011-02-17
  • 0
    @Arturo: I hadn't come across that definition before, thank you. :)2011-02-17
  • 0
    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$.2011-02-18