Logic And Conditionals

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Logic And Conditionals

Postby z4lis » Tue Jun 10, 2008 4:35 pm UTC

I did a lot of thinking about logic and set theory yesterday, in which I stumbled upon the realization of the parallels between the two. My question this time! Suppose we are trying to prove the statement "if p, then q". Most books I've read claim that that statement is true for every case except "p and not q", which I have accepted for my work. However, I still wonder. What would happen if we allowed statements to have a value that is neither true nor false, but "undetermined"? If I have a single sample of p and q, I cannot say that "if p then q" is really true, but I can't quite say it's false. My only knowledge from that single sample lets me claim that "for some p, q". So rather than making the claim "if p then q" is true, I call it "undetermined".

The only way to actually prove an if-then statement true would be to: 1) check every single case of p and see whether or not there is a q, which for most situations is impossible (i.e. "if an integer is even, then it is the sum of two primes) 2) take a set of axioms that make assumed statements about all elements of a given set, and use implications to make new statements about that set or it's subsets

The only way to prove one false: 1) find a single contradictory case 2) use the set of axioms to prove either "for some p, not q"

All other cases leave the statement "undetermined". While I haven't the faintest idea of how (I've looked at the actual paper; I don't think I understood the first sentence) of how Godel proved what he did about algebraic systems or really what it says, *exactly*, but doesn't he basically prove that for any algebraic system, these "undetermined" statements must exist?

I suppose my next step would be to construct some truth tables for other statements, but including the idea of the "undetermined" status of a variable. For instance, if p is undetermined and q is true, then "p and q" would be undetermined. Anyway, would doing such an investigation be worth my time? These fora seem to have a handful of people who have a good deal more experience with math in general, so if someone else has already done this investigation and nothing particularly interesting popped out (as I figured will happen) I would like to know. :P
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Logic And Conditionals

Postby Robin S » Tue Jun 10, 2008 6:09 pm UTC

You are describing ternary logic. You may also be interested to read the thread about fuzzy logic, and Wikipedia articles on fuzzy logic and fuzzy sets.
This is a placeholder until I think of something more creative to put here.

User avatar
yeyui
Posts: 102
Joined: Sun Sep 16, 2007 10:45 pm UTC
Location: Kinston, NC, USA
Contact:

Re: Logic And Conditionals

Postby yeyui » Tue Jun 10, 2008 6:45 pm UTC

Your train of thought is very good. You seem to have come up with the ideas of trivalent logic and first order logic (see wikipedia for more details)

However I want to point out that in your post you are mixing propositional calculus (propositional logic) with first order predicate calculus (first order logic). (And perhaps your instructor is also.)

In propositional logic you have:
Atomic statements A, B, C, ...
some logical operators, usually NOT, AND, OR, and IMPLIES

First order logic is an extension that introduces quantifiers. You have:
objects usually denoted by lowercase letters,
properties which are functions mapping sets of objects to truth values,
operators as above, and
the universal quantifier [imath]\forall[/imath] (for all) and the existential quantifier [imath]\exists[/imath] (there exists).

If you are dealing with propositional logic, then it does not really make sense to say that you check 'all cases of p' in the statement "if p, then q" because p represents a specific statement. It is like saying that you should check all cases of "2+2=5" when testing the truth of the statement "If 2+2=5, then 4 is prime".

When you are proving if-then statements in a math class, you are almost always supposed to be proving a statement in first order logic like [imath]\forall x (P(x) \rightarrow Q(x))[/imath] (For all x, if P(x) then Q(x) ). [imath]\forall x (P(x) \rightarrow Q(x))[/imath] is true if and only if [imath]P(x) \rightarrow Q(x)[/imath] is always true. If there is a single counter example then it is false.

