6
$\begingroup$

I have a situation where I do not know if I need the axiom of choice: Let $\mathcal{B}(\mathbb{R})$ be the collection of Borel measurable subsets of $\mathbb{R}$. I have a (possibly non-Borel) subset $M \subseteq \mathbb{R}$ and a probability measure $P:\mathcal{B}(\mathbb{R})\rightarrow[0,1]$ with the property:

$$ P(A)=P(B) \quad \forall A, B \in \mathcal{B}(\mathbb{R}) \mbox{ such that $M\cap A = M\cap B$} \quad (Eq. 1)$$

So I can group all sets in $\mathcal{B}(\mathbb{R})$ into equivalence classes where $A$ and $B$ are equivalent if $M\cap A = M \cap B$. I want to condense $P$ to a function $g$ on equivalence classes. Specifically, define $$V = \{M\cap A: A \in \mathcal{B}(\mathbb{R})\}$$ Define $g:V\rightarrow[0,1]$ as follows: For each $D \in V$, I can choose an $A \in \mathbb{B}(\mathbb{R})$ such that $M \cap A = D$, then I can define $g(D)=P(A)$. Formally, using the axiom of choice, there is a choice function $c:V\rightarrow \mathcal{B}(\mathbb{R})$ such that $$c(D)\in \{A\in \mathcal{B}(\mathbb{R}):M\cap A=D\} \quad \forall D \in V$$ Then I define $g(D)=P(c(D))$. Notice by (Eq. 1) that this leads to the same $g$ function regardless of my choice function $c(D)$. In particular:

$$g(M\cap A) = P(A) \quad \forall A \in \mathcal{B}(\mathbb{R}) \quad (Eq. 2)$$

Question: Do I really need to use the Axiom of Choice when defining this g function?

I think that, due to (Eq. 2), I do not formally need the axiom of choice here. Perhaps I can simply define objects $(A,P[A])$ for all $A \in \mathcal{B}(\mathbb{R})$ and then simply "say" that I condense these objects according to equivalence classes, so that my function $g$ somehow emerges. However, it is often hard to know if I am inadvertently using the axiom of choice.


Edit: I guess I could just define the set $\{(M\cap A, P[A]) : A \in \mathcal{B}(\mathbb{R})\}$ and $g$ emerges...?

$\endgroup$
9
  • 1
    $\begingroup$ The way I see it, $g$ is the composition $P\circ C$, where $C$ is a choice function. Unless you have a clever method to define it in some other way, I think you do need to use AC. $\endgroup$
    – Ruy
    May 23 at 23:50
  • 1
    $\begingroup$ @Ruy : Yes, indeeed $g=P \circ C$, so that makes me also feel AC is needed. However, see my edit on a possible other way to define $g$ (I just thought of that way after typing up the question). $\endgroup$
    – Michael
    May 23 at 23:53
  • 1
    $\begingroup$ I think you are right. Just say that $g(P)$ is the unique element in the set you described. I guess this is pretty much the same thing as my answer below. $\endgroup$
    – Ruy
    May 24 at 0:19
  • 1
    $\begingroup$ Isn't this almost a duplicate of math.stackexchange.com/questions/4456891/is-ac-necessary-here? $\endgroup$
    – Asaf Karagila
    May 24 at 7:00
  • 1
    $\begingroup$ Does this answer your question? Is AC necessary here? $\endgroup$
    – Ruy
    May 24 at 14:08

2 Answers 2

7
$\begingroup$

You do not need the axiom of choice at all.

In general, suppose you have a set $S$ and an equivalence relation $\sim$ on $S$. Consider the canonical projection map $\pi : S \to S / {\sim}$. The only relevant property of this situation is: $$\forall y \in (S / {\sim}) \,\exists x \in S\,(\pi(x) = y \land \forall w \in S (\pi(w) = y \to w \sim x)).$$

Now suppose you have some function $f : S \to R$ such that for all $x, y \in S$, if $x \sim y$ then $f(x) = f(y)$. Then there exists a unique function $f’ : (S / {\sim}) \to R$ such that $f’ \circ \pi = f$.

To produce such an $f’$, we define the corresponding set of pairs $f’ = \{(\pi(x), f(x)) \mid x \in S\} \subseteq (S / {\sim}) \times R$. It’s easy to prove that $\forall x \in (S / {\sim})\,\exists! y \in R\, ((x, y) \in f’)$, so $f’$ does indeed give us the function we need. Uniqueness is equally straightforward.

