# Homework Help: Predicate Logic and Relations on sets

1. Mar 14, 2009

### kurona

1. The problem statement, all variables and given/known data

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.

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

Many thanks.