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.