Theorem

Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Let T be an object such that T is a binary relation on A. Then we have R∪S o^AT=(R o^AT)∪(S o^AT).

Background

The following background is necessary to understand this theorem.

(.) Let x and y be objects. Then x=y is a proposition.

(.) Let A and B be objects. Then "A∪B" is an object.

(.) Let A and R be objects. Then "R is a binary relation on A" is a proposition.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Then "R o^AS" is an object.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Then we know R∪S is a binary relation on A.

Background for Proof

The following background is necessary for the proof.

(.) Let A and x be objects. Then x∈A is a proposition.

(.) Let φ and ψ be propositions. Then φ∧ψ is a proposition.

(.) Let φ and ψ be propositions. Then φ∨ψ is a proposition.

(.) Let A be an object. Let φ(a) be a proposition depending on a member a of A. Then "∃a∈A⋅φ(a)" is a proposition.

(.) Let φ and ψ be propositions. Assume φ∧ψ. Then we know φ.

(.) Let φ and ψ be propositions. Assume φ∧ψ. Then we know ψ.

(.) Let φ and ψ be propositions. Assume φ∨ψ. Let θ be a proposition. Assume φ implies θ and ψ implies θ. Then we know θ.

(.) Let A be an object. Let φ(a) be a proposition depending on a member a of A. Assume ∃a∈A⋅φ(a). Let ψ be a proposition. Assume for all a ∈ A φ(a) implies ψ. Then we know ψ.

(.) Let A and B be objects. Then "A⊆B" is a proposition.

(.) Let A and B be objects. Assume A⊆B and B⊆A. Then we know A=B.

(.) Let x and y be objects. Then "⟨x,y⟩" is an object.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Assume for all a ∈ A for all b ∈ A ⟨a,b⟩∈R implies ⟨a,b⟩∈S. Then we know R⊆S.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Then we know R o^AS is a binary relation on A.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Let a, b and c be members of A. Assume ⟨a,c⟩∈R and ⟨c,b⟩∈S. Then we know ⟨a,b⟩∈R o^AS.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Let a and b be members of A. Assume ⟨a,b⟩∈R o^AS. Then we know ∃c∈A⋅(⟨a,c⟩∈R∧⟨c,b⟩∈S).

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Let a and b be members of A. Assume ⟨a,b⟩∈R. Then we know ⟨a,b⟩∈R∪S.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Let a and b be members of A. Assume ⟨a,b⟩∈S. Then we know ⟨a,b⟩∈R∪S.

(.) Let A be an object. Let R be an object such that R is a binary relation on A. Let S be an object such that S is a binary relation on A. Let a and b be members of A. Assume ⟨a,b⟩∈R∪S. Then we know ⟨a,b⟩∈R∨⟨a,b⟩∈S.

Proof

Claim: R∪S o^AT⊆(R o^AT)∪(S o^AT).

Proof of Claim: We will show for all a ∈ A for all b ∈ A ⟨a,b⟩∈R∪S o^AT implies ⟨a,b⟩∈(R o^AT)∪(S o^AT). Let a be a member of A. Let b be a member of A. Assume ⟨a,b⟩∈R∪S o^AT. Let c be a member of A such that ⟨a,c⟩∈R∪S∧⟨c,b⟩∈T.

Claim: ⟨a,c⟩∈R∨⟨a,c⟩∈S.

Proof of Claim: Since ⟨a,c⟩∈R∪S∧⟨c,b⟩∈T, we have ⟨a,c⟩∈R∪S. Using this, we are done. This completes the proof of the claim.

Consider the case in which ⟨a,c⟩∈R. It is enough to show ⟨a,b⟩∈R o^AT. Since ⟨a,c⟩∈R∪S∧⟨c,b⟩∈T, we know ⟨c,b⟩∈T. Using this and ⟨a,c⟩∈R, we are done.

Consider the case in which ⟨a,c⟩∈S. We will show ⟨a,b⟩∈S o^AT. Since ⟨a,c⟩∈R∪S∧⟨c,b⟩∈T, we have ⟨c,b⟩∈T. Using this and ⟨a,c⟩∈S, we are done.

Consider the case in which ⟨a,b⟩∈R o^AT. Let c be a member of A such that ⟨a,c⟩∈R∧⟨c,b⟩∈T.

Claim: ⟨a,c⟩∈R∪S.

Proof of Claim: Since ⟨a,c⟩∈R∧⟨c,b⟩∈T, we know ⟨a,c⟩∈R. Using this, we are done. This completes the proof of the claim.

Consider the case in which ⟨a,b⟩∈S o^AT. Let c be a member of A such that ⟨a,c⟩∈S∧⟨c,b⟩∈T.

Claim: ⟨a,c⟩∈R∪S.

Proof of Claim: Since ⟨a,c⟩∈S∧⟨c,b⟩∈T, we know ⟨a,c⟩∈S. Using this, we are done. This completes the proof of the claim.

Click here to modify variable names (JavaScript Must Be Enabled).

Hide Background.

Test yourself on this item.