§ 2.1 Mathematical Systems, Direct Proofs and Counterexamples

Types of Mathematical Statements

1 Axiom - statement that is accepted to be true without proof

>Types of Mathematical Statements 1 Axiom - statement that is accepted to be true without proof Example: Euclid’s axioms, the first of which is “A straight line segment can be drawn joining any two points.” 2 Theorem - a mathematical statement whose truth can be verified, although mathematician usually reserve this term for important or interesting. 3 Corollary - a mathematical statement that is a consequence of a theorem or an axiom. 4 Lemma - a mathematical result that is useful in verifying the truth in another result.

Types of Mathematical Statements

1 Axiom - statement that is accepted to be true without proof Example: Euclid’s axioms, the first of which is “A straight line segment can be drawn joining any two points.”

>Types of Mathematical Statements 1 Axiom - statement that is accepted to be true without proof Example: Euclid’s axioms, the first of which is “A straight line segment can be drawn joining any two points.” 2 Theorem - a mathematical statement whose truth can be verified, although mathematician usually reserve this term for important or interesting. 3 Corollary - a mathematical statement that is a consequence of a theorem or an axiom. 4 Lemma - a mathematical result that is useful in verifying the truth in another result.

Types of Mathematical Statements

1 Axiom - statement that is accepted to be true without proof Example: Euclid’s axioms, the first of which is “A straight line segment can be drawn joining any two points.”

2 Theorem - a mathematical statement whose truth can be verified, although mathematician usually reserve this term for important or interesting.

>Types of Mathematical Statements 1 Axiom - statement that is accepted to be true without proof Example: Euclid’s axioms, the first of which is “A straight line segment can be drawn joining any two points.” 2 Theorem - a mathematical statement whose truth can be verified, although mathematician usually reserve this term for important or interesting. 3 Corollary - a mathematical statement that is a consequence of a theorem or an axiom. 4 Lemma - a mathematical result that is useful in verifying the truth in another result.

Types of Mathematical Statements

1 Axiom - statement that is accepted to be true without proof Example: Euclid’s axioms, the first of which is “A straight line segment can be drawn joining any two points.”

2 Theorem - a mathematical statement whose truth can be verified, although mathematician usually reserve this term for important or interesting.

3 Corollary - a mathematical statement that is a consequence of a theorem or an axiom.

Types of Mathematical Statements

2 Theorem - a mathematical statement whose truth can be verified, although mathematician usually reserve this term for important or interesting.

3 Corollary - a mathematical statement that is a consequence of a theorem or an axiom.

4 Lemma - a mathematical result that is useful in verifying the truth in another result.

Direct Proofs

Definition

A direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions.

>Direct Proofs Definition A direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions. Definition An indirect proof may begin with certain hypothetical scenarios and then proceed to eliminate the uncertainties in each of these scenarios until an inescapable conclusion is forced.

Direct Proofs

Definition

A direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions.

Definition

An indirect proof may begin with certain hypothetical scenarios and then proceed to eliminate the uncertainties in each of these scenarios until an inescapable conclusion is forced.

How To Write Proofs: The Basics

1 Always state the assumptions that can be made.

>How To Write Proofs: The Basics 1 Always state the assumptions that can be made. 2 Always state what you are trying to prove. 3 Always separate strings of equations - whether a simple statement or a long series of algebraic steps, separation makes it easier for the reader to be able to verify the work. 4 Always state that the proof is complete in some way Use a black box or an open box Write Q.E.D., which is the abbreviation for the Latin phrase ‘quod erat demonstrandum,’, which means ‘which had to be demonstrated’ 5 Never refer to yourself in a proof - if you need to use a pronoun, use ‘we’

How To Write Proofs: The Basics

1 Always state the assumptions that can be made.

2 Always state what you are trying to prove.

>How To Write Proofs: The Basics 1 Always state the assumptions that can be made. 2 Always state what you are trying to prove. 3 Always separate strings of equations - whether a simple statement or a long series of algebraic steps, separation makes it easier for the reader to be able to verify the work. 4 Always state that the proof is complete in some way Use a black box or an open box Write Q.E.D., which is the abbreviation for the Latin phrase ‘quod erat demonstrandum,’, which means ‘which had to be demonstrated’ 5 Never refer to yourself in a proof - if you need to use a pronoun, use ‘we’

How To Write Proofs: The Basics

1 Always state the assumptions that can be made.

2 Always state what you are trying to prove.

3 Always separate strings of equations - whether a simple statement or a long series of algebraic steps, separation makes it easier for the reader to be able to verify the work.

>How To Write Proofs: The Basics 1 Always state the assumptions that can be made. 2 Always state what you are trying to prove. 3 Always separate strings of equations - whether a simple statement or a long series of algebraic steps, separation makes it easier for the reader to be able to verify the work. 4 Always state that the proof is complete in some way Use a black box or an open box Write Q.E.D., which is the abbreviation for the Latin phrase ‘quod erat demonstrandum,’, which means ‘which had to be demonstrated’ 5 Never refer to yourself in a proof - if you need to use a pronoun, use ‘we’

