Logic Rules

• Modus Ponens: If A then B
• Moduls Tollens: If not B then not A
• 9 Axioms of set theory from Prof. Fredric Schuller (Axiom of Extensionality, Axiom of the Regularity, Axiom of the Specification (schema), Axiom of Pairing, Axiom of Union, Axiom of Infinity, Axiom of Replacement (schema), Axiom of Power Set, Axiom of Choice) schema stands in for infinitely many axioms.

– E – E

– P – U – R – P

– I – C

– F

All of modern mathematics can be grounded without making any conceptual assumptions except for the inclusion relation (a.k.a. the epsilon relation or \(\epsilon\)–Relation) in axiomatic set theory. To this concept are add nine axioms which allow to build up the machinery for the advanced mathematics that theoretical physics uses. To formulate these axioms propositional and predicate logic provide the symbolic language we use. The nine axioms can be abbreviated as EE PURP IC F:

Basic Existence Axioms

E1: The Axiom on \(\epsilon-Relation \)

\(\forall x \forall y (x\in y) \veebar \neg (x\in y)\)

\(x\in y\) is a proposition if and only if \(x\) and \(y\) are both sets.

E2: Axiom of Existence of an Empty Set

\(\exists x \forall y: y\notin x\)

There exists a set \(x\) such that for all \(y\) it is true that \(y\) is not an element of \(x\). That is, there exists an empty set, a set that contains no elements.

Construction Axioms

P1: Axiom on Pair Sets

\(\forall x \forall y \exists m \forall u (u\in m\leftrightarrow u=x, u=y)\)

Let \(x\) and \(y\) be sets. Then there exists a set that contains as its elements precisely the sets \(x\) and \(y\). Or: For all \(x\) and for all \(y\), there exists a set \(m\), such that for all \(u\), \(u\) is an element of \(m\) if and only if \(u\) is \(x\) or \(u\) is \(y\).

U: Axiom on Union Sets

Let \(x\) be a set. Then there exists a set \(u\) whose elements are precisely the elements of the elements of \(x\).

\(\forall x \exists y \forall c (c\in y \leftrightarrow\exists z (c\in z \wedge z\in x))\)

R: Axiom of Replacement

\(\exists x\forall y \in a(\exists z A(y, z)\rightarrow\exists z\in x A(y, z) )\)

Let \(R\) be a functional relation. Let \(m\) be a set. Then the image of \(m\) under the functional relation \(R\) is again a set.

P2: Axiom on Existence of Power Sets

\(\forall \exists p \forall y (y\in p\leftrightarrow\forall z (z\in y\rightarrow z\in x))\)

Let \(m\) be a set. There exists a set denoted \(\mathbf{P}(m)\) whose elements are precisely the subsets of \(m\).

Further Existence/Construction Axioms

I: Axiom of Infinity

\(\exists m (\emptyset\in m \wedge \forall x\in m((x\cup {x}\in m)))\)

There exists a set that contains the empty set and with every of its elements \(y\) it also contains the set with the element \(y\) (or \({y}\)) as an element.

C: Axiom of Choice

\(\forall X((\forall x\in X\forall y\in X(x=y\leftrightarrow x\cap y\ne\emptyset))\rightarrow\exists z(\forall x\in X\exists ! y y\in x\cap z))\)

if you have a collection \(X\) of pairwise disjoint non-empty sets, then you get a set \(z\) which contains one element from each set in the collection. [Schuller, using different formulae: Let \(x\) be a set whose elements are non-empty and mutually disjoint, then there exists a set \(y\) which contains exactly one element of each element of \(x\).]

Non-Existence Axiom

F: Axiom of Foundation

\(x\neq\emptyset\rightarrow\exists y(y\in x\wedge y\cap x=\emptyset)\)

Every nonempty set is disjunct from one of its elements. [Schuller: Every non-empty set \(x\) contains an element \(y\) that has none of its elements in common with \(x\).]

Differential geometry works with space, and space is made of sets of points. So to study these things, we first will need to look at what sets are. But set theory itself cannot be the absolute foundation. Try to define a set, for example as a collection of elements, we would need some other concepts (which presumably we cannot assume at this foundational level); for example, how do we define a “collection” and an “element”? The way we will get around this is by constructing set theory on the basis of axioms rather than on such definitions. But in order to formulate these axioms, we first need a language, in this case, of propositional and predicate logic. [Note, while it may seem that Schuller will define the terms or concepts in propositional and predicate logic, he in fact uses a logical operator, the biconditional, which is understood merely in terms of its truth functionality, and what is being biconditionally combined are most basically just mechanically operable symbols.]

What could the first definition be? For a definition you need notions that you already have in order to define a new notion. But if you do not have any notion yet, how would you start? The trick is to start axiomatically, and so we will have to write out axiomatic set theory. But that then raises the question, in what language would you possibly do that? So, actually before we come to set theory, we need another building block down here, and that would be logic. And we will deal with propositional and predicate logic first. That will define our language. Then we will be able to write down the axioms of set theory. (quoting Schuller, 0.08.30 - 0.09.15)

