0
$\begingroup$

Let $X$ be a set and $A\subseteq X$. If I define the characteristic function of $A$ (relative to $X$) as the function $\chi_A: X\to \mathbb{F}_2$ such that

$$\chi_A(x) = \begin{cases}0; & x\not\in A \\ 1; & x\in A \end{cases}.$$

If $A, B\subseteq X$, then $\chi_A + \chi_B$ and $\chi_A\chi_B$ are both well defined functions from $X \to \mathbb{F}_2$

If $\chi_D = \chi_A + \chi_B$, then $\chi_D\left(x\right) = 1$ if exactly one of $\chi_A\left(x\right), \ \chi_B\left(x\right) = 1$, so $D = A\vartriangle B$.

I am trying to jump to the identity that:

$$C = A\cup B \iff \chi_C = \max\left(\chi_A, \chi_B\right).$$

Why is it necessary to show that $\mathbb{F}_2$ is an ordered field?

$\endgroup$
  • 1
    $\begingroup$ Perhaps I misunderstand your Question. In the conventional definition $\mathbb F_2$ is not an ordered field (it does not have a "positive cone" closed under addition and multiplication). The point of it "being necessary to show" that escapes me. $\endgroup$ – hardmath Feb 9 '18 at 2:53
  • 1
    $\begingroup$ You need an order to be even be able to talk about $\max$ (this is for the "necessary" part of your question). However, as pointed out by @hardmath, $\mathbb{F}_2$ is not an ordered field. Being an ordered field is much stronger than being a field and equipped with an order. IMHO, you should think of the image of characteristic functions living in a Boolean algebra rather than a field. Even though it does not change anything about computations, it will prevent you from looking for an order in $\mathbb{F}_2$ which is not natural. $\endgroup$ – Clément Guérin Feb 9 '18 at 3:01
0
$\begingroup$

Simply because you couldn't have $\max$ in an unordered field.

$\endgroup$
  • $\begingroup$ But how would the identity follow? $\endgroup$ – Note Feb 9 '18 at 2:58

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.