Proofs about Discrete Structures

Section 1.5 Proofs about Discrete Structures

Objectives

After completing this section, you should be able to do the following.

Read and comprehend definitions related to discrete structures, so you can apply the definitions correctly.
🔗

🔗
Write proofs about discrete structures.
🔗

🔗

Subsection Section Preview

Investigate!

Suppose there are 15 people at a party. Most people know each other already, but there are still some people who decide to shake hands. Is it possible for everyone at the party to shake hands with exactly three other people?

🔗

So far we have seen how the logical form of a statement can inform how to build the scaffolding of a proof. This can only get us so far though: To flesh out the proof skeleton requires an understanding of the mathematical objects and structures the proofs are about. Some of this can come from carefully reading definitions. Yet there is also some less concrete understanding and intuition that comes from working with the objects and structures that can lead to that “ah-ha!” moment of inspiration that suggests how to proceed with a proof.

🔗

Another reason to shift our focus toward proofs about discrete structures is that doing so illustrates an important feature of mathematics: abstraction. We have been proving particular facts about particular problems. We might even start to notice similarities between the proofs for some statements. This might be due to the underlying mathematical structures that the problems are (secretly) about. If we prove the general facts about these structures, then we can apply these “theorems” to many different problems.

🔗

Some discrete structures lend themselves to particular styles of proof and some “standard” proof techniques can apply to particular structures. We will see some of this here, but mostly we take this opportunity to remind ourselves of some of the basic definitions and properties for discrete structures, and use the proofs about them to help understand these better.

🔗

Worksheet Preview Activity
A4 US

In this preview activity, we will explore some basic properties of sets and functions. Later in this section, we will write proofs about these ideas.

🔗

1.

Remember that a set is just a collection of elements. Here are two definitions about sets:

A set $A$ is a subset of a set $B,$ written $A \subseteq B,$ provided every element in $A$ is also an element of $B .$
🔗

🔗
Given sets $A$ and $B,$ the union of $A$ and $B,$ written $A \cup B,$ is the set containing every element that is in $A$ or $B$ or both.
🔗

🔗

🔗

Let’s build some examples.

🔗

(a)

Let

B = {1, 3, 5, 7, 9} .

Give an example of a set

A

containing

3

elements that is a subset of

B .

🔗

What is

A \cup B

for the set

A

you gave as an example?

🔗

(b)

Give an example of two distinct sets

A

and

B

such that

A \cup B = B .

🔗

A =

;

B =

🔗

For the example you gave, is

A \subseteq B ?

yes
🔗

🔗
no
🔗

🔗

🔗

(c)

Find examples, if they exist, of sets

A

and

B

such that

A \cup B \neq B .

🔗

A =

;

B =

🔗

For the example you gave, is

A \subseteq B ?

yes
🔗

🔗
no
🔗

🔗

🔗

2.

Which of the following are always true?

🔗

For any sets $A$ and $B,$ $A \cup B \subseteq B .$
🔗
What if $A = {1, 2, 3}$ and $B = {1, 3, 5} ?$
For any sets $A$ and $B,$ $B \subseteq A \cup B .$
🔗
For any sets $A$ and $B,$ if $A \subseteq B,$ then $A \cup B \subseteq B .$
🔗
For any sets $A$ and $B,$ if $A \cup B = B,$ then $A \subseteq B .$
🔗

🔗

3.

For any function

f : N \to N

and any set

A \subseteq N,

we can define the image of

A

under

f

to be the set of all outputs of

f

when the input is an element of

A .

We write this as

f (A) = {f (x) : x \in A} .

🔗

For the following tasks, let’s explore the function

f : N \to N

defined by

f (x) = x^{2} - 3 x + 8 .

🔗

(a)

Let

A = {1, 2, 3}

and

B = {2, 4, 6} .

Find

f (A)

and

f (B) .

Then find

f (A) \cup f (B) .

🔗

f (A) =

;

f (B) =

;

f (A) \cup f (b) =

🔗

(b)

Now find

A \cup B

