Relations

A tuple is an ordered list of items. A tuple with two items is called a pair, and a tuple with three items is called a triple.

The Cartesian product of two sets and , denoted (or ) is the set of all ordered pairs where and .

(see set builder notation)

(see if and only if)

In the most general form, a relation over sets may or may not hold between respective members of each set.

Formally, a relation over sets is a set of tuples of length , where every . This set of tuples is a subset of the Cartesian product of every set: .

We say holds for values (where ) if and only if the tuple .

A binary relation over two sets may or may not hold between respective members of each set.

Formally, a relation between two sets and is a set of ordered pairs. This set of pairs is a subset of the Cartesian product of and : , and it follows that (power set).

We say holds for values (where ) if and only if , and we write .

The relation "equals" over would be set:

and we say two numbers are equal (, ) if and only if

The relation "less than or equal to" over would be the set:

and we say two numbers are less than or equal to each other (, ) if and only if .

An example to show that and :

Given sets:

some example relations are:

All the predicate/functions on sets can be applied to relations

1. The relation from people to cars in which the people fix cars of a model they own (term)
2. The relation form people to cars in which the people fix cars that they do not own (term)
3. Everyone who fixes a car owns one of that car (WFF)

A homogeneous binary relation is a special case of a heterogeneous binary relation (which we just called "binary relation"). Instead of the relation being over two sets and , we have and the relation is only over one distinct set.

For a binary relation, the domain is all the first elements in the pairs of the relation. The range is all the second elements in the pairs of the relation.

For the relation

For the relation

1. People who own cars
2. Cars of people who both own and fix the car
3. Everyone who fixes a car fixes a car fixes at least one car that they don't own

\op{dom}(\text{fix}) & \subseteq \op{dom}(\text{fix} - \text{own}) \
\op{dom}(\text{fix}) & = \op{dom}(\text{fix} - \text{own}) \
\end

For two relations and :

Domain properties:

Range properties (nearly identical):

For a binary relation , its inverse relation is the relation created by reversing the order of elements of the pairs of , and we write

Think about inverse functions. We switch the and around, which is just switching the domain and range.

Pretty self evident

The identity relation over a set , is a unary relation written as , which is the paring of every element in with itself.

For three sets , , and , and two binary relations on them: and , the relational composition of and is the relation containing the pairs , such that there is a , and and , and we say " followed by ", written as .

Think about function composition: . Using our notation we would write , which is backwards, but it is "g followed by f", where we are applying first and then after.

For , , :

1. Assosiative:
2. Inverse distributive:
3. Domain identity:
4. Range identity:
5. Identity: ,

I was confused about why it was a subset. Given , show that is not valid.

Domains:

For sets where , and relation , the relational image of through denoted by is the set of elements that are in the second element of a pair in whose first elements are in .

Think about this almost like indexing a hashmap/dictionary.

Domain restriction retains only the pairs whose first elements are part of a set.
Range restriction retains only the pairs whose second elements are part of a set.
Domain subtraction retains the pairs whose first elements are not part of a set.
Range subtraction retains the pairs whose second elements are not part of a set.

For and :

Relational overriding allows us to "update" a relation with another relation where the pairs of are added to the relation and any pairs in with the same element of pairs in are eliminated.

For , :

For :

1. Idempotent:
2. Associative: