2. Let D be a relation on the natural numbers N deﬁned by D = {(m,n)...

2. Let D be a relation on the natural numbers N deﬁned by D = {(m,n) : m | n} (i.e., D(m,n) is true when n is divisible by m. For this problem, you’ll be proving that D is a partial order. This means that you’ll need to prove that it is reﬂexive, anti-symmetric, and transitive.

(a) Prove that D is reﬂexive. (Yes, you already did this problem on one of the minihomework assignments. You don’t have to redo the problem, but you should at least copy over your answer from that assignments to this one.)

(b) Prove that D is anti-symmetric. You may use the following fact: for any two natural numbers m and n, if m·n = 1, then m = 1 and n = 1. (Note that D is only anti-symmetric because the domain is the natural numbers. If we switched to the domain of integers, then things would be completely diﬀerent.)

(c) Prove that D is transitive. (You’ve probably done a problem already that is almost exactly the same as this.)

Expert Solution

Colby Messinger answered 1 year ago

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1....

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1. Prove that there is a natural number k such that n divides ((m^k) − 1).

Let D(x, y) be the predicate defined on natural numbers x and y as follows: D(x,...

Let D(x, y) be the predicate defined on natural numbers x and y as follows: D(x, y) is true whenever y divides x, otherwise it is false. Additionally, D(x, 0) is false no matter what x is (since dividing by zero is a no-no!). Let P(x) be the predicate defined on natural numbers that is true if and only if x is a prime number. 1. Write P(x) as a predicate formula involving quantifiers, logical connectives, and the predicate D(x,...

Let the cardinal number of N, the set of all natural numbers, be א0. Prove that...

Let the cardinal number of N, the set of all natural numbers, be א0. Prove that the product set N × N = {(m,n);m ∈ N,n ∈ N} has the same cardinal number. Further prove that Q+, the set of all positive rational numbers, has the cardinal number N_0. Hint: You may use the formula 2^(m−1)(2n − 1) to define a function from N × N to N, see the third example on page 214 of the textbook.

Let S={1,2,3,6} and define the relation ~ on S2 by (m,n) ~ (k,l) for m+l=n+k Show...

Let S={1,2,3,6} and define the relation ~ on S2 by (m,n) ~ (k,l) for m+l=n+k Show that it is an equivalent relation Find the number of different equivalent classes and write all of them

Suppose we define a relation on the set of natural numbers as follows. Two numbers are...

Suppose we define a relation on the set of natural numbers as follows. Two numbers are related iff they leave the same remainder when divided by 5. Is it an equivalence relation? If yes, prove it and write the equivalence classes. If no, give formal justification.

Let the natural number n have the decimal numeral 123,461,46d, where d is the units digit....

Let the natural number n have the decimal numeral 123,461,46d, where d is the units digit. Use divisibility tests to give all of the choices of d by which n is divisible. Complete parts (a) through (h) below. (a) For what value(s) of d is n divisible by 2? (Use a comma to separate answers as needed.) (b) For what value(s) of d is n divisible by 3? (Use a comma to separate answers as needed.) (c) For what value(s)...

A triangular number is the sum of the n natural numbers from 1 to n. For...

A triangular number is the sum of the n natural numbers from 1 to n. For example: The triangular number for 3 is 1 + 2 + 3 = 6 The triangular number for 7 is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 Write a program segment (using a loop), that calculates and then prints the integer n and its triangular number.

Show that |N| = |Z|, where N is the set of natural numbers and Z is...

Show that |N| = |Z|, where N is the set of natural numbers and Z is the set of all integers.

Let D be a division ring, and let M be a right D-module. Recall that a...

Let D be a division ring, and let M be a right D-module. Recall that a subset S ⊂ M is linearly independent (with respect to D) if for any finite subset T ⊂ S, and elements at ∈ D for t ∈ T, if sum of tat = 0, then all the at = 0. (a) If S ⊂ M is linearly independent, show that there exists a maximal linearly independent subset U of M that contains S, and...

2. Define a relation R on pairs of real numbers as follows: (a, b)R(c, d) iff...

2. Define a relation R on pairs of real numbers as follows: (a, b)R(c, d) iff either a < c or both a = c and b ≤ d. Is R a partial order? Why or why not? If R is a partial order, draw a diagram of some of its elements. 3. Define a relation R on integers as follows: mRn iff m + n is even. Is R a partial order? Why or why not? If R is...

Question