Somewhat difficult proof of a transitive relation

[Syrus]

Homework Statement

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.

Homework Equations

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

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.

 

[jbunniii]

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

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

It may or may not be true that b \in X.

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

What happens if b \in X?

 

[Syrus]

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.

 

[jbunniii]

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

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

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

Now suppose that X \cup\{a\} \in F.

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

What can you conclude from this?

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

So now you need to come up with an argument that works if b \in X.

 

[Syrus]

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?

 

[jbunniii]

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?

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

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

I think you can make a similar argument if b \in X, but in that case you can't use X itself to draw the conclusions.

 

[Syrus]

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.

 

[jbunniii]

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

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

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

When I consider the other possibility, b \in X, then X \not \subseteq A \setminus \{a,b\} 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 b \in X case, which I haven't worked out myself yet.

 

[Syrus]

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.

 

[Syrus]

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.



Q.E.D.

 

[jbunniii]

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}.

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

 

[jbunniii]

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.

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

Suppose b \not \in X. Since X \subseteq A \setminus\{a, c\}, we also see that a \not \in X. Therefore X is a subset of A which contains neither a nor b, and therefore X \subseteq A \setminus \{a,b\}.

 

[Syrus]

Anyone else have any suggestions?

 

[wisvuze]

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.

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 }.

 

[Syrus]

When you assume X contained in S \ {a,c} satisfies X u { a }

What exactly do you mean by this? X u { a } ∈ F is a premise, so it is assumed to be satisfied/true.

 

[Syrus]

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

 

[Syrus]

Still looking for help.

 

[wisvuze]

What exactly do you mean by this? X u { a } ∈ F is a premise, so it is assumed to be satisfied/true.

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 )

 

[Syrus]

Maybe you can do more than indicate how "obvious" it is?

 

[stringy]

Suppose X \subseteq A - \left\{a,c\right\} and X \cup \left\{a\right\} \in F.

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

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

Then, take a look at the set ( X \cup \left\{c\right\}) - \left\{b\right\} remembering that (a,b)\in R.

 

[Syrus]

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.

 

[wisvuze]

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 ).

 

[Syrus]

Thank you =).

I'm trying to sketch out the formal PC (pred. calc.) proof for this one and it seems very lengthy and convoluted.