1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Somewhat difficult proof of a transitive relation

  1. Aug 10, 2011 #1
    1. The problem statement, all variables and given/known data

    Suppose A is a set and F ⊆ P(A). Let R = {(a,b) ∈ A x A | for every X ⊆ A\{a,b}, if X∪{a} ∈ F, then X∪{b} ∈ F}. Show that R is transitive.

    * P(A) is the powerset of A.

    2. Relevant equations

    I am looking for an informal, "naive" proof- the text this exercise comes from is not axiomatic one.

    3. The attempt at a solution

    So far I have come up with:

    Let a,b,c ∈ A and suppose (a,b) ∈ R and (b,c) ∈ R. Let X ⊆ A\{a,c} and also assume X∪{a} ∈ F. But then X∪{a} ∈ P(A), which in turn means X∪{a} ⊆ A.

    *I am struggling with a way to show X∪{c} ∈ F, which is (at least what seems to me to be) what is required to prove (a,c) ∈ R.
    Last edited: Aug 10, 2011
  2. jcsd
  3. Aug 10, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Suppose [itex](a,b)\in R[/itex] and [itex](b,c) \in R[/itex]. You want to show that [itex](a,c) \in R[/itex].

    Choose any [itex]X \subseteq A \setminus \{a,c\}[/itex]. Then neither [itex]a[/itex] nor [itex]c[/itex] is in [itex]X[/itex].

    It may or may not be true that [itex]b \in X[/itex].

    If [itex]b \not\in X[/itex], then [itex]X \subseteq A \setminus \{a,b\}[/itex] and [itex]X \subseteq A \setminus \{b,c\}[/itex] and the rest is straightforward.

    What happens if [itex]b \in X[/itex]?
  4. Aug 10, 2011 #3
    The reasoning for the case (presented above) in which b is not an element of X seems to use the vacuous truth which results by writing out the meaning of subset and applying the fact that b is not an element of X to the statements implied by (a,b) ∈ R and (b,c) ∈ R.

    If b ∈ X, then b ∈ A and not b ∈ {a,c}....Perhaps I have been looking at this problem for too long, but i cannot seem to apply this anywhere.
  5. Aug 10, 2011 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm not sure what you mean by vacuous truth.

    Let [itex]X[/itex] be as I indicated above, and suppose that [itex](a,b) \in R[/itex] and [itex](b,c) \in R[/itex]. We want to prove that [itex](a,c) \in R[/itex].

    If [itex]b \not\in X[/itex], then [itex]X \subseteq A \setminus\{a,b\}[/itex] and [itex]X \subseteq A \setminus\{b,c\}[/itex].

    Now suppose that [itex]X \cup\{a\} \in F[/itex].

    Since [itex](a,b) \in R[/itex], it follows that [itex]X \cup\{b\} \in F[/itex]. Then, since [itex](b,c) \in R[/itex], it follows that [itex]X \cup\{c\} \in F[/itex].

    What can you conclude from this?

    The reason why [itex]b \not\in X[/itex] is important is because this means that [itex]X[/itex] is a valid "test set" in the definition of [itex]R[/itex] for both [itex](a,b)[/itex] and [itex](b,c)[/itex].

    So now you need to come up with an argument that works if [itex]b \in X[/itex].
    Last edited: Aug 10, 2011
  6. Aug 10, 2011 #5
    What i was referring to was this:

    We assumed b ∉ X. We also assumed (a,b),(b,c) ∈ R. The logical definition of this, in particular for (a,b) ∈ R, is (∀X ⊆ A\{a,b})(X∪{a} ∈ F → X∪{b} ∈ F). It is analogous for (b,c) ∈ R. The definition of subset is (∀k)(k ∈ X → k ∈ A\{a,b}). Lastly, we have assumed X ⊆ A\{a,c}. By vacuous truth I am referring to the justification that X ⊆ A\{a,b}, which allows us to use (a,b) ∈ R given these premises- unless I am still making an error or regarding the proof in an unneccesary manner?
  7. Aug 10, 2011 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    All the statements you made are correct. I guess I was confused by your use of the word "vacuous."

    The assumption that [itex]b \not\in X[/itex] means that the rest of the argument is valid, in particular, [itex]X[/itex] meets the criteria needed to draw a useful conclusion from the facts that [itex](a,b) \in R[/itex] and [itex](b,c) \in R[/itex].

    I think you can make a similar argument if [itex]b \in X[/itex], but in that case you can't use [itex]X[/itex] itself to draw the conclusions.
  8. Aug 10, 2011 #7
    This is a bit sidetracked, but I'd just like to ascertain that I'm using the term "vacuous" correctly... since the antecedent in the definition of subset above isn't satisfied (since we have b ∉ X for arbitrary b and that definition has k ∈ X for arbitrary k), doesn't that make X ⊆ A\{a,b} vacuously true? Or was it simply the phrasing which was confusing in my previous post?

    Also, thank you for your help jbunniii. I'll post a full copy of my proof once I have it done on paper.
  9. Aug 10, 2011 #8


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    But [itex]b[/itex] isn't arbitrary. It's a specific element, which along with two other specific elements [itex]a[/itex] and [itex]c[/itex], are assumed to satisfy [itex](a,b) \in R[/itex] and [itex](b,c) \in R[/itex].

    The two cases I am then considering are whether or not that specific [itex]b[/itex] is in the candidate set [itex]X[/itex] that I defined above. Depending on how I choose [itex]X[/itex], this may or may not be true. There are valid choices of [itex]X[/itex] with [itex]b \in X[/itex], and other valid choices of [itex]X[/itex] with [itex]b \not\in X[/itex]. I must show that the desired result is true for all valid choices.

    I consider the two possibilities separately. If [itex]b \not \in X[/itex], then that implies that [itex]X \subseteq A \setminus \{a,b\}[/itex]. It's not vacuously true. It's true precisely because [itex]b \in X[/itex].

    When I consider the other possibility, [itex]b \in X[/itex], then [itex]X \not \subseteq A \setminus \{a,b\}[/itex] and this introduces a complication that needs to be overcome.

    Sorry in advance if I'm not addressing your question correctly. It might just be a question of language. To me, "vacuously true" would be a statement like "if pigs can fly, then all cats are blue." Whereas the example above is more like "if 3 is in the set X, then X cannot consist only of even numbers." Hope that makes sense.

    In any case, I look forward to seeing your proof, especially the [itex]b \in X[/itex] case, which I haven't worked out myself yet.
  10. Aug 10, 2011 #9
    hmmmmm. There's a hint which suggests working with the sets (XU{a})\{b} and (XU{c})\{b} for this case. Trying to work off that here. Also the fact that F is a subset of P(A) must play in somewhere.
  11. Aug 10, 2011 #10
    How about this?

    Let a,b,c ∈ A and suppose (a,b),(b,c) ∈ R. Also, let X ⊆ A\{a,c} and assume X∪{a} ∈ F. The proof is now broken into two exhaustive cases:

    Case 1) Suppose b ∉ X. In order for X ⊆ A\{a,b} to be satisfied, it must be true that (∀k)(k ∈ X → k ∈ A\{a,b}). Now, applying the element b introduced above to this statement we have: b ∈ X → b ∈ A\{a,b}, which is logically equivalent to b ∉ X ∨ b ∈ A\{a,b}. This disjunction is clearly true since, by hypothesis, b ∉ X. As a result, we may assume X ⊆ A\{a,b}. Analogous reasoning also provides us with X ⊆ A\{b,c}. Using these conclusions, along with X∪{a} ∈ F above, we may deduce X∪{b} ∈ F (from (a,b) ∈ R) and ultimately X∪{c} ∈ F (from (b,c) ∈ R). Thus, R is transitive.

    Case 2) Suppose b ∈ X. In addition, assume a ∈ X. But this would imply a ∈ A and a ∉ {a,c} (since X ⊆ A\{a,c}) which is a contradiction since, obviously, a ∈ {a,c}. Thus a ∉ X. Now recall that in order for X ⊆ A\{a,b} to be satisfied, it must be true that (∀k)(k ∈ X → k ∈ A\{a,b}). Since any implication is logically equivalent to its contrapositive, we have (∀k)(k ∉ A\{a,b} → k∉ X). Analyzing the logical definition of this statement even more yields: (∀k)((k ∉ A ∨ k ∈ {a,b}) → k∉ X). Further, this implication is equivalent to the following disjunction: (∀k)((k ∈ A ∧ k ∉ {a,b}) ∨ k∉ X). Applying a to this statement, it immediately becomes obvious that it is true because, as demonstrated above, a ∉ X. This shows that X ⊆ A\{a,b}. An analogous argument shows that X ⊆ A\{b,c} is valid. Afterwards, following the reasoning in case 1, it can be seen that R is transitive.

    Last edited: Aug 10, 2011
  12. Aug 10, 2011 #11


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, this can't be right. Right at the start, you said that [itex]b \in X[/itex]. But the last sentence (in bold) cannot be true in that case. [itex]b[/itex] is obviously not in [itex]A\setminus \{a,b\}[/itex], so [itex]X[/itex] cannot be a subset of [itex]A\setminus \{a,b\}[/itex].
  13. Aug 10, 2011 #12


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This case is correct, but I think you are making it too hard. Why not just say this instead of the bolded text:

    Suppose [itex]b \not \in X[/itex]. Since [itex]X \subseteq A \setminus\{a, c\}[/itex], we also see that [itex]a \not \in X[/itex]. Therefore [itex]X[/itex] is a subset of [itex]A[/itex] which contains neither [itex]a[/itex] nor [itex]b[/itex], and therefore [itex]X \subseteq A \setminus \{a,b\}[/itex].
  14. Aug 11, 2011 #13
    Anyone else have any suggestions?
  15. Aug 11, 2011 #14
    Yes, this will lead to the solution. When you assume X contained in S \ {a,c} satisfies X u { a }, assuming that b is also in X ( the second case, after assuming b is not in X ), gives rise to X u { a } \ { b } being contained in S \ { b , c }.
  16. Aug 11, 2011 #15
    What exactly do you mean by this? X u { a } ∈ F is a premise, so it is assumed to be satisfied/true.
  17. Aug 11, 2011 #16
    When you assume b ∈ X... there is no way to deduce X is contained in A/{a,b}. Clearly, the same holds for A/{b,c}. This leads me to believe XU{c} ∈ F must be shown directly (ie. not using Modus Ponens with the givens).

    So far I have, since b ∈ XU{a} and XU{a} ∈ F, b ∈ UF... trying to get through like this
    Last edited: Aug 11, 2011
  18. Aug 11, 2011 #17
    Still looking for help.
  19. Aug 11, 2011 #18
    yes, that is what I mean. I suggest you read more into that hint you were given, the one I followed up on. It is almost a give-away ( as long as you pay attention to all the notation )
  20. Aug 11, 2011 #19
    Maybe you can do more than indicate how "obvious" it is?
    Last edited: Aug 11, 2011
  21. Aug 11, 2011 #20
    Suppose [itex] X \subseteq A - \left\{a,c\right\}[/itex] and [itex] X \cup \left\{a\right\} \in F[/itex].

    Assume [itex] b \in X[/itex]. Then [itex] ( X \cup \left\{a\right\}) - \left\{b\right\} \subseteq A - \left\{b,c\right\}[/itex]. Also, [itex] ( X \cup \left\{a\right\}) - \left\{b\right\} \cup \left\{ b\right\} = X \cup \left\{a\right\} \in F[/itex].

    Therefore, since [itex](b,c) \in R[/itex], we know that [itex] (X\cup \left\{a\right\}) - \left\{b\right\} \cup \left\{c\right\} \in F[/itex]. Remember this inclusion.

    Then, take a look at the set [itex] ( X \cup \left\{c\right\}) - \left\{b\right\}[/itex] remembering that [itex] (a,b)\in R[/itex].
  22. Aug 11, 2011 #21
    Holy mackerel! I Finally got it. This proof is unlike others I have experienced thus far. It has more to do with "constructing" sets using their element representations. Also, working with arbitrary subsets was previously unfamiliar to me.

    Here is case 2:

    Suppose b ∈ X. Then [(X U {a})\{b}] ⊆ A\{b,c}. Note that ([(X U {a})\{b}] U {b}) ∈ F since ([(X U {a})\{b}] U {b}) = (X U {a}), and from above (X U {a}) ∈ F. Because (b,c) ∈ R, we may conclude that ([(X U {a})\{b}] U {c}) ∈ F. Now consider [(X U {c})\{b}] and notice that [(X U {c})\{b}] ⊆ A\{a,b}. Also, [(X U {c})\{b}] U {a} ∈ F since [(X U {c})\{b}] U {a} = ([(X U {a})\{b}] U {c}) ∈ F (shown just prior). This time, using the premise (a,b) ∈ R, we may deduce ([(X U {c})\{b}] U {b}) ∈ F. But this is the same as saying (X U {c}) ∈ F since ([(X U {c})\{b}] U {b}) = (X U {c}) ∈ F. This is exactly what is required to show (a,c) ∈ R and thus prove that R is transitive.
  23. Aug 11, 2011 #22
    looks good, good job ; as you can see, the given hint I think was enough to work with .. too much more information might've given it away (you just had to keep track of all the notation ).
  24. Aug 11, 2011 #23
    Thank you =).

    I'm trying to sketch out the formal PC (pred. calc.) proof for this one and it seems very lengthy and convoluted.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook