Results 1 to 11 of 11

Math Help - Relations on A

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Relations on A

    Def:
    R is irreflexive iff. a\nsim a \ \forall a\in A
    Not irreflexive iff. \exists a\in A \ni a\sim a
    R is asymmetric iff. if a\sim b, then  b\nsim a
    Not asymmetric iff. \exists a\sim b and b\sim a
    R is anti-symmetric iff. if a\sim b \ \mbox{and} b\sim a, then a=b.
    Not anti-symmetric iff. \exists a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b
    \bigtriangleup ={(a,a)|a\in A}

    Proofs:
    Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.

    Since R is symmetric, assume  a\sim b \ \mbox{and} \ b\sim a. Then, since R is transitive, a\sim a. Therefore, R is not irreflexive.
    Q.E.D.

    If R\cap R^{-1}=\bigtriangleup, then R is anti-symmetric.

    (1) R\cap R^{-1}\subseteq\bigtriangleup
    Let (a,b)\in R\cap R^{-1}. Therefore, (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R. By the anti-symmetric hypothesis, if a\sim b \ \mbox{and} \ b\sim a, then a=b.

    (2) \bigtriangleup\subseteq R\cap R^{-1}
    (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b\rightarrow a\sim b \ \mbox{and} \ b\sim a \rightarrow (a,b)\in R^{-1} Thus, (a,b)\in R\cap R^{-1}

    Hence, R is anti-symmetric.

    If R is transitive and irreflexive, then R is asymmetric.

    By contradiction: Suppose R is transitive and irreflexive and R is not asymmetric.
    Let a\sim b \ \mbox{and} \ b\sim a. By transitivity, a\sim a. However, R is irreflexive. Therefore, we have reached a contradiction and R is asymmetric.

    Are these all logically correct?
    Last edited by dwsmith; November 20th 2010 at 11:52 AM. Reason: typed in wrong word for the first proof symmetric should have been irreflexive
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    Def:
    R is irreflexive iff. a\nsim a \ \forall a\in A
    Not irreflexive iff. \exist a\in A \ni a\sim a
    R is asymmetric iff. if a\sim b, then  b\nsim a
    Not asymmetric iff. \exist a\sim b and b\sim a
    R is anti-symmetric iff. if a\sim b \ \mbox{and} b\sim a, then a=b.
    Not anti-symmetric iff. \exist a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b
    \bigtriangleup ={(a,a)|a\in A}

    Proofs:
    Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.


    If this one was true then there wouldn't be equivalence relations...

    Tonio



    Since R is symmetric, assume  a\sim b \ \mbox{and} \ b\sim a. Then, since R is transitive, a\sim a. Therefore, R is not symmetric.
    Q.E.D.

    If R\cap R^{-1}=\bigtriangleup, then R is anti-symmetric.

    (1) R\cap R^{-1}\subseteq\bigtriangleup
    Let (a,b)\in R\cap R^{-1}. Therefore, (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R. By the anti-symmetric hypothesis, if a\sim b \ \mbox{and} \ b\sim a, then a=b.

    (2) \bigtriangleup\subseteq R\cap R^{-1}
    (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b\rightarrow a\sim b \ \mbox{and} \ b\sim a \rightarrow (a,b)\in R^{-1} Thus, (a,b)\in R\cap R^{-1}

    Hence, R is anti-symmetric.

    If R is transitive and irreflexive, then R is asymmetric.

    By contradiction: If R is transitive and irreflexive, then R is not asymmetric.
    Let a\sim b \ \mbox{and} \ b\sim a. By transitivity, a\sim a. However, R is irreflexive. Therefore, we have reached a contradiction and R is asymmetric.

    Are these all logically correct?
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    779
    Quote Originally Posted by dwsmith View Post
    Def:
    R is irreflexive iff. a\nsim a \ \forall a\in A
    Not irreflexive iff. \exist a\in A \ni a\sim a
    R is asymmetric iff. if a\sim b, then  b\nsim a
    Not asymmetric iff. \exist a\sim b and b\sim a
    R is anti-symmetric iff. if a\sim b \ \mbox{and} b\sim a, then a=b.
    Not anti-symmetric iff. \exist a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b
    \bigtriangleup ={(a,a)|a\in A}
    This is how it should be.

    Suppose ~ is a relation on a set A. Consider the following definitions.

    \sim is irreflexive iff \forall a\in A,\;a\nsim a.

    \sim is asymmetric iff \forall a, b\in A, if a\sim b, then  b\nsim a.

    \sim is antisymmetric iff \forall a, b\in A, if a\sim b \ \mbox{and } b\sim a, then a=b.

    \bigtriangleup =\{(a,a)\mid a\in A\}

    Therefore:

    \sim is not irreflexive iff \exists a\in A,\;a\sim a.

    \sim is not asymmetric iff \exists a,b\in A,\;a\sim b\mbox{ and }b\sim a.

    \sim is not antisymmetric iff \exists a,b\in A,\;a\sim b \ \mbox{and} \ b\sim a \ \mbox{and} \ a\neq b.

    (After looking at the source of your post, I see that existential quantifiers were not shown because they were misspelled as \exist instead of \exists.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    779
    Quote Originally Posted by tonio
    Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.

    If this one was true then there wouldn't be equivalence relations...
    The claim is that the relation is not irreflexive. One does not claim it is not reflexive.

    Quote Originally Posted by dwsmith View Post
    Proofs:
    Let R be a nonempty relation on A. If R is symmetric and transitive, then R is not irreflexive.

    Since R is symmetric, assume  a\sim b \ \mbox{and} \ b\sim a. Then, since R is transitive, a\sim a. Therefore, R is not symmetric.
    Q.E.D.
    Should be:

    Proposition 1. Let ~ be a nonempty relation on A. If ~ is symmetric and transitive, then R is not irreflexive.

    Proof.
    ...
    Therefore, ~ is not irreflexive.
    Q.E.D.

    Now, concerning the proof. You should stress where you use the fact that the relation is nonempty: assume that a ~ b. I would also say, "since ~ is symmetric, we have b ~ a" instead of assuming that b ~ a.

    If R\cap R^{-1}=\bigtriangleup, then R is anti-symmetric.

    (1) R\cap R^{-1}\subseteq\bigtriangleup
    Let (a,b)\in R\cap R^{-1}. Therefore, (a,b)\in R \ \mbox{and} \ (a,b)\in R^{-1}\leftrightarrow (b,a)\in R. By the anti-symmetric hypothesis, if a\sim b \ \mbox{and} \ b\sim a, then a=b.

    (2) \bigtriangleup\subseteq R\cap R^{-1}
    (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b\rightarrow a\sim b \ \mbox{and} \ b\sim a \rightarrow (a,b)\in R^{-1} Thus, (a,b)\in R\cap R^{-1}
    You are proving the converse of what is claimed. Besides, in (2), (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b does not make sense. One does not need to know that (a,a)\in\bigtriangleup to conclude a = a, which is always true. Also, it is not clear what b is and so no reason to conclude that a = b.

    If R is transitive and irreflexive, then R is asymmetric.

    By contradiction: If R is transitive and irreflexive, then R is not asymmetric.
    Is this what you are going to show? If you want to prove the original claim by contradiction, then you need to show (1) that R being transitive, irreflexive and asymmetric is impossible or (2) that if R is not asymmetric, then R cannot be transitive and irreflexive. Proving (1) is more natural.

    Let a\sim b \ \mbox{and} \ b\sim a.
    What if the relation is empty and you cannot find such a and b?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    How is \displaystyle \bigtriangleup\subseteq R\cap R^{-1} direction proved?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by emakarov View Post
    The claim is that the relation is not irreflexive. One does not claim it is not reflexive.


    Well, it is what was claimed first time I read the message. Then somebody fixed that.

    A very annoying thing to do, by the way.

    Tonio



    Should be:

    Proposition 1. Let ~ be a nonempty relation on A. If ~ is symmetric and transitive, then R is not irreflexive.

    Proof.
    ...
    Therefore, ~ is not irreflexive.
    Q.E.D.

    Now, concerning the proof. You should stress where you use the fact that the relation is nonempty: assume that a ~ b. I would also say, "since ~ is symmetric, we have b ~ a" instead of assuming that b ~ a.

    You are proving the converse of what is claimed. Besides, in (2), (a,a)\in\bigtriangleup\rightarrow a=a\rightarrow a=b does not make sense. One does not need to know that (a,a)\in\bigtriangleup to conclude a = a, which is always true. Also, it is not clear what b is and so no reason to conclude that a = b.

    Is this what you are going to show? If you want to prove the original claim by contradiction, then you need to show (1) that R being transitive, irreflexive and asymmetric is impossible or (2) that if R is not asymmetric, then R cannot be transitive and irreflexive. Proving (1) is more natural.

    What if the relation is empty and you cannot find such a and b?
    .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    What?

    I didn't make an changes until today 3:52 today, and what I changed was the line at the end stating: Therefore, R is not irreflexive (I had symmetric in this line by accident first).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by dwsmith View Post
    How is \displaystyle \bigtriangleup\subseteq R\cap R^{-1} direction proved?
    Why do you want to prove something you are given?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    I am not given that it is a subset. It says they are equal, but to prove the are equal I must prove they are both subsets of each other, correct?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    779
    Of the three problems in the OP, only the second one mentions \Delta: "If R\cap R^{-1}=\bigtriangleup, then R is anti-symmetric." In this problem R\cap R^{-1}=\bigtriangleup is an assumption, not something to prove.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,680
    Thanks
    1618
    Awards
    1
    This is what you are to prove.
    Given that R\cap R^{-1}=\Delta prove that R is anti-symmetric.
    Proof:
    If (a,b)\in R~\&~(b,a)\in R then it follows that (b,a)\in R^{-1}~\&~(a,b)\in R^{-1} by definition.
    That implies that (a,b)\in(R\cap R^{-1}).
    BUT R\cap R^{-1}=\Delta so (a,b)\in \Delta so a=b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. [SOLVED] More Relations on A
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 20th 2010, 04:43 AM
  4. help with relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 6th 2008, 03:56 PM
  5. Can someone please help me with relations?
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: March 21st 2008, 07:28 PM

/mathhelpforum @mathhelpforum