is anybody good at discrete math?

- anonymous

is anybody good at discrete math?

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- perl

me

- anonymous

Thanks!!

- anonymous

alright my question is how do you figure out if anything is antisymmetric

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- perl

thats not very specific

- anonymous

like okay R1 (1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)

- perl

In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X
if aRb and bRa then a = b,

- anonymous

yeah but how does that explain if this is antisymmetric or not

- perl

well first you have to state what the relation is, equality? less than, greater than? division modulo n?

- perl

I would say this is not anti-symmetric because you have
(3,4) ( 4,1) but 3 does not equal 1

- perl

if you delete the point (3,4) then it is anti-symmetric

- anonymous

what about (1,2) and (2,1) and (1,1)

- anonymous

Wait so basically its anti symmetric if no points equal each other like a is not equal 2 b?

- perl

1R2 and 2R1 so 1 =1 is true

- anonymous

ohh so in that situation a = b?

- anonymous

and if thats the case then it would be antisymmetric

- perl

well the order relation <= is anti-symmetric

- perl

so the definition of anti-symmetry generalises what we find in the usual order relation <= .
for instance if a<=b and b <= a , then a = b , where a,b are integers and <= means less than or equal (usual ordering).
but notice you can have unusual relations, like subset.
if A is a subset of B and B is a subset of A, then A = B

- anonymous

i dnt get that sorry this type of math is really confusing it took me 3 weeks to understand sets and now im trying to understand relations bim pretty much behind in class :/

- anonymous

That make sense but how does that apply to that problem

- perl

well we try to find in math the most general or abstract definitions. we find definitions that strip the terms of any specific meaning, so we can generalise to many different types of relations.

- perl

so we find many 'things' that behave in math just like the ordering <= where 2<= 3 . in advanced math we look for patterns

- anonymous

Yeah thats why im being confused because im so used to specific examples that this abstract way of thinking leaves me lost in the dark

- anonymous

ohhh okay

- perl

so how do you define <= . when you define it, you realise that other mathematical objects behave similiar to how 2 <= 3 . for instance {1,2} is a subset of {1,2,3}

- anonymous

Yeah
i get that

- perl

so you could say {1,2} < {1,2,3} , or you could say <= to indicate that it is not a proper subset

- anonymous

alright

- perl

so using our austere definition we have R is antisymmetric
if whenever (a,b) is in R and (b,a) is in R, then it must be the case that a = b

- anonymous

OHHHH IGET IT !!!!!!!

- anonymous

lol thanks but hold on
lol hold on

- perl

lol

- perl

right, aRb is the same thing as saying (a,b) is in R. or equivalent

- anonymous

wait but if thats the case where (a,b) element of R and (b,a) an element of R and a = b then isnt that kinda like being symmetric

- anonymous

because (1,2) is symmetric to (2,1)

- perl

symmetric is different

- anonymous

how so

- perl

R is symmetric when if (a,b) is in R, then (b,a) is in R

- anonymous

thats the same thing i said tho

- perl

antisymmetry is different

- perl

right, sorry i didnt see what you wrote

- anonymous

yeah but using that.. isnt that the same as antisymmetric

- perl

ok so here are some examples one sec , thinking

- anonymous

okay

- perl

R = { (1,1) (2,1) (2,1) } is antisymmetric.
R= { (1,1) , (1,2) (2,1) } is symmetric

- perl

A relation can be both symmetric and antisymmetric

- perl

woops

- perl

R= { (1,1) ( 1,2) } is anti symetric

- anonymous

a null set would be everything but i dnt get why the first one is antisymmetric

- anonymous

a = 2 right?

- anonymous

and b = 1?

- anonymous

lol careful you are speaking to an open mind at the moment

- perl

R= { (1,1) ( 2,1) } is antisyemmetric

- perl

The terms 'symmetric' and 'anti-symmetric' apply to a binary relation R:
R symmetric means: if aRb then bRa.
R anti-symmetric means: if aRb and bRa, then a=b.

- anonymous

okay i get that now because a in the R = {(1,1), (2,1)} is basically 1 and b is 1 as well
so a is 1 in the (1,1) and b is 1 in the (2,1) right?

- perl

well it satisfies it because it doesnt violate it

- perl

it satisfies it trivially, since there is no occurence of both (a,b) and (b,a) in R
R = {(1,1), (2,1)}

- perl

the antisymmetry is an 'AND' condition. if you have both (a,b) AND (b,a) , then a=b.
the symmetry condition is if-then condition

- anonymous

hmm i guess sheesh why is this math so hard i swear who thinks of creating stuff like this

- perl

well they are both if then conditions, but the antisymmetry has a little extra in it

