Sequence

A sequence is obtained when we list some objects

For example:

• 1, 2, 3, 4, 1, 3
• a, c, u,w, a, a
• 9, 8, 7, 4, 2.

The length of a sequence is the number of elements, including repetitions, that appear in it.

Tuple

Tuples are just finite sequences.

A k-tuple is a tuple of length k.

Tuples are written within parentheses.

For example:

• (1, 2, 3, 4)
• (a, c, u,w)

Cross products

Definition

The cross product (or Cartesian product) of A and B, written A × B, is the set of all pairs (a, b) such that a \(\in\) A and b \(\in\) B.

For example

• For A = {1, 2} and B = {1, 2, 3}, A × B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}.
• For A = {1, 2} and B = \(\mathbb{N}\), A × B = {(1,0), (2,0), (1,1), (2,1), (1,2), (2,2), (1,3), (2,3), …}.

Definition

The cross product of \(A_1\), . . ., \(A_k\) , written \(A_1\) × . . . × \(A_k\) , is the set of all k-tuples (\(A_1\), . . . , \(A_k\) ) such that \(a_1\) \(\in\) \(A_1\), …, \(a_k\) \(\in\) \(A_k\).

If all \(A_i\) are the same set A, then we write \(A^k\).

For instance, let us can compute the Cross product of A = {0, 1} to itself three times, that is A × A × A.

Geometric meaning

When A = \(\mathbb{Z}\) then

• \(A^2\) consists of points in the plane whose coordinates are integer numbers
• \(A^3\) consists of points in the the space whose coordinates are integer numbers
• \(A^2\) consists of points in the k-dimensional space whose coordinates are integer numbers

Relations

Definition

A relation of arity k on the set A is any subset of \(A^k\). Sometimes these are called k-place relations or relations with k-arguments or parameters.

Let R be a relation of arity k on set A.

• When k = 1, then these relations are called unary relations. Unary relations are simply subsets of A.
• When k = 2, then such relations are called binary relations.
• When k = 3, then such relations are called ternary relations.

Here are examples of relations on A = {0, 1, 2, 3, 4}:

• unary relation
  • {0, 2, 4}
  • {0, 4}
  • {1, 2, 3}
• binary relation
  • {(0,1), (1,2), (2,3), (3,4)}
  • {(0,4), (4,0), (2,4)}
  • {(0,0), (1,1), (2,2), (3,3), (4,4)}
• ternary relation
  • {(0,1,0), (1,2,1), (2,3,2), (3,4,3)}
  • {(0,0,4), (0,4,0), (1,2,4), (1,1,1)}
  • {(0,0,0), (1,1,1), (2,2,2), (3,3,3), (4,4,4)}

Binary Relations

Let R be a binary relation on A. We give the following directed graph representation of R:

• The vertex set V of the digraph is A
• The edges set E of the digraph is R

Reflexive relations

Definition

A binary relation R on set A is a reflexive relation if (x,x) \(\in\) R for all x \(\in\) A.

For example

• On set \(\mathbb{Z}\): R = {(x,y) \(\vert\) \(\vert\)x\(\vert\) = \(\vert\)y\(\vert\)}.
• On set \(\mathbb{N}\): Div = {(x,y) \(\vert\) x is a factor of y}.
• On \(\mathbb{Z}\): mod(p) = {(n,m) \(\vert\) n − m is divided by p}
• Let G be an undirected graph. The relation {(x,y) \(\vert\) x and y are connected}
• On set \(\mathbb{N}\) the binary relation S = {(x,y) \(\vert\) x + 1 = y} is not a reflexive relation.

Symmetric relations

Definition

A binary relation R on A is a symmetric relation if for all (x,y) \(\in\) R it must be the case that (y,x) \(\in\) R.

For example

• On set \(\mathbb{Z}\): R = {(x,y) \(\vert\) \(\vert\)x\(\vert\) = \(\vert\)y\(\vert\)}.
• The relation mod(p) on Z.
• Let A be a set. Take any two elements a, b \(\in\) A. The relation R = {(a,b),(b,a)} is a symmetric relation.
• The empty relation.

Transitive relations

A binary relation R on A is a transitive relation if whenever (x,y) \(\in\) R and (y,z) \(\in\) R it must be the case that (x,z) \(\in\) R.

For example

• On set \(\mathbb{Z}\): R = {(x,y) \(\vert\) \(\vert\)x\(\vert\) = \(\vert\)y\(\vert\)}.
• On set \(\mathbb{N}\): R = {(x,y) \(\vert\) x is a factor of y}.
• R = {(a,b),(b,a),(a,a),(b,b)}, where a, b \(\in\) A.
• mod(p) on \(\mathbb{Z}\) and Connect(G) on graph G.
• The empty relation.

Antisymmetric relations

Definition

A binary relation R on set A is an antisymmetric relation if whenever (x,y) \(\in\) R and (y,x) \(\in\) R it must be the case that x = y.

For example

• On set \(\mathbb{Z}\): R = {(x,y) \(\vert\) x \(\leq\) y}.
• On set \(\mathbb{N}\): R = {(x,y) \(\vert\) x is a factor of y}.
• The empty relation.
• Let A be a set. Take elements \(a_1\), \(b_1\), …, \(a_k\), \(b_k\) \(\in\) A all distinct from each other. The relation: R = {(\(a_1\), \(b_1\)), … ,(\(a_k\), \(b_k\))}.

Equivalence relations

Definition

A binary relation E on A is an equivalence relation if E is reflexive, symmetric, and transitive.

For an equivalence relation E, if (x,y) \(\in\) E then we say that x and y are equivalent (or E-equivalent).

For example

• mod (p) relation on \(\mathbb{Z}\).
• Connect(G) relation on graph G

Equivalence class

Definition

Let E be an equivalence relation on A. For a \(\in\) A, define the set [a] as follows: [a] = {x \(\vert\) x \(\in\) A and (x,a) \(\in\) E}. The set [a] is called the equivalence class of a.

Properties

Property 1. Every element of the set A belongs to some equivalence class.

Property 2. For any two equivalence classes [a] and [b] we have either [a] \(\cap\) [b] = \(\varnothing\) (i.e. no overlap) or [a] = [b].