Give formal proofs of the following two statements.
Proof:
1. Let \(x=0\). Note that \(x \in \mathbb{Z}\).
2. Let \(y\) be an arbitrary integer.
3. Then \(x+y = 0+y = y\) (by axioms of arithmetic)
4. (\(\forall y \in \mathbb{Z}. x+y=y\)) is true (by generalization 2,3)
5. (\(\exists x \in \mathbb{Z}.\forall y \in \mathbb{Z}. x+y=y\)) is true (by construction 1,4)
Proof:
1. Let \(y\) be an arbitrary integer.
2. Let x = -y. Note that \(x \in \mathbb{Z}\) since \(y \in \mathbb{Z}\)
3. x + y = (-y)+y = 0 (by axioms of arithmetic)
4. \((\exists x \in \mathbb{Z}. x+y=0)\) is true (by construction 2,3)
5. \((\forall y \in \mathbb{Z}.\exists x \in \mathbb{Z}. x+y=0)\) is true (by generalization 1,4)
From the two questions above, notice that the order of the quantifiers changes the nature of the proofs.
To prove a proposition of the form \(\forall y \in D. \exists x \in C. p(x,y)\) (as in question 2), we pick an arbitrary element \(y\) in the domain \(D\) and we can use \(y\) to construct an \(x\) in \(C\).
However, when proving a proposition of the form
\(\exists x \in C. \forall y \in D.p(x,y)\) (as in question 1), we must define \(x\) before we pick \(y\),
so we cannot use \(y\) to construct \(x\).
It depends whether or not the variable \(y\) occurs in \(F\). If \(y\) does not occur in \(F\), then \((\forall x \in D. F)\) and \((\forall y \in D. F')\) are equivalent.
However, consider the following example:
Let \(F = (x \textrm{ AND } ( \textrm{NOT } y))\). Then, \(F' = (y \textrm{ AND } (\textrm{NOT } y))\). Therefore, \(F'\) always evaluates to false. So, under any interpretation that sets \((\forall x \in D. F)\) to true, the statements \((\forall x \in D. F)\) and \((\forall y \in D. F')\) are not equivalent.
Use a proof by contradiction. Start by assuming that there exist two distinct inverses for x.
Let a and b be two such distinct inverses. Try to show that \(a=b\).
To obtain a contradiction, assume that there exist two distinct inverses for \(x\), say \(a\) and \(b\). Then, by definition of inverse, we know that \(ax=1\). Multiply both sides by \(b\) to get \(axb = b\). Again, by the definition of inverse, \(xb=1\). Substituting this into \(axb=b\), it follows that \(a=b\), which contradicts the fact that \(a\) and \(b\) are distinct.