and

f (A \cup B) .

🔗

A \cup B =

;

f (A \cup B) =

🔗

(c)

Give an example, if one exists, of two distinct sets

A

and

B

such that

A \subseteq B

and

f (A) \subseteq f (B) .

🔗

A =

;

B =

🔗

Give an example, if one exists, of two distinct sets

A

and

B

such that

A \subseteq B

but

f (A) ⊈ f (B) .

🔗

A =

;

B =

🔗

Subsection Proofs about Sets

Recall that a set is an unordered collection of elements. We can describe a set by listing these elements, or by specifying a property that all elements in the set satisfy. For example,

A = {1, 2, 3, 4, 5},

B = {x \in N : x < 10} .

The second set here is the set of natural numbers (

0, 1, 2, \dots

) less than 10. Notice that every element in

A

is also an element of

B .

Here is a definition that captures that idea.

🔗

Definition 1.5.1.

A set

A

is a subset of a set

B,

written

A \subseteq B,

provided every element of

A

is also an element of

B .

🔗

The set

B

is sometimes called a superset of

A .

🔗

We say

A

is a proper subset of

B,

written

A \subset B,

provided

A \subseteq B

and

A \neq B .

In other words, if every element in

A

is an element in

B,

and there is at least one element in

B

that is not in

A .

🔗

Example 1.5.2.

Let

A = {x \in N : x < 5}

and

B = {x \in N : x^{2} < 10} .

B \subseteq A ?

B

a proper subset of

A ?

🔗

Solution.

We are asking whether every natural number less than 5 is also a natural number whose square is less than 10. Okay, we could just write out the elements of the sets:

A = {0, 1, 2, 3, 4}

and

B = {0, 1, 2, 3}

(since

3^{2} = 9

and

4^{2} = 16

). So

B \subseteq A .

But

B \neq A,

so in fact

B \subset A .

🔗

The sets in the example above were small, and it is easy enough to write down the elements of the sets. However, we can also prove subset relationships between sets if this isn’t practical or even possible (perhaps the sets are infinite). Let’s look carefully at how we could have reasoned about the example above.

🔗

We claimed that every element of

B

was also an element of

A .

Another way to say this: For all numbers

n,

n

is an element of

B,

then

n

is also an element of

A .

Recognizing this as a conditional statement, we can proceed to give a direct, contrapositive, or contradiction proof of the fact. Here a direct proof would be perfectly acceptable. Let’s try it:

🔗

Proof.

Let

n

be an element of the set

B .

Then

n^{2} < 10,

by the definition of

B .

Since

4^{2} = 16,

we must have that

n < 4 .

By the definition of

A,

and the fact that

4 < 5,

we see that

n \in A .

🔗

To be clear, this proof is way more than we would normally do for this example, but its format should be illuminating. Proving that one set is a subset of another is really the same as proving an implication!

🔗

To give an example of how we can apply the definition of “subset” in a more general setting, let’s prove a basic fact about subsets.

🔗

Proposition 1.5.3.

For any sets

A,

B,

and

C,

A \subseteq B

and

B \subseteq C,

then

A \subseteq C .

🔗

Proof.

We will give a direct proof. Let

A,

B,

and

C

be sets, and assume that

A \subseteq B

and

B \subseteq C .

We will prove that

A \subseteq C .

🔗

Let

x

be an element of

A .

Since

A \subseteq B,

we know that

x \in B .

Since

B \subseteq C,

we know that

x \in C .

Therefore,

A \subseteq C .

🔗

Now let’s prove a fact about numbers: Every multiple of 9100 is also a multiple of 13. We could factor 9100, but here is an easier way. The set of multiples of 9100 is a subset of the set of multiples of 91. And the set of multiples of 91 is a subset of the set of multiples of 13. Now apply the proposition above.

🔗

The proof of Proposition 1.5.3 is what is sometimes called an element chasing proof. By the definition of subset,

A \subseteq B

means every element of

A

is an element of

B,

or equivalently, for all

x,

x

