Problem Set 3:

5. (a) Considering the expression $\phi \wedge \psi \vee \theta$ in which we can assign truth values to each formula, ambiguity arises by the lack of parentheses, as the order operations is unknown and could therefore change the meaning of the overall formula. Consider the following binary truth values for each expression for use in Boolean algebra: $\phi = 0, \psi = 1, \theta = 1$.

Without parentheses, we get $0 \,X\, 1 + 1$. If we were to perform the AND operation first, we would get $(0 \,X\, 1) + 1 = 0 + 1 = 1$. However, if we were to perform the OR operation first, we get $0 \,X\, (1 + 1) = 0 \,X\, 1 = 0$.

Since, as demonstrated by example, the final truth value can change depending on the order, without parentheses, we cannot be certain to have an unambiguous statement.

(b) A formula is uniquely readable if and only if there is precisely one possible interpretation of the formula under the rules of the established logical language being used.

(c) All WFFs must satisfy the above definition of unique readability because no WFF has any initial statement that is also a WFF, meaning that it is impossible to read any component formula to an overall WFF in more than one way. Since, for any basic WFF like, for example, $(\Phi \rightarrow \Psi)$, every WFF that exists within the statement is closed within itself, any construction of a WFF from such components cannot have any ambiguity.

FINAL VERSION:

Proposition: Every WFF has the form of exactly one of the following cases: $\left(x=y\right),\left(x\in y\right)$,$\lnot\Phi,\left(\Phi\land\Psi\right)$,$\left(\Phi\vee\Psi\right)$,$\left(\Phi\rightarrow\Psi\right)$,$\forall x\Phi,\exists x\ \Phi$, where $\Phi$ and $\Psi$ are WFFs.

Moreover, if a WFF has the form $\left(\Phi\ \ast\ \Psi\right)$ and $\left(\alpha\ \ast\ \beta\right)$ for the same binary connective $\ast$, then $\Phi=\ \alpha$ and $\Psi=\ \beta$.

Since WFFs satisfy this property and cannot contain any initial segments that are WFFs, we say that they have unique readability.

Definition:

6. Thm: There exist irrational numbers, a and b, and rational number, c, such that $a^b = c$

Consider the case $a = \sqrt{2}^\sqrt{2}, b = \sqrt{2}$.

In this case, we know that b is irrational, and, using laws of exponents can show that $a = ({2^{1/2}})^{(2^{1/2})} = 2^{({1/2})*(2^{1/2})}$.

(Thanks Maria for the following: If a is rational, then we are done. Thus, assume a is irrational.)

In our example, we can see that $a^b = {(\sqrt{2}^\sqrt{2})}^\sqrt{2} = \sqrt{2}^{\sqrt{2}*\sqrt{2}} = \sqrt{2}^2 = 2$. And 2 is rational, thus there exist irrational numbers, a and b, and rational number, c, such that $a^b = c$.

This proof does not give a specific method for finding values of a and b that fulfill the condition. However, other values could be generated rational number r and irrational number i but considering ${(r^i)}^{1/i} \,$ where $\,\,p^i \notin \mathbb{Q}$.

Comments - Andrew Furash

You don't provide a characterization for unique readability so you are not able to prove that all wffs exhibit this property.

6 looks good.

……………………………………………………………………………………………………………………………………………………………………………………………………………………

Problem Set 2:

1. Since the set WFF contains only atomic formulas and is closed by application of all quantifiers, negations, and connectors to the atomic formulas, it is a "good" set. Thus, the intersection of all good sets is a subset of WFF. Additionally, we can see that, by nature of the definition of a good set, in that it must include all atomic formulas and be closed under application of the quantifiers, negations, and connectors, every element of WFF is contained in the intersection of all good sets, meaning that the intersection of all good sets is a subset of WFF. And since WFF and the intersection of all good sets are subsets of each other, they are exactly the same set.

2. The primary issue with this set building idea is that it uses circular definitions. Essentially, in order to be "good," a set must include all the WFFs. It makes little sense then to prove that the intersection of all sets S equals WFF because we have basically defined it as so. Rather, we should establish some sort of definition that we have not already stated in order to prove something new and useful.

Comments - Andrew Furash

Nice work here. An inductive argument is needed to show that each wff is in each good set, though.

……………………………………………………………………………………………………………………………………………………………………………………………………………………

Problem Set 1:

Proof:

Consider R, a generic right triangle as described above. With that triangle, consider the diagram below, consisting of four congruent right triangles, R, positioned around a square, H, with side length c:The legs of the right triangles create a polygon, G, which must have only four sides, because the points at which the vertices of square H meet a corner of two triangles R must have an angle of measure 180 degrees, as angles A and B are complimentary and the angle of any corner of square H must be 90 degrees. Therefore, since the four triangles are congruent, we can consider the four-sided polygon, G, created by their legs to be a square, as its corners all measure 90 degrees and its sides all measure a + b.

Thus, the area measured as the sum of the areas of the inscribed polygons equals the area of the outer square.

Thus, $(a+b)^2 = 4(ab/2)+ c^2$. Thus, $(a+b)^2= 4(ab/2)+ c^2$, which implies $a^2+ 2ab + b^2= 2ab + c^2$, and $a^2+ b^2= c^2$.

2a. Theorem: There are infinitely many prime numbers.

Proof: Suppose not. Assume toward contradiction that there exists a finite set of all prime numbers: $P_{n}=\left \{ p_{1},p_{2},...\,, p_{n}\right \}$.

Let $M \epsilon \,\mathbb{N}= \prod _{i=1}^{n} p_{i}$. Consider $N = 1 + M > 1$.

By the Fundamental Theorem of Arithmetic, there must exist some prime $p_{i} \,\epsilon \, P$ such that $(M\mod \,p_{i}) = (N\mod \,p_{i}) = 0$. But, this is impossible, as, for all i, $p_{i} > 1$ and $N – M = 1$.

Thus, by contradiction the set P of all prime numbers cannot be finite.

2b. Algorithm with input n and output PR, a prime greater than n:

Let $P_{n}=\left \{ p_{1},p_{2},...\,, p_{n}\right \}$, the ordered set of all prime numbers.

Algorithm:

(1)Proof:

This algorithm will work for any n, as in order to do so it needs to satisfy two conditions. First, PR(n) must output a number greater than n. In base case n = 1, PR(n) = 3. As n increases by one unit, the value PR - 1 increases by a minimum of a factor of 2. Thus, PR > n for all n.

Second, PR must output a prime. Consider M, the product of all primes less than M. The M modulus any prime number less than M is zero. Since all primes are greater than 1, M + 1 = PR modulus any prime number cannot equal zero. Thus, PR will be prime for all n.