27. Prove that the binary relation on sets defined by X- Y if, and only if, card

Question

27. Prove that the binary relation on sets defined by X- Y if, and only if, card(CX) card (Y) is an equivalence relation. 28. Prove the Schröder-Bernstein Theorem. 29. Give a recursive definition of the relation is equal to on N N using the operator s 30. Give a recursive definition of the relation greater than on N x N using the successor 31. Give a recursive definition of the set of points [m, n] that lie on the line n 3m in 32. Give a recursive definition of the set of points [m, n] that lie on or under the line n 3m 33) Give a recursive definition of the operation of multiplication of natural numbers using 34. Give a recursive definition of the predecessor operation operator s. N x N. Use s as the operator in the definition. in N x N. Use s as the operator in the definition. the operations s and addition. pred(n)n-1 otherwise

Explanation / Answer

17. Let EZ be the set of even integers. Consider the map g : N EZ defined by:

g(n) = n if n is even

n 1 if n is odd

we can claim that g is a one to one correspondence. If g(n) = g(m) then either g(n) = g(m) 0 or g(n) = g(m) < 0. From the definition of g, it is clear that if g(k) 0 then k = g(k). So in that case: n = g(n) = g(m) = m. On the other hand, if g(k) < 0 then g(k) = k 1, so in that case:

n 1 = g(n) = g(m) = m 1

from which n = m also follows. Thus g is one to one. Now consider an arbitrary even integer z. If z 0, then z = g(z). On the other hand, if z < 0 then z = g(z + 1). So g is also onto.

12) Equivalence relations are the relations which are reflexive,symmetric and transitive.

Suppose there are 2 relations: x<y and x<z

by above 2 relations we can conclude that x<z which means less than function (LT) is transitive.

But we can't say that x<x so it is not reflexive also we can't conclude that y<x so not following symmetric rule also.

Therefore less than (LT) is not equivalence.

33)

Let +denote addition.

The binary operation × is recursively defined on N as follows:

m,nN:{m×0 =0

m×(n+1)=m×n+m

This operation is called multiplication.

Equivalently, multiplication can be defined as:

m,nN:m×n:=+nm

where +nm denotes the nnth power of mm under ++.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.