Question

In: Advanced Math

Define d to be the set of all pairs (x,y) of natural numbers such that x...

Define d to be the set of all pairs (x,y) of natural numbers such that x divides y. Show that N is partially ordered by d. Define d analogously on Z. Is then d also a partial order on Z?

Solutions

Expert Solution

Given

So, is a relation over the set of all natural numbers. We have to show that is partially ordered by , that is, is a partial order relation on the set .

1. Every number divides itself, so

Hence the relation d is reflexive.

2. Let

that is, a divides b, and, b divides c, that is

Clearly, this implies that a divides c

Thus,

Therefore the relation d is transitive.

3. Now, let

That is, a divides b, and, b divides a. As a,b are natural numbers, this is only possible when they are equal. Hence

Therefore, the relation is antisymmetric.

Thus, from 1,2, and 3, we can say that is a partial order relation on .

However, this does not hold true when the underlying set changes to , the set of all integers. In this case, antisymmetry fails, because we can have numbers such as:-

such that

and

but clearly,

Hence, d fails to be a partial order on Z.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

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,...

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.

Suppose (X, dX) and (Y, dY ) are metric spaces. Define d : (X ×Y )×(X...

Suppose (X, dX) and (Y, dY ) are metric spaces. Define d : (X ×Y )×(X × Y ) → R by d((x, y),(a, b)) = dX(x, a) + dY (y, b). Prove d is a metric on X × Y .

Let S be the set of all ordered pairs of real numbers. Deﬁne scalar multiplication and...

Let S be the set of all ordered pairs of real numbers. Deﬁne scalar multiplication and addition on S by: α(x1,x2)=(αx1,αx2) (x1,x2)⊕(y1,y2)=(x1 +y1,0) We use the symbol⊕to denote the addition operation for this system in order to avoid confusion with the usual addition x+y of row vectors. Show that S, together with the ordinary scalar multiplication and the addition operation⊕, is not a vector space. Test ALL of the eight axioms and report which axioms fail to hold.

Let V be the set of all ordered pairs of real numbers. Consider the following addition...

Let V be the set of all ordered pairs of real numbers. Consider the following addition and scalar multiplication operations V. Let u = (u1, u2) and v = (v1, v2). Show that V is not a vector space. • u ⊕ v = (u1 + v1 + 1, u2 + v2 + 1 ) • ku = (ku1 + k − 1, ku2 + k − 1) 1)Show that the zero vector is 0 = (−1, −1). 2)Find the...

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 be the set of all natural numbers that are describable in English words using...

Let S be the set of all natural numbers that are describable in English words using no more than 50 characters (so, 240 is in S since we can describe it as “two hundred forty”, which requires fewer than 50 characters). Assuming that we are allowed to use only the 27 standard characters (the 26 letters of the alphabet and the space character), show that there are only finitely many numbers contained in S. (In fact, perhaps you can show...

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...

From a set of all eight-digit natural numbers, where only the digits from the set {0,1,...

From a set of all eight-digit natural numbers, where only the digits from the set {0,1, 3, 5, 7, 9} are present in decimal notation. we draw one. Calculate the probability of the event that the sum of digits of the drawn number is equal to 3.

Find all pairs of x and y for both of the following two equalities hold: x...

Find all pairs of x and y for both of the following two equalities hold: x + y = 10 xy - 4

Subjects