Quiz Access

Test 2
Name: DrSarah Greenwald
Start Time: Jul 31, 2000 16:39	Time Allowed: 45 min
Number of Questions: 5

Question 1 (9 points)

Find the flaw in the following proof that all horses are the same color (you may choose more than one answer - this question will be graded on an all or nothing scale):

We proceed by induction. Let S={n in N | in any set of n horses, all members are the same color}. Since in any set of 1 horse, all members are the same color, we know that 1 is in S. For the induction step, let k be an element of N and assume that k is an element of S. We must show that k+1 is an element of S, ie in any set of k+1 horses, all members are the same color. Let A be a set of k+1 horses, call them H1,...,H(k+1). We will show that they all have the same color. Since {H2,...,H(k+1)} is a set of k horses, and k is in S, we know that H2,...,H(k+1) all have the same color. Since {H1,...,Hk} is a set of k horses, and k is in S, we also know that H1,...,Hk all have the same color. Thus H1 and H2 are the same color, and hence H1,...,H(k+1) are the same color. Therefore, k+1 is an element of S. Therefore S=N, ie all horses are the same color.

1. The flaw is in the part of the proof showing 1 is an element of S

2. The flaw is in the setup of the induction step

3. The flaw is in the statement Since {H2,...,H(k+1)} is a set of k horses, and k is in S, we know that H2,...,H(k+1) all have the same color.

4. The flaw is in the statement Since {H1,...,Hk} is a set of k horses, and k is in S, we also know that H1,...,Hk all have the same color.

5. The flaw is in the statement Thus H1 and H2 are the same color, and hence H1,...,H(k+1) are the same color. Therefore, k+1 is an element of S.

Question 2 (28 points)

Notice that in the following statements on the left, the type and order of quantifiers matters very much since switching them around results in a statement that is logically very different than the original.

Match the statement to the proof that either proves or disproves it.

1. For all x in R\{0}, there exists y in R s.t. xy=1
a. Let y in R be arbitrary. We will produce x in R\{0} s.t. xy is not 1.
Case 1 y not 0
Take x=2/y. Notice that x is in R\{0} since y is not equal to 0. Also, xy=2/y(y)=2(y/y)=2(1)=2. Since 2 is not equal to 1, we have shown that xy is not equal to 1.
Case 2 y=0
Take x=3. Notice that x is in R\{0} since 3 is in R\{0}. Also, xy=3(0)=0. Since 0 is not equal to 1, we have shown that xy is not equal to 1.
So, for each y in R, we have produced x in R\{0} so that xy is not equal to 1, as desired.

2. There exists y in R s.t. for all x in R\{0}, xy=1
b. Let x be an arbitrary element of R\{0}. We will produce y in R s.t. xy is not 1. Take y=0. Notice that y is in R. Also, xy=x(0)=0 by multiplication by 0. Since 0 is not equal to 1, we have shown xy is not equal to 1, as desired.

3. There exists x in R\{0} s.t. for all y in R, xy=1
c. We will produce y in R s.t. for all x in R\{0}, xy is not equal to 1. Take y=0. Notice that y is in R. Let x be in R\{0}. We will show that xy is not equal to 1. Notice that xy=x(0)=0, by multiplication by zero. Since 0 is not equal to 1, we have shown that xy is not equal to 1, as desired.

4. For all y in R, there exists x in R\{0} s.t. xy=1
d. Let x be an arbitrary element of R\{0}. We will produce y in R s.t. xy=1. Take y=1/x. Notice that 1/x is in R since x is not 0 by def. Also,
xy=x(1/x)=x/x=1, as desired.

1 -->

2 -->

3 -->

4 -->

Question 3 (5 points)

Question 4 (9 points)

Question 5 (9 points)

Match the following people with their math:

Francisco Maurolycus a. mentions the equation 8x8x8x8=4 in the cut "As" from Songs in the Key of Life.