How To Write Proofs: The Basics

1 Always state the assumptions that can be made.

2 Always state what you are trying to prove.

3 Always separate strings of equations - whether a simple statement or a long series of algebraic steps, separation makes it easier for the reader to be able to verify the work.

4 Always state that the proof is complete in some way

Use a black box or an open box

How To Write Proofs: The Basics

1 Always state the assumptions that can be made.

2 Always state what you are trying to prove.

3 Always separate strings of equations - whether a simple statement or a long series of algebraic steps, separation makes it easier for the reader to be able to verify the work.

4 Always state that the proof is complete in some way

Use a black box or an open box

Write Q.E.D., which is the abbreviation for the Latin phrase ‘quod erat demonstrandum,’, which means ‘which had to be demonstrated’

How To Write Proofs: The Basics

1 Always state the assumptions that can be made.

2 Always state what you are trying to prove.

4 Always state that the proof is complete in some way

Use a black box or an open box

Write Q.E.D., which is the abbreviation for the Latin phrase ‘quod erat demonstrandum,’, which means ‘which had to be demonstrated’

5 Never refer to yourself in a proof - if you need to use a pronoun, use ‘we’

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

>A First Proof Example If n is an odd integer then 5n + 3 is an even integer. We need to start with something of the form 2k + 1 and we need to end with something of the form 2k. So we want to use the definitions we established above and keep these in mind. Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer. Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now, 5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4) Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

We need to start with something of the form 2k + 1 and we need to end with something of the form 2k. So we want to use the definitions we established above and keep these in mind.

>A First Proof Example If n is an odd integer then 5n + 3 is an even integer. We need to start with something of the form 2k + 1 and we need to end with something of the form 2k. So we want to use the definitions we established above and keep these in mind. Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer. Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now, 5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4) Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

We need to start with something of the form 2k + 1 and we need to end with something of the form 2k. So we want to use the definitions we established above and keep these in mind.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

>A First Proof Example If n is an odd integer then 5n + 3 is an even integer. We need to start with something of the form 2k + 1 and we need to end with something of the form 2k. So we want to use the definitions we established above and keep these in mind. Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer. Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now, 5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4) Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

We need to start with something of the form 2k + 1 and we need to end with something of the form 2k. So we want to use the definitions we established above and keep these in mind.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1.

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,

5n + 3 =

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,

5n + 3 = 5(2k + 1) + 3 =

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,

5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 =

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,

5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 =

A First Proof

Example

If n is an odd integer then 5n + 3 is an even integer.

Proof: Assume that n is an odd integer. We want to show that 5n + 3 is an even integer.

Since n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Now,

5n + 3 = 5(2k + 1) + 3 = (10k + 5) + 3 = 10k + 8 = 2(5k + 4)

Since 5k + 4 ∈ Z, 5n + 3 is an even integer. Q.E.D.

Another Example

Example

If n is an odd integer then n2 is odd.

>Another Example Example If n is an odd integer then n2 is odd. Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z. Consider n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form necessary for inclusion in the set of odd integers. Therefore, if n is odd then n2 is as well. Q.E.D.

Another Example

Example

If n is an odd integer then n2 is odd.

Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z.

>Another Example Example If n is an odd integer then n2 is odd. Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z. Consider n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form necessary for inclusion in the set of odd integers. Therefore, if n is odd then n2 is as well. Q.E.D.

Another Example

Example

If n is an odd integer then n2 is odd.

Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z. Consider

n2 = (2k + 1)2 =

>Another Example Example If n is an odd integer then n2 is odd. Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z. Consider n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form necessary for inclusion in the set of odd integers. Therefore, if n is odd then n2 is as well. Q.E.D.

Another Example

Example

If n is an odd integer then n2 is odd.

Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z. Consider

n2 = (2k + 1)2 = 4k2 + 4k + 1 =

Another Example

Example

If n is an odd integer then n2 is odd.

Suppose n is an odd integer. Then we can write n in the form n = 2k + 1 where k ∈ Z. Consider

n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1

Since k is an integer, so is 2k2 + 2k and so we can write n2 in the form necessary for inclusion in the set of odd integers. Therefore, if n is odd then n2 is as well. Q.E.D.

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

>Perfect Squares Example Every odd integer is the difference of two perfect squares. Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since k is an integer, k2 and (k + 1)2 are both perfect squares. Consider (k + 1)2 = k2 + 2k + 1 and k2 + 2k + 1 − k2 = 2k + 1 Therefore, if n is odd then we can express n as the difference of perfect squares. Q.E.D.

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

Let n be an odd integer.

>Perfect Squares Example Every odd integer is the difference of two perfect squares. Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since k is an integer, k2 and (k + 1)2 are both perfect squares. Consider (k + 1)2 = k2 + 2k + 1 and k2 + 2k + 1 − k2 = 2k + 1 Therefore, if n is odd then we can express n as the difference of perfect squares. Q.E.D.

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

Let n be an odd integer. We want to show that n is the difference of two perfect squares.