- anonymous

okay so symmetry mean something must happen first then something else happen.. its like a program

- perl

R is symmetric means: if (a,b) is in R then (b,a) is in R.
R anti-symmetric means: if (a,b) and (b,a) is in R, then a=b.

- anonymous

okay so what about this one (3,4) what properties you give this
in my eyes i see no reflexive no symmetry no antisymmetry and no transitive

- perl

yes its like rules for a checking program , you could program it to check

- anonymous

okay

- perl

so just that one point?
R = { ( 3,4) } ?

- anonymous

yea

- perl

then it is not symmetric, but it is anti-symmetric (trivially)

- anonymous

its in an example in my book i hate that they dnt explain stuff

- anonymous

Yes thats what they said but it makes no sense

- perl

it is anti symetric why? do you see, because it is an if then condition

- anonymous

how its only (3,4)

- perl

if (a,b) and (b,a) are in R, then a=b. but you dont have (a,b) and (b,a) in R

- anonymous

yea okay you just have (a,b)

- perl

because 'if-then' is true when the 'if' part is false

- perl

i think thats called trivial or vacuously true. we just say true though :)

- anonymous

are you talking about the logic statement if p is false but q is true then the whole statement ends up being true?

- perl

p-> q is true when p is false.

- perl

or another way to read the definition... is
,

- perl

Program:
if you can find two points in your relation (a,b) & (b,a) .... then it must be the case that
a = b.
else true

- perl

or true otherwise

- anonymous

and a specific example would be (3,4) so basically any single point except (1,1) or other any points similar to that are antisymmetric

- perl

Program: if you can find two points in your relation (a,b) & (b,a) .... then it must be the case that a = b. (if a does not equal B then your anti-symmetry is false.)
otherwise true (if you cant find any two points (a,b) (b,a) )

- perl

right , any relation
R = { (a,b) } is antisymmetric , trivially , since there is only one point

- perl

since you need at least two points to even check the condition

- anonymous

true cool so one answer down for the rest of my life a single point is antisymmetric

- perl

lol

- perl

well, you have to be more precise.
the relation R= { (a,b)} is anti symmetric

- perl

and also better say its a binary operation, and 'point' is an element of your relation aRb or (a,b) ordered pair

- anonymous

yeah lol that .. R = { (a,b) }

- perl

now, how can we make your original relation antisymmetric. can we delete something

- anonymous

okay i get you

- perl

R= { (1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4) }
now what are the least amount of points we can delete to make this anti-symmetric
its no fair if we delete all but one , lol

- anonymous

lol okay

- anonymous

all try my best

- anonymous

ill*

- perl

ask yourself, why does it fail anti-symmetry (clue)

- anonymous

(4,40 and (1,1) and (2,2) and (3,4)

- anonymous

(4,4) i meant

- anonymous

everything left will make it anti symmetric

- perl

let's see

- anonymous

wait no keep (4,4)

- anonymous

so the elements shall be (1,2), (2,1), (4,1), (4,4)

- perl

right, i guess there is more than one solution, ok can you write out the new R

- perl

actually (4,4) is fine

- anonymous

so R = { (1,2), (2,1) , (4,1) , (4,4)}

- anonymous

wow thanks your like a teacher right.. you have to be.. if not you should Seriously!!! lol

- anonymous

huh but wont you need (4,1) to be with (4,4)

- perl

thanks.
we have to be careful though

- perl

lets look at the definitoin again

- anonymous

ohh yeah i forgot its a single element once the the other antisymmetric elements are taken out of play.. right?

- perl

R anti-symmetric means: if (a,b) and (b,a) is in R, then a=b.

- anonymous

Ohh and even so a = 1 and b= 1 ohh okay!!

- anonymous

Yeah so its the one!!

- perl

but you have (1,2) (2,1) so 2 = 1 , that is false

- anonymous

so (4,4) can be out or in right?

- perl

or (1,2) and (2,1) are in R , but 1 != 2, i use != for not equal

- perl

(4,4) can be in

- perl

ok lets start from left to right

- anonymous

i think i get it.. it might be misconstrued but i get it better than how this conversation began

- anonymous

okay

- perl

(1,1) is fine . now (1,2) and (2,1) is a problem, so we have to delete one or the other

- perl

remember we only look at pairs of (a,b) , (b,a)

- perl

we dont care about points that are not in the form (a,b) (b,a)

- anonymous

ohh okay

- perl

so thats the only problem i see , (1,2) (2,1)

- perl

so there are two possible solutions for problem outline above
R = { (1,1), (2,1),(2,2),(3,4),(4,1),(4,4) }
R= { (1,1),(1,2) ,(2,2),(3,4),(4,1),(4,4) }

- perl

thats two antisymmetric relations , which i deleted minimal number of terms

- perl

given the original R

- anonymous

See this is where i mess up and im just realizing i do this i look at (1,2) and call that (a,b) then i look at (2,1) and call that (b,a) lol like i see it in reverse.. okay am i looking at it wrong or what

- anonymous

ahh i see so an easy way to look at it is to see where a = b or b = a?

- perl

yes if (a,b) is (1,2) then (b,a) is (2,1) , correct

- perl

so there is your only potential 'problem'

- perl

because clearly 1 is not equal to 2

- anonymous

yeah true

- anonymous

okay i understand

- anonymous

okay ill right out a set

- perl

ok :)

