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!

  • 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
    תודה רבה אסף, תשובה מעולה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