Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm just getting started with sentential logic and set theory in Discrete Math.

I'd learned that to show two sets equal, say $A$ and $B$, you show $A$ is a subset of $B$ and that $B$ is a subset of $A$. But is it also possible to show that the sets are equal by showing that they are logically equivalent? Or is that comparing apples and oranges?

Basically, is showing $A \equiv B$ the same as $A = B$ ?

If my question isn't clear I can add an example of what I'm talking about.

Thanks!

share|improve this question
1  
What do you even mean by saying that two groups are "logically equivalent"? –  Henning Makholm Sep 19 '11 at 12:55
    
And are you sure you really mean "groups" here, rather than sets? (A group is a set together with an associative binary operation that has an identity element and inverses for all elements). –  Henning Makholm Sep 19 '11 at 12:57
    
@Henning Makholm: I'm refering to sets, not groups. Thanks for pointing out the difference. I'm really really new to this :-) –  Robert S. Barnes Sep 19 '11 at 13:23
    
Also, I'm posting from Linux. How do I add math symbols? –  Robert S. Barnes Sep 19 '11 at 13:24
    
@Robert: This has nothing to do with your operating system (a linux user myself), this is called $\LaTeX$, compiled here using the MathJax script. –  Asaf Karagila Sep 19 '11 at 13:51

2 Answers 2

up vote 3 down vote accepted

We start in a given model in which we consider the sets $A,B$.

Suppose $A=\{x\mid\varphi(x)\}$, and $B=\{x\mid\psi(x)\}$. That is $A$ and $B$ are sets defined as all the elements with property $\varphi$ or $\psi$.

Note the following things:

  1. $A\cup B=\{x\mid x\in A\lor x\in B\} = \{x\mid\varphi(x)\lor\psi(x)\} = \{x\mid\big(\varphi\lor\psi\big)(x)\}$

  2. $A\cap B=\{x\mid x\in A\land x\in B\} = \{x\mid\big(\varphi\land\psi\big)(x)\}$

  3. $A^c = \{x\mid x\notin A\} = \{x\mid\lnot\varphi(x)\}$

  4. $A\setminus B=\{x\mid x\in A\land x\notin B\} = \{x\mid\big(\varphi\land\lnot\psi\big)(x)\}$

  5. $A\subseteq B$ means $x\in A\rightarrow x\in B$, that is $\varphi(x)\rightarrow\psi(x)$, similarly to before $\big(\varphi\rightarrow\psi\big)(x)$.

We can formulate logical equivalence as: $$\varphi\leftrightarrow\psi\iff(\varphi\rightarrow\psi)\land(\psi\rightarrow\varphi)$$

From this and the list above we reach the following conclusion:

$$\{x\mid\varphi(x)\} = \{x\mid\psi(x)\}\iff\varphi\leftrightarrow\psi$$

Of course all the above is true in the context of a given model. The formulas might not be equivalent in a different interpretation.

For example, let $\mathcal L=\{<,a\}$ be a language with a binary relation $<$ and a constant $a$. (We of course include $=$ as well)

Now consider $\varphi(x) = a<x$, and $\psi(x) = \lnot(x=a)$.

  1. Take the model of $\mathbb N$, interpret $a=0$ and $<$ as the usual ordering. We have that $\{x\in\mathbb N\mid\varphi(x)\} = \{x\in\mathbb N\mid\psi(x)\}$, since in $\mathbb N$ being greater than $0$ is the same as being nonzero.

  2. Take the model of $\mathbb Z$, interpret $a$ and $<$ as before. Now $\{x\in\mathbb Z\mid\varphi(x)\}\subsetneqq\{x\in\mathbb Z\mid\psi(x)\}$, since $-1$ is nonzero, but not positive either.


A final word, of utter importance (I think) is that in general there can be much more sets than formulae, therefore some sets cannot be described by a formula. To add on that the whole process of showing logical equivalence above is pretty much the same amount of work as to show the two sided inclusions this brings one important moral: Two sided inclusion is a safe way to show equality of sets in a general setting.

share|improve this answer
    
The line for A intersection B isn't displaying correctly. –  Robert S. Barnes Sep 19 '11 at 15:13
    
@Robert: Thanks! I have correct that now. –  Asaf Karagila Sep 19 '11 at 15:22
    
2 Questions: Showing logical equivalence means showing the condition for inclusion in each set results in the same set of members, and this depends on the model in use? So 2 sided inclusion can work in any general case, but logical equivalence may or may not work depending on the model in use? –  Robert S. Barnes Sep 20 '11 at 8:44
    
@Robert: Logical equivalence is to show that under certain assumptions two sentences are equivalent. Different models may have different properties which imply the assumptions are different. The inclusion is a relatively "safer" way to work with. –  Asaf Karagila Sep 20 '11 at 9:04
    
תודה רבה אסף, תשובה מעולה –  Robert S. Barnes Sep 20 '11 at 9:09

The truth is that $(A\subseteq B \land B\subseteq A) \leftrightarrow (\forall x(x\in A \leftrightarrow x\in B))$. On the right side you see the logical equivalence $\leftrightarrow$, not equivalence of sets, but equivalence of logical formulas that say that $x$ belongs to a set. Yes, in a sense you can prove equality of sets by proving logical equivalence.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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