is an element of

A,

then

x

is an element of

B .

One way to prove this is to “chase” the element

x

from

A

B .

🔗

Example 1.5.4.

Prove that if

A \subseteq B,

then

A \cup B \subseteq B .

Recall that

A \cup B

is the union of sets

A

and

B,

and contains all elements that are in

A

B

or both.

🔗

Solution.

We will write a direct proof. So we will assume that

A \subseteq B

and prove that

A \cup B \subseteq B .

Our desired conclusion is a statement about subsets, so let’s do an element chasing proof for it.

🔗

Proof.

Let

A

and

B

be sets and assume

A \subseteq B .

Now let

x

be an element in

A \cup B .

This means that

x

is an element of

A,

x

is an element of

B,

or both.

⁵

From the definition of union.

🔗

Consider the cases. If

x

is an element of

A,

then since

A \subseteq B,

we know that

x

is an element of

B .

On the other hand, if

x

is not an element of

A,

then

x

must be an element of

B

(since

x

is in

A \cup B

). In either case,

x

is an element of

B .

Therefore,

A \cup B \subseteq B .

🔗

We can actually prove a strong statement:

A \subseteq B

if and only if

A \cup B = B .

You are asked to do this in the exercises.

🔗

Subsection Proofs about Functions

A function

f : A \to B

is a rule that assigns each element of the set

A

(the domain) to exactly one element of the set

B

(the codomain). It is any rule: There doesn’t have to be a formula or rationale for it; we just need to match up elements from

A

to elements in

B .

For example, we could let

A

be the set of students enrolled in a particular Discrete Math course and let

B

be the set of months of the year. Now define the function

f : A \to B

to be the rule that assigns to each student the month in which their birthday falls. Since every student has an assigned month, and no more than one month, this is a function.

🔗

Here is a definition of a particular type of function.

🔗

Definition 1.5.5.

A function

f : A \to B

is injective (or one-to-one) provided every element in

B

is the image of at most one element in

A .

In other words, no element in

B

is the output for more than one input from

A .

🔗

In the example below, we use two-line notation to describe a function. The top row contains the inputs, and the bottom row lists the corresponding outputs. So

f : {1, 2, 3, 4} \to {a, b, c, d}

might be defined as,

f = (\begin{matrix} 1 & 2 & 3 & 4 \\ a & b & c & d \end{matrix}),

which means that

f (1) = a,

f (2) = b,

f (3) = c,

and

f (4) = d .

🔗

Example 1.5.6.

Let

A = {1, 2, 3}

and

B = {2, 4, 6, 8} .

Consider the functions

f : A \to B

and

g : A \to B

defined by,

f = (\begin{matrix} 1 & 2 & 3 \\ 2 & 8 & 6 \end{matrix}), g = (\begin{matrix} 1 & 2 & 3 \\ 4 & 6 & 4 \end{matrix}) .

Which of these functions is injective?

🔗

Solution.

The function

f

is injective: Each element of

B

is the image of at most one element of

A .

The function

g

is not injective: The element 4 in

B

is the image of both 1 and 3 in

A .

🔗

Consider the student-to-birth-month function again. Could this possibly be injective? Or put another way, must there be two students in the course with the same birth month (which would say the function is not injective)? The answer seems to depend on how many students are in the class.

🔗

But let’s pause and think about the more general fact about functions we have here. Let’s prove the following fact. Recall that

| A |

denotes the cardinality (size) of the set

A :

the number of elements in

A .

🔗

Proposition 1.5.7.

Suppose

f : A \to B

is a function with

A

and

B

both finite sets. If

| A | > | B |,

then

f

is not injective.

🔗

Proof.

We will give a proof of the contrapositive: If

f

is injective, then

| A | \leq | B | .

Let

| B | = n .

Since

f

is injective, each element of

B

must be the output for at most one element of

A .

Thus there are at most

n

elements in

A

that get mapped to

B

f .

But the definition of a function requires that every element of the domain is mapped to exactly one element of the codomain, so there must be at most

