8
$\begingroup$

Here is my proof. My instructor claims that it is invalid because I did not use a set membership table, and that the use of a predicate logic truth table is invalid.

That makes no sense to me. If I can do S := { x | P(x) }, then I should obviously be able to use predicate logic on the members of sets!

Given 2 sets A and B such that A ∩ B = A ∪ B, what can be concluded about A and B?

A ∩ B = A ∪ B                                                           restatement

∀x(x ∈ A ∩ B ↔ x ∈ A ∪ B)                                               definition of set equality

∀x(x ∈ A ∧ x ∈ B ↔ x ∈ A ∨ x ∈ B)                                       set membership distributed over union and intersection

p(x) := x ∈ A

q(x) := x ∈ B

p    q    p ∧ q    p ∨ q    p ∧ q ↔ p ∨ q    p ↔ q

T    T      T        T            T            T

T    F      F        T            F            F

F    T      F        T            F            F

F    F      F        F            T            T

∀x(x ∈ A ↔ x ∈ B)                                                        logical equivalence (p ↔ q ≡ p ∧ q ↔ p ∨ q)

∀x(x ∈ A → x ∈ B ∧ x ∈ B → x ∈ A)                                        logical equivalence (p → q ∧ q → p ≡ p ↔ q)

∀x(x ∈ A → x ∈ B) ∧ ∀x(x ∈ B → x ∈ A)                                    universal quantifier distributed over conjunction

A ⊆ B ∧ B ⊆ A                                                            definition of subset

A = B                                                                     definition of set equality

We see that the sets A and B are equal. A and B may both be the empty set.

So, is my proof valid?

Edit: after further reflection, I think the point of contention may be the use of a truth table to demonstrate logical equivalence over an infinite domain. This proof may not be valid for infinite sets. I could instead demonstrate the logical equivalence p ↔ q ≡ p ∧ q ↔ p ∨ q another way.

$\endgroup$
  • $\begingroup$ In any argument with an instructor, the instructor always wins. $\endgroup$ – Somos Jun 15 at 21:55
  • 1
    $\begingroup$ @Somos: If that is so, then that instructor is a stupid and lousy one. $\endgroup$ – user21820 Jun 16 at 7:07
  • 1
    $\begingroup$ Your conclusions are not mutually exclusive. $\endgroup$ – okovko Jun 16 at 7:23
  • 2
    $\begingroup$ @JohnColeman She claimed that the proof is not rigorous, in exact terms. In direct quote, "you adapted and tried to use a truth table for predicates which you can't do." $\endgroup$ – okovko Jun 16 at 21:56
  • 1
    $\begingroup$ @SolomonUcko Thanks, I was just using the exact equivalences presented in my textbook (Rosen, 7th ed.). The section about demonstrating set equivalence explicitly asks to demonstrate mutual subsets. But I also used the definition you just mentioned as my first step, which was also in the book. Good point, the proof should be shorter. This is my first logic class, if it is not obvious :P $\endgroup$ – okovko Jun 16 at 21:58
9
$\begingroup$

Your reasoning is perfectly valid. At the point where you use a truth table to show a propositional equivalence you're already looking at one particular $x$ (at a time), so the possibilities you need to consider are just the for rows of your table.

Formally, once you have established the propositional equivalence $$ (p\land q)\leftrightarrow(p\lor q) \quad\equiv\quad p\leftrightarrow q $$ you're now allowed to substitute anything for $p$ and $q$, and it will be a valid equivalence -- even predicate-logic formulas.


