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.

I feel confused comparing partial order on sets and that on logic.

$$x\ge 1 \implies x\ge 0$$

Here we see a smaller set "implies" a bigger set

But, if we know three facts, fact1,fact2,fact3, we know thus fact1, fact2, which can be written as

$$\{\text{fact1}, \text{fact2}, \text{fact3}\} \implies \{\text{fact1}, \text{fact2}\}$$

Here a bigger set "implies" a smaller set.

I feel thus confused facing the logic partial order "implies". What's my problem??

share|improve this question
1  
You seem to be confusing the fact that $\implies$ (or, to be more precise, $\vdash$) is a preorder on the set of propositions with the idea of reasoning about partially ordered sets. –  Zhen Lin Aug 2 '11 at 7:16

2 Answers 2

up vote 1 down vote accepted

First we need to review the definition of "implies".

Suppose $P,Q$ are two sentences. $P\implies Q$ is exactly the case that if $P$ is true then $Q$ is also true.

In your example, $x\ge 1$ implies $x\ge 0$ because $1\ge 0$ and $\ge$ is transitive, that is if $x\ge y$ and $y\ge z$ then $x\ge z$.

Suppose now that you have $\mathcal P=\{P_1,\ldots\}$ a set of sentences (not necessarily finite), and $Q$ another sentence. We say that $\{P_1,\ldots\}\implies Q$ exactly if all the sentences in $\mathcal P$ are true, then $Q$ is also true.

An example is:

$$\{"x\ge2", "x\text{ is odd}"\}\implies x\ge 3$$

Neither $x\ge 2$ nor $x\text{ is odd}$ imply $x\ge 3$ on their own, however combine the two facts and you have that $x\ge 3$.

This can be extended into replacing $Q$ by some $\mathcal Q=\{Q_1,\ldots\}$ another set of sentences, in which case we say that $\mathcal P\implies\mathcal Q$ exactly whenever all the sentences in $\mathcal P$ are true, then all the sentences in $\mathcal Q$ are true as well.

For example:

$$\{"x\ge 1", "x\text{ is even}", "x\text{ can be divided by } 6"\}\implies\{"x\text{ can be divided by } 3", "x\ge 6"\}$$

There is no strict requirement that a "big" sets have to imply the truth of some "smaller" or "bigger" set than itself. One sentence can imply many sentences, and it may be the case that several sentences are required to imply a single sentence.


A mistake in your post is that $\implies$ is not a partial order, but rather a quasi-order. That means reflexive and transitive. It is not antisymmetric.

For example: $$"x<1 \text{ and } x>-1"\implies "x=0"$$ as well: $$"x=0"\implies "x<1 \text{ and } x>-1"$$

However formally speaking, $x=0$ is not the same sentence as $"x<1 \text{ and } x>-1"$.

share|improve this answer

($A$ or $B$) implies ($A$ or $B$ or $C$). ($A$ and $B$ and $C$) implies ($A$ and $B$).

$x\ge1$ is an "or": it's ($x=1$ or $x=2$ or $x=3$ or ...).

$\lbrace{\rm fact1,\ fact2,\ fact3}\rbrace$ is an "and": (fact1 and fact2 and fact3).

share|improve this answer
    
Gerry: What about the case $\{\text{fact}_n\mid n\in\mathbb N\}$? :-) –  Asaf Karagila Aug 2 '11 at 7:08
    
@Asaf, makes no difference. If it's preceded by "we know", it's "and": we know fact1 and we know fact2 and .... If it's preceded by "$x$ is in" then it's "or": $x$ is fact1 or $x$ is fact2 or .... –  Gerry Myerson Aug 2 '11 at 7:18
    
It was a semi-humourous remark, I was being a smartypants on my side. :-) –  Asaf Karagila Aug 2 '11 at 7:19
1  
Yes, I think a quick answer would be: (Disjunctive_facts, ==>) corresponds to (Sets, \subset), whicle (Conjunctive_facts, ==>) correspoinds to (Sets, \supset). –  zell Aug 2 '11 at 7:22

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.