n

elements in

A .

🔗

Does this proof remind you of our pigeonhole-like proofs? It should, since this is precisely (one of) the careful formulations of the pigeonhole principle. We could have proved the fact about students sharing a birth month, but now we can just apply the proposition above and be done. When you apply a theorem or proposition to directly prove another result, we call the latter result a corollary.

🔗

Corollary 1.5.8.

Suppose a class has 25 students. Then at least two students share the same birth month.

🔗

Proof.

Consider the function that maps each student to their birth month. Since the domain has 25 elements and the codomain has 12 elements, the function is not injective, by Proposition 1.5.7. Therefore, at least two students share the same birth month.

🔗

Functions always have inputs from a set (called the domain) and outputs in a set as well (called the codomain). This naturally leads to facts to consider about the interaction between sets and functions.

🔗

Definition 1.5.9.

Given a function

f : X \to Y

and a set

A \subseteq X,

we define the image of

A

under

f

to be the set

f (A) = {f (a) \in Y : a \in A} .

That is,

f (A)

is the set of all outputs of the function for inputs in

A .

🔗

Example 1.5.10.

Let

f : N \to N

be defined by

f (n) = 2 n .

Let

A = {1, 2, 3} .

Find

f (A) .

🔗

Solution.

Evaluate each element of

A

f .

f (1) = 2; f (2) = 4; f (3) = 6 .

We want the set of these outputs. So

f (A) = {2, 4, 6} .

🔗

Now let’s prove something.

🔗

Proposition 1.5.11.

Let

f : X \to Y

be a function, and let

A

and

B

be subsets of

X .

A \subseteq B,

then

f (A) \subseteq f (B) .

🔗

Proof.

Let

f,

A,

and

B

be as in the proposition. Assume that

A \subseteq B .

Now consider an element

y \in f (A) .

By definition, this means that there is some

a \in A

such that

f (a) = y .

Since

a \in A

and

A \subseteq B,

we have that

a \in B .

Then by definition,

y = f (a) \in f (B) .

Since

y

was an arbitrary element of

f (A),

we have proved that

f (A) \subseteq f (B) .

🔗

Notice that the proof above is an element chasing proof again. This makes sense as soon as you remember that

f (A)

and

f (B)

are just the names of sets. To prove one set is a subset of another, we chase elements from the subset to the superset.

🔗

Subsection Proofs about Relations

A relation on a set

A

is a set of ordered pairs of elements from

A .

We can think of a relation as a way to describe a type of relationship between elements of

A .

For example, we might have a relation on the set of people at a party that describes who is friends with whom. We might have a relation on the set of natural numbers that describes which pairs of numbers are related by the relation

x < y .

🔗

Relations permeate all of mathematics, often without us even thinking of them. Whenever we make a statement about two elements of a set, we are implicitly defining a relation. The statement is true when the pair is in the relation. For example, the statement, “3 is less than 5,” is true because the pair

(3, 5)

is in the relation

< .

In fact, using the language we developed in the subsection Quantifiers and Predicates, we can say that a relation is just a predicate, where the variables come from the same set.

🔗

Often relations have special symbols like “

=

” or “

\leq

” or “

⊥

”. When we talk about a general relation, we will either use

\sim

and write

x \sim y,

or use a capital letter like

R,

and write

R (x, y)

x R y

or even

(x, y) \in R

(these all mean the same thing).

🔗

When we study relations, we try to identify properties that relations might have. Here is an example of a very common property.

🔗

Definition 1.5.12.

A relation

R

on a set

A

is transitive provided for all

x, y, z \in A,

x R y

and

y R z,

then

x R z .

🔗

Example 1.5.13.

Consider the relation

\sim

on the set of students in your Discrete Math course that holds of two students, provided they have some other class together. Is this relation transitive?

🔗

Solution.

No, not necessarily (although for some sets of students it could be). For example, suppose Alice has another class with Bruce, say Introduction to Programming. Carlos is not in Intro to Programming, but he and Bruce are both in Organic Chemistry. So then Alice

