Contradictions imply everything (a proof)

[A Toy Windmill]

First, we'll prove that either a proposition P holds, or else it implies everything.

To do so, we will admit that we can quantify over and form sets of propositions and that we have the axiom of choice. We'll let T stand for a true proposition, whichever you like.

1) Consider the set of propositions Q such that P or Q. This is non-empty since it at least contains T.
2) Consider the set of propositions R such that either P or else (R implies everything). This is non-empty since it at least contains the proposition "everything holds".
3) Pair the above sets and use the axiom of choice to pick out a Q and R respectively.
  4) Assume P
  5) Then the sets considered above are the same set: the universal set of propositions.
  6) Thus choice picked out only one proposition above. In other words, Q = R
    7) Assume Q
    8) Assume R implies everything
    9) Hence Q implies everything (from 6 and 8)
    10) Everything (from 7 and 9)
  11) If Q and R implies everything, then everything (from 7-10)
12) If P, Q and R implies everything, then everything (from 4-11).
13) (if Q and R implies everything) then P implies everything (reordering the antecedents of 12)
14) (P or Q) and (P or R implies everything) (from 1, 2 and 3)
15) P or (Q and R implies everything) (from 14 by distributivity)
16) P or P implies everything (from 13 and 15)

As a corollary:

1) Assume P.
2) Assume not-P.
3) Have P or P implies everything (from the proof above)
4) P implies everything (disjunctive syllogism from 2 and 3).
5) Anything. (from 1 and 4).

 

[fast]

Are P and Q collectively exhaustive? Like P and not P are

 

[A Toy Windmill]

Are P and Q collectively exhaustive? Like P and not P are

P and Q cannot both be false. They may both be true.

 

[fast]

Are P and Q collectively exhaustive? Like P and not P are

P and Q cannot both be false. They may both be true.

If P and Q cannot both be false, then one must be true rendering Q equivalent to not P, but if they may both be true, Q isn’t equivalent to not P.

 

[steve_bank]

I am used to using trtuth tables and symbolic logic.

OR function. A || B = C

A B C
F F F
F T T
T F T
T T T

A || !A = TRUE From the truth table for OR any true in gives a true out. If A is false !A is true if A is false !A is true.

 

[A Toy Windmill]

Are P and Q collectively exhaustive? Like P and not P are

P and Q cannot both be false. They may both be true.

If P and Q cannot both be false, then one must be true rendering Q equivalent to not P

That doesn't follow. Not sure if it's just a silly mistake, but you might like to check its invalidity using a truth-table as steve suggests.

 

[fast]

If P and Q cannot both be false, then one must be true rendering Q equivalent to not P

That doesn't follow. Not sure if it's just a silly mistake, but you might like to check its invalidity using a truth-table as steve suggests.

Is there any part of what I said you agree with?

 

[A Toy Windmill]

If P and Q cannot both be false, then one must be true rendering Q equivalent to not P

That doesn't follow. Not sure if it's just a silly mistake, but you might like to check its invalidity using a truth-table as steve suggests.

Is there any part of what I said you agree with?

No. Everything was wrong.

I'm happy to help with basic logic, but given the OP, this isn't the appropriate thread.

 

[Angra Mainyu]

Thanks for trying to do that.

One would need to restrict the propositions, though, otherwise a universal set of propositions runs into trouble (proper classes won't help, either). Do you have some restrictions in mind?

In any case, (P&¬P)->Q is more basic than the axiom of choice. But I feel like every attempt at proving it will fail to persuade those who don't see it.

 

[A Toy Windmill]

Thanks for trying to do that.

One would need to restrict the propositions, though, otherwise a universal set of propositions runs into trouble (proper classes won't help, either). Do you have some restrictions in mind?

Assume that P and Q are carved out of subsets of X = {T, all propositions hold}. Line 5 then changes to

5) Then the sets considered above are the same set: X.

In any case, (P&¬P)->Q is more basic than the axiom of choice. But I feel like every attempt at proving it will fail to persuade those who don't see it.

The features of the proof I was going for are:

1) The absence of clear irrelevancies, cases where a Q comes out of nowhere. Instead, I consider "everything holds" (∀p. p).
2) No reliance on the definition of material implication. I don't assume that everything implies true, or that false implies everything.

So even if mathematicians are using an intuitive logic without 1 and 2 (it wouldn't surprise me), they are still forced to conclude that inconsistencies imply everything by axioms of logic to which they explicitly hold, specifically choice.

Obviously, I don't think this way, and I take it as basic that falsehoods imply everything. My favourite axiom system for classical propositional logic is this one:

1) P → (Q → P)
2) (P → Q) → (Q → R) → (P → R)
3) ((P → Q) → P) → P
4) ⊥ → P

Here, negation isn't even a basic connective. Contradictions are captured directly by a special proposition ⊥ whose single defining characteristic is that it implies everything. Negation is then defined as P → ⊥.

