Content

Relations

The set of all predicates (or relations) of type (A) is the power set ℘(A) = 2A. For any cardinalities of A, it is in fact true that |2A| = 2|A|. These predicates of ℘(A) have the form:

ρ ⊆ A

Particularly, the set of all binary predicates (or binary relations) of type (A×B) is the power set ℘(A×B). These predicates have the form:

ρ ⊆ A × B

Properties of Relations

Relations (or binary predicates) can formally be classified with these properties.

The relation ~ ⊆ M×M is:
reflexive
if ∀a∈M a ~ a
⇔ Δ⊆~
irreflexive
if ∀a∈M ¬(a ~ a)
⇔ Δ∩~=∅
partimreflexive
if it is neither reflexive nor irreflexive.
symmetric
if ∀a,b∈M (a ~ b ⇒ b ~ a)
⇔ ~ = ~-1
asymmetric
if ∀a,b∈M (a ~ b ⇒ ¬(b ~ a)).
partimsymmetric
if it is neither symmetric nor asymmetric.
anti-symmetric
if ∀a,b∈M (a ~ b ∧ b ~ a ⇒ a = b). Then it is partimsymmetric as well.
transitive
if ∀a,b,c∈M (a ~ b ∧ b ~ c ⇒ a ~ c).
Euclidean
if ∀a,b,c∈M (a ~ c ∧ b ~ c ⇒ a ~ b), sometimes also formulated as ∀a,b,c∈M (a ~ b ∧ a ~ c ⇒ b ~ c), instead.
equivalence
if it is reflexive, symmetric, and transitive.
(partial) order
if it is reflexive, anti-symmetric, and transitive.
strict order
if it is irreflexive, and transitive (⇒ ~ is anti-symmetric).
total order
if it is an order and connex.
total strict order
if it is a strict order and connex.
connex/linear/definite/total
if ∀a,b∈M (a = b ∨ a ~ b ∨ b ~ a).
(partial) quasi-order
if it is reflexive, and transitive.
Then ~ defines a (partial) order on M/≡ by passing to the quotient, per a≡b :⇔ a~b∧b~a.
dense
∀a,b∈M (a ~ b ⇒ ∃z∈M (a ~ z ∧ z ~ b)).
weakly connected
∀a,b,c∈M (a ~ b ∧ a ~ c ⇒ (b = c ∨ b ~ c ∨ c ~ b)).
weak directed, directly confluent
∀a,b,c∈M (a ~ b ∧ a ~ c ⇒ ∃w∈M (b ~ w ∧ c ~ w)).
confluent?
∀a,b∈M (a ~ b ⇒ ∃w∈M (a ~ w ∧ b ~ w)).
With the diagonal Δ := {(a,a) ¦ a∈M}.

Orders ≤ ⊆ M×M and strict orders < ⊆ M×M bijectively correspond to each other per

 

Let ≤ ⊆ M×M be a (partial) order.
lower bound
s∈M is a lower bound of U⊆M if ∀x∈U s≤x
infimum
inf U := the greatest lower bound of U⊆M
minimum
m∈M is the minimum of U⊆M if m=inf U ∈ U
⇔ m∈U ∧ ∀x∈U m≤x
minimal element
x∈M is a minimal element of M if ¬∃y∈M y≠x ∧ y≤x
well-ordered
(M,≤) is well-ordered if ∀∅≠U⊆M U has a minimum.
lattice
(M,≤) is a lattice if ∀{a,b}⊆M ∃sup{a,b} ∧ ∃inf{a,b}
⇒
complete order
(M,≤) is completely ordered if M has a minimum and ∀(an)⊆M monotonic ascending chain, i.e. ∀n an≤an+1 ∃sup (an)∈M.
Noetherian
(M,≤) is Noetherian if every ascending chain eventually becomes stationary, i.e. ∀(an)⊆M (∀n an≤an+1) ⇒ ∃n∀k≥0 an=an+k.
Artinian
(M,≤) is Artinian if every descending chain eventually becomes stationary, i.e. ∀(an)⊆M (∀n an≥an+1) ⇒ ∃n∀k≥0 an=an+k.

Dual to the notions of lower bound, infimum, minimum, and minimal element concerning ≤ are the notions upper bound, supremum, maximum, maximal element concerning the converse order ≥.