\sim

Bruce and Bruce

\sim

Carlos, but it might not be the case that Alice

\sim

Carlos (since Alice need not be in Organic Chemistry with Carlos).

🔗

Proving that a relation is not transitive takes nothing more than finding a counterexample, which means finding three elements

a,

b,

and

c

such that

a \sim b,

b \sim c,

but

a ≁ c

(remember, the only way for an implication to be false is for the hypothesis to be true and the conclusion to be false).

🔗

Perhaps slightly more interesting would be proof that a relation is transitive.

🔗

Example 1.5.14.

Consider the set of all students in your Discrete Mathematics class, and define the relation

\sim

that holds of students

a

and

b

(so

a \sim b

is true), provided

a

is taller than

b .

Prove that this relation is transitive.

🔗

Solution.

The definition of transitive is an implication, so we can try a direct proof.

🔗

Proof.

Let

a,

b,

and

c

be arbitrary students in your Discrete Math course. Assume,

a \sim b

and

b \sim c .

That means that

a

is taller than

b,

and that

b

is taller than

c .

But then surely

a

must be even taller than

c

than they are taller than

b,

so we have that

a \sim c

is true as well. Thus

\sim

is transitive on this set.

🔗

Subsection Proofs about Graphs

We will spend all of Chapter 2 studying proofs about graphs since this is such a rich area of mathematics. As a preview, here is an example of how graph proofs can go.

🔗

A graph is a set

V

of vertices and a set

E

of edges. The edges are two-element subsets of the vertices, and we can think of them as representing relationships between the vertices. Note, this is an abstract definition of a graph using sets, but we often draw graphs using dots for the vertices connected by lines for the edges, as this gives us a nice picture of what is going on.

🔗

Since graphs represent a type of relationship between elements (vertices), we can use graphs to represent many real-world problems. For example, the vertices of a graph might represent people at a party. Each edge can represent a handshake between two people. So if we wondered whether it is possible for the 15 people at a party to each shake hands with exactly 3 people there, we are really asking whether there is a graph with 15 vertices where each vertex belongs to 3 edges. (“Belongs to”?? Yes, because an edge is a two-element subset of the vertices, so if an edge “touches” or “comes out of” a vertex, that means the vertex belongs to that particular two-element subset.)

🔗

Here is a definition related to this idea.

🔗

Definition 1.5.15.

Let

v

be a vertex in a graph

G .

The degree of

v,

written

d (v),

is the number of edges that contain

v,

i.e., the number of edges incident to

v .

🔗

Example 1.5.16.

Consider the graph

G

with vertices

V = {1, 2, 3, 4}

and edges

E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}} .

What is the degree of each vertex in

G ?

🔗

Solution.

It might be helpful to picture the graph:

🔗

$A graph with four vertices labeled 1 through 4. There are edges from vertex 1 to each of the other vertices, and an edge between vertices 2 and 3.$

We have

d (1) = 3,

d (2) = 2,

d (3) = 2,

and

d (4) = 1 .

You can see this by counting how many edges are incident to each vertex, or by counting how many edges (subsets) each vertex belongs to.

🔗

So is it possible for 15 people to each shake hands with exactly three people in their group? Well, is there a graph with 15 vertices, all of degree 3? The answer is no!

🔗

One way you can see this is if you ask how many edges such a graph would have. Each vertex is incident to three edges, so counting incidences, we get

15 \cdot 3 = 45 .

But every edge is incident to two vertices, so we have counted each edge twice. So the number of edges in such a graph would be

45 / 2 = 22.5 .

But the number of edges in a graph must be a whole number, so there is no such graph.

🔗

This suggests that we can say something more in general. The following proposition is a simple consequence of the Handshake Lemma 2.1.8, which we will prove in Section 2.1. Here we give a complete proof of this particular formulation of it.

🔗

Proposition 1.5.17.

In any graph, the number of vertices with odd degree must be even.

🔗

Proof.

