# Ordered Pairs and Operations on Sets

1. Recall that ordered pairs must have the property that (x,y) = (u,v) if and only if x = u and y = v.

a) Prove that {{x}, {x,y}} = {{u}, {u,v}} if and only if x = u and y = v. Therefore, although we know that (x,y) does not equal {x,y} , we can define the ordered pair (x,y) as the set {{x}, {x,y}}.

b) Show by an example that we cannot define the ordered triple (x, y, z) as the set {{x}, {x,y}, {x,y,z}}

2. Which of the following are binary or unary operations on the given sets? For those that are not, where do they fail?

a) x ◦ y = 1/x if x is positive S = set of all real numbers

1/(-x) if x is negative

b) x ◦ y = xy (concatenation); S = se of all finite-length strings of symbols from the set {p,q,r}

c) x ^ # = [x] where [x] denotes the greatest integer less than or equal to x; S = set of all real numbers

d) x ◦ y = min(x,); S = set of all non-negative integers

e) x ◦ y = greatest common multiple of x and y; S = set of all non-negative integers

f) x ◦ y = x + y; S = the set of Fibonacci numbers

g) x ^ # = the string that is the reverse of x; S = set of all finite-length strings of symbols from the set {p,q,r}

h) x ◦ y = x + y; S = set of all real numbers minus the set of all rational numbers

3. We have written binary operations in infix notation, where the operation symbol appears between the two operands, as in A + B. Evaluation of a complicated arithmetic expression is more efficient when the operations are written in postfix notation, where the operation symbol appears after the two operands, as in AB +. Many compilers change expressions in a computer program from infix to postfix form. One way to produce an equivalent postfix expression from an infix expression is to write the infix expression with a full set of parentheses, move each operator to replace its corresponding right parenthesis, and then eliminate all left parentheses. (Parentheses are not required in postfix notation.) Thus,

A*B + C becomes when fully parenthesized, ((A*B) + C) and the postfix notation is AB*C +.

Rewrite each of the following in postfix notation:

a. (A +B) * (C - D)

b. A ** B - C*D

c. A * C + B/(C + D*B)

See attached file for full problem description.

#### Solution Preview

1.

a) Recall that ordered pairs must have the property that (x,y) = (u,v) if and only if x = u and y = v. Prove that {{x}, {x,y}} = {{u}, {u,v}} if and only if x = u and y = v. Therefore, although we know that (x,y) does not equal {x,y} , we can define the ordered pair (x,y) as the set {{x}, {x,y}}.

Look at what happens under two conditions:

x ≠ y:

If {{x},{x,y}}= {{u},{u,v}}, then either {x}={u} and {x,y}={u,v}, OR {x}={u,v} and {x,y}={u}. The second case can't occur because if two finite sets are equal they have the same number of elements.

Therefore{x}={u}, which means that x = u. Because {x,y}={u,v}, either x = u and y = v or x = v and y = u. However, we already know that x = u, so (because we're saying that x and y are not equal), y = v.

x = y:

Again, {{x},{x,y}}= {{u},{u,v}} means that {x}={u} and {x,y}={u,v}. The first equality shows us that x = u and the second shows us that x = u and y = v or x = v and y = u. Since x = y, this means that the second equality implies that x = u and x = v or x = v and x = u. Therefore x = y = u = v.

b) Show by an example that we cannot define the ordered triple (x, y, z) as the set {{x}, {x,y}, {x,y,z}}

We want to disprove the fact that {{x}, {x,y}, {x, y, z}} = {{u}, {u,v}, {u, v, w}} if and only if x = u, y = v, and z = w.

If that fact we're true, then x = u, y = v, and z = w would imply that {{x}, {x,y}, {x, y, z}} = {{u}, {u,v}, {u, v, w}}.

But consider the case of x = 1, y ...

#### Solution Summary

This solution provides work and answers for each question in the problem set in plain text and formatted in an attached Word document.