Antisymmetric Vs. Asymmetric Discrete Structures

Concepts Readings 'antisymmetric' VS. asymmetric Note that 'antisymmetric' is not the logical negative of 'symmetric' (whereby aRb implies bRa). (N.B.: Both are properties of relations expressed as universal statements about their members; their logical negations must be existential statements.) Thus, there are relations which are both symmetric and antisymmetric (e.g., the equality relation) and there are relations which are neither symmetric nor antisymmetric (e.g., the preys-on relation on biological species). Therefore the statement "an equivalence relation can be antisymmetric" is correct. One example is "equal" relation. It is both "symmetric" and "antisymmetric". Therefore it is both "an equivalence relation and antisymmetric"

it is possible that relations are both symmetric and antisymmetric (e.g., the equality relation). From

the definition of symmetric, you only care the aRb implies bRa. From the definition of antisymmetric, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is R to b and b is R to a, then a = b. In another words, there is only one possible that make aRb and bRa in R is a=b, if a is not equal to b, then it must not be in the relation R. Antisymmetry is different from asymmetry. According to one definition of asymmetric, anything that fails to be symmetric is asymmetric. Another definition of asymmetric makes asymmetry equivalent to antisymmetry plus irreflexivity. Antisymmetry and symmetric has only one intersection, that is the equality relation. A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:   

a ≤ a (reflexivity); if a ≤ b and b ≤ a then a = b (antisymmetry); if a ≤ b and b ≤ c then a ≤ c (transitivity).

In other words, a partial order is an antisymmetric preorder. A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets.

Examples Standard examples of posets arising in mathematics include:



The real numbers ordered by the standard less-than-or-equal relation ≤ (a totally ordered set as well).



The set of natural numbers equipped with the relation of divisibility.



The set of subsets of a given set (its power set) ordered by inclusion (see the figure on top-right).



The set of subspaces of a vector space ordered by inclusion.



For a partially ordered set P, the sequence space containing all sequences of elements from P, where sequence a precedes sequence b if every item in a precedes the corresponding item in b. Formally, if and only if for all n in N.



For a set X and a partially ordered set P, the function space containing all functions from X to P, where f ≤ g if and only if f(x) ≤ g(x) for all x in X.



The vertex set of a directed acyclic graph ordered by reachability.

Total order In mathematics and set theory, a total order, linear order, simple order, or (non-strict) ordering is a binary relation (here denoted by infix ≤) on some set X. The relation is transitive, antisymmetric, and total. A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain. If X is totally ordered under ≤, then the following statements hold for all a, b and c in X: If a ≤ b and b ≤ a then a = b (antisymmetry); If a ≤ b and b ≤ c then a ≤ c (transitivity); a ≤ b or b ≤ a (totality). Contrast with a partial order, which lacks the third condition. A relation having the property of "totality" means that any pair of elements in the set of the relation are mutually comparable under the relation. Totality implies reflexivity, that is, a ≤ a. Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive. Hence a total order is also a partial order satisfying the "totality" condition.

Strict total order For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) relation <, called a strict total order, which can equivalently be defined in two ways:  

a < b if and only if a ≤ b and a ≠ b a < b if and only if not b ≤ a (i.e., < is the inverse of the complement of ≤)

Properties:   

The relation is transitive: a < b and b < c implies a < c. The relation is trichotomous: exactly one of a < b, b < a and a = b is true. The relation is a strict weak order, where the associated equivalence is equality.

We can work the other way and start by choosing < as a transitive trichotomous binary relation; then a total order ≤ can equivalently be defined in two ways:  

a ≤ b if and only if a < b or a = b a ≤ b if and only if not b < a

Two more associated orders are the complements ≥ and >, completing the quadruple {<, >, ≤, ≥}. We can define or explain the way a set is totally ordered by any of these four relations; the notation implies whether we are talking about the non-strict or the strict total order.

Examples 

The letters of the alphabet ordered by the standard dictionary order, e.g., A < B < C etc.



