Talk:Frege's theorem
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
The page has been updated to reflect its inaccuracy.
DC (talk) 14:08, 30 March 2016 (UTC)
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)
I agree with it not holding as a tautology. I reached the same conclusion independently. Ashleynewson (talk) 00:37, 29 January 2015 (UTC)
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)
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)
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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)
- Do you think we should place the table in the article nevertheless? - Jochen Burghardt (talk) 19:30, 30 March 2016 (UTC)
- I placed it there today, inserting the missing rightmost paranthesis. - Jochen Burghardt (talk) 16:33, 2 April 2016 (UTC)
Basic Law V and unrestricted comprehension
editThe 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)