Notes

Description: In this note the results of Harper/Rubin [1976] are summarized.

Content:

In this note the results of Harper/Rubin [1976] are summarized.

Definition: Suppose that \(R\) is a relation on \(X\).

  1. \(R\) is connected on \(X\) if \((\forall u, v\in X)(u\neq v \rightarrow uRv\) or \(vRu)\).
  2. An element \(u \in X\) is \(R\)-maximal in \(X\) if \((\forall v\in X)(uRv\rightarrow vRu\)). \(R\)-minimal is defined similarly.
  3. If \(Y\subseteq X\), \(u\in X\) is an (\(R\)) upper bound for \(Y\) if \((\forall v\in Y)(v\neq u\to vRu)\). Lower bound is defined similarly.
  4. \(X\) is directed (upwards) by \(R\) iff \(R\) partially orders \(X\) and every finite subset of \(X\) has an upper bound.
  5. If \(y \in X\), the initial segment generated by \(y\) is \(y^{*} = \{u\in X: uRy\}\).
  6. \(X\) is ramified by \(R\) if \(R\) partially orders \(X\) and for every \(y \in X\), \(y^{*}\) is linearly ordered by \(R\).
  7. \((X,R)\) is a forest if \(R\) is a partial ordering and \(y^{*}\) is well ordered by \(R\) for every \(y \in X\).
  8. \((X,R)\) is a tree if \((X,R)\) is a forest and is directed downward by \(R\).
  9. \(Q \subseteq X\) is quasi-cofinal in \(X\) if \(Q\) has no strict upper bound in \(S\). (``Strict'' = ``not in \(Q\)''.)
  10. \(Q \subseteq X\) is cofinal in \(X\) if \(Q\) is linearly ordered by \(R\) and \((\forall y\in X)(\exists z\in Q)( y\,R\,z )\).
  11. \(A \subseteq X\) is an antichain if \(\forall x, y\in A\), neither \(xRy\) nor \(yRx\) holds.

In Harper/Rubin [1976], the following weak forms of \(AC\) are studied:

  1. \(Z(Q,U)\): Every non-empty \(Q\)-ordered set in which every \(U\)-ordered subset has an upper bound, has a maximal element.
  2. \(C(Q,U)\): Every \(Q\)-ordered set contains a quasi-cofinal \(U\)-ordered subset.
  3. \(H(Q,U)\): Every \(Q\)-ordered set contains a \(\subseteq \)-maximal, \(U\)-ordered subset.
  4. \(H'(Q,U)\): Every \(Q\)-ordered set has the property that each \(U\)-ordered subset can be extended to a \(\subseteq \)-maximal \(U\)-ordered subset.
where \(Q\) and \(U\) range over the following properties:
  • \(A\): arbitrary (binary) relation
  • \(TR\): transitive
  • \(AS\): antisymmetric
  • \(C\): connected
  • \(P\): partially ordered
  • \(W\): well ordered
  • \(L\): linearly ordered
  • \(D\): directed
  • \(R\): ramified
  • \(F\): forest
  • \(T\): tree
  • \(AS \) & \(C\)
  • \(TR\) & \( C\).

In particular:

Form Is Equivalent To:
Form 51 \(Z(L,U)\) where \(U = W, F\) or \(T\) and to \(Z(R,F)\) and to \(Z(R,T)\).
Form 143 \(H(C,TR)\) and \(H(C,TR\&C)\).
Form 202 ([202 A]) \(H(TR\&C,U)\) where \(U = AS,\ AS\&C,\ P,\ L,\ D\), or \(R\).
Form 255 \(Z(P,R)\)
Form 256 \(Z(Q,U)\) where \(Q \in \{P,D\}\) and \(U \in \{F,T\}\).
Form 257 \(Z(TR,AS)\) and \(Z(TR,P)\).
Form 258 \(Z(D,U)\) where \(U \in \{C,AS \& C,TR \& C,L\}\).
Form 259 \(Z(TR \& C,U)\) where \(U \in \{W,F,T\}\).
Form 260 \(Z(TR \& C,U)\) where \(U \in \{AS,AS \& C,P,L,D,R\}\).
Form 261 \(Z(TR,F)\) and \(Z(TR,T)\).
Form 263 \(H(AS \& C,U)\) where \(U\in \{TR,TR \& C,P,L,D,R\}\).
Form 264 \(H(C,U)\) where \(U \in \{P,L,D,R\}\).
Form 266 \(H(AS,TR)\) and \(H(AS,P)\) and \(\{AS,AS \& C,P,L,D,R\}\).
Form 261 \(Z(TR,F)\) and \(Z(TR,T)\).
Form 263 \(H(AS \& C,U)\) where \(U \in \{TR,TR \& C,P,L,D,R\}\).
Form 264 \(H(C,U)\) where \(U \in \{P,L,D,R\}\).
Form 202 ([202 A]) \(H(TR\&C,U)\) where \(U = AS,\ AS\&C,\ P,\ L,\ D\), or \(R\).
Form 266 \(H(AS,TR)\) and \(H(AS,P)\).

Howard-Rubin number: 39

Type: Definitions and summaries

Back