Any subset of a totally ordered set, with the restriction of the order on the whole set.



Any partially ordered set X where every two elements are comparable (i.e. if a,b are members of X either a ≤ b or b ≤ a or both).



Any set of cardinal numbers or ordinal numbers (more strongly, these are well-orders).



If X is any set and f an injective function from X to a totally ordered set then f induces a total ordering on X by setting x1 < x2 if and only if f(x1) < f(x2).



The lexicographical order on the Cartesian product of a set of totally ordered sets indexed by an ordinal, is itself a total order. For example, any set of words ordered alphabetically is a totally ordered set, viewed as a subset of a Cartesian product of a countable number of copies of a set formed by adding the space symbol to the alphabet (and defining a space to be less than any letter).



The set of real numbers ordered by the usual less than (<) or greater than (>) relations is totally ordered, hence also the subsets of natural numbers, integers, and rational numbers. Each of these can be shown to be the unique (to within isomorphism) smallest example of a totally ordered set with a certain property, (a total order A is the smallest with a certain property if whenever B has the property, there is an order isomorphism from A to a subset of B): o The natural numbers comprise the smallest totally ordered set with no upper bound. o The integers comprise the smallest totally ordered set with neither an upper nor a lower bound. o The rational numbers comprise the smallest totally ordered set with no upper or lower bound, which is dense in the sense that for every a and b such that a < b there is a c such that a < c < b. o The real numbers comprise the smallest unbounded connected totally ordered set. (See below for the definition of the topology.)

Orders on the Cartesian product of totally ordered sets In order of increasing strength, i.e., decreasing sets of pairs, three of the possible orders on the Cartesian product of two totally ordered sets are:   

Lexicographical order: (a,b) ≤ (c,d) if and only if a < c or (a = c and b ≤ d). This is a total order. (a,b) ≤ (c,d) if and only if a ≤ c and b ≤ d (the product order). This is a partial order. (a,b) ≤ (c,d) if and only if (a < c and b < d) or (a = c and b = d) (the reflexive closure of the direct product of the corresponding strict total orders). This is also a partial order.

All three can similarly be defined for the Cartesian product of more than two sets. Applied to the vector space Rn, each of these make it an ordered vector space. See also examples of partially ordered sets. A real function of n real variables defined on a subset of Rn defines a strict weak order and a corresponding total preorder on that subset.

Lexicographical order In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets.

Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as (a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′). The result is a partial order. If A and B are totally ordered, then the result is a total order also. More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

Maximal element

Definition Let

be a partially ordered set and

for all

,

. Then

is a maximal element of S if

implies m = s.

The definition for minimal elements is obtained by using ≥ instead of ≤.

Existence and uniqueness Maximal elements need not exist. Example 1: Let < s (that is,

, for all

we have

but m

but not m = s).

Meet: Let A be a set with a partial order , and let x and y be two elements in A. An element z of A is the meet (or greatest lower bound or infimum) of x and y, if the following two conditions are satisfied: 1. and (i.e., z is a lower bound of x and y); and 2. for any w in A, such that and , we have any other lower bound of x and y).