I like to justify this in a few ways. First, you can read ⊥ as an arbitrary absurdity like "I'm the Queen of Sheba", and so negation is just everywhere the colloquialism "if that's true, then I'm the Queen of Sheba!" Secondly, it understands negation as a kind of bet. To declare a proposition false, I must put up a forfeit should I be mistaken and the proposition turn out to be true. And that forfeit is ⊥, a proposition designed to render the entire enterprise pointless and boring by being the ultimate cheat code for all other problems, the master key to the dungeon.

As Hardy declared of proof by contradiction, the mathematician is willing to sacrifice the game (⊥).

 

[Angra Mainyu]

I think I'm probably not getting the notation, but what I was trying to get at is something like this: We are using AC (if we don't have AC, one can make other arguments), so every set has a cardinality. Suppose that Y is a set of propositions with cardinality a, and let b be the next cardinal. For every cardinal c<=b such that c=\=a, let P(c) be the proposition "It is not the case that the cardinality of Y is c", and let P(a) be the proposition "The cardinality of Y is a". Then, for all c<=b, P(c) is a true proposition, and at least one of those true propositions is not an element of Y (else, we would have a>=c, contradicting the hypothesis). Thus, there is no set of all true propositions.

The features of the proof I was going for are:

1) The absence of clear irrelevancies, cases where a Q comes out of nowhere. Instead, I consider "everything holds" (∀p. p).
2) No reliance on the definition of material implication. I don't assume that everything implies true, or that false implies everything.

I agree, those sound like good ideas for a proof.

 

[A Toy Windmill]

I think I'm probably not getting the notation, but what I was trying to get at is something like this: We are using AC (if we don't have AC, one can make other arguments), so every set has a cardinality. Suppose that Y is a set of propositions with cardinality a, and let b be the next cardinal. For every cardinal c<=b such that c=\=a, let P(c) be the proposition "It is not the case that the cardinality of Y is c", and let P(a) be the proposition "The cardinality of Y is a". Then, for all c<=b, P(c) is a true proposition, and at least one of those true propositions is not an element of Y (else, we would have a>=c, contradicting the hypothesis). Thus, there is no set of all true propositions.

Yes. Sets of propositions would either need to be suitably stratified or an impredicative class. But we can sidestep this and only consider subsets of the finite set X = {T, everything holds}. So long as X can be admitted to exist, we go with

1) Consider the subset of X consisting of propositions Q such that P or Q. This is non-empty since it at least contains T.
2) Consider the subset of X consisting of propositions R such that either P or else (R implies everything). This is non-empty since it at least contains the proposition "everything holds".

 

[Speakpigeon]

First, we'll prove that either a proposition P holds, or else it implies everything.

To do so, we will admit that we can quantify over and form sets of propositions and that we have the axiom of choice. We'll let T stand for a true proposition, whichever you like.

1) Consider the set of propositions Q such that P or Q. This is non-empty since it at least contains T.
2) Consider the set of propositions R such that either P or else (R implies everything). This is non-empty since it at least contains the proposition "everything holds".
3) Pair the above sets and use the axiom of choice to pick out a Q and R respectively.
  4) Assume P
  5) Then the sets considered above are the same set: the universal set of propositions.
  6) Thus choice picked out only one proposition above. In other words, Q = R
    7) Assume Q
    8) Assume R implies everything
    9) Hence Q implies everything (from 6 and 8)
    10) Everything (from 7 and 9)
  11) If Q and R implies everything, then everything (from 7-10)
12) If P, Q and R implies everything, then everything (from 4-11).
13) (if Q and R implies everything) then P implies everything (reordering the antecedents of 12)
14) (P or Q) and (P or R implies everything) (from 1, 2 and 3)
15) P or (Q and R implies everything) (from 14 by distributivity)
16) P or P implies everything (from 13 and 15)

As a corollary:

1) Assume P.
2) Assume not-P.
3) Have P or P implies everything (from the proof above)
4) P implies everything (disjunctive syllogism from 2 and 3).
5) Anything. (from 1 and 4).

Non-Aristotelian logic. Not human.
EB

 

[Angra Mainyu]

I think I'm probably not getting the notation, but what I was trying to get at is something like this: We are using AC (if we don't have AC, one can make other arguments), so every set has a cardinality. Suppose that Y is a set of propositions with cardinality a, and let b be the next cardinal. For every cardinal c<=b such that c=\=a, let P(c) be the proposition "It is not the case that the cardinality of Y is c", and let P(a) be the proposition "The cardinality of Y is a". Then, for all c<=b, P(c) is a true proposition, and at least one of those true propositions is not an element of Y (else, we would have a>=c, contradicting the hypothesis). Thus, there is no set of all true propositions.

Yes. Sets of propositions would either need to be suitably stratified or an impredicative class. But we can sidestep this and only consider subsets of the finite set X = {T, everything holds}. So long as X can be admitted to exist, we go with