It has been my experience that the difference between [imath]P \rightarrow Q[/imath] and [imath]\forall x (P(x) \rightarrow Q(x))[/imath] is rarely stressed and the universal quantifier is often only implied. My theory is that this happens because in common usage of English, we don't usually actually use universal quantifiers. Consider the sentence "Cows say moo." Rather than taking this sentence as containing an unbound term "cow" and ask the speak which cow(s) they are talking about, we understand the statement to mean "All cows say moo." or perhaps "Most cows say moo.". So we carry this practice into more formal mathematical language and say things like "If n is an even number greater than two, then n is not prime." when we mean "For all integers n, If n is even and greater than two, then n is not prime." The rule of thumb is that whenever you see a logical statement with a variable not bound by a quantifier, add a universal quantifier to bind it.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Logic And Conditionals

Postby z4lis » Tue Jun 10, 2008 8:32 pm UTC

I'll toss this idea into this thread, since it's still concerned with logic.

Consider the set S of x that do not belong to any set. If this set is non-empty, there exists some x that does not belong to any set that belongs to S, which is a contradiction. Therefore, S must be empty and every x belongs to some set.

Nothing particularly astounding, but I just thought it was an interesting enough idea to put into the thread. 8)

And the above links were pretty interesting; I'll file them away in my head for ammo to be used on my future conquests of reality.
Last edited by z4lis on Tue Jun 10, 2008 8:34 pm UTC, edited 1 time in total.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Logic And Conditionals

Postby Robin S » Tue Jun 10, 2008 8:34 pm UTC

That's a lot like Russell's paradox, and is avoided by rejecting naive set theory in favour of axiomatic set theory.
This is a placeholder until I think of something more creative to put here.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Logic And Conditionals

Postby z4lis » Tue Jun 10, 2008 8:34 pm UTC

But is there really any reason to reject it?
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Logic And Conditionals

Postby Robin S » Tue Jun 10, 2008 8:38 pm UTC

Well, if such a set existed then, as you've pointed out, there is an immediate contradiction. If you allow contradictions into your system, in general, bad things happen (because if contradictions are ok, then every possible statement is simultaneously true and false). There are ways around this, such as giving elements probabilities of set membership as opposed to a fixed yes/no answer, as discussed in the "fuzzy set" article that I linked to earlier.
This is a placeholder until I think of something more creative to put here.

User avatar
SimonM
Posts: 280
Joined: Sat Jul 21, 2007 4:49 pm UTC
Location: Guernsey, CI
Contact:

Re: Logic And Conditionals

Postby SimonM » Tue Jun 10, 2008 8:41 pm UTC

Yes, the reason is that it is paradoxical and contains a contradiction. We like maths to be free from them so we use axioms so we can all agree on what is an acceptable statement.
mosc wrote:How did you LEARN, exactly, to suck?

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Logic And Conditionals

Postby Ended » Tue Jun 10, 2008 9:48 pm UTC

Robin S wrote:Well, if such a set existed then, as you've pointed out, there is an immediate contradiction.

There's no contradiction (every element x is indeed a member of the singleton {x}). I think one might formulate z4lis's set axiomatically as [math]S=\{x \in A \mid \not\exists B \subset A : x \in B\}[/math] where A is some given set*. Then S must be empty since it's a subset of A itself.


*(Is this type of construction allowed? On second thoughts, I'm not sure.)
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
diotimajsh
Posts: 658
Joined: Wed Nov 14, 2007 7:10 am UTC
Contact:

Re: Logic And Conditionals

Postby diotimajsh » Tue Jun 10, 2008 9:54 pm UTC

z4lis wrote:All other cases leave the statement "undetermined". While I haven't the faintest idea of how (I've looked at the actual paper; I don't think I understood the first sentence) of how Godel proved what he did about algebraic systems or really what it says, *exactly*, but doesn't he basically prove that for any algebraic system, these "undetermined" statements must exist?

My knowledge of how Gödel's proof works comes pretty much entirely from Gödel, Escher, Bach, but the "undetermined" quality that his proof shows is different from the kind you mean here. "Undetermined" may not even be the appropriate word: "undecidable" is the more common description, meaning that a statement's truth or falsity cannot be shown in the formal system at hand (or that both the statement and its negation can be derived in the same system). The reason formal systems include these statements doesn't have to do with a lack of information about the members of sets and the properties applied theretoward, but rather it is a necessary consequence of the system being of sufficient power to formulate statements about itself. I don't think it would be wise to conflate that kind of undecidability with the sort of undeterminedness you're proposing here.

z4lis wrote:The only way to actually prove an if-then statement true would be to: 1) check every single case of p and see whether or not there is a q, which for most situations is impossible...

