1

I am studying Bridges' Varieties of Constructive Mathematics. Exercise 7 in the first chapter is confounding to me. I don't know how the hinted proof strategy works.

Let $A$ be a subset of a set $B$. A subset $A'$ of $B$ is a (strong) complement of $A$ if $A \cup A' = B$ and $A\cap A' = \varnothing$. Following Diaconescu, show that the axiom of choice implies that every subset has a complement, by letting $C = B_1 \cup B_2$ be the disjoint union of two copies of $B$, and $D$ be $C$ with corresponding elements of $A_1$ and $A_2$ identified.

I don't know what the last sentence means because it's not precise enough. Any explanation is appreciated. Thanks!

Xiaoyu Liu
  • 113
  • 7
  • Is there more to the context? In plain ZF, existence of a complement is obvious from the axiom schema of specification / restricted comprehension; no choice needed. – aschepler Apr 30 '22 at 14:47
  • I think we are no longer in ZF and comprehension does not work, because $\forall x, x\in A \lor x \not \in A$ is not true, since it's constructive mathematics and there's no Excluded Middle. – Xiaoyu Liu Apr 30 '22 at 15:04
  • That's the kind of context I meant. – aschepler Apr 30 '22 at 15:53

1 Answers1

0

Here is the rough scheme:

Come up with bijections $b_1 : B \to B_1$, $b_2 : B \to B_2$ such that $B_1 \cap B_2 = \emptyset$.

Then note that $\sim := \{(x, x) \mid x \in B_1 \cup B_2\} \cup \{(b_1(x), b_2(x)) \mid x \in A\} \cup \{(b_2(x), b_1(x)) \mid x \in A\}$ is an equivalence relation on $B_1 \cup B_2$.

Then consider the projection map $\pi : B_1 \cup B_2 \to (B_1 \cup B_2) / \sim$. Using the axiom of choice, take a section $f : (B_1 \cup B_2) / \sim \to B_1 \cup B_2$.

Now define $C = \{x \in B \mid f(\pi(b_1(x))) \neq f(\pi(b_2(x)))\}$. Show that $C$ is the complement of $A$.

Mark Saving
  • 31,855