I would like to know if the following statement is true in the 2-adic integers.

$\forall n( n=0 \lor Ex( (x \neq 0 \land x+x=0 \bmod n) \lor (x+x=1 \bmod n) ))$

I will define a modulo predicate as:

$M(x,n,r) := (n=0 \lor Ey(x=yn+r))$

$\forall n( (n=0 \lor Ex( x \neq 0 \land M(x,n,0)) \lor M(x,n,1) ))$

Would my expression be false for some n = an irrational 2-adic integer?

Edit: The second statement should be

$\forall n( n=0 \lor Ex( (x \neq 0 \land M(x+x,n,0)) \lor M(x+x,n,1) ))$

In response to anon.

I may be totally confused, but I think part of your argument implicitly assumes $Z_2$ has an "odd" number of elements. The number of elements in $Z_2$ is neither even nor odd. $\exists x(x \neq 0 \land x+x = 0) \overline{\vee} \exists x(x+x = 1)$ is false in $Z_2$.

You state "If $n$ is even with $n=2m$ then $x=m$ is a solution to $2x \equiv 0$." This statement is false in rings with an odd number of elements because every element is both even and odd "inside" the ring. Even numbers in an even size ring have two solutions to $n=2m$ and only one of these solutions satisfy my expression (in rings with more than 2 elements). Consider the ring $\mathbb{Z} /10 \mathbb{Z}$ and let $n = 8$. There are two solutions to $8=2m$ inside the ring.

$9 + 9 = -1 + -1 = 8 = -2 \bmod 10$ and $4 + 4 = -6 + -6 = 8 = -2 \bmod 10$ However, only $4+4 = 0 \bmod 8$. $9+9 = 2 \bmod 8$ is not a solution to my expression.

Now consider the ring $\mathbb{Z} /11 \mathbb{Z}$ and let $n=9$. There is one solution to $9 = 2m$.

$10 + 10 = -1 + -1 = 9 = -2 \bmod 11$ Clearly, $10 + 10 \neq 0 \bmod 9$.

Let $n = -2 \in Z_2$. $-2$ is even "inside" $Z_2$ because the $2^0$ bit is $0$. Your argument says because $-2 = -1 + -1$ then $x = -1$ is a solution to $2x \equiv 0$. I think $-1 \equiv 1 \bmod -2$ is a theorem. $-1 + -1 \equiv 2 \bmod -2$. Would this mean $Z_2 \bmod -2 \in Z_2 \equiv \mathbb{Z} /2 \mathbb{Z}$?

I have to apologise. I've realized I need to make one of my assumptions more explicit.

$\forall n( n=0 \lor Ex( (x \neq 0 \bmod n \land x+x=0 \bmod n) \lor (x+x=1 \bmod n) ))$

I am sorry for any confusion my omission may have caused. $x \neq 0 \bmod n$ is an important part of my definition of even because it removes solutions of the form $0=0+0$. anon's post helped me figure out where the mis-communication occurred and I hope he will respond to this new constraint on the problem.

• The number of elements in $\Bbb Z_2$ (which is uncountable infinity) has absolutely nothing to do with my answer, neither explicitly nor implicitly. It is true in any ring that $n$ is a multiple of itself (which is what saying $x=m$ is a solution to $2x\equiv 0\bmod n$ means), and this has no dependence on elements being both odd and even or whatever. What in the world does $$Z_2\bmod -2\in Z_2\equiv\Bbb Z/2\Bbb Z$$ mean by the way? It looks like gibberish to me. – anon Oct 13 '13 at 5:25
• I show why your argument doesn't work for $\mathbb{Z} /10 \mathbb{Z}$. I am using the modulo function on elements of a ring. For example, $\mathbb{Z} /10 \mathbb{Z} \bmod -2 \in \mathbb{Z} /10 \mathbb{Z} \equiv \mathbb{Z} /8 \mathbb{Z}$. Since $Z_2$ is an uncountable set, $Z_2 \bmod -2$ must also be an uncountable set. – Russell Easterly Oct 13 '13 at 18:09
• "Since $Z_2$ is an uncountable set, $Z_2/(-2)$ must be an uncountable set." Uh no, the quotient of a ring need not have the same size as the original ring. In fact the $2$-adic integers modulo the principal ideal generated by $-2$ is the ring of integers modulo $2$: this has two elements, not uncountably infinitely many (which you would write as $\Bbb Z_2/(-2)\cong\Bbb Z/2\Bbb Z$). – anon Oct 13 '13 at 20:16

Of course every $2$-adic integer is either even or odd. Observe:

$$a_0+a_12+a_22^2+a_32^3+\cdots=a_0+(a_1+a_22+a_32^2+\cdots)+(a_1+a_22+a_32^2\cdots)$$

where $a_0$ is either $0$ or $1$. Since $p$-adic expansions are unique, $a_0$ is unique, so not only is every $2$-adic integer even or odd, but no $2$-adic integers are both even and odd.

More generally, there is a quotient map $\Bbb Z_p\to\Bbb Z/p\Bbb Z$ given by

$$a_0+a_1p+a_2p^2+\cdots\mapsto a_0+p\Bbb Z.$$

This is a surjective ring homomorphism with kernel $p\Bbb Z_p$ hence $\Bbb Z_p/p\Bbb Z_p\cong\Bbb Z/p\Bbb Z$ and every $p$-adic integer has a unique residue $r\in\{0,\cdots,p-1\}$ modulo $p\Bbb Z_p$. Even more generally, every system of coset representatives for $p\Bbb Z_p$ forms a set of possible 'digits' from which to pick the $a_i$s, and for each digit set, every $p$-adic integer has a unique $p$-adic expansion using these digits.

If your definition of $\Bbb Z_p$ is either through inverse limits or Cauchy sequences in $\Bbb Z$, you will need to show that every $p$-adic integer has an associated formal power series in $p$.

• I can't accept this answer in its current form. I am asking if every element of $Z_2$ is even or odd. Your argument starts with "If $n$ is odd" and then says "If $n$ is even". You are assuming we already know that every $n \in Z_2$ is even or odd. If you are assuming $-2$ is even because $-2 = -1 + -1$ then your proof doesn't work even for the rings $\mathbb{Z} /n \mathbb{Z}$. – Russell Easterly Oct 15 '13 at 1:24
• @RussellEasterly Let $R$ be the ring of 2-adic integers, and let $2R$ be the principal ideal generated by $2$. Then $R/2R \cong \mathbb{Z}/(2) = \{0, 1 \mod 2\}$. If $x \in R$, this means $x \equiv 0 \mod 2R$, i.e., $x \in 2R$, i.e. $x$ is even, or $x \equiv 1 \mod 2R$, i.e. $x -1 \in 2R$, i.e., $x$ is odd. Hopefully this addresses your concern. – user43208 Oct 16 '13 at 1:04
• Thanks for addressing my concerns and defining what you mean by even or odd. I will study your answer. I think my definition of even is stronger than yours. – Russell Easterly Oct 16 '13 at 3:38