In order to discuss how predicates and functions correspond, it is useful to define further properties of relations like the following.

The relation ~ ⊆ A×B is:
left-total
if ∀x∈A∃y∈B x ~ y. Also called "serial" which is a kind of existence presupposition in ∘R.
right-total
if ∀y∈B∃x∈A x ~ y.
left-unique
if ∀y∈B ∀x1,x2∈A (x1 ~ y ∧ x2 ~ y ⇒ x1=x2).
right-unique
if ∀x∈A ∀y1,y2∈B (x ~ y1 ∧ x ~ y2 ⇒ y1=y2).
functional
if it is left-total and right-unique.

"Implications"

Let ρ ⊆ A × B be a relation. Then

Closures

Note that relations form a lattice.

Let ρ ⊆ M×M be a relation. Then the following relations exist and are unique:
reflexive closure
⋂R⊇ρ ∧ R reflexive R = ρ ∪ Δ
transitive closure
ρ+ := ⋂R⊇ρ ∧ R transitive R = {(a,b)∈M×M ¦ ∃n∈N∖{0} ∃{a=a1,a2,...,an-1,an=b}⊆M ∀i∈{1,...,n} (ai,ai+1)∈ρ}

Non-characterisable in first-order logic.

reflexive, transitive closure
ρ* := ⋂R⊇ρ ∧ R reflexive and transitive R = ρ+ ∪ Δ
symmetric closure
ρs := ⋂R⊇ρ ∧ R symmetric R = ρ ∪ ρ-1
equivalence closure
ρ.... := ⋂R⊇ρ ∧ R reflexive, symmetric, and transitive R
Of course, the reflexive closure is reflexive, the transitive closure transitive, the symmetric closure symmetric, etc.

Functions

The set of all functions (or maps) of type A→B is called Map(A,B) = BA. For any cardinalities of A,B, it is in fact true that |BA| = |B||A|. These functions of Map(A,B) have the form:

f: A→B; a ↦ f(a)

Properties of Functions

A function f:A→B; a↦f(a) = apply(a1,a2,...,an) is
functional
if its corresponding relation is left-total and right-unique. This is the case if and only if
∀x∈A ∃!y∈B f(x)=y
f is then called a function. Sometimes being right-unique is also called consistent or determinant.
injective
if ∀x,y∈A (f(x)=f(y) ⇒ x=y). ⇔ ∃g:f(A)→A g∘f=idA, i.e. f has a left-inverse. A function is injective if and only if the corresponding relation is left-unique.
We denote injective functions from A to B as f:A↪B
surjective
if f(A) := {f(a)∈B ¦ a∈A} = B. ⇔ ∃g:B→A f∘g=idB, i.e. f has a right-inverse. A function is surjective if and only if the corresponding relation is right-total.
We denote surjective functions from A to B as f:A↠B
bijective
if it is both surjective and injective. This is the case if and only if there is an inverse f-1:B→A of f, i.e. f ∘ f-1 = idB ∧ f-1 ∘ f = idA.
identical, reflexive
if x=f(x)=id(x).
symmetric
if x=f(y) ⇒ y=f(x).
involutive/idempotent
if f-1=f, i.e. ∀x∈A x=f(f(x)).
In the context of magmas, there are even more notions for an operation ⋆:M×M→M which is a function and written in infix notation, here.
associative
if ∀a,b,c∈M a ⋆ (b ⋆ c) = (a ⋆ b) ⋆ c. Also called flat.
M contains one neutral element
if ∃0∈M a ⋆0 = a = 0 ⋆a.
M contains inverse elements
if ∀a∈M ∃ā∈M a ⋆ ā = 0 = ā ⋆ a.
commutative
if ∀a,b∈M a ⋆ b = b ⋆ a. Also called orderless.
definite
if f(x)=0 ⇔ x=0.
(homo-)morph for ⋆
if ∀a,b∈M f(a) ⋆ f(b) = f(a ⋆ b).
Let ≤ be a (partial) order on A, and ≤ be a (partial) order on B (sharing the same denotation for simplicity).
monontonic
f:A→B is monotonic if ∀x≤y f(x)≤f(y)
chain-continuous
Provided that (≤,A) and (≤,B) are complete partial orders, f:A→B is chain-continuous if ∀(an)⊆M monotonic ascending chain sup f(an) = f(sup an)