4. Ordered Pairs, Cartesian products, Graphical Relations Lists, and Strings

Pair Axiom

Suppose that X and Y are sets. Then there is a set whose elements are exactly X and Y.

This is the unordered pair of X and Y {X,Y}

Define : Ordered Pair

Suppose that X and Y are sets. Suppose that x,x’∈X and y,y’∈Y are elements.

Then an ordered pair (x,y) contains x and y in that order.

Two ordered pairs (x,y) and (x’,y’) are equal if and only if x=x’ and y=y’

(x,y) is an ordered pair, then x is the first entry and y is the second entry.

Ordered Pair Axiom

Suppose that X and Y are sets. Suppose that x∈X and y∈Y. Then the ordered pair (x,y) exists.

Definition: Cartesian product

Suppose that X and Y are sets. Then the collection of all ordered pairs with first entry from X and second entry from Y is

X x Y ={(x,y)|x∈X,y∈Y)

is called the Cartesian product of X and Y.

Axiom - Cartesian product Set

Suppose that X and Y are sets. Then the Cartesian product X x Y is a set.

Sketch a proof that [|m|] x[|n|] has cardinality m x n

What is the domain for add and sub of natural numbers and multiplication

Gives functions from N² to N

Suppose that X is a set. Show that X is a set. Show that X x ∅ = ∅ x X = ∅

Define : A relation R from X to Y

A relation R from X to Y consists of the following

• A set X, called the domain

• A set Y, called the codomain

• A subset of X x Y

Example 4.13

What is xRy

if X=Y

What is the empty relation?

What is the universal relation?

When X=Y then what set gives the identity relation on Y?

Definition:- Graphical Relation

Suppose that X and Y are sets. A relation G from X to Y is graphical if for ever y x∈ X there is exactly one y∈Y so that xGy: that is, so that (x, y) lies in G.

Function Defintion

A function f : X → Y is a relation G, from X to Y , which is graphical. As a bit of notation, if xGy then we write f(x) = y.

List definition

Suppose that A is a set. Suppose that n is a natural number. A list L is a function L: 􏰁n􏰂 → A. We call n the length of the list L. We also say that the elements of L are taken from A.

empty string definition

Over any alphabet A there is a unique string εA of length zero; this is called the empty string.

Binary Strings definition

Suppose that B = {0, 1} is our alphabet. We call the elements of B bits. Strings over B are called binary strings.