Thread: discrete math functions

1. Can a function be a reflexive relation? Explain
2. Is it possible for a function f: R implies R to be symmetric as a relation? Give an example or explain why answer is no
3. Is it possible for a function f: R implies R to be transitive as a relation? Give an example or explain why answer is no
4. Suppose f: A implies B and g: B implies C are functions. If g o f is one to one and f is onto, show that g is one to one.
5. Let [A] = n and [B] = m for n,m belongs to N. use the definition of cardinality of a finite set to show that if A intersects B = empty set, then [A union B] = n + m

Originally Posted by glost

1. Can a function be a reflexive relation? Explain
2. Is it possible for a function f: R implies R to be symmetric as a relation? Give an example or explain why answer is no
3. Is it possible for a function f: R implies R to be transitive as a relation? Give an example or explain why answer is no

yes to all. the identity function is an example for all of these

defined by for all ...........it is not R "implies" R by the way, it is f:R --> R, or f maps from R to R, or f: R to R or something

i leave it to you to check that this is a reflexive, symmetric and transitive relation (aka, an equivalence relation)

4. Suppose f: A implies B and g: B implies C are functions. If g o f is one to one and f is onto, show that g is one to one.

do you know the definitions for one-to-one and onto?

remember (g o f)(x) = g(f(x)). what does it mean for this function to be one-to-one? what does it mean for f to be onto? playing around with these definitions should help

5. Let [A] = n and [b] = m for n,m belongs to N. use the definition of cardinality of a finite set to show that if A intersects B = empty set, then [A union B] = n + m

what definitions are you working with? i'd say use induction on the cardinality of one of the sets. but maybe the definition you are using will give us an easier way. you may also want to look at the proof of theorem 1 here

Originally Posted by Jhevon

yes to all. the identity function is an example for all of these

defined by for all ...........it is not R "implies" R by the way, it is f:R --> R, or f maps from R to R, or f: R to R or something

i leave it to you to check that this is a reflexive, symmetric and transitive relation (aka, an equivalence relation)

do you know the definitions for one-to-one and onto?

remember (g o f)(x) = g(f(x)). what does it mean for this function to be one-to-one? what does it mean for f to be onto? playing around with these definitions should help

what definitions are you working with? i'd say use induction on the cardinality of one of the sets. but maybe the definition you are using will give us an easier way. you may also want to look at the proof of theorem 1 here

the cardinality of a finite set is the number of elements in the set

Originally Posted by tygracen

the cardinality of a finite set is the number of elements in the set

do you know glost? how do you know that's the definition? it is not a very mathematically precise definition, by the way, doesn't help much to proving something in a rigorous sense--as the problem requested.

Originally Posted by Jhevon

do you know glost? how do you know that's the definition? it is not a very mathematically precise definition, by the way, doesn't help much to proving something in a rigorous sense--as the problem requested.

yes, I do know glost, she is as lost as I am. that is the definition that my book gives.

Originally Posted by tygracen

yes, I do know glost, she is as lost as I am. that is the definition that my book gives.

are you familiar with things like induction, functions (particularly bijective ones), things of that sort. what tools to you have at your disposal for solving problems like this?

Hi!!
You should focus on the relation between a mathematical relation and a function.
Like it was asked if a function can be reflexive relation. Answer is yes (f(x)=x).now you may think when a relation becomes a function. If a relation can become function then as like a relation a function can also be reflexive,symmetric,transitive etc.(I hope you know what is the difference between a function and a relation). Now think can being reflexive,symmetric,transitive etc become a hurdle to a relation for being a function (its easy but sort it out urself)
4) f:A-->B
g:B--C
gof is one to one i.e if gof(a)=gof(b) then a=b
f is onto i.e for Every element of set B There is a pre image in set A
[a belengs to A,b belongs to b]
let g(b1)=g(b2)
since f is onto b1 and b2 will surely have pre-image in A
such that f(a)=b
therfor g(f(a1))=g(f(a2))
gof(a1)=gof(a2)
so a1=a2
f(a1)=f(a2)
b1=b2
so finally we have
if g(b1)=g(b2) then b1=b2 hence g is one to one
5) its very easy you may prove it using venn diagram (cardinality is number of elements in the set]

Hi nikhil

good to see you participating in our forum!

Originally Posted by nikhil

Hi!!
You should focus on the relation between a mathematical relation and a function.

interesting word choice

5) its very easy you may prove it using venn diagram (cardinality is number of elements in the set]

in general, proofs via Venn Diagrams are not accepted as valid. i'd recommend waiting on the poster to see what weapons she has in her arsenal to tackle this problem

Hi!Jhevon
thanks for a warm reply

Originally Posted by Jhevon

in general, proofs via Venn Diagrams are not accepted as valid. i'd recommend waiting on the poster to see what weapons she has in her arsenal to tackle this problem

I agree that in general,proofs by venn diagram are not accepted(wonder why ?) but they are good analytical tools.
I'd definetly wait to see her hitting the jackpot!!