Results 1 to 15 of 15
Like Tree3Thanks
  • 1 Post By Deveno
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - Reflexive, Symmetric, Transitive Relation Proof

  1. #1
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Reflexive, Symmetric, Transitive Relation Proof

    Let X be a set and let R be the relation "" defined on subsets of X.

    Prove whether reflexive, symmetric, transitive.

    Is this the right approach?
    Proof: (Reflexive)
    Suppose S is a subset of X. Suppose y is in S.

    (Now I need to show that (y, y) is in R. Can I say that y y, so (y, y) is in R?
    I don't understand how to show that elements are in this relation since the relation is in terms of subsets.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    700

    Re: Reflexive, Symmetric, Transitive Relation Proof

    You don't need to show that $(y,y) \in R$, you need to show that for every $S \subseteq X$, that $(S,S) \in R$.

    What this amounts to, is showing that for every subset $S$ of $X$, that $S \subseteq S$.

    Now to show THIS, we can take any element $y \in S$, and we must show that this implies $y \in S$. Since this is (OBVIOUSLY!) always true, $S \subseteq S$, that is $(S,S) \in R$, so $R$ is reflexive.
    Thanks from Convrgx
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    MORE QUESTIONS:

    Let R be a relation on a set A. Then, R is reflexive iff for all y in A, (y, y) is in R.

    In this case, R is still a relation on a set. This set is some set, S, which is a subset of X.
    So, wouldn't the proof still have to satisfy the definition of reflexive as defined above.
    Something like:

    Proof (Reflexive)
    Suppose S is a subset of X. Suppose y is in S. Then clearly y is in S, and S ⊆ S. So, R = S X S.
    Thus, (y, y) is in R and R is reflexive.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Also, is it important that the problem states "...R be the relation "⊆" defined ON subsets of X?"
    As apposed to, "...R be the relation "⊆" defined BETWEEN subsets of X."
    If the problem stated BETWEEN, then that would change things right?
    In this case, we could have two subsets of X that were disjoint, which would prevent R from being reflexive, right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    700

    Re: Reflexive, Symmetric, Transitive Relation Proof

    I think you are misunderstanding which set $R$ is a relation ON. It is NOT a relation on $X$, but on the set $\mathcal{P}(X)$, the POWER SET of $X$ (also written as $2^{X}$).

    If two subsets of $X$, say $A,B$ are disjoint, then sure, $(A,B) \not\in R$, but that says nothing about $(A,A)$ or $(B,B)$.

    It is a curious fact about sets: elements of one set (for example, a power set, or "set of subsets" like we have here) can be sets themselves. There is no "inherent" type distinction between sets and elements in set theory, although there IS a distinction between $x$ (whatever object $x$ might be) and $\{x\}$, the set whose only element is $x$, for example, $x \in \{x\}$ but $x \not\in x$.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    So, is the way that I suggested proving the reflexive property incorrect? (on post #3)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Never mind. I get it now. It would have been better if the book said:
    Let R be the relation "⊆" defined on THE SET OF ALL SUBSETS OF X.
    Then I would have better understood that each element in this set is a set.
    Which makes sense given the "⊆" property of the relation.
    So, R is a set of ordered pairs of sets. Thus, it makes sense to prove the reflexive property as:

    Proof:
    Suppose S is a subset of X. Suppose y is in S. Then clearly y is in S, and S ⊆ S.
    Thus, (S, S) is in R and R is reflexive.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    700

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Well it has some parts that are correct, but it is NOT true that $R = S \times S$.

    Let me give you a slightly more "targeted example", by actually specifying the set $X$.

    So suppose $X = \{a,b\}$ ($X$ has two elements, $a$ and $b$).

    The set of all subsets of $X$, is THIS one :$\mathcal{P}(X) = \{\emptyset,\{a\},\{b\},\{a,b\}\}$. We want to show for all sets $S \in \mathcal{P}$ that $S \sim_R S$, that is: $S \subseteq S$.

    Fortunately, in this example, $\mathcal{P}(X)$ is pretty small, it only has 4 elements. Let's rename them like so:

    $N = \emptyset$
    $A = \{a\}$
    $B = \{b\}$
    $X = \{a,b\}$

    To show $R$ is reflexive, we need to show that $(N,N),(A,A),(B,B)$ and $(X,X)$ are all in $R$. The set that $R$ is a relation on is $\mathcal{P}(X)$, NOT $X$.

    So let's start with $N$. Since $N$ HAS no elements (it is empty), any element of $N$ (that is to say, none) are automatically in ANY set, including $N$ itself. Hence $N \subseteq N$.

    Well, that wasn't very exciting. Let's look at $A$. Now $A$ has only one element, $a$, and (what a coincidence!), $a$ just happens to be in $A$ as well, so $A \subseteq A$.

    The proof that $B \subseteq B$ is exactly the same.

    $X$ is a little bit more interesting: we have our choice of two elements in $X,\ a$ or $b$. Either way, we can conclude that $a \in \{a,b\}$, and similarly, $b \in \{a,b\}$, so every element of $X$ is also in $X$, and thus $X \subseteq X$.

    So in all four cases, we see that $(S,S)$ is in $R$, whether $S = N,A,B$ or $X$.

    A different way to say a relation $R$ on a set $S$ is reflexive is to say: $\Delta(S) \subset R$, where $\Delta(S)$ is the DIAGONAL of $S \times S$, consisting of all pairs $(s,s)$ for any element $s$ of $S$. The containment of sets in this case ($R$ is reflexive) goes like this:

    $\Delta(S) \subseteq R \subseteq S \times S$.

    If a relation $R$ on a set $S$ is actually $S\times S$, that means ANY two elements are related, which isn't a very interesting relation at all.

    The relation in this question is not on some subset $S$ of $X$, it is on the set of ALL subsets of $X$ which is "bigger" than just one subset.
    Thanks from Convrgx
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Yes, that spells it out quite nicely, thank you.
    The big problem I had was in interpreting "on subsets of X" to mean "on the set of all subsets of X."
    I am now working through the symmetric and transitive proofs...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Proof (Symmetric)
    Counterexample: Suppose X = {a, b}. [Then the set of all subsets is P(X)={∅,{a},{b},{a,b}}.]
    Let A = {a} and B = {a, b}. Then A and B are subsets of X. If x is in A, then x = a.
    Since a is in B, A ⊆ B. However, b is in B but b is not in A. So, B is not a subset of A.
    Thus, R is not symmetric.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Proof (Transitive)
    Suppose A, B, and C are all subsets of X and ARB and BRC.
    Suppose y is in A. Since ARB, y is in B. Since BRC, y is in C.
    Thus, ARC and R is transitive.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Are the two proofs above correct?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    700

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Yes, in fact this type of relation is typical of what is called a "partial ordering", which is:

    1. reflexive
    2. transitive
    3. anti-symmetric: by this, we mean that if aRb and bRa, then we have a = b.

    Other examples of partial orderings:

    "less than or equal to" on the set of real numbers,
    "divides" on the set of positive integers,

    partial orderings are very important things in the world of mathematics.
    Thanks from Convrgx
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Jan 2014
    From
    Arizona
    Posts
    60
    Thanks
    3

    Re: Reflexive, Symmetric, Transitive Relation Proof

    I am not familiar with partial ordering, but I will take note of that.
    The examples that you gave are helpful in understanding the concept.
    This is my first "proof/analysis" type course so this is all new to me.
    I heard these concepts are really important in abstract algebra but I'm not sure where else they're used.
    Although, I imagine they are found in a variety of contexts.
    I'm so used to numerical/graphical expressions that it's taking some time to think more in terms of these principals/concepts.
    Fortunately, these are pretty simple. I am taking real analysis next semester, so I need to make sure really understand this stuff.
    Well, thanks again, I'm sure I'll have plenty more post floating around soon...
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    700

    Re: Reflexive, Symmetric, Transitive Relation Proof

    Well sets, and "sets of sets" are very important.

    In calculus, one often deals with the real numbers. But what turns out to be important is certain kinds of subsets of real numbers: namely, open intervals. We can use an open interval (a,b) that contains a point x as a way of saying we're "somewhere around x", and this idea of proximity, becomes the basis for ideas like limits and continuity. It turns out that we can order open intervals by inclusion, which captures the notion of "zeroing in on x".

    Another way in which relations, especially relations that are reflexive, symmetric and transitive (equivalence relations), are important, is that conceptually, they provide a looser notion of "the same" than "exactly equal". Often, especially when dealing with infinite things, there's just too many to get a good grip on how they behave by looking at every single one. But if we can lump them together into "equivalence classes", we might wind up with few enough "things" to analyze thoroughly.

    Here is an equivalence relation you probably have encountered before, even if you didn't realize it. Suppose $f,g$ are two differentiable functions. Define $f \sim g$ if $f' = g'$. In this case, it should be clear that if $f \sim g$, then $f - g$ is a constant function. You implicitly appeal to this equivalence every time you integrate a continuous function, it's what the "+ C" at the end of an indefinite integral equation means.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Friendship as Reflexive, Symmetric, and transitive.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 14th 2013, 07:11 PM
  2. Transitive, Symmetric, Non-Reflexive Relation
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 24th 2010, 07:12 AM
  3. Symmetric, transitive, not reflexive?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 2nd 2010, 12:32 AM
  4. Reflexive, symmetric, and transitive
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2009, 11:08 AM
  5. Reflexive, Transitive, Symmetric
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 20th 2009, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum