# relationship help

• October 9th 2009, 02:29 PM
garrett12
relationship help
Just wondering if I could have some help proving that there is an injection from the set of all integers to the set of all reals. I think I need to use the identity function but not too sure

Thanks!
• October 9th 2009, 02:32 PM
tonio
Quote:

Originally Posted by garrett12
Just wondering if I could have some help proving that there is an injection from the set of all integers to the set of all reals. I think I need to use the identity function but not too sure

Thanks!

Is the identity function an injection? Well, there you go.

Tonio
• October 10th 2009, 12:16 AM
garrett12
Thanks for the reply. I get how the identity function is an injection, but I don't quite get the formal way to write a proof saying that the injection exists between Z and R. Any hints on the formal definition?
• October 10th 2009, 02:12 AM
Defunkt
Quote:

Originally Posted by garrett12
Thanks for the reply. I get how the identity function is an injection, but I don't quite get the formal way to write a proof saying that the injection exists between Z and R. Any hints on the formal definition?

$f:\mathbb{Z} \to \mathbb{R}$ is an injection if $\forall x,y \in \mathbb{Z} , f(x) = f(y) \Rightarrow x = y$

Let $f(x) = x$, the identity function. Let $x_0, y_0 \in \mathbb{Z}$ such that $x_0 \neq y_0$. Then, obviously, $f(x_0) \neq f(y_0)$ and so $f(x)$ is an injection.
• October 10th 2009, 06:13 PM
garrett12
Thanks Defunkt, that was what I was looking for. Just another quick question, along the same lines. If I'm asked to prove that the injection relationship is reflexive and transitive - but i'm not given a domain or range with it - how would i go about proving this? Can I just make up my own domain and range that it works for and then prove that?

Thanks
• October 10th 2009, 10:52 PM
Defunkt
Quote:

Originally Posted by garrett12
Thanks Defunkt, that was what I was looking for. Just another quick question, along the same lines. If I'm asked to prove that the injection relationship is reflexive and transitive - but i'm not given a domain or range with it - how would i go about proving this? Can I just make up my own domain and range that it works for and then prove that?

Thanks

You don't "make up" your domain and range -- you have to show that it holds for any domain and range, ie. that:

if there exist injections $f:X \to Y$ , $g: Y \to Z$ then there exists an injection $h:X \to Z$ (this is transitivity).

and that for any set X, there exists an injection $f:X \to X$

Can you finish from here?
• October 11th 2009, 12:18 AM
garrett12
Quote:

Originally Posted by Defunkt
You don't "make up" your domain and range -- you have to show that it holds for any domain and range, ie. that:

if there exist injections $f:X \to Y$ , $g: Y \to Z$ then there exists an injection $h:X \to Z$ (this is transitivity).

and that for any set X, there exists an injection $f:X \to X$

Can you finish from here?

I have trouble coming up with the formal ways of explaining it..

For transitivity:

If f:X->Y and g:Y->Z are injections..
For all x in X, y in Y and z in Z s.t f(x) = y and f(y) = z, ???

I get that xRz as no other unique value from X can relate to z but can't explain it :(

For symmetric:

Should the identity function be used again here? Seems like it should be
• October 11th 2009, 01:00 AM
Defunkt
Quote:

Originally Posted by garrett12
I have trouble coming up with the formal ways of explaining it..

For transitivity:

If f:X->Y and g:Y->Z are injections..
For all x in X, y in Y and z in Z s.t f(x) = y and f(y) = z, ???

I get that xRz as no other unique value from X can relate to z but can't explain it :(

For symmetric:

Should the identity function be used again here? Seems like it should be

To show transitivity, you need to show that given that there are injections $f:X \to Y \ , g: Y \to Z$, there is an injection $h:X \to Z$.

Easily enough, let $h = g \circ f$, then $h:X \to Z$. Can you show that h is an injection?

For reflexivity: The identity function is an injection from X to X.

The relation is not symmetric, though. Can you see why?
• October 11th 2009, 11:24 AM
garrett12
Quote:

Originally Posted by Defunkt
To show transitivity, you need to show that given that there are injections $f:X \to Y \ , g: Y \to Z$, there is an injection $h:X \to Z$.

Easily enough, let $h = g \circ f$, then $h:X \to Z$. Can you show that h is an injection?

For reflexivity: The identity function is an injection from X to X.

The relation is not symmetric, though. Can you see why?

Could I use the counterexample of X={1,2,3} Y={7,8,9} and say that (1,3) is in the relation, but (3,1) is not?

And would a correct counterexample for antisymmetry be X={1,2,3} Y={1,2,3,4} and say that (1,2) is in the relation and (2,1) is in the relation but 2 != 1?
• October 11th 2009, 11:52 AM
Defunkt
Quote:

Originally Posted by garrett12
Could I use the counterexample of X={1,2,3} Y={7,8,9} and say that (1,3) is in the relation, but (3,1) is not?

And would a correct counterexample for antisymmetry be X={1,2,3} Y={1,2,3,4} and say that (1,2) is in the relation and (2,1) is in the relation but 2 != 1?

No, that is incorrect. The relation is between whole sets, ie. if $X = \left\{1,2,3\right\}, Y = \left\{7,8,9\right\}$ then $(X,Y)$ is in the relation and so is $(Y,X)$ since there is an injection from X to Y and also an injection from Y to X.

A proper counterexample to symmetry would be $X = \{1\}, Y = \{1,2\}$. Obviously, there is an injection from X to Y however there is no injection from Y to X, and so $(X,Y)$ would be in the relation but $(Y,X)$ would not be.

Can you come up with an example to anti-symmetry now?
• October 12th 2009, 02:52 AM
garrett12
Quote:

Originally Posted by Defunkt
No, that is incorrect. The relation is between whole sets, ie. if $X = \left\{1,2,3\right\}, Y = \left\{7,8,9\right\}$ then $(X,Y)$ is in the relation and so is $(Y,X)$ since there is an injection from X to Y and also an injection from Y to X.

A proper counterexample to symmetry would be $X = \{1\}, Y = \{1,2\}$. Obviously, there is an injection from X to Y however there is no injection from Y to X, and so $(X,Y)$ would be in the relation but $(Y,X)$ would not be.

Can you come up with an example to anti-symmetry now?

Right, well for anti-symmetry I think that you just need the two sets to have the same cardinality and different elements to prove that it is not antisymmetric.

E.g X = {1,2,3}, Y={4,5,6}

There exists an injection from X->Y and Y->X, however X != Y. Hence the relation is not antisymmetric.

?
• October 12th 2009, 06:42 AM
Defunkt
Quote:

Originally Posted by garrett12
Right, well for anti-symmetry I think that you just need the two sets to have the same cardinality and different elements to prove that it is not antisymmetric.

E.g X = {1,2,3}, Y={4,5,6}

There exists an injection from X->Y and Y->X, however X != Y. Hence the relation is not antisymmetric.

?

Yep, that is correct!