Talk:Frege's theorem

The page has been updated to reflect its inaccuracy.

DC (talk) 14:08, 30 March 2016 (UTC)[reply]

I believe that this doesn't hold as a tautology. I seek confirmation before I edit the page though.

Consider P, Q, R as false. Then the expression is false.

Consider P, R as true, Q as false. Then the expression is true.

Thus, it is not a tautology, since their exists an interpretation under which it is not true. However it is satisfiable as there is an interpretation under which it is true.

DC (talk) 20:01, 25 January 2015 (UTC)[reply]

I agree with it not holding as a tautology. I reached the same conclusion independently. Ashleynewson (talk) 00:37, 29 January 2015 (UTC)[reply]

More specifically:

(Using 0 as false and 1 as true)

Clarifying the → operator:

0 → 0 is true

0 → 1 is true

1 → 0 is false

1 → 1 is true

∧ is conjuntion (and), ¬ is negation:

Consider, (P → (Q → R)) → ¬((Q → P) ∧ (R → Q)), under the interpretation P=0, Q=0, R=0:

(0 → (0 → 0)) → ¬((0 → 0) ∧ (0 → 0)) becomes (0 → 1) → ¬(1 ∧ 1) becomes 1 → ¬1 becomes 1 → 0 which is false.

Therefore, as not all interpretations satisfy (P → (Q → R)) → ¬((Q → P) ∧ (R → Q)), it is not a tautology. Ashleynewson (talk) 01:05, 29 January 2015 (UTC)[reply]

I still believe the formula is a tautology; and I don't understand why negation and conjunction appear in Ashleynewson's calculation, they don't stem from the formula, do they? I have made a table about all 8 possibilities of P,Q,R being false or true; I suggest to put it into the article, with the suggested caption. - Jochen Burghardt (talk) 16:55, 30 March 2016 (UTC)[reply]

P	→	Q	→	R	→	P	→	Q	→	P	→	R
	Y		✓		Y	✗	✓	✗	Y	✗	✓	✗
	Y		✓		Y	✗	✓	✗	Y	✗	✓	✓
	Y		✗		Y	✗	✓	✓	Y	✗	✓	✗
	Y		✓		Y	✗	✓	✓	Y	✗	✓	✓
	Y		✓		Y	✓	✗	✗	Y	✓	✗	✗
	Y		✓		Y	✓	✗	✗	Y	✓	✓	✓
	N		✗		Y	✓	✓	✓	N	✓	✗	✗
	Y		✓		Y	✓	✓	✓	Y	✓	✓	✓
1	2	3	4	5	6	7	8	9	10	11	12	13

Truth table for Frege's theorem. For all possible assignments of false (✗) or true (✓) to P, Q, and R (columns 1, 3, 5), each subformula is evaluated according to the rules for material conditional, the result being shown below its main operator. Column 6 shows that the whole formula evaluates to true in every case, i.e. that it is a tautology. In fact, its antecedent (column 2) and its consequent (column 10) are even equivalent.

The formula presented on the Wikipedia page has since changed. It used to have an erroneous negation in it which has been removed since the comment I originally made. Therefore, Jochen Burghardt's evaluation is correct and the tautology holds. Ashleynewson (talk) 17:15, 30 March 2016 (UTC)[reply]

Do you think we should place the table in the article nevertheless? - Jochen Burghardt (talk) 19:30, 30 March 2016 (UTC)[reply]

I placed it there today, inserting the missing rightmost paranthesis. - Jochen Burghardt (talk) 16:33, 2 April 2016 (UTC)[reply]

Basic Law V and unrestricted comprehension

The quote

Most of these axioms were carried over from his Begriffsschrift; the one truly new principle was one he called the Basic Law V (now known as the axiom schema of unrestricted comprehension): the "value-range" of the function f(x) is the same as the "value-range" of the function g(x) if and only if ∀x[f(x) = g(x)]. However, not only did Basic Law V fail to be a logical proposition, but the resulting system proved to be inconsistent, because it was subject to Russell's paradox.

may be incorrect. Joel David Hamkins showed in "Fregean abstraction in Zermelo-Fraenkel set theory: a deflationary account" that Basic Law V follows from ZF in a sense (theorem 1), although it cannot literally follow from ZF as it isn't a first-order sentence. However it does not entail Russell's paradox. C7XWiki (talk) 09:27, 26 October 2023 (UTC)[reply]