We will prove this by contradiction. Suppose there was a graph with an odd number of vertices with odd degree. Consider the sum of the degrees of all the vertices. The sum for the odd-degree vertices would be odd (since the sum of an odd number of odd numbers is odd). The sum of the even-degree vertices will be even (any sum of even numbers must be even). The sum of an odd number and an even number is odd. Thus the sum of all the degrees will be odd.

🔗

However, the number of edges in a graph is half the sum of the degrees (by Lemma 2.1.8, or simply because each edge contributes one to the count of the degree of two vertices). Since the number of edges is a whole number, we see that the sum of the degrees must be even. This contradicts what we found in the previous paragraph.

🔗

Therefore, in any graph, the number of vertices with odd degree must be even.

🔗

Reading Questions Reading Questions

1.

Which of the following is the definition of a function

f : A \to B

being injective?

🔗

Every element of $B$ is the image of at most one element of $A .$
🔗
The domain $A$ is a larger set than the codomain $B .$
🔗
No, in fact, this can never happen if $f$ is injective.
Every element of $A$ is sent to at most one element of $B .$
🔗
This is just part of the definition of a function.
The codomain $B$ is no smaller than the domain $A .$
🔗
This must be true if $f$ is injective, but it is not part of the definition of injective.

🔗

2.

When would you most likely use element chasing as part of a proof?

🔗

When proving that one set is a subset of another.
🔗
When proving that a function is injective.
🔗
When proving that a relation is transitive.
🔗
When proving that a graph has an odd number of edges.
🔗

🔗

3.

What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

🔗

Exercises Practice Problems

1.

Given sets

A

and

B,

the intersection of

A

and

B,

written

A \cap B,

is the set of all elements that are in both

A

and

B .

🔗

Suppose you wanted to prove that if

A \cap B = B

then

B \subseteq A .

🔗

Which would be a good start to this proof if you used a direct proof?

🔗

Let $a$ be an element of $A \cap B .$
🔗
Let $b$ be an element of $B .$
🔗
Let $a$ be an element of $A .$
🔗
Suppose there is an element $b$ in $B$ that is not in $A .$
🔗
This would be a good start to a proof by contradiction or contrapositive, not a direct proof.

🔗

2.

Suppose you wanted to prove that for all sets

A

and

B

that

A \cap B \subseteq A .

Which of the following would be a good start to a proof by contradiction?

🔗

Suppose there is an element $a$ in $A$ that is not in $A \cap B .$
🔗
Suppose there is an element $a$ in $A \cap B$ that is not in $A .$
🔗
Let $a$ be an element of $A .$
🔗
Let $a$ be an element of $A \cap B .$
🔗
This would be a good start to a direct proof, not a proof by contradiction.

🔗

3.

Arrange some of the statements below to form a correct proof of the following statement: “For any sets

A

and

B,

B \subseteq A \cap B

then

B \subseteq A .

”

🔗

Suppose \(B \subseteq A \cap B\text{,}\) and let \(b\) be an element of \(B\text{.}\)🔗

---
Then \(b\) is an element of \(A \cap B\) since \(B \subseteq A \cap B\text{.}\)🔗

---
Since \(A \cap B\) contains all the elements that are in both \(A\) and \(B\text{,}\) \(b\) is an element of \(A\text{.}\)🔗

---
Therefore \(B \subseteq A\text{.}\)🔗

---
Therefore \(B \subseteq A \cap B\)🔗
 #distractor
---
Then \(b\) is an element of \(B\) since \(B \subseteq A \cap B\text{.}\)🔗
 #distractor
---
Let \(b\) be an element of \(A \cap B\text{.}\)🔗
 #distractor
---
Suppose \(B \subseteq A\text{.}\)🔗
 #distractor
---
Suppose \(A \subseteq B\text{.}\)🔗
 #distractor

🔗

4.

Prove that for any sets

A

and

B,

(A \cap B) \cup A = A

🔗

Arrange the statements below to form a correct proof.

🔗

First we will prove that \((A \cap B) \cup A \subseteq A\text{.}\)🔗

