# Explain how these proofs work

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Mar 28th 2014, 11:52 AM
michaelgg13
Explain how these proofs work
Hi all,

We have made it to function proofs in my class. I really have a hard time understanding proofs at all. Can someone explain to me how these couple examples:

These are 2 of many questions from my homework, and I have no idea how to do them.

Let f : Z x Z --> Z state whether the following function is onto or not, then prove or disprove.

f(m, n) = m2 + n4

I understand that the domain is Z x Z and the codomain is Z, And I know that to be onto the function, if y element Y implies there is an x element X such that f(x)=y, I just don't understand how you prove it.
Let f : Z --> Z state whether the following function is one to one or not, then prove or disprove.

f(n) = n2 + 1

Thank for everyone who helps me learn how to prove these, I really won't be able to understand the rest of my work without you're explanations.
• Mar 28th 2014, 12:46 PM
Plato
Re: Explain how these proofs work
Quote:

Originally Posted by michaelgg13
Hi all,

We have made it to function proofs in my class. I really have a hard time understanding proofs at all. Can someone explain to me how these couple examples:

These are 2 of many questions from my homework, and I have no idea how to do them.

Let f : Z x Z --> Z state whether the following function is onto or not, then prove or disprove.

f(m, n) = m2 + n4

I understand that the domain is Z x Z and the codomain is Z, And I know that to be onto the function, if y element Y implies there is an x element X such that f(x)=y, I just don't understand how you prove it.
Let f : Z --> Z state whether the following function is one to one or not, then prove or disprove.

f(n) = n2 + 1

Thank for everyone who helps me learn how to prove these, I really won't be able to understand the rest of my work without you're explanations.

Is it possible for $f(m,n)=0~?$ If not, then the function is not onto.

For number two: If $f(x)=f(y)$ does that force $x=y~?$ If not then the function is not one-to-one.
• Mar 28th 2014, 01:46 PM
michaelgg13
Re: Explain how these proofs work
ok so correct me if I am wrong on this problem,

Let f : R- --> (7, infinity) prove or disprove f(x) = 5x2 +7 is a bijection.

Suppose y is an element of (7, infinity)

Notice that x = sqrt(y-7)/5 is NOT and element of R- since 7<y<infinity

Thus f is not onto, so it is also not a bijection
• Mar 28th 2014, 01:52 PM
Plato
Re: Explain how these proofs work
Quote:

Originally Posted by michaelgg13
ok so correct me if I am wrong on this problem,

Let f : R- --> (7, infinity) prove or disprove F(x) = 5x2 +7 is a bijection.

Suppose y is an element of (7, infinity)

Notice that x = sqrt(y-7)/5 is NOT and element of R- since 7<y<infinity

Thus f is not onto, so it is also not a bijection

Since $f(-1)=f(1)$ it cannot be an injection so it cannot be a bijection.
• Mar 28th 2014, 02:34 PM
Deveno
Re: Explain how these proofs work
One thing to understand about a function is it has THREE parts:

1. the domain (sometimes called "the source set" or "set of input values").
2. the co-domain (this is NOT the same as the range, the range is the part of the co-domain that f actually "reaches"). This is also sometimes called "the target set".
3. The actual rule that gives us the specific pairs (a,f(a)) for a in the domain.

So you cannot tell if a function is injective or surjective just by looking at 3, you have to look at 1 and 2, as well. For example, the function $f(x) = x^2$ is:

a) Injective, from $\Bbb R^+ \to \Bbb R$ (every positive real number has a unique positive square root, so if two positive squares are equal, and both are squares of a positive real number, the two positive real numbers (their positive square roots) they are squares of, are equal).
b) Surjective, from $\Bbb R \to \Bbb R^+$ (every positive real number is the square of some other positive real number, namely its positive square root)
c) Neither, from $\Bbb R \to \Bbb R$ (both $x$ and $-x$ square to the same number, so $f$ is not injective, and there are no negative squares, so $f$ is not surjective).
d) Bijective (both injective and surjective) from $\Bbb R^+ \to \Bbb R^+$

You can FORCE a function to be injective by restricting its domain, but you may have to SEVERELY restrict it to do so. For example, if $f$ is a constant function, the domain must be restricted to a single point for it to become injective.

You can also FORCE a function to be surjective, by restricting its co-domain to the range of $f$. This is fairly easy to do, but we get a DIFFERENT function when we do this (even though it has "the same rule").

It is often rather hard to FORCE bijectivity, without altering $f$ so drastically it bears little resemblance to what we started with. This is not to say it cannot be done in some cases, but one must proceed with caution. For example, if $f: \Bbb R \to \Bbb R$ is a constant function: $f(x) = c$ for all real $x$, then we can force $f$ to be bijective by considering $f: \{a\} \to \{c\}$, but this function is so "stripped down" it loses a LOT of information.
• Mar 29th 2014, 05:10 AM
emakarov
Re: Explain how these proofs work
Quote:

Originally Posted by Plato
Since $f(-1)=f(1)$ it cannot be an injection so it cannot be a bijection.

There is an easy-to-miss superscript - near R, so I assume the domain is the set of negative numbers.

Quote:

Originally Posted by michaelgg13
Let f : R- --> (7, infinity) prove or disprove f(x) = 5x2 +7 is a bijection.

Suppose y is an element of (7, infinity)

Notice that x = sqrt(y-7)/5 is NOT and element of R- since 7<y<infinity