- anonymous

R5 = { (1,1), (1,2) , (1,3) , ( 1,4) , ( 2,2) , ( 2,3) ,( 2,4) , (3,3) , (3,4) ,( 4,4) }

- anonymous

well set A = {1,2,3,4}

- anonymous

So that R 5 is a relation of the set

- perl

why do you call it R5, thats just a label , like R_5

- anonymous

ehh i just say that because i cant make a sub script

- perl

no problem, so you want to know if R5 is antisymmetric?

- anonymous

and okay This is Reflexive, but not symmetric, this is transitive, but not antisymmetric

- perl

it looks antisymmetric, i dont see any 'inverse pairs', like (a,b) (b,a) .

- perl

where the (a,b) are switched

- anonymous

well i thought it has to be for all values of a and b not just for some?

- perl

whatever is in your relation ,

- anonymous

so the antisymmetric part would be (3,4) and (4,4)

- perl

no because (3,4) and (4,3) are not in the relation

- anonymous

ohh i see your point sorry i mixed that up

- perl

you have to find a pair like (1,2) (2,1) when it fails antisymmetry
,

- anonymous

(1,2) and (2,2)

- perl

dont want to call it 'anti anti-symmetry'. lets just say it is 'not' antisymmetric if we can find a pair (a,b) (b,a)

- perl

nope, (1,2) and (2,2) are fine. (1,2) and (2,1) are a problem

- anonymous

yeah we cant find a pair
so because of that its antisymmetric?

- perl

yes !!

- perl

so it 'trivially' satisfies the antisymmetric condition

- anonymous

ohh okay i get this abstract thing however where my other deductions correct?

- anonymous

were*

- perl

I found an equivalent condition. might be easier to read
R is antisymmetric if whenever (a,b) is in R with a ≠ b then (b,a) must not be in R

- anonymous

okay makes sense.. so what about the transitive property

- perl

So if you can find at least two points (a,b) (b,a) with a not equal to b, then it is not antisymmetric relation. Otherwise it is antisymmetric

- perl

transitive,
if aRb and bRc , then aRc
if (a,b) is in R and (b,c) is in R, then it must be that (a,c) is in R

- anonymous

SO we have (2,3) (3,4) and (2,4) is that what makes it transitive

- perl

you have to check all possibilities R5 = { (1,1), (1,2) , (1,3) , ( 1,4) , ( 2,2) , ( 2,3) ,( 2,4) , (3,3) , (3,4) ,( 4,4) }

- perl

yes you are right

- anonymous

ohh and i have a question as long as i find one thing inside the relation does that make the whole relation transitive or symmetric or whatever?

- perl

(2,3) (3,4) are in R, so it must be that (2,4) in R. (and it is) , similarly we check other candidates

- perl

if you find one example? no you have to check to make sure that if (a,b) (b,c) are in R then (a,c) is in R. for any a,b,c

- perl

but you can do shortcuts. if you have (a,b) and (b,b) then transitive says (a,b) must be in it, and clearly that is already there

- anonymous

ohh okay so (1,2) (2,3) (1,3)

- perl

yes that works

- anonymous

(1,3) (3,4) (1,4) that makes 3

- anonymous

but thats it how will i know when i satisfied the quota to make it transitive or any other property

- perl

so basically we have to check
(1,2) (2,3) --> (1,3) is in R
(1,3) (3,4) ---> (1,4) is in R...

- perl

when there is nothing left to check

- anonymous

but their is some thing left to check (1,1) (2,2) (3,3) (4,4)

- perl

and we dont need to check (a,a)

- anonymous

and those are not transitive they are reflexive

- anonymous

ohh okay

- anonymous

make sense

- perl

let me check reflexive relation, i believe a relation is reflexive when..

- anonymous

great so i now understand transitive and antisymmetric and oddly enough the symmetric property thanks to you ^_^

- perl

In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself

- perl

so we need (1,1 ) (2,2) (3,3) (4,4)

- perl