---
Let \(x\) be an element of \((A \cap B) \cup A\text{.}\)🔗

---
Then \(x\) is an element of \(A \cap B\text{,}\) or \(x\) is an element of \(A\text{.}\)🔗

---
So in particular, \(x\) is an element of \(A\text{.}\)🔗

---
Therefore \((A \cap B) \cup A \subseteq A\text{.}\)🔗

---
Second, we will prove that \(A \subseteq (A \cap B) \cup A\text{.}\)🔗

---
Let \(x\) be an element of \(A\text{.}\)🔗

---
Then \(x\) is an element of \((A \cap B) \cup A\text{,}\) since \(x\) is in \(A\) or in the other set.🔗

---
Therefore \(A \subseteq (A \cap B) \cup A\text{.}\)🔗

---
Since \((A \cap B) \cup A \subseteq A\) and \(A \subseteq (A \cap B) \cup A\text{,}\) we have \((A \cap B) \cup A = A\text{.}\)🔗

🔗

5.

Let

f : X \to Y

be a function and let

B \subseteq Y

be a subset of the codomain. Define the inverse image of

B

under

f

to be the set

f^{- 1} (B) = {x \in X : f (x) \in B} .

That is, it is all the elements in the domain that are mapped to elements in

B .

🔗

Prove that if

B_{1} \subseteq B_{2}

are subsets of the codomain, then

f^{- 1} (B_{1}) \subseteq f^{- 1} (B_{2}) .

🔗

Arrange some of the statements below to form a correct proof.

🔗

Suppose \(B_1 \subseteq B_2\text{.}\)🔗

---
Let \(a\) be an element of \(f\inv(B_1)\text{.}\)🔗

---
This means that \(f(a)\) is an element of \(B_1\text{.}\)🔗

---
Since \(B_1 \subseteq B_2\text{,}\) \(f(a)\) is an element of \(B_2\text{.}\)🔗

---
This then means that \(a\) is an element of \(f\inv(B_2)\text{.}\)🔗

---
Therefore \(f\inv(B_1) \subseteq f\inv(B_2)\text{.}\)🔗

---
Let \(b\) be an element of \(B_1\text{.}\)🔗
 #distractor
---
Therefore \(b\) is an element of \(B_2\text{.}\)🔗
 #distractor
---
Thus \(B_1 \subseteq B_2\text{.}\)🔗
 #distractor

🔗

Exercises Additional Exercises

1.

Prove that for any two sets

A

and

B,

A \subseteq B

if and only if

A \cup B = B .

🔗

Hint.

To prove that

A \subseteq B

if and only if

A \cup B = B,

you need to prove two implications:

If $A \subseteq B,$ then $A \cup B = B .$
🔗

🔗
If $A \cup B = B,$ then $A \subseteq B .$
🔗

🔗

🔗

To prove two sets are equal, we usually prove that each is a subset of the other.

🔗

2.

The intersection of sets

A

and

B,

denoted

A \cap B,

is the set of all elements that are in both

A

and

B .

🔗

Prove that for any two sets

A

and

B,

A \subseteq B

if and only if

A \cap B = A .

🔗

3.

Prove that for any sets

A,

B,

and

C,

A \cup B \subseteq C,

then

A \subseteq C

and

B \subseteq C .

🔗

4.

Prove that for any sets

A,

B,

and

C,

A \subseteq C

and

B \subseteq C,

then

A \cup B \subseteq C .

🔗

5.

The difference of sets

A

and

B,

written

A ∖ B,

is the set of all elements that are in

A

but not in

B .

🔗

The empty set, written

\emptyset,

is the set that contains no elements.

🔗

Prove that if

A ∖ B = A

then

A \cap B = \emptyset .

🔗

6.

Prove that if

A ∖ B = B ∖ A

then

A = B .

🔗

7.

Let

f : X \to Y

be a function, and let

A

and

B

be subsets of

X .

🔗

(a)

Prove that

f (A \cap B) \subseteq f (A) \cap f (B) .

