Direct Proof In Advanced Structures And Mappings

1) In proving "If a relation R is symmetric and transitive, and every element is related to at least one element, then R is reflexive" directly, we need to:

Assume aRa is false for some a

Prove the contrapositive statement

Use induction on the number of elements

For each a, find b such that aRb, then use symmetry and transitivity to show aRa

We take an arbitrary element a. Since every element is related to at least one element, there exists b such that aRb. By symmetry, bRa. Then by transitivity, from aRb and bRa, we have aRa. Thus, R is reflexive.

Explanation

We take an arbitrary element a. Since every element is related to at least one element, there exists b such that aRb. By symmetry, bRa. Then by transitivity, from aRb and bRa, we have aRa. Thus, R is reflexive.

2) In a direct proof that "If a|b and a|c, then a|(b+c)," which is the appropriate formalization of the premises?

Let b+c = an for some integer n

Assume a does not divide b or c

Suppose a does not divide b+c

Let b = ak and c = am for integers k,m

We assume a|b and a|c, so b = a k and c = a m for integers k and m. Then, b+c = a k + a m = a(k+m), so a|(b+c).

Explanation

We assume a|b and a|c, so b = a k and c = a m for integers k and m. Then, b+c = a k + a m = a(k+m), so a|(b+c).

3) Which approach is appropriate for a direct proof of "If n is divisible by 6, then n is divisible by 2 and 3"?

Assume n is not divisible by 2 or 3

Prove the contrapositive statement

Use mathematical induction on k

Let n = 6k, then show n = 2(3k) and n = 3(2k)

We assume n is divisible by 6, so n = 6k for some integer k. Then, n = 2(3k), so divisible by 2, and n = 3(2k), so divisible by 3.

Explanation

We assume n is divisible by 6, so n = 6k for some integer k. Then, n = 2(3k), so divisible by 2, and n = 3(2k), so divisible by 3.

4) True or False: In a direct proof, we assume the conclusion is true and work backwards.

True

False

In a direct proof, we assume the hypothesis is true and work forwards to derive the conclusion. Assuming the conclusion is true is not part of direct proof.

Explanation

In a direct proof, we assume the hypothesis is true and work forwards to derive the conclusion. Assuming the conclusion is true is not part of direct proof.

5) In a direct proof of "If it is raining, then the ground is wet," we start by assuming:

It is not raining

The ground is wet

The ground is not wet

It is raining

We assume the hypothesis: it is raining. Then, based on common knowledge, we can derive that the ground is wet.

Explanation

We assume the hypothesis: it is raining. Then, based on common knowledge, we can derive that the ground is wet.

6) Which is a valid direct proof approach for "If x² = y² and x,y > 0, then x = y"?

Assume x ≠ y and derive contradiction

Prove the contrapositive statement

Use mathematical induction

Since x² - y² = 0, we have (x-y)(x+y) = 0, so x-y = 0 (since x+y > 0)

From x² = y², we get x² - y² = 0, so (x-y)(x+y)=0. Since x,y > 0, x+y > 0. Thus, x-y=0, so x=y.

Explanation

From x² = y², we get x² - y² = 0, so (x-y)(x+y)=0. Since x,y > 0, x+y > 0. Thus, x-y=0, so x=y.

7) In proving "If a and b are both odd, then a+b is even" directly, we should:

Assume a+b is odd

Prove the contrapositive statement

Use mathematical induction on a+b

Let a = 2k+1 and b = 2m+1, then a+b = 2(k+m+1)

We assume a and b are odd, so a=2k+1 and b=2m+1 for integers k,m. Then a+b=2k+1+2m+1=2(k+m+1), which is even.

Explanation

We assume a and b are odd, so a=2k+1 and b=2m+1 for integers k,m. Then a+b=2k+1+2m+1=2(k+m+1), which is even.

8) Which is the correct first step in a direct proof that "If A and B are countable sets, then A∪B is countable"?

Assume A∪B is uncountable

Prove the contrapositive statement

Use induction on the size of A and B

List the elements of A as a₁, a₂, ... and B as b₁, b₂, ...

Since A and B are countable, we can list their elements. Then, we can interleave these lists to form a sequence for A∪B, showing it is countable.

Explanation

Since A and B are countable, we can list their elements. Then, we can interleave these lists to form a sequence for A∪B, showing it is countable.

9) True or False: A direct proof of "If P then Q" involves assuming P is true.

True

False

In a direct proof, we always assume P is true and then show that Q must be true.

Explanation

In a direct proof, we always assume P is true and then show that Q must be true.

10) In a direct proof, after assuming the hypothesis, our goal is to:

Find a contradiction

Prove the negation of the hypothesis

Relevant with examples

Derive the conclusion through logical steps

After assuming the hypothesis, we use logical steps, definitions, and theorems to derive the conclusion.

Explanation

After assuming the hypothesis, we use logical steps, definitions, and theorems to derive the conclusion.

11) In a direct proof that "If f is increasing and g is increasing, then f•g is increasing," we begin by:

Assuming f(g(x)) < f(g(y))

Letting h = f•g and assuming h is increasing

Assuming x < y and showing f(g(x)) < f(g(y))

Supposing f•g is not increasing

We start by assuming x

Explanation

We start by assuming x

12) For proving "If a ring R has no zero divisors, and ab = ac with a ≠ 0, then b = c" directly, the key step is:

Assume b ≠ c and find contradiction

Prove the contrapositive statement

Use induction on the number of ring elements

Rewrite as a(b-c) = 0, then use no zero divisors property

From ab=ac, we get ab - ac = 0, so a(b-c)=0. Since a ≠ 0 and R has no zero divisors, b-c=0, so b=c.

Explanation

From ab=ac, we get ab - ac = 0, so a(b-c)=0. Since a ≠ 0 and R has no zero divisors, b-c=0, so b=c.

13) Which is a valid direct proof approach for "If a|b and b|c, then a|c"?

Assume a does not divide c

Prove the contrapositive statement

Use mathematical induction on c

Since b = ak and c = bm, we have c = a(km), so a|c

We assume a|b and b|c, so b=ak and c=bm for integers k,m. Then c=(ak)m=a(km), so a|c.

Explanation

We assume a|b and b|c, so b=ak and c=bm for integers k,m. Then c=(ak)m=a(km), so a|c.

14) Direct proof is the only valid proof technique in mathematics.

True

False

There are many proof techniques, such as contradiction, contrapositive, induction, and counterexample, all of which are valid.

Explanation

There are many proof techniques, such as contradiction, contrapositive, induction, and counterexample, all of which are valid.

15) In proving "If f and g are continuous at x = c, then f+g is continuous at x = c" directly, we start by:

Assuming f+g is continuous at c

Proving the contrapositive statement

Using proof by contradiction

Using the definition of continuity for f and g at c

We use the definition: since f and g are continuous at c, lim_{x→c} f(x) = f(c) and lim_{x→c} g(x) = g(c). Then, lim_{x→c} (f+g)(x) = f(c) + g(c) = (f+g)(c), so f+g is continuous.

Explanation

We use the definition: since f and g are continuous at c, lim_{x→c} f(x) = f(c) and lim_{x→c} g(x) = g(c). Then, lim_{x→c} (f+g)(x) = f(c) + g(c) = (f+g)(c), so f+g is continuous.

Direct Proof in Advanced Structures and Mappings

What do you like, dislike, and how can we improve?