Question

For any two integers \(m\) and \(n,\) we say \(m\) divides \(n\) if there is an integer \(k\) such that \(n=\) \(m k\). (Many programming languages give easy ways to say that, such as \(n \% m=0\) or \(n\) div \(m=0 .\) ) Define \(D i v(m, n)\) to be \(m\) divides \(n\). Translate each of the following propositions and quantified formulas into a clear English sentence. Label each as being true or false, with the universe as the set \(\mathbb{Z}\). (a) \(\operatorname{Div}(5,7)\) (b) \(\operatorname{Div}(4,16)\) (c) \(\operatorname{Div}(16,4)\) (d) \(\operatorname{Div}(-8,0)\) (e) \(\forall m(\forall n(\operatorname{Div}(m, n)))\) (f) \(\forall n(\operatorname{Div}(1, n))\) (g) \(\forall m(\operatorname{Div}(m, 0))\) (h) \(\forall m(\forall n(\operatorname{Div}(m, n) \rightarrow \operatorname{Div}(n, m)))\) (i) \(\forall m(\forall n(\forall p((D i v(m, n) \wedge \operatorname{Div}(n, p)) \rightarrow \operatorname{Div}(m, p))))\) (j) \(\forall m(\forall n((D i v(m, n) \wedge \operatorname{Div}(n, m)) \rightarrow m=n))\)

Short answer

(a) False; (b) True; (c) False; (d) True; (e) False; (f) True; (g) True; (h) False; (i) True; (j) True.

Step-by-step solution

Evaluating Proposition (a)

The proposition \( \text{Div}(5,7) \) states that 5 divides 7. This means there exists an integer \( k \) such that \( 7 = 5k \). Checking for this, 7 divided by 5 gives 1 with a remainder of 2, not 0. Hence, 5 does not divide 7 and the proposition is False.

Evaluating Proposition (b)

The proposition \( \text{Div}(4,16) \) asks if 4 divides 16. This implies there is an integer \( k \) such that \( 16 = 4k \). Since \( 16 \div 4 = 4 \), which is an integer, 4 divides 16. Therefore, the proposition is True.

Evaluating Proposition (c)

The proposition \( \text{Div}(16,4) \) states that 16 divides 4. This requires there to be an integer \( k \) such that \( 4 = 16k \). Dividing 4 by 16 gives a non-integer quotient of \( \frac{1}{4} \). Hence, 16 does not divide 4 and the proposition is False.

Evaluating Proposition (d)

The proposition \( \text{Div}(-8,0) \) asks if -8 divides 0. For any non-zero integer \( m \), \( m \div 0 \) is undefined. However, 0 can be considered as \( -8 \times 0 \), making \(-8\) a divisor of 0 according to mathematical extension. Thus, this proposition is True.

Evaluating Proposition (e)

The proposition \( \forall m(\forall n(\text{Div}(m, n))) \) claims that every integer divides every other integer, which means for any integers \( m \) and \( n \), there should exist an integer \( k \) such that \( n = mk \). This is clearly false as not all integers divide others evenly (e.g., 5 does not divide 7). Hence, the proposition is False.

Evaluating Proposition (f)

The proposition \( \forall n(\text{Div}(1, n)) \) states that 1 divides any integer \( n \), which means there should be an integer \( k \) such that \( n = 1k \). Since multiplying any integer \( k \) by 1 results in \( k \), this statement is True.

Evaluating Proposition (g)

The statement \( \forall m(\text{Div}(m, 0)) \) is saying every integer divides zero, which implies for any integer \( m \), there exists an integer \( k \) such that \( 0 = mk \). As \( 0 = m \times 0 \) for any \( m \), this is True.

Evaluating Proposition (h)

The statement \( \forall m(\forall n(\text{Div}(m, n) \rightarrow \text{Div}(n, m))) \) claims if \( m \) divides \( n \), then \( n \) divides \( m \). This is not true since this implies a reciprocal relationship (e.g., 4 dividing 16 would mean 16 divides 4, which is incorrect). Thus, the proposition is False.

Evaluating Proposition (i)