Not most situations, only the interesting/non-trivial ones =P. E.g., "For all integers, if an integer is identical to 2, then it is even"; "For all integers, if an integer is identical to 4, then it is even"; etc.

(I'm sure that's what you had in mind anyway, I'm just teasing.)
Osha wrote:Foolish Patriarchy! Your feeble attempts at social pressure have no effect on my invincible awesomeness! Bwahahahaa


Blog type thing

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Logic And Conditionals

Postby Robin S » Tue Jun 10, 2008 10:53 pm UTC

Ended wrote:There's no contradiction (every element x is indeed a member of the singleton {x}). I think one might formulate z4lis's set axiomatically as [math]S=\{x \in A \mid \not\exists B \subset A : x \in B\}[/math] where A is some given set*. Then S must be empty since it's a subset of A itself.
I keep skim-reading. I really need to stop doing this. I saw "the set S of x that do not belong to any set", "if this set is nonempty" and "contradiction" and thought, yes, if this set is nonempty, there is a contradiction. Maybe I'm just tired.
This is a placeholder until I think of something more creative to put here.

Bsidney
Posts: 7
Joined: Wed Jun 11, 2008 7:01 pm UTC

Re: Logic And Conditionals

Postby Bsidney » Wed Jun 11, 2008 7:45 pm UTC

Couple of thoughts,

The Godel Incompleteness Theorem, which I think you are referring to, has to do with the "completeness" of a logic, to grok which you must separate the notions of "true" and "provable". (Logical) truth is a semantic concept, and refers always to truth under some interpretation of the non-logical symbols (letters or words) that assigns them to objects in a world. So under the usual interpretation of the words involved, the sentence "birds have feathers" is true (in our world). (Logical) proof is a syntactical notion, having to do with the rules whereby some sentence can be derived from others. For instance, from the sentences "trout are fish" and "fish live in trees" I can validly derive the sentence "trout live in trees" by the usual rules of predicate logic. Even though that sentence is not true (in our world), the proof of it from the given premises is perfectly valid. So "true" and "provable" are distinct concepts.

Now, a logic is Sound if you cannot derive false conclusions from true premises. It is Complete if every true statement can be derived. Ordinary predicate logic of the sort mathematicians use is both Sound and Complete in itself. (Godel himself proved the completeness part circa 1930.) However, if you add in powerful-enough concepts to permit you to also do basic arithmetic with your logic, then it remains Sound but becomes Incomplete. This is what Godel famously proved circa 1936.

The upshot is that any formal system (like math) rich enough in concepts to permit arithmetic has the following property: there exist statements in the language of that system that are true in the world (mathematicians say "model") of that system, but which cannot be derived (proved) in the language of that system.

In other words, it is not that there are statements whose truth is indeterminate, but that there are true statements that cannot be known (formally) to be true.

More broadly, as was proved by Alfred Tarski some years later using similar ideas, the notion of Truth as it regards statements in any formal system of thought cannot be "defined" (completely specified) within the system.

Incidentally, I am indebted to z4lis for the set S. I had not previously realized that the empty set could be defined by separation without the use of equality. (It's usually done as "the set of all x such that x \not\eq x".) Kudos for a lovely thought.

Sid


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests