The set of all predicates (or relations) of type (A) is the power set ℘(A)
= 2^{A}. For any cardinalities of A, it is in fact true that |2^{A}|
= 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.
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
a<b ⇔ a≤b ∧ a≠b
a≤b ⇔ a<b ∨ a=b
This means that ≤ is the reflexive closure of <
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}
⇒
a ∩ b = the greatest c∈M such that c ≤ a and c ≤ b (infimum),
i.e. c satisfies c ≤ a, c ≤ b, ∀d∈M (d ≤ a, d ≤ b
⇒ d ≤ c)
a ≤ b ⇔ a ∩ b = a
complete order
(M,≤) is completely ordered if M has a minimum and ∀(a_{n})⊆M
monotonic ascending chain, i.e. ∀n a_{n}≤a_{n+1} ∃sup
(a_{n})∈M.
Noetherian
(M,≤) is Noetherian if every ascending chain eventually becomes
stationary, i.e. ∀(a_{n})⊆M (∀n a_{n}≤a_{n+1})
⇒ ∃n∀k≥0 a_{n}=a_{n+k}.
Artinian
(M,≤) is Artinian if every descending chain eventually becomes
stationary, i.e. ∀(a_{n})⊆M (∀n a_{n}≥a_{n+1})
⇒ ∃n∀k≥0 a_{n}=a_{n+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 ∀x_{1},x_{2}∈A (x_{1}
~ y ∧ x_{2} ~ y ⇒ x_{1}=x_{2}).
right-unique
if ∀x∈A ∀y_{1},y_{2}∈B (x ~
y_{1} ∧ x ~ y_{2} ⇒ y_{1}=y_{2}).
functional
if it is left-total and right-unique.
"Implications"
Let ρ ⊆ A × B be a relation. Then
ρ asymmetric ⇒ ρ irreflexive
ρ transitive ∧ ρ irreflexive ⇒ ρ asymmetric
ρ symmetric ⇒ (ρ Euclidean ⇔ ρ transitive)
ρ reflexive ∧ ρ Euclidean ⇔ ρ equivalence
ρ reflexive ⇒ ρ dense
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=a_{1},a_{2},...,a_{n-1},a_{n}=b}⊆M
∀i∈{1,...,n} (a_{i},a_{i+1})∈ρ}
Non-characterisable in first-order logic.
reflexive, transitive closure
ρ^{*} := ⋂_{R⊇ρ}_{ ∧ R reflexive and transitive}
R = ρ^{+} ∪ Δ
ρ^{....} := ⋂_{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) = B^{A}.
For any cardinalities of A,B, it is in fact true that |B^{A}| = |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(a_{1},a_{2},...,a_{n})
is
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=id_{A}, 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=id_{B},
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} =
id_{B} ∧ f^{-1} ∘ f = id_{A}.
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 ∀(a_{n})⊆M monotonic ascending chain sup f(a_{n})
= f(sup a_{n})
f chain-continuous ⇒ f monotonic
f monotonic ∧ (≤,A) Noetherian order ⇒ f chain-continuous