1
$\begingroup$

I've got as part of an assignment to determine whether a given function is total, and if so, to say whether it's injective, surjective, or bijective. I can tell the answer by looking at it, but I feel that I need to make some kind of concrete proof that the function is total.

$$f:\mathbb{N}\to \mathbb{N},f(x)=x^2+4$$

I can tell by looking at it that it's a one-to-one total function. But is there a satisfactory way I can prove that this is a total function? I'm extremely new to this whole idea of functions outside of algebraic functions (such as total and partial functions)...

  • 0
    What is your definition of "partial function"?2012-11-07
  • 0
    @wj32 http://en.wikipedia.org/wiki/Partial_function A function where the domain is a subset of the original domain, or where the function is undefined at some point in the codomain. In this example, for all $\mathbb{N}$, $x^2+4$ will be defined... so it is not a partial function... Whereas if the function was $1/x$ then it would not be defined at any point other than $x=1$2012-11-07
  • 1
    If your definition of *partial function* is the usual one ($f\subseteq X\times Y$ is a partial function from $X$ to $Y$ if $f$ is a function from some subset of $X$ to some subset of $Y$), then this $f$ is clearly total: it’s defined on all of $\Bbb N$.2012-11-07
  • 0
    @agent154: I don't think I made my point very well :). What I was suggesting was for you to go back to the definition and see why it is so easy to "tell the answer by looking at it".2012-11-07
  • 0
    Or in other words: is it true that $f(n)$ is defined for every $n\in\Bbb N$?2012-11-07
  • 0
    @wj32 Well, that's it - I don't know how to explain myself. All I know is that for all $n\in \mathbb{N}, x^2+4$ will lie within the codomain of $\mathbb{N}$. $1^2+4=5, (x+1)^2+4=x^2+2x+5\in \mathbb{N}$2012-11-07
  • 0
    @BrianM.Scott Yes - that's what I'm trying to write down properly. I don't know how to say it without leaving any possible holes in my logic, if there is indeed a way to say so.2012-11-07
  • 0
    You have the idea. How about: Let $n\in\Bbb N$. $\Bbb N$ is closed under multiplication and addition, so $f(n)=n^2+4\in\Bbb N$. Therefore $f$ is total.2012-11-07
  • 0
    @agent154: If I write down $f(x)=\mbox{what wj32 says f(x) ought to be}$, is $f$ a total function? It is to me, but it might not be to you. You have to make sure what you write down is well-defined to people who read it, but looking for some kind of a formal proof that $f$ is a total function is unnecessary unless you are working in a computer algebra or automated reasoning system.2012-11-07

2 Answers 2

0

I went with Brian's suggestion from above comments:

You have the idea. How about: Let $n\in \mathbb{N}$. $\mathbb{N}$ is closed under multiplication and addition, so $f(n)=n^2+4\in \mathbb{N}$. Therefore f is total.

1

To formally prove that it's a total function, you need to look up the definitions/basic theorems about $\mathbb{N}$ and multiplication (or squaring) and addition, and check that

  1. $x^2+4$ has a fixed value for each $x\in\mathbb{N}$.
  2. That value is actually in $\mathbb{N}$. (This is something to check if your definitions only ensure it's in $\mathbb{Z}$, or something like that.)

Since I don't have your definitions, and you may not even have definitions for some of this stuff, I can't help you further except to say "if you don't have definitions for something, just argue intuitively for that part".

  • 0
    That does seem a little beyond me at this point... But then again, this whole question was beyond what I should have been doing at this point in the class. This professor likes to ask questions on assignments for which he hasn't even covered the material. I ended up passing in the assignment last week and forgot to mark this question as answered. Thanks anyhow though.2012-11-13
  • 0
    Well, you're probably not expected to worry about formally proving it completely rigorously at this level. But you seemed worried about rigor, so I described what more rigor would be like. If you feel this question is answered you can either accept my answer or add an answer of your own and accept that (since you had an answer first), or I think you can vote to delete your question if you really want.2012-11-13