Relations over a set

If \(X = Y\) then we simply say that the binary relation is over \(X\), or that is an endorelation over \(X\). In CS, such a relation is called a homogeneous (binary) relation. Some types of endorelations are widely studied in graph theory, where they are known simple as directed graphs permitting loops.

The set of binary relations \(\mathbf{\mbox{Rel}}(X)\) on a set \(X\) is the set \(2^{X\times X}\) which is a Boolean algebra augmented with the inovlution of mapping of a relation to its inverse relation.

Some important properties that a binary relation \(R\) over as set \(X\) may have are:

• reflexive: \(\forall x\in X\) it holds that \(xRx\). For example "greater than or equal to" (\(\ge\)) is a reflexive relation but "greater than" (>) is not.
• irreflexive (or strict): \(\forall x\in X\) it holds that not \(xRx\). For example, \(>\) is an irreflexive relation, but \(\ge\) is not.
• coreflexive relation: \(\forall x\wedge y\in X\) it holds that if \(xRy\) then \(x=y\). An example of a coreflexive relation is the relation on integers in which each odd number is related to itself and there are no other relations. The equality relation is the only example of a both reflexive and coreflexive relation, and any coreflexive relation is a subset of teh identity relation.
• symmetric: \(\forall x\wedge y\in X\) it holds that if \(xRy\) then \(yRx\). "Is a blood relative of" is a symmetric relation, because \(x\) is a blood relative of \(y\leftrightarrow y\) if a blood relative of \(x\)
• antisymmetric: \(\forall x\wedge y\in X\), if \(xRy\) and \(yRx\) then \(x=y\). For example, \(\ge\) is anti-symmetric; so is \(>\), but vacuously (the condition in the definition is always false).
• asymmetric: \(\forall x\wedge y\in X\), if \(xRy\) then not \(yRx\). A relation is asymmetic if and only if it is both anti-symmetric and irreflexive. For example, \(>\) is asymmetic, but \(\ge\) is not.
• transitive: \(\forall x, y\wedge z\in X\) it holds taht if \(xRy\) and \(yRz\) then \(xRz\). For example, "is ancestor of" is transitive, while "is parent of" is not. A transitive relation is irreflexive \(\leftrightarrow\) it is asymmetric.
• total: \(\forall x\wedge y\in X\) it holds that \(xRy\) or \(yRz\) (or both) then \(xRz\). This definition of total is different from left total in the previous section. For example, \(\ge\) is a total relation.
• trichotomous: \(\forall (x\wedge y)\in X\) exactly one of \(xRy\), \(yRx\) or \(x=y\) holds. For example, \(>\) is a trichotomous relation, while the relation "divides" on natural numbers is not.
• Right Euclidean: \(\forall (x, y\wedge z)\in X\) it holds that if \(yRx\) and \(zRx\). then \(yRz\)
• Left Euclidean: \(\forall x, y\wedge z\in X\) it holds that if \(yRx\) and \(zRx\), then \(yRz\).
• Euclidean: A Euclidean relation is both left and right Euclidean. Equality is a Euclidean relation because if \(x=y\wedge x=z\), then \(y=z\).
• serial: \(\forall x\in X\exists y: xRy\), "Is greater than" is a serial relation on the integers. But it is not a serial relation on the positive integers, because there is no \(y\) in the positive integers such that 1>y. However, "is less than" is a serial relation on the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given \(x\), choose \(y=x\). A serial relation can be equivalently characterized as every element having a non-empty successor neighborhood (see the previous section for the definition of this notion). Similarly an inverse serial relation is a relation in which every element has non-empty predecessor neighborhood.
• set-like (or local): \(\forall x\in X\), the class of all \(y\) such that \(yRx\) is a set. (This makes sense only if relations on proper classes are allowed.) The usual ordering \(<\) on the class of ordinal numbers is set-like, while its inverse \(>\) is not.

A relation that is reflexive, symmetric, and transitive is called an equivalence relation. A relation that is symmetric, transitive, and serial is also reflexive. A relation that is only symmetric and transitive (without necessarily being reflexive) is called a partial equivalence relation.

A relation that is reflexive, antisymmetric, and transitive is called a partial order. A partial order that is total is called a total order, simple order, linear order, or a chain.[25] A linear order where every nonempty subset has a least element is called a well-order.

Binary endorelations by property

	reflexivity	symmetry	transitivity	symbol	example
directed graph				\(\rightarrow\)
undirected graph	\(X\)	\(\checkmark\)
tournament	\(X\)	antisymmetric			pecking order
dependency	\(\checkmark\)	\(\checkmark\)
strict weak order	irreflexive	antisymmetric	\(\checkmark\)	\(<\)
total preorder	\(\checkmark\)		\(\checkmark\)	\(\le\)
preorder	\(\checkmark\)		\(\checkmark\)	\(\le\)	preference
partial order	\(\checkmark\)	antisymmetric	\(\checkmark\)	\(\le\)	subset
partial equivalence		\(\checkmark\)	\(\checkmark\)
equivalence relation	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(-,=,\approx,\cong,\equiv\)	equality
strict partial order	\(X\)	\(X\)	\(\checkmark\)	\(<\)	proper subset

