Teeradaj Racharak A log of everyday life

Unless (Mathematical Logic)

X unless Y

The simple way to interpret this statement is as

  • IF not X THEN Y; or
  • IF not Y THEN X

Example I will go to the park unless I stay home.

This means I will go to the park if I do not stay home. Precisely speaking,

  • IF not home THEN park; or
  • IF not park THEN HOME.

Reference

Skolem Normal Form (Mathematical Logic)

In mathematical logic, reducing to skolem normal form is a method for removing existential quantifiers from formal logic statements – often performed as the first step in an automated theorem prover.

A formula of first-order logic is in skolem normal form if it is in prenex normal form with only universal first-order quantifiers. The resulting skolem form is not necessarily equivalent to the original one. It only preserves satisfiability, i.e. it is satisfiable if and only if the original one is satisfiable.

References

Ordinal Number (Set Theory)

In set theory, an ordinal number (or ordinal) is a generalisation of the natural number that is used to describe a way to arrange a collection of objects in order - one after another. Put it in another way, ordinal numbers are the labels needed to arrange collections of objects in order.

For finite collections of objects, ordinal numbers are just counting numbers. On the other hand, a more generalised concept called well-ordering is introduced for infinite collections.

Every ordinal number is either zero, or a successor ordinal, or a limit ordinal. For example, 0, 1, 2, …, \omega, \omega + 1, \omega is a limit ordinal because, for any smaller ordinal, there is another ordinal larger than it, but still less than \omega. Also, 1, 2, … and \omega + 1 are successor ordinals.

Ordinals are distinct from cardinal numbers, which are useful for saying how many objects are in a collection. For finite sets, these two notions are not apparently different; however, different infinite ordinals may associate with the same cardinal.

Von Neumann Definition of Ordinals

The standard definition, suggested by John von Neumann, is: each ordinal is the well-ordered set of all smaller ordinals, in symbols x = [0, x). Formally,

A set S is an ordinal if and only if S is strictly well-ordered w.r.t. set membership and every element of S is also a subset of S.

Well-order

A well-order (or well-order relation) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. The set S together with the well-order relation is called a well-ordered set.

Every non-empty well-ordered set has a least element. Every element s of a well-ordered set, except a possible greatest element, has a unique successor. There may be elements besides the least element which have no predecessor. In a well-ordered set S, every subset T which has an upper bound has a least upper bound, i.e. the least element of the subset of all upper bounds of T in S. Furthermore, every well-ordered set is uniquely order isomorphic to a unique ordinal number.

References

Non-decreasing vs Non-increasing (Definition)

Non-decreasing Function

A function f(x) is said to be non-decreasing on an interval I if f(b) >= f(a) for all b > a, where a, b \in I.

Non-increasing Function

A function f(x) is said to be non-increasing on an interval I if f(b) <= f(a) for all b > a, where a, b \in I.

References

Cardinal Number (Set Theory)

In set theory, cardinal numbers (or cardinal) are a generalisation of the natural number used to measure the cardinality (size) of sets. On the one hand, the cardinality of a finite set is a natural number. On the other hand, the transfinite cardinal numbers describe the sizes of infinite sets.

A fundamental theorem, by Georg Cantor, shows that it is possible for infinite sets to have different cardinalities. In particular, the cardinality of the set of real numbers is greater than the one of the set of natural numbers. It is also possible that a proper subset of an infinite set to have the same cardinality as the original set. This cannot happen with proper subsets of finite sets.

References