Axiom of Choice in Logic

Question

The completeness and compactness theorems of first-order logic are well known to be equivalent to the ultrafilter lemma. Are there any theorems of logic that are similarly equivalent to the full axiom of choice? A slightly lesser question: does the ultrafilter lemma suffice for intuitionist logic, which (as I understand it) needs an infinite set of truth values?

Answer 1

Another equivalent:

Given a set $S$ of sentences of first order logic, and a subset $B$ of $S$ such that $B$ is consistent, there is a consistent subset $A$ of $S$ such that $A$ is maximal among the consistent subsets of $S$, and such that $B\subseteq A.$

Result due to Klimovsky (iirc). See Rubin & Rubin Theorem 8.4.

Answer 2

I can't fully answer this, because I don't know enough about intuitionistic logic. I will point out to this question and its links.

But I can answer the other part about equivalents to the axiom of choice:

1. It was proved by P. Howard that $\sf BPI+LT$ (Łoś Theorem) imply the axiom of choice.

2. In Rubin & Rubin's Equivalents of the Axiom of Choice II there are three particular forms related to first-order logic which are equivalent to the axiom of choice:

   1. If $\varphi$ is a formula which has a model of cardinality $\kappa$, then it has a model of cardinality $\mu$ for every $\aleph_0\leq\mu\leq\kappa$.

   2. If $\varphi$ is a formula which as model of cardinality $\aleph_0$, then it has a model of cardinality $\kappa$ for every $\kappa\geq\aleph_0$.

   3. If $Q$ is a set of formulas in a language of cardinality $\kappa$, and every finite subset of $Q$ has a model, then $Q$ has a model whose cardinality is at most $\kappa+\aleph_0$.

You may recognize these statements as the downward Löwenheim-Skolem, and the upward Löwenheim-Skolem theorems.

All these (including Howard's proof) appear in the book, in the first pages of chapter 8.