Thus f is not onto, so it is also not a bijection

First, $x=\frac{\sqrt{y-7}}{5}$ is not a correct solution to $y=5x^2+7$ even for positive $x$. Second, some $x$ that you found is not in the domain. So what? Maybe there is another $x$ that is in the domain and is mapped to the same $y$.
• Mar 30th 2014, 02:09 PM
michaelgg13
Re: Explain how these proofs work
thank you all for the help, I have another question though.

Say that f: Z --> Z and f(n) = 17

Can this be injective? or surjective for that matter?
• Mar 30th 2014, 02:14 PM
emakarov
Re: Explain how these proofs work
Quote:

Originally Posted by michaelgg13
Say that f: Z --> Z and f(n) = 17

For all n or for some n?
• Mar 31st 2014, 09:29 AM
michaelgg13
Re: Explain how these proofs work
Quote:

Originally Posted by emakarov
For all n or for some n?

well the question says

Let f : Z --> Z. State whether or not f is one-to-one (injective) for each of the following.

f(n) = 17

I think it is injective because if a,b are elements of Z, then f(a)=17=f(b).

I just want to know if this is correct or if it cannot not even be injective because there is no n on the right side of the problem.
• Mar 31st 2014, 09:39 AM
emakarov
Re: Explain how these proofs work
Quote:

Originally Posted by michaelgg13
f(n) = 17

I think it is injective because if a,b are elements of Z, then f(a)=17=f(b).

You are not applying the definition of injectivity correctly. Please review it.

Imagine a postal service as a function that maps mail to appropriate houses. Injectivity means that mail for two different houses is not delivered into the same house. Surjectivity means that all houses on the street are served. The function f(n) = 17 deliveres everybody's mail into house #17.
• Mar 31st 2014, 09:57 AM
michaelgg13
Re: Explain how these proofs work
Quote:

Originally Posted by emakarov
You are not applying the definition of injectivity correctly. Please review it.

Imagine a postal service as a function that maps mail to appropriate houses. Injectivity means that mail for two different houses is not delivered into the same house. Surjectivity means that all houses on the street are served. The function f(n) = 17 deliveres everybody's mail into house #17.

Ok, I get it. So because a and b map to the same location, by definition it cannot be injective.
• Mar 31st 2014, 10:02 AM
emakarov
Re: Explain how these proofs work
Yes, different a and b are mapped by f(n) = 17 to the same number.
• Mar 31st 2014, 10:03 AM
Plato
Re: Explain how these proofs work
Quote:

Originally Posted by michaelgg13
Let f : Z --> Z. State whether or not f is one-to-one (injective) for each of the following.

I don't think you understand the definitions of functions.

A function is a set of ordered pairs: $f:A\to B$ means $f\subset A\times B$.
That set of pairs has two necessary properties:
1) No two pairs have the same first term.
2) Every term in $A$ is the first term of some pair in $f$.

A function is injective if no two pairs have the same second term.

A function is surjective if each term in $B$ is the second term of some pair in $f$

Consider $f:\mathbb{Z}\to\mathbb{Z}$ where $f(n)=17$ that means $f=\{(n,17) : n\in\mathbb{Z}\}$
So every term in $f$ has the same second term. So is $f$ injective?
• Mar 31st 2014, 10:33 AM
michaelgg13
Re: Explain how these proofs work
Quote:

Originally Posted by Plato
I don't think you understand the definitions of functions.

A function is a set of ordered pairs: $f:A\to B$ means $f\subset A\times B$.
That set of pairs has two necessary properties:
1) No two pairs have the same first term.
2) Every term in $A$ is the first term of some pair in $f$.

A function is injective if no two pairs have the same second term.

A function is surjective if each term in $B$ is the second term of some pair in $f$

Consider $f:\mathbb{Z}\to\mathbb{Z}$ where $f(n)=17$ that means $f=\{(n,17) : n\in\mathbb{Z}\}$
So every term in $f$ has the same second term. So is $f$ injective?

Thank you for this. f most definitely is not injective cause a and b both map to 17, and by the definition of injectivity they can not.

I need to go back to my OP now though. I asked about

Let f : Z x Z --> Z state whether the following function is onto or not, then prove or disprove.

and I have four different functions I need to prove or disprove. Like I said I understand Z x Z -->Z is the doman/codomain. But is this basically the same as Z -->Z because Z x Z is all integers, or is that incorrect? I know the Cartesian product would be something like (1,1) (1,2) (1,3) etc... for all integers.

seeing as I still don't fully understand how you incorporate the domain/codomain into a problem, how would you do this one?

Don't give me the answer, but for example, explain how you would incorporate this domain/codomain into proving/disproving f(m,n) = 2m+n

I really appreciate all of everyone's help. I really have a hard time following how my professor teaches things. This forum and youtube have been valuable tools in helping me learn.
• Mar 31st 2014, 11:20 AM
Plato
Re: Explain how these proofs work
Quote:

Originally Posted by michaelgg13
In $f: \mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ the set $\mathbb{Z}\times\mathbb{Z}$ is the initial set and $\mathbb{Z}$ is the finial set.
Ordered pairs of integers are mapped to an integer: $(m,n)\mapsto k$ so $f=\{((m,n),k) : (m,n)\in(\mathbb{Z}\times\mathbb{Z})~\&~k\in \mathbb{Z}\}$.