This is my first time posting here, so let know if I'm doing anything incorrect. This is possibly a really stupid question.


So I'm walking through a book called "The formal semantics of Programming Languages" as I'm told it helps introduce important concepts for designing programming languages. And I'm not entirely sure how to address the questions in the book, since I don't really have a strong maths background

The Question

(a, b) = (a', b') ⇔ a = a' & b = b’

Prove the property above hold of the suggests representation of ordered pairs. For the sets X & Y, their product is the set

X x Y = {(a, b) | a ∈ X & b ∈ Y }

the set of ordered pairs of elements with the first from X and the second from Y .

A Triple (a, b, c) is the set (a, (b, c)), and the product X x Y x Z is the set of triples

{(x, y, z) | x ∈ X & y ∈ Y & z ∈ Z }

More generally X1 x X2 x … x Xn consists of the set of n-tuples

(x1, x2, …, xn) = (x1, (x2, (x3, ….)))

My Problem

I don't really have any point of reference of how to address this question, since I'm going through this by myself I don't really have a lecture or classmates to ask the kind of questions.

My Interpretation of this

I think I need to state examples of why the example checks out, so I may need to prove the following.

A two ordered pairs are equal, when values in the same index are equal.

I've never written a proof before so I don't really know how to best to go about it...

Possibly solution?

I know that an ordered pair can be represented as a set like this

(a, b) = {{a}, {a, b}}

I think this might be useful for proving equality as you can probably use the set value (on the right) to reconstruct the original pair (on the left). Kind of like a means of casting it into a different data structure without losing information about the original shape. I don't know this is if this true or not, but there are examples of transforming pairs to sets of this structure in the book i’m following.

If you made the two pairs in the original example sets like so, and assigned them to the values X & Y

X = (a, b) = {{a}, {a, b}} Y = (a', b') = {{a'}, {a', b'}}

Then if the following is true, then the initial example is true?

Z1 = X ∩ Y Z2 = X ∪ Y (Z1 = X & Z1 = Y) ⇔ (Z2 = X & Z2 = Y) (X = Y) ⇔ (Z1 = Z2)

So with real values

X := {{1}, {1, 2}}; // the pair (1, 2)
Y := {{1}, {1, 2}}; // the pair (1, 2)

Z1 := X ∩ Y; 
Z2 := X ∪ Y;

assert(Z1 = Z2)

This might prove that X & Y are equal?

  • 1
    $\begingroup$ Continue what you are doing to calculate Z1 and Z2. Use those results for the next step or two. There is the special case for (x,y) when x = y. $\endgroup$ Sep 17 '17 at 3:40

(a,b) = (r,s) implies a = r, b = s
{a} = $\cap$(a,b) = $\cap$(r,s) = {r}; a = r
{a,b} = $\cup$(a,b) = $\cup$(r,s) = {r,s} = {a,s}
b = a or b = s
if b = a: {a} = {a,s}; s = a = b


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.