This result is exactly what you require here, and it requires no choice whatsoever (though unless you take a non-standard approach, you will need at least countable choice to make the Borel $\sigma$-algebra work, since without countable choice, we can have $\mathbb{R}$ being a countable union of countable sets). In category-theoretic terms, the fact that quotients exist and have this property amounts to stating that the category of sets is exact (in the sense of Barr).

$\endgroup$
5
  • 1
    $\begingroup$ I made some small edits for readability, I hope you don't mind. The main thing is that S / \sim typesets as $S/\sim$, while S / {\sim} removes the weird spacing: $S/{\sim}$. $\endgroup$ May 24 at 0:48
  • $\begingroup$ I am learning logic notation from you and Ruy. It seems to me from your first statement that parentheses that follow "there exists" are interpreted with an implicit "such that" while parentheses that follow "for all" are interpreted with an implicit "we have." Is that a good interpretation? ("For all $y$ in the set of equivalence classes, there exists an $x\in S$ [such that]...) $\endgroup$
    – Michael
    May 24 at 1:02
  • $\begingroup$ Nice! This is surely the simplest way to do it. But I wonder whether or not your definition of $f'$ requires the axiom of specification. I know it looks a bit fussy to pinpoint every axiom used, but I think this is relevant here. $\endgroup$
    – Ruy
    May 24 at 1:22
  • $\begingroup$ @Ruy Defining $f’$ requires a weakened form of specification known as the axiom of $\Delta_0$ specification (also known as bounded specification/separation), which is the weakest form of specification that anyone actually uses. It states that if $P(x)$ is a proposition containing only bounded quantifiers (of the form $\exists a \in S$ or $\forall a \in S$), the set $\{x \in A \mid P(x)\}$ exists. Interestingly, $\Delta_0$ specification is finitely axiomatizable in the presence of other reasonable axioms, unlike full specification. $\endgroup$ May 24 at 1:49
  • $\begingroup$ Your set $f'$ looks like a generalization of my set (call it $f'$) given by $\{(M \cap A, P[A]): A \in \mathcal{B}(\mathbb{R})\}$. So in other words: With $V$ the set of equivalence classes, define $\pi_1:f'\rightarrow V$ and $\pi_2:f'\rightarrow [0,1]$ as projections onto the first and second coordinates of each $(D,p) \in f'$; observe $\pi_1$ is a bijection; then define $g:V\rightarrow [0,1]$ by $g(v)=\pi_2(\pi_1^{-1}(v)) \quad \forall v \in V$. [But perhaps I'll never know about the implicit "such that" and "there exist" in the logical expressions before parentheses. =) ] $\endgroup$
    – Michael
    May 24 at 2:49
0
$\begingroup$

Contradicting my comment above, I think it is indeed possible to define $g$ without the axiom of choice, but using the axiom of specification (https://en.wikipedia.org/wiki/Axiom_schema_of_specification) instead.

Consider the formula $$ \forall X \in V, \ \exists! \lambda \in \mathbb R, \ \underbrace{\forall A \in \mathcal B(\mathbb R), \ (M\cap A= X \Rightarrow P(A)=\lambda )}_{\textstyle \varphi (X, \lambda )} $$ Then the axiom os specification guarantees the existence of a function $g$ such that, for every $X$ in $V$, one has that $\varphi (X, g(X))$, so $g(X)$ is what we expect it to be.

$\endgroup$
5
  • $\begingroup$ How can I interpret the commas in your formula? It looks like the first comma can be ignored while the second means "such that"? $\endgroup$
    – Michael
    May 24 at 0:21
  • 1
    $\begingroup$ Well, commas are just for clarity and are not required (or even allowed) in first order logic. So just ignore them! $\endgroup$
    – Ruy
    May 24 at 0:23
  • $\begingroup$ But then I need help parsing the formula since I think I want to add “such that” but there is no symbol for it: Is it “For all $X \in V$, there is no $\lambda \in \mathbb{R}$ (such that?) the following statement holds: For all $A \in \mathcal{B}(\mathbb{R})$, if $M \cap A=X$ then $P[A]=\lambda$.” [And perhaps it should be “there exists $\lambda \in \mathbb{R}$” rather than “there does not exist $\lambda \in \mathbb{R}$”? (I am interpreting the exclamation point as negation). $\endgroup$
    – Michael
    May 24 at 0:39
  • 2
    $\begingroup$ Sorry, "$\exists !$" is usually interpreted as "there exists a unique". $\endgroup$
    – Ruy
    May 24 at 0:51
  • 2
    $\begingroup$ First order logic doesn't actually need a symbol for "such that" but if you want to insert it where you mentioned, it is OK. $\endgroup$
    – Ruy
    May 24 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.