Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite logic

  1. Apr 21, 2005 #1
    Hi! I've problem proving a logical statement. I really can nothing about logic. I just messing around with some in a try to prove another theorem.

    Anyway, I would be useful to be able to prove that:
    ([itex]P_b[/itex] and not [itex]P_1[/itex]) and ([itex]P_b[/tex] and not [itex]P_2[/tex] and ...
    as P1, P2, P3 ...
    equals Pb and not (P1, P2, P3 ...)

    I don't know if this is the proper way to express this, but I hope you will get my point. If not ask. And please correct me.
  2. jcsd
  3. Apr 22, 2005 #2


    User Avatar
    Gold Member

    "Pb and not (P1, P2, P3 ...)" would be a formula of infinite length, and I don't know of any language that allows formulas of infinite length. However, you can have an infinite set of formulas of finite length- which I suppose would work just as well.
    For your proof, the setup isn't fun, but here goes.
    The primitive symbols of formal language L fall into two disjoint sets: a countably infinite set of propositional symbols and a set of two distinct connective symbols, "NOT" denoted by ~ and "AND" denoted by &.
    Formulas are defined as follows:
    1) a propositional symbol is a formula.
    2) If P is a formula, then ~P is a formula.
    3) If P and Q are formulas, then &PQ is a formula.
    A (truth-)valuation V on L is a mapping from the set of formulas to the set {T, F} of (truth-)values, defined as follows:
    1) If P is a propositional symbol, Pv denotes the value assigned to P by V (Pv = T or Pv = F).
    2) If P is a formula, (~P)v = {T if Pv = F, F if Pv = T}.
    3) If P and Q are formulas, (&PQ)v = {T if Pv = T and Qv = T, F otherwise}.
    You want to prove that & has the associative and commutative properties. Informally, this is simple. Say that two formulas P and Q are equivalent iff Pv = Qv for every V. So you want to prove that if R, S, and T are formulas, then (&R&ST)v = (&&RST)v and (&RS)v = (&SR)v for every V. This follows immediately from the definitions.
    You also want to prove that (&PP)v = Pv (so you can get rid of all those extra Pbs). If Pv = T, then (&PP)v = T, and vice versa. If Pv = F, then (&PP)v = F, and vice versa. So they're equivalent.
    We can write "&PQ" as "P & Q" and introduce parentheses and subscripts for convenience. I think the meaning of your original statement is clear, if stated as follows:
    For any n in N, [(P1 & ~P2) & (P1 & ~P3) & ... & (P1 & ~Pn)] is equivalent to [P1 & (~P2 & ~P3 & ... & ~Pn)].

    Note that you cannot write ~(P2, P3, ..., Pn), unless you say what the commas mean. Note also that ~(P2 & P3 & ... & Pn) is not equivalent to (~P2 & ~P3 & ... & ~Pn)- "~" doesn't distribute that way.
    If that didn't help, just say so. Is that what you wanted to say?
  4. Apr 22, 2005 #3
    Thanks! You clear a few questionmarks, but created even more. I'll read a book on mathematical logic in the future i think.
  5. Apr 22, 2005 #4
    Try googling "infinitary logic."
  6. Apr 23, 2005 #5


    User Avatar
    Gold Member

    If you have questions, just ask. :smile:
    The best book on logic I've ever read is "Logic" by Wilfrid Hodges. If you read no other book on logic, read this one- Hodges is hysterical and seriously knows his stuff. You should also read this before any mathematical logic book. After that, "Set theory, logic, and their limitations" by Moshé Machover is great. "Mathematical Logic" by Joseph Shoenfield is also good.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Infinite logic
  1. Logic Question! (Replies: 4)

  2. Intuitionistic logic (Replies: 25)

  3. Nonformal logic (Replies: 14)

  4. Math and logic (Replies: 4)