Stevie Wonder b. the first mathematician known to use induction (in the proof that for all n in N, 1+3+5+...+(2n-1)=n^2.

Sophie Germain c. proved that x^5+y^5=z^5 has no non-zero whole number solutions.

Pierre de Fermat d. used modular arithmetic methods to try and prove that x^p + y^p = z^p has no non-zero whole number solutions for an odd prime p which does not divide x,y, or z.

Leonhard Euler e. proved that x^3+y^3=z^3 has no non-zero whole number solutions.

Adrien-Marie Legendre f. proved that x^4+y^4=z^4 has no non-zero whole number solutions.

Francisco Maurolycus -->

Stevie Wonder -->

Sophie Germain -->

Pierre de Fermat -->

Leonhard Euler -->

Adrien-Marie Legendre -->

	1.	The flaw is in the part of the proof showing 1 is an element of S
	2.	The flaw is in the setup of the induction step
	3.	The flaw is in the statement Since {H2,...,H(k+1)} is a set of k horses, and k is in S, we know that H2,...,H(k+1) all have the same color.
	4.	The flaw is in the statement Since {H1,...,Hk} is a set of k horses, and k is in S, we also know that H1,...,Hk all have the same color.
	5.	The flaw is in the statement Thus H1 and H2 are the same color, and hence H1,...,H(k+1) are the same color. Therefore, k+1 is an element of S.

1. For all x in R\{0}, there exists y in R s.t. xy=1		a. Let y in R be arbitrary. We will produce x in R\{0} s.t. xy is not 1. Case 1 y not 0 Take x=2/y. Notice that x is in R\{0} since y is not equal to 0. Also, xy=2/y(y)=2(y/y)=2(1)=2. Since 2 is not equal to 1, we have shown that xy is not equal to 1. Case 2 y=0 Take x=3. Notice that x is in R\{0} since 3 is in R\{0}. Also, xy=3(0)=0. Since 0 is not equal to 1, we have shown that xy is not equal to 1. So, for each y in R, we have produced x in R\{0} so that xy is not equal to 1, as desired.
2. There exists y in R s.t. for all x in R\{0}, xy=1		b. Let x be an arbitrary element of R\{0}. We will produce y in R s.t. xy is not 1. Take y=0. Notice that y is in R. Also, xy=x(0)=0 by multiplication by 0. Since 0 is not equal to 1, we have shown xy is not equal to 1, as desired.
3. There exists x in R\{0} s.t. for all y in R, xy=1		c. We will produce y in R s.t. for all x in R\{0}, xy is not equal to 1. Take y=0. Notice that y is in R. Let x be in R\{0}. We will show that xy is not equal to 1. Notice that xy=x(0)=0, by multiplication by zero. Since 0 is not equal to 1, we have shown that xy is not equal to 1, as desired.
4. For all y in R, there exists x in R\{0} s.t. xy=1		d. Let x be an arbitrary element of R\{0}. We will produce y in R s.t. xy=1. Take y=1/x. Notice that 1/x is in R since x is not 0 by def. Also, xy=x(1/x)=x/x=1, as desired.

	1.	produce two consecutive numbers of the form (15n+k)^7 mod 15 and (15n+j)^7 mod 15, where k is not equal to j and k and j run from 0 to 14.
	2.	look at all the numbers of the form (15*n+j)^7 mod 15, where j runs from 0 to 14, and then show that 2 of them are consecutive.
	3.	look at all the numbers of the form (15*n+j)^7 mod 15, where j runs from 0 to 14, and then show that all of them are consecutive.

Francisco Maurolycus		a. mentions the equation 8x8x8x8=4 in the cut "As" from Songs in the Key of Life.
Stevie Wonder		b. the first mathematician known to use induction (in the proof that for all n in N, 1+3+5+...+(2n-1)=n^2.
Sophie Germain		c. proved that x^5+y^5=z^5 has no non-zero whole number solutions.
Pierre de Fermat		d. used modular arithmetic methods to try and prove that x^p + y^p = z^p has no non-zero whole number solutions for an odd prime p which does not divide x,y, or z.
Leonhard Euler		e. proved that x^3+y^3=z^3 has no non-zero whole number solutions.
Adrien-Marie Legendre		f. proved that x^4+y^4=z^4 has no non-zero whole number solutions.

Francisco Maurolycus	-->
Stevie Wonder	-->
Sophie Germain	-->
Pierre de Fermat	-->
Leonhard Euler	-->
Adrien-Marie Legendre	-->

	1.	yes
	2.	no
	3.	sometimes