This table: $$\begin{array}{|c|cc|} \hline +& 0& 1\\ \hline 0& 0& 1\\ 1& 1& 0\\ \hline \end{array}$$ "feels" right, but how can you prove that $1+1=0$? What is the reason? I assume that due to $F \times F \rightarrow F$, the result of $1+1$ must be within the field F after all.

I'm looking for a logical explanation.

  • 3
    You can't prove it, it's by definition. At best you can ask for the motivation behind this definition. – Git Gud Oct 31 '14 at 20:27
  • 23
    For $\{0,1\}$ to be a group, $1$ must have an additive inverse $x$ for which $1+x = 0$. $x$ can't be $0$ because $1+0=1$, so $x$ must be $1$ . – MJD Oct 31 '14 at 20:27
  • If $1+1=1$ (the only choice since you refuse to consider the possibility that $1+1=0$), then, on subtracting $1$ from both sides, we arrive at $1=0$ which is not permitted by those who insist that in a field the multiplicative identity $1$ must be different from the additive identity $0$. – Dilip Sarwate Oct 31 '14 at 20:29
  • 3
    previous comments are right, but also to say that $0$ represents all even integers, and $1$ represents all odd ones (in the usual way where $F=\Bbb Z_2$ comes from). So, $1+1=2$, but $2=0$ in this model. – Mirko Oct 31 '14 at 20:34
  • 1
    @Dilip: Even if you allow the null ring to be a field, you can't have $1=0$ once you have decided on $1+1\ne 0$ yet $1+1=1$. – Henning Makholm Oct 31 '14 at 22:13
up vote 18 down vote accepted

Recall the two axioms about addition:

  1. There exists a unique element $0$ such that for every $x$, $x+0=x$.
  2. For each element $x$ there exists a unique element $y$ such that $x+y=0$.

If $1+1=1$ it has to be the case that $1+0=0$. But in that case you just reversed the roles of $0$ and $1$, as dictated by the axioms. That's fine, and it still defines a group structure, but it's easier to just relabel them to the traditional roles, where $0$ is the additive unit.

So if $1+1\neq 1$, it has to be the case that $1+1=0$.

  • Ah yes. I should have re-looked-up these two axioms our prof gave us. Thank you! – user1511417 Oct 31 '14 at 20:47

As a Finite Field, the distribute law must hold: The distributive law holds: (a+b) · c = a · c+b · c for all a,b, c ∈ F. You can chose 1 or 0.

Now, consider Boolean Logic. Using the Or operator, then 1 is the correct answer. 0,1,1,1 If Exclusive Or, then 0,1,1,0 (as you have in your table)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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