>Perfect Squares Example Every odd integer is the difference of two perfect squares. Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since k is an integer, k2 and (k + 1)2 are both perfect squares. Consider (k + 1)2 = k2 + 2k + 1 and k2 + 2k + 1 − k2 = 2k + 1 Therefore, if n is odd then we can express n as the difference of perfect squares. Q.E.D.

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1.

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since k is an integer, k2 and (k + 1)2 are both perfect squares.

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since k is an integer, k2 and (k + 1)2 are both perfect squares. Consider (k + 1)2 = k2 + 2k + 1

Perfect Squares

Example

Every odd integer is the difference of two perfect squares.

Let n be an odd integer. We want to show that n is the difference of two perfect squares. Since n is odd, ∃ k ∈ Z where n = 2k + 1. Since k is an integer, k2 and (k + 1)2 are both perfect squares. Consider (k + 1)2 = k2 + 2k + 1

and k2 + 2k + 1 − k2 = 2k + 1

Therefore, if n is odd then we can express n as the difference of perfect squares. Q.E.D.

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

>More Odd and Even Integers Example If n is an odd integer then 4n3 + 2n − 1 is odd. Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer. If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider 4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1 = 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1 = 32k3 + 48k2 + 28k + 5 = 2(16k3 + 24k2 + 14k + 2) + 1 Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and this completes the proof.

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

>More Odd and Even Integers Example If n is an odd integer then 4n3 + 2n − 1 is odd. Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer. If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider 4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1 = 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1 = 32k3 + 48k2 + 28k + 5 = 2(16k3 + 24k2 + 14k + 2) + 1 Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and this completes the proof.

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1.

>More Odd and Even Integers Example If n is an odd integer then 4n3 + 2n − 1 is odd. Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer. If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider 4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1 = 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1 = 32k3 + 48k2 + 28k + 5 = 2(16k3 + 24k2 + 14k + 2) + 1 Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and this completes the proof.

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

4n3 + 2n − 1 =

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1

= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1

= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1

= 32k3 + 48k2 + 28k + 5

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1

= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1

= 32k3 + 48k2 + 28k + 5

= 2(16k3 + 24k2 + 14k + 2) + 1

More Odd and Even Integers

Example

If n is an odd integer then 4n3 + 2n − 1 is odd.

Proof: Suppose n is an odd integer. We will prove that 4n3 + 2n − 1 is an odd integer.

If n is odd, then ∃ k ∈ Z ∋ n = 2k + 1. Consider

4n3 + 2n − 1 = 4(2k + 1)3 + 2(2k + 1) − 1

= 4(8k3 + 12k2 + 6k + 1) + 4k + 2 − 1

= 32k3 + 48k2 + 28k + 5

= 2(16k3 + 24k2 + 14k + 2) + 1

Since 16k3 + 24k2 + 14k + 2 is an integer, 4n3 + 2n − 1 is odd and this completes the proof.

A Better Way

Although this is correct, it is not the most efficient proof we could have written. We could have simply noted that

4n3 + 2n − 1 = 4n3 + 2n − 2 + 1 = 2(2n3 + n − 1) + 1

is odd for all n, making this a trivial proof. It would be better to rewrite the hypothesis as ‘if n is an integer’.

Intersections and Unions

Example

For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z.

Let X, Y, Z be sets.

>Intersections and Unions Example For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z. Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We will show that Y and Z are subsets of each other. Let y ∈ Y. Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So, y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z. In a symmetric argument, it can be shown by assuming that we have some z ∈ Z that Z ⊆ Y. Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we have arrived at the desired result. Q.E.D.

Intersections and Unions

Example

For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z.

Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z.

>Intersections and Unions Example For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z. Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We will show that Y and Z are subsets of each other. Let y ∈ Y. Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So, y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z. In a symmetric argument, it can be shown by assuming that we have some z ∈ Z that Z ⊆ Y. Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we have arrived at the desired result. Q.E.D.

Intersections and Unions

Example

For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z.

Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We will show that Y and Z are subsets of each other.

>Intersections and Unions Example For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z. Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We will show that Y and Z are subsets of each other. Let y ∈ Y. Then y ∈ X ∪ Y. So, y ∈ X ∪ Z. That means y ∈ X or y ∈ Z. If y ∈ Z, we are done. So suppose y ∈ X. Then y ∈ X ∩ Y. So, y ∈ X ∩ Z. Thus both cases lead to y ∈ Z. Hence, Y ⊆ Z. In a symmetric argument, it can be shown by assuming that we have some z ∈ Z that Z ⊆ Y. Since Y ⊆ Z and Z ⊆ Y, it must be the case that Y = Z. Thus, we have arrived at the desired result. Q.E.D.

Intersections and Unions

Example

For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z.

Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We will show that Y and Z are subsets of each other.

Let y ∈ Y.

Intersections and Unions

Example

For all sets X, Y, Z, prove that if X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z then Y = Z.

Let X, Y, Z be sets. Assume X ∩ Y = X ∩ Z and X ∪ Y = X ∪ Z. We will show that Y and Z are subsets of each other.

Let y ∈ Y. Then y ∈ X ∪ Y. So,