Propositional Logic -- expressing in formal logic notataion

[QuietMind]

Homework Statement

Problem from a discrete structures online open course. I don't have the answers and was quite confused about this unit, so I was hoping to check my work/ clarify a few questions.

Problem 5.5. Express each of the following predicates and propositions in formal logic notation. The domain of discourse is the nonnegative integers, N. Moreover, in addition to the propositional operators, variables and quantifiers, you may define predicates using addition, multiplication, and equality symbols, but no constants (like 0, 1,. . .) and no exponentiation (like $x^y$). For example, the proposition “n is an even number” could be written (
$\exists{m}. (m+m=n)$
a) n is the sum of two fourth-powers (a fourth-power is $k^4$ for some integer k).

Since the constant 0 is not allowed to appear explicitly, the predicate “x = 0” can’t be written directly, but note that it could be expressed in a simple way as: x + x = x. Then the predicate x > y could be expressed
∃w. (y + w = x) ∧ (w $\neq$ 0).

Note that we’ve used “w $\neq$ 0” in this formula, even though it’s technically not allowed. But since “w $\neq$ 0” is equivalent to the allowed formula “¬(w + w = w),” we can use “w $\neq$ 0” with the understanding that it abbreviates the real thing. And now that we’ve shown how to express “x > y,” it’s ok to use it too. (

b) x = 1.

(c) m is a divisor of n (notation: m | n) (

d) n is a prime number (hint: use the predicates from the previous parts)

(e) n is a power of 3.

Homework Equations

None
I used $\wedge for AND and \vee for or$.
I personally prefer writing out the word but I wanted to keep it consistent with the question

The Attempt at a Solution

One thing I'm unclear about is when I have to "define" a new variable. If the question states "x=1" for example, am I correct in that I don't have to define x, but must define anything else I use with a $\exists{} or \forall{}$ symbol?I personally prefer writing out the word but I wanted to keep it consistent with the question
a)
Since exponentiation is not allowed, I try to do this with just multiplication and addition. I introduce my two arbitrary variables k and l
$\exists{k}\exists{l}. (k*k*k*k+l*l*l*l=n)$

b)
I think I came up with two ways to do this? The first is a two step approach:
Division(x,y) is "given by"
$\exists{w}. (x=wy)$

Then I divide a value by itself,
$\exists{w}. (x=Division(w,w)) \wedge(\neg{(w+w=w)}))$Is that considered cheating in the world of propositional logic? I had to write this explicitly in one step, my best attempt would be
$\exists{w}. (w=wx)\wedge(\neg(w+w=w))$

c) $\exists{u} . (n=um)\wedge( \neg(u+u=u))$
if n is 0 the logic will claim m is a factor unless I say that u can't be 0

d)
I'll try to reuse part c and a. The question seems to indicate it's ok to reuse stuff once you've defined it:
$\neg\exists{u}. ($u is divisor of n$) \wedge (u\neq 1 \wedge u\neq n)$

So it's saying there does not exist an u such that: u is a factor of n, and u is not 1 and not n.

e) I think I need to start by accessing the number 3. I also use part b, so that I'm allowed to set something equal to 1

$\exists{a}\exists{b}\exists{c}. (b=ba)\wedge(b\neq0)\wedge(c=a+a+a)$
so c=3.

$\forall{u}. ($u is a divisor of n$) \wedge (u=1 \vee ($c is a divisor of u$))$

my logic is that every factor of n must itself be a divisible by 3, unless that factor is 1.

 

[andrewkirk]

For (b) your only quantifier is 'exists' $\exists$. Recall the definition of the identity element in a field or ring, eg here. That definition contains an 'exists' but that's because it's asserting the existence of a multiplicative identity element. Your proposition is a bit different, because it's referring to a specified element $x$ and claiming that it is an identity element. How would you change the definition in the link to a statement that $x$ is an identity element? The 'exists' bit would disappear but there's another quantifier there that won't.

 

[andrewkirk]

if n is 0 the logic will claim m is a factor unless I say that u can't be 0

I don't think you need the second part. In my algebra books every number is considered to be a divisor of zero. That is $\forall m:\ m|0$. Note that if $n\neq 0$ then $u=0$ will not divide it anyway, so there's no need to exclude $u=0$.

e) I think I need to start by accessing the number 3. I also use part b, so that I'm allowed to set something equal to 1

$$\exists{a}\exists{b}\exists{c}. (b=ba)\wedge(b\neq0)\wedge(c=a+a+a)$$
so c=3.

That doesn't say c=3, because the variable symbol c is quantified in the formula and so has no meaning outside the scope of the quantification. To assert c=3 we need to write an expression in which c is not quantified.

$\forall{u}. ($u is a divisor of n$) \wedge (u=1 \vee ($c is a divisor of u$))$

This says, amongst other things, that $n$ is divisible by every number. As discussed above, that means that $n=0$. The problem is that one of the logical connectors used in the formula is not the right tool for this job. A different logical connector is needed.

 

[QuietMind]

For b)
$\forall{w}. (w=wx)$

I think that makes more sense, but wouldn't what I originally had for b also work?
If there exists a w that is not 0, and w=wx, wouldn't x have to be 1?

For e)
I was trying to imply a "substitution" of sorts, but if it has no meaning outside the scope of the quantification, I take it that means I need to combine the two statements for e)? I would have put the logic into the bottom equation, but I was more concerned about the rest of the logic.

For the second statement, I'm wondering if I've written down what I meant to say.
I am trying to say say: for all divisors (u) of n, that divisor is either 1 or that divisor itself has 3 as a divisor.

Is the $\forall$ statement reasonable? Here is my next attempt
$\forall{u}. ($u is a divisor of n$) IMPLIES (u=1 \vee(u=3))$
(for the sake of focusing on this piece I just went ahead and used the 3)

I'm shaky on how to think about this kind of logic. My understanding is that if n is a power of 3, then that means that the predicate must be true for all nonnegative integers u, correct? I want to use imply because for the values of u where u is not a divisor of n, then IMPLY evaluates to True. But if u has a value such that the first statement is true, and the second is false, then n is not a valid power of 3, which I think is what I want.

 

[andrewkirk]

@QuietMind Re (b): Yes, if you are allowed to assume the axioms of arithmetic then what you wrote for (b) is fine, as we can prove using those axioms that the only number x that satisfies your formula is 1.

Re (e) and other bits: the usual strategy for writing a formula that identifies a particular constant and then uses that constant in another formula is to write: $\forall x:\ P(x)\to Q(x, y, z,...)$ where $P(x)$ specifies the property that uniquely identifies $x$ (note that $x$ must not be quantified in $P$, ie it must be what we call a free variable), and $Q$ is the formula in which you want to use that constant, with $y,z,...$ being the other variables you want to use in that formula. It's good to think for a while about why that structure works, as people often find it unintuitive.

Your revised structure for (e) should work.