Register to reply

Abstract math help if possible

by H2Pendragon
Tags: abstract, math
Share this thread:
H2Pendragon
#1
Dec12-08, 12:50 AM
P: 17
Man I've become desperate. I just signed up needing help on this homework. Can anyone help me with these two problems?

Let A be the set {1,2,3,4}. Prove that a relation R on A with 15 ordered pairs is not transitive.

I've got no clue on that one.



And this second one, which I know the proof, but I need some help wording it correctly:

If f is injective (one-to-one) and C subset D are any subsets of A, then f(D-C) = f(D) - f(C).

I know the proof, but every time I try and word it, it just sounds wrong.
Phys.Org News Partner Science news on Phys.org
What lit up the universe?
Sheepdogs use just two simple rules to round up large herds of sheep
Animals first flex their muscles
lurflurf
#2
Dec12-08, 04:05 AM
HW Helper
P: 2,264
Since there are 16 possible ordered pairs, if 15 are in the relation only 1 is omited. Show that there exist a pair of pairs that implicate the omited pair.
hint can you do
Let A be the set {1,2,3}. Prove that a relation R on A with 8 ordered pairs is not transitive.
or
Let A be the set {1,2}. Prove that a relation R on A with 3 ordered pairs is not transitive.


Since the function is injective you can work with f(x) instead of x.
if f(x) is in f(D-C) what can we say about x.
if f(x) is in f(D)-f(C) what can we say about x.
crazyjimbo
#3
Dec12-08, 07:05 AM
P: 13
Quote Quote by lurflurf View Post
Let A be the set {1,2}. Prove that a relation R on A with 3 ordered pairs is not transitive.
What about {(1,1), (1,2), (2,2)}?

EDIT: Sorry, I'm just being nit-picky. The general case and idea is sound. It works for 3 elements and above.

lurflurf
#4
Dec12-08, 07:25 AM
HW Helper
P: 2,264
Abstract math help if possible

Quote Quote by crazyjimbo View Post
What about {(1,1), (1,2), (2,2)}?

EDIT: Sorry, I'm just being nit-picky. The general case and idea is sound. It works for 3 elements and above.
My mistake darn combinatorics.
H2Pendragon
#5
Dec12-08, 07:41 AM
P: 17
Quote Quote by lurflurf View Post
Since there are 16 possible ordered pairs, if 15 are in the relation only 1 is omited. Show that there exist a pair of pairs that implicate the omited pair.
hint can you do
Let A be the set {1,2,3}. Prove that a relation R on A with 8 ordered pairs is not transitive.
or
Let A be the set {1,2}. Prove that a relation R on A with 3 ordered pairs is not transitive
See I really have no idea on this. I know I'm only omitting one but I have no idea why that would cause a problem. The book we're using is pretty bad and I suspect it's not telling me something important.

{(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4)}
crazyjimbo
#6
Dec12-08, 08:01 AM
P: 13
If you pick one ordered pair and remove it from that relation you have listed, can you find an example of ordered pairs such that (a,b) and (b,c) is in the relation but (a,c) isn't? I.e. the relation isn't transitive.

At first pick an actual pair. You should then see that the case is the same whichever pair you remove, which answers your question.
H2Pendragon
#7
Dec12-08, 08:09 AM
P: 17
Ok, I see the problem at least. I couldn't visualize with symmetric originally. But if you have (4,3) and (3,4) but not (4,4) you aren't transitive. Well at least that group isn't, but it's supposed to be for any a,b,c right?

Now the problem is... how do I put that in words?
crazyjimbo
#8
Dec12-08, 08:24 AM
P: 13
If you remove (a,b) then since you have four elements you can pick an element c which isn't equal to a or b. Try going from there.

This is the condition which doesn't hold with only two elements.
H2Pendragon
#9
Dec12-08, 08:30 AM
P: 17
So does this seem sufficient?:

A relation R on A has 16 possible ordered pairs. Let R be a relation on A with 15 ordered pairs excluding aRc. Since all the other remaining pairs are in R, then aRb and bRc. However, since a does not relate to c, R is not transitive.
HallsofIvy
#10
Dec12-08, 11:13 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,533
Yes, that is perfectly good.

By the way, this should have been posted in the "homework and coursework" section.


Register to reply

Related Discussions
Sequence Limit (abstract math) Calculus & Beyond Homework 2
How Abstract Are You In Math? General Math 27
Abstract algebra Calculus & Beyond Homework 2
Always abstract? Linear & Abstract Algebra 1
Abstract alg - SL(2,Z3) Linear & Abstract Algebra 1