After learning how quantified statements become true or false, we now compare predicates over a common universe. Logical equivalence and implication of predicates extend familiar propositional ideas to open statements. Two predicates are equivalent when they agree for every element; one predicate implies another when the first being true always forces the second. In this lesson, logical equivalence and implication of predicates will be proved through universal statements. :::definition[Logically Equivalent Predicates] Let $p(x)$ and $q(x)$ be open statements over the same universe. The predicates $p(x)$ and $q(x)$ are called logically equivalent if $$\begin{equation*} \forall x[p(x)\leftrightarrow q(x)] \end{equation*}$$ is true. In this case, $p(x)$ and $q(x)$ have the same truth value for every element of the universe. ::: :::definition[Logical Implication of Predicates] Let $p(x)$ and $q(x)$ be open statements over the same universe. The predicate $p(x)$ logically implies $q(x)$ if $$\begin{equation*} \forall x[p(x)\to q(x)] \end{equation*}$$ is true. This means that whenever $p(x)$ is true, $q(x)$ is also true. ::: :::theorem[Biconditional as Two Predicate Implications] For predicates $p(x)$ and $q(x)$ over the same universe, $$\begin{equation*} \forall x[p(x)\leftrightarrow q(x)] \end{equation*}$$ is equivalent to $$\begin{equation*} [\forall x[p(x)\to q(x)]]\land[\forall x[q(x)\to p(x)]]. \end{equation*}$$ ::: :::proof Given that $p(x)$ and $q(x)$ are predicates over the same universe. To prove that $\forall x[p(x)\leftrightarrow q(x)]$ is equivalent to $[\forall x[p(x)\to q(x)]]\land[\forall x[q(x)\to p(x)]]$. For any element $a$ in the universe, $p(a)\leftrightarrow q(a)$ is true exactly when both $p(a)\to q(a)$ and $q(a)\to p(a)$ are true. Therefore, the biconditional holds for every element exactly when both implications hold for every element. Hence the stated equivalence holds. $\square$ ::: :::example[Equiangular and Equilateral Triangles] Let the universe be the set of all triangles in the plane. Let $p(x):x$ is equiangular and $q(x):x$ is equilateral. For triangles in the plane, $p(x)$ and $q(x)$ are logically equivalent. Therefore, $$\begin{equation*} \forall x[p(x)\leftrightarrow q(x)] \end{equation*}$$ is true. ::: :::solved-problem Let the universe be the set of all integers. Let $p(n):n$ is odd and $q(n):n^2$ is odd. Show that $p(n)$ and $q(n)$ are logically equivalent. ::: :::solution Given that the universe is the set of all integers. To prove that $p(n)$ and $q(n)$ are logically equivalent, we prove $$\begin{equation*} \forall n[p(n)\leftrightarrow q(n)]. \end{equation*}$$ This is equivalent to proving both $\forall n[p(n)\to q(n)]$ and $\forall n[q(n)\to p(n)]$. First suppose $n$ is odd. Then there exists an integer $k$ such that $n=2k+1$. Therefore, $$\begin{align*} n^2&=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{align*}$$ Hence $n^2$ is odd. Conversely, suppose $n^2$ is odd. If possible let $n$ be even. Then $n=2k$ for some integer $k$, and hence $$\begin{equation*} n^2=4k^2=2(2k^2), \end{equation*}$$ which is even. This contradicts the assumption that $n^2$ is odd. Therefore $n$ is odd. Hence $\forall n[p(n)\leftrightarrow q(n)]$. $\square$ ::: For predicates, the statement $\forall x[p(x)\to q(x)]$ says that $p(x)$ is sufficient for $q(x)$ and $q(x)$ is necessary for $p(x)$. The reverse implication $\forall x[q(x)\to p(x)]$ says the opposite direction. When both directions hold, each condition is necessary and sufficient for the other. Students often confuse these phrases, so it is safer to translate them into implications first. :::exercise Let $p(n):n$ is odd and $q(n):n^2$ is odd over the integers. Determine which statements express $q(n)\to p(n)$: if the square of any integer is odd, then the integer is odd; $p(n)$ is necessary for $q(n)$; the square of any odd integer is odd; given any integer whose square is odd, that integer is odd; $\forall n[\neg p(n)\to\neg q(n)]$. ::: :::answer The first, second, fourth, and fifth statements express $q(n)\to p(n)$. The third statement expresses $p(n)\to q(n)$. The statement $\forall n[\neg p(n)\to\neg q(n)]$ is the contrapositive of $q(n)\to p(n)$. ::: :::faq[Frequently Asked Questions] Q: When are two predicates logically equivalent? A: They are equivalent when they have the same truth value for every element in the universe. Q: What does predicate implication mean? A: It means every element satisfying the first predicate also satisfies the second. Q: Why prove two implications for equivalence? A: A biconditional is true exactly when both directions of implication are true. ::: :::call-to-action[Prove Predicate Equivalence] subtitle: Practise proving both directions before studying converse, inverse, and contrapositive forms. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/converse-inverse-and-contrapositive-of-quantified-implications button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/truth-conditions-for-quantified-statements :::