1) Consider the subset of X consisting of propositions Q such that P or Q. This is non-empty since it at least contains T.
2) Consider the subset of X consisting of propositions R such that either P or else (R implies everything). This is non-empty since it at least contains the proposition "everything holds".

Okay, now I see what I misunderstood in the notation.

I take it that "everything holds" the proposition 'all propositions are true', or something like that?

By the way, for finite sets, the axiom of choice follows from ZF, so it's a theorem of choice, so one does not need to add it to the proof.

Still, I think I'm not reading this right, for the following reason:

Assuming P, the subset of X consisting of propositions Q such that P or Q is X. The subset of X consisting of propositions R such that either P or else (R implies everything) is also X. Okay, so you're saying choice was used only to pick one proposition because you're picking from the singleton {X}. I see.

We could also give a proof independent of the ZF axioms. But Speakpigeon will not accept any proofs.

 

[fast]

Could someone please translate “or else open parenthesis the letter “R” implies everything close parenthesis” in plain English? I’m especially confused with the “(“ following the word, “else.”

 

[A Toy Windmill]

Okay, now I see what I misunderstood in the notation.

I take it that "everything holds" the proposition 'all propositions are true', or something like that?

Yes. In second order propositional calculus, it's just (∀p. p).

By the way, for finite sets, the axiom of choice follows from ZF, so it's a theorem of choice, so one does not need to add it to the proof.

Ah, of course!

The proof in the OP is adapted from another theorem, but when you unfold it using finite choice, it simplifies to the classic!

1) Assume P
2) Then P or R
3) Assume ~P
4) Therefore R (by 2 and 3)

 

[A Toy Windmill]

Could someone please translate “or else open parenthesis the letter “R” implies everything close parenthesis” in plain English? I’m especially confused with the “(“ following the word, “else.”

I want to say that there are two possible cases:

Either:
1) P is true.
2) R implies everything.

Getting that into one line can create ambiguity. I could write "either P or R implies everything", but that could be read as

If it is the case that P or it is the case that R, then we have everything.

Brackets disambiguate. The intended reading is "P or (R implies everything)". The other reading is "(P or R) implies everything."

There should be even more brackets in the OP, but they're ugly to write. It would have been easier to do everything symbolically.

 

[fast]

Thank you. That helps.

 

[Speakpigeon]

First, we'll prove that either a proposition P holds, or else it implies everything.

To do so, we will admit that we can quantify over and form sets of propositions and that we have the axiom of choice. We'll let T stand for a true proposition, whichever you like.

1) Consider the set of propositions Q such that P or Q. This is non-empty since it at least contains T.
2) Consider the set of propositions R such that either P or else (R implies everything). This is non-empty since it at least contains the proposition "everything holds".
3) Pair the above sets and use the axiom of choice to pick out a Q and R respectively.
  4) Assume P
  5) Then the sets considered above are the same set: the universal set of propositions.
  6) Thus choice picked out only one proposition above. In other words, Q = R
    7) Assume Q
    8) Assume R implies everything
    9) Hence Q implies everything (from 6 and 8)
    10) Everything (from 7 and 9)
  11) If Q and R implies everything, then everything (from 7-10)
12) If P, Q and R implies everything, then everything (from 4-11).
13) (if Q and R implies everything) then P implies everything (reordering the antecedents of 12)
14) (P or Q) and (P or R implies everything) (from 1, 2 and 3)
15) P or (Q and R implies everything) (from 14 by distributivity)
16) P or P implies everything (from 13 and 15)

As a corollary:

1) Assume P.
2) Assume not-P.
3) Have P or P implies everything (from the proof above)
4) P implies everything (disjunctive syllogism from 2 and 3).
5) Anything. (from 1 and 4).

We would need first to prove empirically that your method of logical proof here is correct.

Me, I'm 100% confident it's wrong and I'm also not aware of any empirical proof that it would be correct.

Short of that, this is just a mathematical pie in the sky meaning nothing.

You should refrain from making it look as if your proof had any authoritative value. You are misleading posters here.

You know, a disclaimer would be appropriate here. Someone might decide to sue you and I think he would win.
EB

 

[steve_bank]

I finally figured out why I have trouble with those logic threads. People shift between informal and attempts a t formal proofs with no constancy or structure.

When I read (P&¬P)->Q I see Q as always false. I am always trying to convert text to symbolic logic.

I see the OP trying to prove a tautology, or the definition of OR and AND.I am a little slow so I like pictures.

There is a box of apples and a box of peaches. I say put one or the other in the car. That is an exclusive or XOR. One or the other but not both.

If I say take one or the other or both that is inclusive or.

If I say take the apples and peaches t means take both.

See the link on Boolean Algebra on the tread I started for logic functions and the truth tables.

.

This is where truth tables come in. To precisely define what you mean post a truth tale. It is unambiguous and not open to interpretation.