tuples

Tuple

Let

I

be an index set, and

S

a set then we say that a function

t : I \to S

is a tuple,

Empty Tuple

Suppose

t : I \to S

is a tuple such that

I = \emptyset

then

t

is said to be the empty tuple and is notated by

()

Tuple at an Index

Suppose that

t

is a tuple and

i \in dom (t)

, then we define that the tuple's value at index $i$ as

t (i)

Tuple Subscript Notation

Suppose that

t

is a tuple, then we define

t_{i}

to be

t

at index

i

Ordered Tuple Notation

Suppose that the index set has some natural ordering, then the notation

(t_{i_{1}}, t_{i_{2}}, \dots)

Finite Tuple

A finite tuple is a tuple with a finite index set

Integer Indexed Tuple

A integer indexed tuple is a tuple whose index set equals

{a, \dots, b}

for some

a, b \in Z

or is some

I \subseteq Z

Note that a integer indexed tuple is represented using ordered tuple notation using $(a_{1}, a_{2}, \dots)$ . When it's finite we get $(a_{- 2}, a_{- 1}, a_{0}, a_{1}, a_{2}, a_{3}, a_{4})$

When an Integer Indexed Tuple is Empty

Suppose that

i > j \in Z

then

(a_{i}, \dots, a_{j}) = ()

By definition we can see that it's index set is

{i, \dots, j}

which is equal to

\emptyset

and therefore it is the empty tuple.

Finite Tuple Equality

We define two

n

tuples

(x_{1}, x_{2}, . . ., x_{n})

and

(y_{1}, y_{1}, . . ., y_{n})

to be equal when

\forall i \in [1 \dots n], x_{i} = y_{i}

Note that finite tuples tuples are indexed starting from 1

Length

Suppose that

a = (a_{1}, a_{2}, \dots, a_{n})

then

len (a) = n

Zero Indexed Tuple

A zero indexed tuple is a tuple of the form

a = (a_{0}, a_{1}, \dots a_{m})

Length of a Zero Indexed Tuple

Suppose that

a = (a_{0}, a_{1}, \dots a_{m})

is a zero indexed tuple, then

len (a) = m + 1

Converting from Regular to Zero Indexing

Let

a

be a finite tuple and suppose

len (a) = n

, let

r

a

but indexed regularly, and let

z

a

but using zero indexing, then for all

i \in [1 . . . n], r_{i} = z_{i - 1}

Reverse of a Finite Tuple

Suppose that

a = (a_{1}, a_{2}, \dots, a_{n})

, is an

n

tuple, then we define

rev (a) : = (a_{n}, \dots, a_{1})

Reverse Cancels

For any

n

tuple

a

rev (rev (a)) = a

Concatenation

Suppose that

a = (a_{1}, \dots, a_{n})

and

b = (b_{1}, \dots, b_{m})

are finite tuples, then

concat (a, b) = (a_{1}, \dots a_{n}, b_{1}, \dots, b_{m})

Sorted in Ascending Order

Suppose that

a = (a_{1}, a_{2}, \dots, a_{n}) \in R^{n}

, then we say that

a

is sorted in ascending order when for any

i \in [1 \dots n - 1]

a_{i} \leq a_{i + 1}

Sorted in Strictly Ascending Order

Suppose that

a = (a_{1}, a_{2}, \dots, a_{n}) \in R^{n}

, then we say that

a

is sorted in strictly ascending order when

b o p_h o l d s (<, a)

A Binary Relation Holds Consecutively on a Tuple

Suppose that

⋆

is a binary operation, then we say that it holds consecutively on a tuple

a = (a_{1}, \dots, a_{n})

whenever we have

a_{i} ⋆ a_{i + 1}

for each

i \in [1, \dots, n - 1]

, we also define the predicate

b o p_h o l d s

as follows:

b o p_h o l d s (⋆, a) = T

iff the above property holds true.

Sorted Tuple Predicate

Suppose that

a \in R^{n}

then define the

s o r t e d_a s c : R^{n} \to {T, F}

such that

s o r t e d_a s c (a) = b o p_h o l d s (\leq, a)

sorted_asc Holds iff It is Sorted in Ascending Order

s o r t e d_a s c (a) = T

iff

a

is sorted in ascending order

Sorted in Strictly Ascending order Predicate

Suppose that

a \in R^{n}

then we define

s t r i c t_a s c_s o r t e d (a) = b o p_h o l d s (<, a)

Set of a Tuple

Suppose that

a = (a_{1}, \dots, a_{n})

is a tuple, then we define the function

set (a) = {a_{i} : i \in [1, \dots, n]}

Strictly Ascending Sorting Function

Suppose that

a \in R^{n}

then we define the function

s t r i c t_a s c_s o r t : R^{n} \to R^{n}

such that if

s = s t r i c t_a s c_s o r t (a)

then we have

s t r i c t_a s c_s o r t e d (s) = T

such that

| a | = | s |

and

set (a) = set (s)

Intersection of Two Sorted Tuples

Suppose that

a, b \in R^{n}

then

a \cap b

is defined as the tuple

s

such that

s = s t r i c t_a s c_s o r t (concat (a, b))

using the sorting function and concatenation

Ascending Tuple

Show that

(1, 2, 3, 4, 100)

is an ascending

n

tuple

Sorted in Descending Order

Suppose that

a = (a_{1}, a_{2}, \dots, a_{n}) \in R^{n}

, then we say that

a

is sorted in descending order when for any

i \in [1 \dots n - 1]

a_{i} \geq a_{i + 1}

Descending Tuple

Show that

(8, 5, 3, 1, 0)

is a descending

n

tuple

The reverse of Ascending is Descending

Suppose that

a

is a finite tuple sorted in ascending order, then

rev (a)

is sorted in descending order.

Inversion

Suppose that

(a_{1}, a_{2}, \dots, a_{n}) \in R^{n}

, then an inversion is a tuple

i, j \in [1 \dots n] \times [1 \dots n]

such that

i < j

but

a_{i} > a_{j}

Given the tuple $a : = (8, 9, 10, 11, 3)$ then we can see that $(1, 5)$ is an inversion because $1 < 5$ but $8 > 3$

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)