The proposition \( \forall m(\forall n(\forall p((\text{Div}(m, n) \wedge \text{Div}(n, p)) \rightarrow \text{Div}(m, p)))) \) claims a transitive property: if \( m \) divides \( n \) and \( n \) divides \( p \), then \( m \) divides \( p \). This holds true under integer arithmetic laws. Therefore, it is True.

Evaluating Proposition (j)

The proposition \( \forall m(\forall n((\text{Div}(m, n) \wedge \text{Div}(n, m)) \rightarrow m=n)) \) suggests that if \( m \) divides \( n \) and \( n \) divides \( m \), then \( m \) must equal \( n \). This is indeed true, as only equal numbers can divide each other without remainder in both directions. Therefore, this proposition is True.

Key concepts

Integer Division

Integer division is the process of dividing one integer by another. In this operation, you get a quotient without a remainder, or you determine that one number does not divide the other evenly. For example, when you divide 16 by 4, the result is 4 with no remainder, meaning that 4 is a divisor of 16.

It’s important to recognize the notation used in discrete mathematics. "Div" function, as in \( \text{Div}(m,n) \), represents that "\( m \) divides \( n \)." This is true if there exists an integer \( k \) such that \( n = mk \). Here are some cases to illustrate:

• \( \text{Div}(4, 16) \): 4 divides 16 because 16 can be expressed as \( 4 \times 4 \).
• \( \text{Div}(5, 7) \): 5 does not divide 7 since there is no integer \( k \) making \( 7 = 5k \).
• \( \text{Div}(-8, 0) \): Any non-zero integer technically divides 0 since \( 0 = m \times 0 \).

These examples illustrate the basic principles of integer division used in mathematical proofs and logical reasoning.

Quantified Propositions

Quantified propositions use logical quantifiers such as "for all" (\( \forall \)) or "there exists" (\( \exists \)) to express statements over a range of numbers or elements. In the study of discrete mathematics, these allow you to explore general truths or properties that hold under specific conditions.

For example, if we consider the expression \( \forall n(\text{Div}(1,n)) \), it asserts that "for every integer \( n \), 1 divides \( n \)." Since multiplying any integer by 1 results in itself, this proposition is universally true.

Contrast this with \( \forall m(\forall n(\text{Div}(m, n))) \), which claims that every integer \( m \) divides every integer \( n \). This is false as demonstrated by the non-divisibility of 5 by 7.
Quantified propositions are powerful in formal argument techniques and mathematical proofs, clarifying the scope and truth of statements.

Logical Reasoning

Logical reasoning involves using a well-defined sequence of steps to reach a conclusion. In discrete mathematics, propositions are evaluated to be true or false by applying logical operations like "and", "or", "not", "implication", and more.

Consider the proposition \( \forall m(\forall n(\text{Div}(m, n) \rightarrow \text{Div}(n, m))) \). This suggests that if \( m \) divides \( n \), then \( n \) should divide \( m \) too. However, this logic falls apart because, for example, 4 divides 16, but 16 does not divide 4.

Logical reasoning also helps in understanding transitive properties, like in the proposition \( \forall m(\forall n(\forall p((\text{Div}(m, n) \wedge \text{Div}(n, p)) \rightarrow \text{Div}(m, p)))) \). It concludes the truth of a statement based on the relationships of divisibility between three numbers, highlighting a transitive sequence.

Mathematical Proofs

Mathematical proofs provide a structured approach to confirm whether a proposition is true or false. They are critical in establishing facts in mathematics through logical deductions and verified results.

To illustrate, let's analyze the proposition \( \forall m(\forall n((\text{Div}(m, n) \wedge \text{Div}(n, m)) \rightarrow m = n)) \). This proof argues that if \( m \) divides \( n \) and \( n \) divides \( m \), then \( m \) and \( n \) must be equal. This is true because such mutual divisibility without remainder is only possible when both numbers are the same.

Mathematical proofs begin with assumptions and proceed through logical deductions, using known axioms or previously proven statements to finally reach the conclusion. Writing proofs accurately is an essential skill in discrete mathematics, demanding clarity of logic and precision of detail.