MATH 101: Logic and Set Theory - Ordering Relations

Flashcards covering the definitions of ordering relations, partial and total orders, well-ordered sets, bounds, and foundational axioms like Zorn's Lemma and the Axiom of Choice.

Antisymmetric Relation

A relation $\rho$ is antisymmetric if and only if whenever $x \rho y$ and $y \rho x$ then $x = y$.

Partial Ordering

A relation $\rho$ in a set $A$ that is reflexive, antisymmetric, and transitive.

Partially Ordered Set (Poset)

A set $A$ together with a specific partial order relation $\rho$ in $A$, denoted as $\langle A, \rho \rangle$.

Precedes

A way to read the partial order notation $(x \preceq y)$.

Dominates

A way to read the partial order notation $(x \preceq y)$, specifically saying that $y$ dominates $x$.

Multiple of a number $x$

Any quantity $nx$ where $n \in \mathbb{Z}$.

Divides ($a | b$)

For $a, b \in \mathbb{Z}$ with $a \neq 0$, we say $a | b$ if there exists an integer $q$ such that $b = aq$.

Comparable Elements

Two elements $x$ and $y$ in a partially ordered set where either $x \preceq y$ or $y \preceq x$.

Incomparable Elements

Two elements in a partially ordered set that are not comparable.

Poset Diagram

A diagram that shows the relationship between two elements of a partially ordered set.

Total Ordering (Simple or Linear Ordering)

A partial ordering $\rho$ on a set $A$ where $x \rho y$ or $y \rho x$ whenever $x, y$ are distinct elements of $A$.

First (Least) Element

An element $z \in A$ such that $z \preceq x$ for all $x \in A$, meaning it precedes every element in the set.

Last (Greatest) Element

An element $w \in A$ such that $x \preceq w$ for all $x \in A$, meaning it dominates every element in the set.

Well-ordered Set

A partially ordered set $\langle A, \preceq \rangle$ where every non-empty subset of $A$ has a first element.

Well-ordering Principle

The principle stating that if $A$ is a non-empty set, then there exists a total ordering $\preceq$ of $A$ such that $\langle A, \preceq \rangle$ is well-ordered.

Maximal Element

An element $z \in A$ such that $z \preceq x$ implies $z = x$, meaning no element in $A$ strictly dominates it.

Minimal Element

An element $w \in A$ such that $x \preceq w$ implies $w = x$, meaning no element in $A$ strictly precedes it.

Upper Bound

Given a poset $\langle A, \preceq \rangle$ and $B \subseteq A$, an element $y \in A$ is an upper bound for $B$ iff $\forall x \in B$, $x \preceq y$.

Least Upper Bound (Supremum)

An element $z \in A$ that is an upper bound for $B$ and satisfies $z \preceq y$ for all upper bounds $y$ for $B$.

Lower Bound

Given a poset $\langle A, \preceq \rangle$ and $B \subseteq A$, an element $t \in A$ is a lower bound for $B$ iff $\forall x \in B$, $t \preceq x$.

Greatest Lower Bound (Infimum)

An element $w \in A$ that is a lower bound for $B$ and satisfies $t \preceq w$ for all lower bounds $t$ for $B$.

Zorn's Lemma

The statement that if every totally ordered subset of a non-empty partially ordered set $A$ has an upper bound, then $A$ contains at least one maximal element.

Axiom of Choice (ZF9)

For any set $A$, there exists a function $f$ whose domain is the collection of nonempty sets of $A$ and, for every $B \subseteq A$ with $B \neq \emptyset$, $f(B) \in B$.

Choice Function

A function $f$ from the set of all nonempty subsets of $S$ to $S$ such that $f(A) \in A$ for all $A \neq \emptyset, A \subseteq S$.