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.

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?

share|improve this question
1  
It's spelled a r i t h m e t i c; you've tried about three different variations so far... –  Arturo Magidin Feb 19 '12 at 5:49
add comment

3 Answers

up vote 11 down vote accepted

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

share|improve this answer
    
Intresting, so a specific instance of a number that can be written as $2k$ for k some integer, is in the language to say that number is even where as, saying for all k , $2k$ is going to be even is in the meta-language? If I have understood correctly that can be used to use different approaches to proving language statements to proving meta-language statement. –  Arjang Feb 19 '12 at 2:34
    
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. –  Asaf Karagila Feb 19 '12 at 8:22
add comment

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.

share|improve this answer
    
yes, that is what I am really trying to ask, a uniform way to treat one thing rather than two very similar things. Tx –  Arjang Feb 19 '12 at 2:24
    
@Arjang As an introduction you may find helpful Halmos' Monthly exposition The Basic Concepts of Algebraic Logic, Amer. Math. Monthly, 63, 6, 363-387. –  Math Gems Feb 19 '12 at 2:42
add comment

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$)

share|improve this answer
add comment

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.