if you are going to use elements 1,2,3,4 in your R

- perl

if we dont use 4 at all in our R, then we dont need (4,4)

- anonymous

ohkay

- anonymous

makes sense

- perl

for instance, im going to delete terms

- anonymous

alright

- perl

R = { (1,1), (1,2) , (1,3) , ( 2,2) , ( 2,3) , (3,3) }

- perl

this is antisymmetric, transitive, reflexive

- anonymous

okay shall i prove it

- perl

sure , you can check exhaustively

- perl

that just means you exhaust the possibilities

- anonymous

(claps hands) time to work..

- anonymous

its antisymmetric because (2,3) and (3,3) and its reflexive because (1,1) (2,2) (3,3) and
its transitive because (1,2) (2,3) (1,3)

- perl

it is antisymmetric because there are no pairs (a,b) and (b,a) in R . so it satisfies antisymmetry trivially

- anonymous

dammit i always mess that one up .. lol

- perl

heheh

- anonymous

ill learn over dam lol

- anonymous

ill learn over time i meant to say

- perl

try the new equivalent definition,
whenever (a,b) is in R then (b,a) cannot be in R. if it is in R , then it is not antisymmetric relation

- perl

if both (a,b) and (b,a) are in R, then it is not antisymmetric , (where a and b are distinct)

- anonymous

ohh okay but if (b,a) is in R then a must equal to b for to be antisymmetric

- perl

so in other words, you are looking for counterexamples to antisymmetry. if you cannot find any counterexamples (a,b) and (b,a) , then it is true antisymmetry

- perl

yes, which brings you back to the old definition

- anonymous

great this makes sense now

- perl

many paths that lead to Rome

- anonymous

by the way what is irreflexive?

- perl

An irreflexive, or anti-reflexive, relation is the opposite of a reflexive relation. It is a binary relation on a set where no element is related to itself. An example is the "greater than" relation (x>y).

- perl

so R = { (1,1) } is not irreflexive
R = { (1,2) } is irreflexive

- anonymous

ohh that easy!!

- anonymous

okay i understood that off rip

- perl

actually, reflexive, irreflexive, and antisymmetry are easy to check. the one that takes a bit of work is transitive

- anonymous

yeah now that i understand them it does take me a bit longer to figure out the transitive ones

- perl

now, we define an 'equivalence relation' as a relation which is reflexive, symmetric, and transitive.

- anonymous

ahh yes i was just reading about that

- perl

there are also 'order' relations,. partially orders , and total orders

- anonymous

yeah i have no idea about those havent read up to that part yet

- perl

so now we see the point of all this work . we can define equivalence relations, and order relations using the definitions we used earlier (transitive, reflexive, symmetric, antisymmetric, etc)

- anonymous

Yeah just about to bad those i might have to get into tomorrow its like 4 am right nw

- perl

well now you a grasp of this :)

- anonymous

Yup!! :)

- anonymous

thanks

- perl

yeah the book should be clear about the 'trivial' satisfying . that a relation can trivially satisfy antisymmetry (since there are no pairs (a,b) (b,a) ).

- perl

this gets into the logic thing, p->q is true in the case that p cannot be satisfied. for instance , the empty set is a subset of any set.

- anonymous

it does but i understand best when some one is pointing me in the right direction especially when i have questions which the book doesnt ever want to answer

- perl

its like, the definition says
for all a,b in R
if (a,b ) & (b,a) is in R then a=b.
well, what if there are no (a,b), (b,a) in R. then it is taken to be true vacuously or trivially/

- perl

but it is easier to just look for (a,b) (b,a) where a not equal to b. If you find it, it is not antisymmetric, if you cannot find it then it is antisymmetric

- perl

It is often easier to use 'equivalent' definitions. also for programming :)

- anonymous

Hmm how so?

- perl

computer programmers have different needs than mathematicians . mathematicians want precise rigor , to be able to prove things. but at a cost , it might be harder to understand what the mathematician is talking about .

- perl

computer programmers are not as concerned with proving things . computer scientists, maybe. :)

- anonymous

I am
a programmer well tryna be

- perl

here is the way mathematicians define antisymmetry ,
http://en.wikipedia.org/wiki/Antisymmetric_relation

- anonymous

lol well thanks for the help i must go to bed thanks ^_^

- perl

gnite :)

- anonymous

yea hthe upside down A means for all right

- perl

right

- perl

R(a,b) means (a,b) is in R

- perl

I like this part
R is antisymmetric
.. if R(a,b) with a ≠ b, then R(b,a) must not hold.

- perl

i got that from wikipedia. thats the easiest way to look at it

Looking for something else?

Not the answer you are looking for? Search for more explanations.