🔗

(b)

Find an example of a function and two sets

A

and

B

such that

f (A \cap B) \neq f (A) \cap f (B) .

🔗

8.

Let

f : X \to Y

be a function, and let

A

and

B

be subsets of

X .

🔗

(a)

Prove that

f (A \cup B) \subseteq f (A) \cup f (B) .

🔗

(b)

Prove that

f (A) \cup f (B) \subseteq f (A \cup B)

🔗

(c)

What can you conclude from the two proofs above?

🔗

9.

Given a function

f : X \to Y

and a set

B \subseteq Y,

we define the inverse image of

B

under

f

as the set

f^{- 1} (B) = {x \in X : f (x) \in B .

That is, it is all the elements in the domain that are mapped to elements in

B .

🔗

(a)

For

f : N \to N

defined by

f (n) = n^{2},

what are each of the following sets?

$f^{- 1} ({1, 4, 9})$
🔗

🔗
$f^{- 1} ({2, 3, 5, 7})$
🔗

🔗
$f^{- 1} ({1, 2, \dots, 10})$
🔗

🔗

🔗

(b)

Prove that for any set

C \subseteq X,

C \subseteq f^{- 1} (f (C)) .

🔗

(c)

Give an example of a function

f

and a set

C

such that

C \neq f^{- 1} (f (C)) .

🔗

(d)

Prove that for any set

D \subseteq Y,

f (f^{- 1} (D)) \subseteq D .

🔗

(e)

Give an example of a function

f

and a set

D

such that

f (f^{- 1} (D)) \neq D .

🔗

10.

Let

f : X \to Y

be a function, and let

A

and

B

be subsets of

Y .

Prove that

f^{- 1} (A \cap B) = f^{- 1} (A) \cap f^{- 1} (B) .

🔗

11.

Let

f : X \to Y

be a function, and let

A

and

B

be subsets of

Y .

Prove that

f^{- 1} (A \cup B) = f^{- 1} (A) \cup f^{- 1} (B) .

🔗

12.

For each relation below, determine whether it is transitive. If it is, prove it. If it is not, give a counterexample.

🔗

(a)

The relation “

|

” (divides) on

Z

defined by

a | b

provided

b

is a multiple of

a .

🔗

(b)

The relation “

\leq

” (less than or equal to) on

R .

🔗

(c)

The relation “

⊥

” (is perpendicular to) on the set of lines in the plane.

🔗

(d)

The relation “

\sim

” (is similar to) on the set of triangles in the plane (two triangles are similar if they have the same angles, but are not necessarily the same size).

🔗

You have attempted 1 of 8 activities on this page.

🔗

Prev Top Next

Section 1.5 Proofs about Discrete Structures

Objectives

Subsection Section Preview

Investigate!

Worksheet Preview Activity A4US

1.

(a)

(b)

(c)

2.

3.

(a)

(b)

(c)

Subsection Proofs about Sets

Definition 1.5.1.

Example 1.5.2.

Proof.

Proposition 1.5.3.

Proof.

Example 1.5.4.

Proof.

Subsection Proofs about Functions

Definition 1.5.5.

Example 1.5.6.

Proposition 1.5.7.

Proof.

Corollary 1.5.8.

Proof.

Definition 1.5.9.

Example 1.5.10.

Proposition 1.5.11.

Proof.

Subsection Proofs about Relations

Definition 1.5.12.

Example 1.5.13.

Example 1.5.14.

Proof.

Subsection Proofs about Graphs

Definition 1.5.15.

Example 1.5.16.

Proposition 1.5.17.

Proof.

Reading Questions Reading Questions

1.

2.

3.

Exercises Practice Problems

1.

2.

3.

4.

5.

Exercises Additional Exercises

1.

2.

3.

4.

5.

6.

7.

(a)

(b)

8.

(a)

(b)

(c)

9.

(a)

(b)

(c)

(d)

(e)

10.

11.

12.

(a)

(b)

(c)

(d)

Worksheet Preview Activity
A4 US