1
$\begingroup$

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!

  • 1
    What do you even mean by saying that two groups are "logically equivalent"?2011-09-19
  • 0
    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).2011-09-19
  • 0
    @Henning Makholm: I'm refering to sets, not groups. Thanks for pointing out the difference. I'm really really new to this :-)2011-09-19
  • 0
    Also, I'm posting from Linux. How do I add math symbols?2011-09-19
  • 0
    @Robert: This has nothing to do with your operating system (a linux user myself), this is called $\LaTeX$, compiled here using the MathJax script.2011-09-19
  • 0
    What is "sentinel logic"? Is that supposed to be "sentential logic" (aka propositional calculus)?2011-09-19
  • 0
    @ArturoMagidin Yes, I mean sentential - just a typo...2011-09-20
  • 0
    This question is not yest answered in terms which I can understand.2018-12-18

2 Answers 2

4

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, 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.

  • 0
    The line for A intersection B isn't displaying correctly.2011-09-19
  • 0
    @Robert: Thanks! I have correct that now.2011-09-19
  • 0
    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?2011-09-20
  • 0
    @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.2011-09-20
  • 0
    תודה רבה אסף, תשובה מעולה2011-09-20
0

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.

  • 0
    "in a sense" is somewhat vague and this answer hasn't been up-voted so I don't know how much to trust it.2018-12-18