7
$\begingroup$

In "$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?" It has been shown that arithmetic shouldn't be included. So the new modified question is:

The analogy of $\wedge,\cap$ and $\vee,\cup$ are seem to be in Logic and Set Theory are seem to be so similar that one might might be forgiven to think they are the same thing but with different notation.

My question is are $\wedge,\cap$ the same thing and just different symbols are being used depending on the framework? same question regarding $\vee,\cup$

What about infinite cases? does this type of intuition break down between Logic and Set theory?

  • 2
    It's spelled `a r i t h m e t i c`; you've tried about three different variations so far...2012-02-19

3 Answers 3

13

In classical logic this is the same thing. This is a direct result from Stone's Representation theorem, which says that every Boolean algebra is isomorphic to a field of sets, where $\lnot$ is complement; $\land$ is $\cap$ and $\lor$ is $\cup$.

Since in classical logic we mainly deal with Boolean expressions, this should hint you enough.

When considering FOL (where free variables apply) and a structure $M$ one can consider $\varphi(x)$ to be a formula, then $\{a\in M: M\models\varphi(a)\}$ is empty if and only if $\forall x\lnot\varphi(x)$; and the set is $M$ if and only if $M\models\forall x\varphi(x)$.

Indeed this is a good way to think about the formulae, as subsets of the universe. In such case it is easy to see that $\land$ is $\cap$ and $\lor$ is $\cup$.


The infinite case is slightly more complicated since classical logic does not permit infinitary disjunctions or conjunctions. If one allows that, then the same reasoning as above applies.

Indeed what is the meaning of $x\in\bigcup_{n=0}^\infty A_n$? It means that for at least one $n$ we have $x\in A_n$. If $A_n =\{a\in M : M\models\varphi_n(a)\}$ then $x\in\bigcup A_n$ is to say that $M\models\left(\bigvee_{n=0}^\infty\varphi_n\right)(x)$. It is important to distinct between things we do within the language (i.e. formulae we can write) and things we do in the meta-language (i.e. things we know are true due to "higher" reasonings).

  • 0
    Take $\mathbb Z$ as a structure for the language $\{\le\}$, you cannot tell what is zero, even or products of exactly three primes, however when examining an element we know (in the external point of view) what is the element and what are the properties of it. On the other hand, if we take $\mathbb Z$ as a model for an ordered ring then the model knows what are even, odds, etc. because the language is strong enough to express it.2012-02-19
4

Yes. Your intuition is correct. $\land , \lor$ and $\cap , \cup$ are isomorphic. Notice that the following is true:

$ \{ x : \phi \land \psi \} = \{ x : \phi \} \cap \{ x : \psi \}$

$\{ x : \phi \lor \psi \} = \{ x : \phi \} \cup \{ x : \psi \} $

Class abstraction can be seen as an isomorphism between $\cap$ and $\land$ and $\cup$ and $\lor$.

The difference? $\cap$ and $\cup$ deal with classes, while $\land$ and $\lor$ deal with propositions.

To answer the second question, with infinite cases, the universal and existential quantifiers are analogous to indexed intersection and union. For example:

$ \bigcap_{x \in A} \{ y : \phi \} = \{ y : \forall x \in A: \phi \} $

$ \bigcup_{x \in A} \{ y : \phi \} = \{ y : \exists x \in A: \phi \} $ (assume that $\phi$ is some function of $x$ and $y$)

4

If you're wondering whether one can completely algebraicize logic and set theory then the answer is yes. For some approaches see the following books: Halmos and Givant, Logic as Algebra, and Tarski and Givant, A formalization of set theory without variables.

  • 0
    @Arjang As an introduction you may find helpful Halmos' Monthly exposition [The Basic Concepts of Algebraic Logic,](http://www.jstor.org/stable/2309396) Amer. Math. Monthly, 63, 6, 363-387.2012-02-19