Mg Problems 20 22


20: Prove that the polynomial ring $\mathbb{Z}{[x]}$ over the integers is countably infinite.

We've never defined polynomial rings or "countably infinite," so I'm assuming that will be covered in lecture Tues., and so I guess we'll be able to do this after Tues. 3-20.

22: Let $(R,0,1,+,\cdot,\leq)$ be an ordered ring with identity.

a. Prove that if $x>0$ then $-x<0$.

We define $-x$ as the additive inverse of $x$, that is the number which we add to $x$ to generate $0$. If $x>0$, adding another number greater than zero will result in a number even more greater than zero than $x$. Since zero is the additive identity, the only number to which it could be added to generate zero is zero, and since $x>0$, zero cannot be the inverse of $x$. Therefore, the additive inverse of an $x>0$ must be some $-x<0$. $QED$

b. Prove that $1>0$.

Suffice it to prove the equivalent statement $0<1$. Since this is an ordered ring, we know that it preserves the linear order from the naturals. Therefore, it suffices to prove from the definition of $<_{\mathbb{N}}$ that $0<_{\mathbb{N}}1$. We define $0$ as $\emptyset$ and $1$ as $\{\emptyset\}$. Since $\emptyset \in \{\emptyset\}$, $0<_{\mathbb{N}}1$. Therefore, by the preservation of this linear order, $1>0$ in this ordered ring. $QED$


20. Prop: The polynomial ring $\mathbb{Z}[x]$ is countably infinite.

Proof: Since the countable union of countably infinite sets is countably infinite, it suffices to prove that $\mathbb{Z}[x]$ is such a union. Therefore, let us construct $\mathbb{Z}[x]$ as $\cup{S}$ where $S = \{S_0, S_1, ... ,S_n,...\}$ and $S_n$ is the set of all polynomials with integer coefficients and degree $n$.

We establish that this union is countable by outlining a bijective map from $\mathbb{N} \rightarrow \{S_0, S_1, ... , S_n, ...\}$ where $n \in \mathbb{N}$ maps to $S_n \in S$. This map is clearly bijective.

Therefore it remains to prove that each $S_n \in S$ is a countably infinite set. Proceed by inducting on $n$. In base case $n=0$, the $S_0$ is all polynomials of the form $ax^0 = a$ where $a \in \mathbb{Z}$. In this way, we have $S_0 \simeq \mathbb{Z}$. Since $\mathbb{Z}$ is countably infinite, then $S_0$ is countably infinite.

Now assume that $S_k$ is countably infinite for some $n=k \in \mathbb{N}$. It remains to show that $S_{k+1}$ is countably infinite. Since each polynomial of degree $k$ may be written as $a_{0}x^{0} + a_{1}x^{1} + ... + a_{k}x^{k}$, we can see that $S_{k+1}$ can be constructed by $S_k \, X\, \mathbb{Z}$. Since $S_k$ is countably infinite by inductive hypothesis and $\mathbb{Z}$ is countably infinite by construction and the product of finitely many countably infinite sets is countably infinite, we conclude that $S_{k+1}$ is countably infinite. $QED$

(Prof. Simmons 4-23-18: Good; don't need the part I crossed out.)

22. Prop: Given ordered ring with identity $(R, 0, 1,+,\cdot,\leq)$,

a. If $x > 0$ then $-x < 0$.

Proof: Define $-x := x' | x + x' = 0$. Then, given $x >0$ we add $-x$ to both sides, preserving the linear order, to get $x + (-x) > 0 + (-x)$ from which we simplify to get $0 > -x$. $QED$.

b. 1 > 0

Proof: Prove this statement by proving the more general statement $x^2 = (x)(x) > 0$ for all $x \neq 0$. Suppose $x > 0$. Then we have $x(x) > 0(x)$.

Lemma: $0(x) = 0$ for all $x$.
Proof: $0 = y + (-y)$ from the definition of $-y$. Thus $0(x) = (y + (-y))x = yx + (-yx)$ by substitution and distribution of multiplication over addition. Next we have $yx + (-yx) = 0$ from the definition of the additive inverse. Therefore the lemma is proven.

Apply the lemma to $x(x) > 0(x)$ to get $x^2 > 0$ if $x>0$. Next consider $x<0$. We will prove $x^2 > 0$ in this case by proving that $x^2 = (-x)^2$, since we have $x^2 > 0$ for $x>0$ and part (a), showing that in this case $-x < 0$.

To prove $(-x)^2 = x^2$, we will prove the following lemma:

Lemma: $(-1)(x) = -x$ for all $x$.
Pf of lemma: $x(0) = 0$ and [[0 = 1 + (-1)$]]. Therefore, $x(0) = x(1 + (-1)) = (1)(x) + (-1)(x) = x + (-1)(x) = 0$ Since $-x$ is defined as the value that when added to $x$ returns $0$, we have $(-1)(x) = -x$.

Now, simply multiply $(-x)^2 = (-x)(-x) = (-1)(x)(-1)(x) = (-1)(-1)(x)(x) = (1)(x)(x)$, noting that $(-1)(-1) = 1$ since $(-1)(z)$ is the additive inverse of $z$. Finally, simplify using the multiplicative identity and get $(-x)(-x) = x^2$.

Since $1$ is the multiplicative identity, $(1)(1) = 1^2 = 1 > 0$. $QED$

(Prof Simmons 4-23-18: Looks good.)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License