(i.e., z is greater than

If there is a meet of x and y, then indeed it is unique, since if both z and z' are greatest lower bounds of x and y, then , whence indeed . If the meet does exist, it is

denoted . Some pairs of elements in A may lack a meet, either since they have no lower bound at all, or since none of their lower bounds is greater than all the others. If all pairs of elements have meets, then indeed the meet is a binary operation on A, and it is easy to see that this operation fulfils the following three conditions: For any elements x, y, and z in A, a. b. c.

(commutativity), (associativity), and (idempotency).

Join: Let A be a set with a partial order , and let and be two elements in A. An element of A is the join (or least upper bound or supremum) of and , if the following two conditions are satisfied: 1. and (i.e., is an upper bound of and ); and 2. for any in A, such that and , we have (i.e., equal to any other upper bound of and ).

is less than or

If there is a join of and , then indeed it is unique, since if both and are least upper bounds of and , then , whence indeed . If the join does exist, it is denoted . Some pairs of elements in A may lack a join, either because they have no upper bound at all, or because none of their upper bounds is less than or equal to all the others. If all pairs of elements have joins, then indeed the join is a binary operation on A, and it is easy to see that this operation fulfils the following three conditions: For any elements , , and in A, a. b. c.

(commutativity), (associativity), and (idempotency).

Lattices as posets A poset (L, ≤) is a lattice if it satisfies the following two axioms. Existence of binary joins For any two elements a and b of L, the set {a, b} has a join (also known as least upper bound or supremum). Existence of binary meets For any two elements a and b of L, the set {a, b} has a meet (also known as greatest lower bound or infimum).

The join and meet of a and b are denoted by a∨b and a∧b, respectively. This definition makes ∨ and ∧ binary operations. The first axiom says that L is a join-semilattice; the second says that L is a meet-semilattice. Both operations are monotone with respect to the order: a1 ≤ a2 and b1 ≤ b2 implies that a1∨b1 ≤ a2∨b2 and a1∧b1 ≤ a2∧b2. It follows by an induction argument that every non-empty finite subset of a lattice has a join (supremum) and a meet (infimum). With additional assumptions, further conclusions may be possible; see Completeness (order theory) for more discussion of this subject. That article also discusses how one may rephrase the above definition in terms of the existence of suitable Galois connections between related posets – an approach of special interest for the category theoretic approach to lattices. A bounded lattice has a greatest and least element, denoted 1 and 0 by convention (also called top and bottom). Any lattice can be converted into a bounded lattice by adding a greatest and least element, and every finite lattice is bounded, by taking the join (resp., meet) of all elements. A poset is a bounded lattice if and only if every finite set of elements (including the empty set) has a join and a meet. Here, the join of an empty set of elements is defined to be the least element 0, and the meet of the empty set is defined to be the greatest element 1. This convention is consistent with the associativity and commutativity of meet and join: the join of a union of finite sets is equal to the join of the joins of the sets, and dually, the meet of a union of finite sets is equal to the meet of the meets of the sets, i.e., for finite subsets A and B of a poset L,

and

hold. Taking B to be the empty set,

and

which is consistent with the fact that

Lattices as algebraic structures

.

An algebraic structure (L, ∨, ∧), consisting of a set L and two binary operations ∨ and ∧ on L is a lattice if the following axiomatic identities hold for all elements a, b, c of L. Commutative laws a∨b = b∨a, a∧b = b∧a.

Associative laws a∨(b∨c) = (a∨b)∨c, a∧(b∧c) = (a∧b)∧c.

Absorption laws a∨(a∧b) = a, a∧(a∨b) = a.

The following identity can be derived from the axioms. Idempotent laws a∨a = a, a∧a = a. These axioms assert that both (L,∨) and (L,∧) are semilattices. The absorption laws, the only axioms above in which both meet and join appear, distinguish a lattice from a random pair of semilattices and assure that the two semilattices interact appropriately. In particular, each semilattice is the dual of the other. A bounded lattice is an algebraic structure of the form (L, ∨, ∧, 1, 0) such that (L, ∨, ∧) is a lattice, 0 (the lattice's bottom) is the identity element for the join operation ∨, and 1 (the lattice's top) is the identity element for the meet operation ∧. See semilattice for further details. Lattices have some connections to the family of group-like algebraic structures. Because meet and join both commute and associate, a lattice can be viewed as consisting of two commutative semigroups having the same domain. For a bounded lattice, these semigroups are in fact commutative monoids. The absorption law is the only defining identity that is peculiar to lattice theory. By commutativity and associativity one can think of join and meet as operations that are defined on non-empty finite sets, rather than pairs, of elements. In a bounded lattice the empty join and the empty meet can also be defined (as 0 and 1, respectively). This makes bounded lattices somewhat more natural than general lattices, and many authors require all lattices to be bounded. The algebraic interpretation of lattices plays an essential role in universal algebra.