Predicate Logic and Relations on sets

[kurona]

Homework Statement

Here are a few questions from an exercise sheet that I need help on. I really don't have a clue on how to start them. Could anyone help me attempt at each a) for each question?

1. Use (nested) quantifiers (∀ and ∃) (and propositional junctors) and only equality ``='', conventional ordering ``≤'', ``<'', etc., and divisibility ``|'' as predicates, and arithmetic operators as functions to express the following statements as predicate logic formulae:
a)**“Exponentiation on reals distributes over multiplication to the left.”
b)**“Each positive real number has a logarithm.”
c)**“Exponentiation on reals has no left identity.”
d)**“Any two natural numbers have a least common multiple.”
e)**“There are infinitely many primes. (I.e., for each natural number, there is a prime number above it.)”
f)**“Each Pythagorean triple involves at least one even number.”

2. Assume that Q and R are relations on a set A. Prove (using relation-algebraic calculations) or disprove (by providing counterexamples) each of the following statements.
a)**If Q and R are both reflexive, then Q ∩ R is reflexive, too.
b)**If Q and R are both reflexive, then Q ∪ R is reflexive, too.
c)**If Q and R are both transitive, then Q ; R is transitive, too.
d)**If Q and R are both symmetric, then Q ∩ R is symmetric, too.
e)**If Q and R are both transitive, then Q ∪ R is transitive, too.
f)**If Q is symmetric, then Q ; Q is symmetric, too.

The Attempt at a Solution

1a) ∀x∀y∀z((xy)z = xzyz | x,y,z ∈ ℝ)
2a) not sure how to start...

Many thanks.

 

[mighty2000]

Hello there, I am happy to help with your questions. Let's take a look at each of them and see if we can come up with some solutions together.

1a) To express the statement "Exponentiation on reals distributes over multiplication to the left" in predicate logic, we can use the following formula:

∀x∀y∀z((xy)z = xzyz)

This formula states that for any real numbers x, y, and z, if we multiply x and y and then raise the result to the power of z, it will be equal to the result of raising x to the power of z and then multiplying it by y raised to the power of z. This is the definition of left distribution for exponentiation on reals.

1b) To express the statement "Each positive real number has a logarithm" in predicate logic, we can use the following formula:

∀x∃y(x > 0 ∧ y > 0 ∧ xy = 1)

This formula states that for every positive real number x, there exists a positive real number y such that when we multiply x and y, the result is equal to 1. This is the definition of a logarithm.

1c) To express the statement "Exponentiation on reals has no left identity" in predicate logic, we can use the following formula:

∀x∃y(x ≠ 0 ∧ xy ≠ x)

This formula states that for every real number x, there exists a real number y that is not equal to 0 and when we multiply x and y, the result is not equal to x. This means that there is no real number that can serve as a left identity for exponentiation.

1d) To express the statement "Any two natural numbers have a least common multiple" in predicate logic, we can use the following formula:

∀x∀y∃z(z ≥ x ∧ z ≥ y ∧ x|z ∧ y|z ∧ ∀w(w ≥ z ∧ x|w ∧ y|w → z ≤ w))

This formula states that for any two natural numbers x and y, there exists a natural number z that is greater than or equal to both x and y, and is divisible by both x and y. Furthermore, for any other natural number w that is also divisible by x and y, z is the smallest possible value for w. This is the definition of a least common