Logic & set theory

Context of a line

The collection of all assumptions that have this line in their scope

When is a formula valid

A formula at some line in a derivation is valid on this, and all lines below it, until the scope of on eof the assumptions ends.

When is a relation reflexive?

A_x[x element of A : xRx]

When is a relation symmetric?

A_x,y[x, y elemnt of A : xRy => yRx]

When is a relation transitive?

A_x,y,z[x, y, z element of A : (xRy and yRz) => xRz]

Relation R is an equivalence relation if and only if:

R is reflexive, symmetric and transitive

The relation R is a mapping when..

x element of A relates to exactly one y element of B

Mapping F is a surjection when

every b element of B has at least one incoming arrow

Mapping F is an injection when

every b element of B has at most one incoming arrow

Mapping F is a bijection when

every b element of B has exactly one incoming arrow

A reflexive ordering is

• reflexixive

• antisymmetric

• transitive

An irreflexive ordering is

• irreflexive

• strictly antisyme

Direct succesors are

two elements with no others elements of the ordering between them

x an d y are comparable if

xRy or yRx or x=y

an ordering is linear when

every two elements are comparable

image