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.

While doing work on propositional logic (namely, proving the Generalized De Morgan's Laws), I found myself wondering why precisely an infinite conjunction or disjunction are not permitted, due to the fact that in predicate logic (also a finitary logic), quantification over domains of discourse with infinite size are allowed. Using the definition of the existential and universal quantifiers as: $ \exists( x \in X) P(x) \Leftrightarrow \bigvee_{x_i \in X}{P(x_i)} $ and $\forall (x \in X)P(x) \Leftrightarrow \bigwedge_{x_i \in X}{P(x_i)} $, along with the duality of the quantifiers (namely $ \neg\exists x P \Leftrightarrow \forall x \neg P $ and $ \neg\forall x P \Leftrightarrow \exists x \neg P $), does this not imply that 1) infinite conjunctions and disjunctions must be allowed in order to quantify over infinite domains and 2), at least in predicate logic, De Morgan's Laws hold for the infinite case? Thanks

share|improve this question
    
Infinitary disjunctions are permited in geometric logic, which is the natural internal logic of Grothendieck toposes and geometric morphisms. De Morgan's law fails here, but that is because it fails already in the finitary fragment of geometric logic (called coherent logic). –  Zhen Lin Mar 23 '12 at 16:26
add comment

2 Answers

up vote 2 down vote accepted

If this doesn't completely answer your question, I can expand it later if you ask a followup in a comment. The simple answer is just that there's a difference between letting a formula have infinite length and letting the interpretation (and truth-value) of a formula depend on infinitely many assignments. You make a clear split between (i) the formal language and its deductive system as just mechanical manipulations of meaningless strings of symbols, (ii) the structures that you interpret the language to be talking about, and (iii) the way that the interpretations (mappings from (i) to (ii)) themselves work. Very generally/vaguely, restricting things to be finite should keep things simpler. This seems reasonable, yes? So there might be advantages to confining the infinite bits to one or two of the above steps. It turns out that this does make a difference, and this is one thing that introducing quantifiers allows you to do.

To answer your questions more directly:

(1) Yes, in some sense, but where these infinite things are and how precisely they are infinite (i.e., what their structure is) is another matter. In FOL, they are relegated to the metalanguage and metatheory.

(2) This seems like a reasonable way to think of things, but it depends on the details of what you mean. De Morgan's laws are about relationships between the logical operators, and the operators are exactly the same in propositional and predicate/first-order logic. De Morgan's laws do hold in FOL -- they're exactly the same as in propositional logic. If you want to point out a relationship among the concepts of negation, conjunction, and disjunction that we use in the different steps above (in the object language and metalanguage) and how they relate to quantification, then yes, you seem to have the right idea. The reason that the existential and universal quantifiers are related in the way that you point out is because of how negation, conjunction, and disjunction are related in the metatheory. But you might be able to trace this idea back to Aristotle and company.

Cheers, Rachel

Edit to answer comment: Yes, the distinction between finitary and infinitary logics usually has to do with the formal language and formal deduction part. You can allow formulas or proofs (or both) of infinite length.

The same distinction between formal, syntactic types of things and meaningful, semantic types of things is also applied to propositional logic. It is not always brought to everyone's attention when studying propositional logic because it's a simpler system, and the pieces are related in a way that makes the distinction not of much consequence. The thing to note is that the same steps are happening in propositional logic, but humans don't need to be told how to do them because using natural language has already taught them how to do this mapping between form and meaning. It's more like natural language has made the steps invisible, and they need to be pointed out. Well, also, people don't consciously know how they use natural language, and that is where the work is -- to make these things explicit.

If you're interested in logic and a bit of model theory, two very good books are Hodges' Logic and Machover's Set theory, logic, and their limitations. Hodges is incredibly funny and insightful, and Machover is very good about pointing out clearly and thoroughly the relationships just touched on.

share|improve this answer
    
Thanks, that clears things up. I had a feeling that it had to do with the fact that predicate logic had additional structure to it, so to speak, but didn't know the specifics of it. So I take it that when we say that a logic is finitary that it refers to the length of formulas, rather than the assignment of interpretations, which is why this is allowed to work? –  Hayden Mar 23 '12 at 20:27
    
@Hayden, My reply was longish, so I edited it in above. –  Rachel Mar 23 '12 at 20:58
    
thanks again, that was very insightful. And yes, I'll keep that in mind. Right now I'm reading Wolfe and then Mendelson. Wolfe is a nice intro, but isn't extremely thorough or rigorous, so I've been using a lot of graduate texts to supplement it. –  Hayden Mar 24 '12 at 16:10
    
@Hayden, I'm not familiar with Wolfe. If you don't already have Mendelson and can handle graduate texts, check out Shoenfield before getting Mendelson. And you might also still like Machover. –  Rachel Mar 25 '12 at 8:04
add comment

This is not really an answer, but I thought I would talk a little bit about one class of logics that are related to the question.

One class of logics which allow infinite conjunctions/disjunctions are Infinitary Logics. These logics specify the number of conjunctions/disjunctions allowed, and also the number of quantifiers allowed. In short, given infinite cardinals $\kappa, \lambda$ the logic $L_{\kappa\lambda}$ allows for the following infinitary constructions:

  • If $\delta < \kappa$ and $\{ \phi_\xi : \xi < \delta \}$ is a family of formulas, then $\bigvee_{\xi < \delta} \phi_\xi$ and $\bigwedge_{\xi < \delta} \phi_\xi$ are formulas;
  • If $\epsilon < \lambda$ and $\{ x_\xi : \xi < \epsilon \}$ is a family of individual variables, then given any formula $\phi$ the expressions $( \forall x_0 \ldots x_\xi \ldots ) \phi$ and $( \exists x_0 \ldots x_\xi \ldots ) \phi$ are formulas.

(In this formulation, $L_{\omega\omega}$ is the standard (finitary) first-order logic.) (There are also "unbounded versions" where $\kappa$ or $\lambda$ may be $\infty$, meaning unrestricted lengths of conjunctions/disjunctions or quantifiers, respectively.)

The infinitary de Morgan's Laws should be theorems in any formal axiomatization, and are likely to be taken as axioms themselves. However, these logics are often unsuitable from a "practical" standpoint.

  • Only $L_{\omega\omega}$ and $L_{\omega_1\omega}$ satisfy the following Completeness property: if a sentence $\phi$ is true in every model, then $\phi$ is a theorem.
  • Given $\kappa > \omega$, natural extensions of the Compactness Theorem for $L_{\kappa\kappa}$ fails except when $\kappa$ is a large cardinal.
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.