Operations on Binary Relations

If \(R, S\) are binary relations over \(X and Y\), then each of the following is a binary relation over \(X\) and \(Y\):

• Union: \(R\cup S\subseteq X × Y\), defined as

\(R\cup S = (x, y) | (x, y)\in R\; or (x, y)\in S\). For example, $ ≥ $ is the union of $ > $ and $ = $.

• Intersection: \(R\cap S\subseteq X × Y\), defined as \(R\cap S = (x, y) | (x, y)\in R\) and \((x, y)\in S \).

If \(R\) is a binary relation over \(X\) and \(Y\), and \(S\) is a binary relation over \(Y\) and \(Z\), then the following is a binary relation over \(X\) and \(Z\):

• Composition: \(S\circ R\), also denoted \(R\circ S\) (or \(R\circ S\)),

defined as \(S\circ R = (x, z)|\exists y\in Y\), such that \((x, y)\in R\wedge (y, z)\in S\). The order of \(R\) and \(S\) in the notation \(S\circ R\), used here agrees with the standard notational order for composition of functions. For example, the composition "is mother of" \(\circ\) "is parent of" yields "is maternal grandparent of", while the composition "is parent of" \(\circ\) "is mother of" yields "is grandmother of". A relation \(R\) on sets \(X\) and \(Y\) is said to be contained in a relation \(S\) on \(X\) and \(Y\) if \(R\) is a subset of \(S\), that is, if \(xRy\) always implies \(xSy\). In this case, if \(R\) and \(S\) disagree, \(R\) is also said to be smaller than \(S\). For example, \(>\) is contained in \(\ge\).

If \(R\) is a binary relation over \(X\) and \(Y\), then the following is a binary relation over \(Y\) and \(X\):

• Inverse or converse: \(R^{-1}\), defined as

\(R^{-1} = (y, x) | (x, y)\in R\). A binary relation over a set is equal to its inverse if and only if it is symmetric. See also duality (order theory). For example, "is less than" (\(<\)) is the inverse of "is greater than" (\(>\)). If \(R\) is a binary relation over \(X\), then each of the following is a binary relation over \(X\):

• Reflexive closure: \(R^{=}\), defined as

\(R^{=} = (x, x) | x\in X\cup R\) or the smallest reflexive relation over \(X\) containing \(R\). This can be proven to be equal to the intersection of all reflexive relations containing \(R\).

• Reflexive reduction: \(R^{\ne}\), defined as \(R^{\ne} = R\ (x, x) | x\in X\)

or the largest irreflexive relation over \(X\) contained in \(R\).

• Transitive closure: \(R^{+}\), defined as the smallest transitive relation over \(X\)

containing \(R\). This can be seen to be equal to the intersection of all transitive relations containing \(R\).

• Reflexive transitive closure: \(R^{*}\),

defined as \(R^{*} = (R^{+})^{=}\), the smallest preorder containing \(R\). Reflexive transitive symmetric closure: \(R^{\equiv}\), defined as the smallest equivalence relation over \(X\) containing \(R\).

Complement

If \(R\) is a binary relation over \(X\) and \(Y\), then the following too:

The complement \(S\) is defined as \(xSy\) if not \(xRy\). For example, on real numbers, \(\le\) is the complement of \(>\). The complement of the inverse is the inverse of the complement.

If \(X=Y\), the complement has the following properties:

If a relation is symmetric, the complement is too. The complement of a reflexive relation is irreflexive and vice versa. The complement of a strict weak order is a total preorder and vice versa. The complement of the inverse has these same properties.

Restriction

The restriction of a binary relation on a set \(X\) to a subset \(S\) is the set of all pairs \((x, y)\) in the relation for which \(x\) and \(y\) are in \(S\).

If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, total, trichotomous, a partial order, total order, strict weak order, total preorder (weak order), or an equivalence relation, its restrictions are too.

However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting the relation "x is parent of y" to females yields the relation "x is mother of the woman y"; its transitive closure doesn't relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of" is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother.

Also, the various concepts of completeness (not to be confused with being "total") do not carry over to restrictions. For example, on the set of real numbers a property of the relation "\(\le\)" is that every non-empty subset \(S\) of \(R\) with an upper bound in \(R\) has a least upper bound (also called supremum) in \(R\). However, for a set of rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation "\(\le\)" to the set of rational numbers.

The left-restriction (right-restriction, respectively) of a binary relation between \(X\) and \(Y\) to a subset \(S\) of its domain (codomain) is the set of all pairs \((x, y)\) in the relation for which \(x(y)\) is an element of \(S\).