(It is a bit the long way around, though. It's faster to see $$ A \subseteq A \cup B = A \cap B \subseteq B $$ and vice versa, so $A\subseteq B$ and $B\subseteq A$, and therefore the sets are equal).

$\endgroup$
  • $\begingroup$ "At the point where you use a truth table to show a propositional equivalence you're already looking at one particular x (at a time), so the possibilities you need to consider are just the for rows of your table." I thought so too. As long as the domain is countable, even if it infinite, then it should be valid to inspect every truth table over every x. $\endgroup$ – okovko Jun 15 at 21:12
  • $\begingroup$ Oh, so if I demonstrate (p∧q)↔(p∨q)≡p↔q for propositional logic, then it is valid for use in any predicate logic substitution? $\endgroup$ – okovko Jun 15 at 21:13
  • $\begingroup$ @okovko: Yes, exactly. (In the usual development of mathematical logic, this is the primary reason to care about propositional logic at all: We can use it to prove a certain kind of "easy" truths in predicate logic, which is what we're really after). $\endgroup$ – Henning Makholm Jun 15 at 21:15
  • 1
    $\begingroup$ @okovko: In that question the asker seemed to be asking for a truth-table-like method to prove formulas whose validity depends on looking about the relation between the parts of the formula that is inside/outside of a quantifier. Such formulas can't be gotten by substituting into a propositional tautology. So the point there was not that it is invalid to substitute predicate formulas for a psopositional tautology -- merely that it doesn't do the more complex job the asker there wanted and can't realy be extended to do so. $\endgroup$ – Henning Makholm Jun 15 at 22:09
  • 1
    $\begingroup$ @okovko: Concerning your question about the linked post, in general truth-tables are insufficient to handle first-order logic (aka predicate logic). One needs inference rules or axioms to handle quantifiers. Indeed, if you look at the Fitch-style proof I gave you, we use one quantifier-rule (∀-intro) at the end, to get from the inner proof of "$x∈A ⇔ x∈B$" under the context of any given object $x$, to the outer conclusion of "$A = B$". $\endgroup$ – user21820 Jun 16 at 7:35
5
$\begingroup$

Your proof is fine. That you have shown $(x\in A\land x\in B)\iff(x\in A\lor x\in B)$ is equivalent to $(x\in A)\iff(x\in B)$ extends to all $x$ with no problem; if $\phi(x)$ is equivalent to $\psi(x)$, $\forall x(\phi(x))$ is equivalent to $\forall x(\psi(x))$.

$\endgroup$
  • $\begingroup$ What about this? It looks like my proof is only valid for finite sets. $\endgroup$ – okovko Jun 15 at 21:10
  • 1
    $\begingroup$ @okovko No, your proof is perfectly OK whether the sets are finite or infinite. Your argument applies to every $x$, no matter how many $x$'s there might be. $\endgroup$ – Andreas Blass Jun 15 at 22:11
2
$\begingroup$

Let me show you a Fitch-style proof corresponding to your (correct)reasoning, to make sure you understand why it is valid:


Given any sets $A,B$ such that $A∩B = A∪B$:

  Given any object $x$:

    $x∈A∩B ⇔ x∈A∪B$.

    Thus $x∈A ∧ x∈B ⇔ x∈A ∨ x∈B$.

    Let $P :≡ x∈A$.

    Let $Q :≡ x∈B$.

    Then $P∧Q ⇔ P∨Q$.

    Thus $P ⇔ Q$.   [by the truth-table you gave]

    Thus $x∈A ⇔ x∈B$.

  Therefore $A = B$.


Note that you perform the same reasoning for any given object $x$, so even though the $P,Q$ in the above proof may differ in truth-value for different $x$, it still holds in every case that $P ⇔ Q$, and hence you get the conclusion you seek. If your instructor cannot understand this, ask him/her to give you any sets $A,B$ such that $A∩B = A∪B$ and any object $x$ and explicitly follow the proof to show (by a single use of the truth-table) that $x∈A ⇔ x∈B$. If it is clear that he/she cannot prevent your conclusion no matter what $A,B,x$ he/she gives you, then you have won. (This is called game semantics, by the way, and I recommend you think of quantifiers this way to fully grasp the meaning of order of quantification.)

$\endgroup$
  • $\begingroup$ If you could share a source for Fitch-style proofs, that would probably help my case. $\endgroup$ – okovko Jun 16 at 7:27
  • $\begingroup$ @okovko: I don't have a good online reference for it, and the one I wrote is intentionally brief. The main point is that if you have a propositional logic proof from "$P∧Q ⇔ P∨Q$" to "$P ⇔ Q$", then you can insert that in-between those two steps in the above proof. And if anyone doesn't like the use of extra propositional variables $P,Q$, you can replace them everywhere by "$x∈A$" and "$x∈B$" respectively. Anyway I'm a logician; is that good enough for a reference? =) $\endgroup$ – user21820 Jun 16 at 7:32
  • $\begingroup$ Well, you have stoked my critical thinking fire and taught me, so I very much appreciate your time and energy. Unfortunately, there is probably no way to change my instructor's mind. In particular, understanding why my proof is correct has changed my perspective on logic in a fundamental and insightful way. Thank you! $\endgroup$ – okovko Jun 16 at 7:50
  • $\begingroup$ @okovko: I'm very glad you fully understand the logical reasoning involved here, so you're welcome! If you have any future questions you can find me in chat. $\endgroup$ – user21820 Jun 16 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.