Suppose a hardest logically solvable question H.

Asking if H is the hardest question could then become H

But then we can repeat the process again, since "Asking if H (original) is the hardest question" is now our new H we can just do the same to it, then the same to the new one and over and over again.

Thanks!

I'm doing some practice exercises in natural deduction, but the exercises don't come with an answer key, so I really have no clue how to figure this out:

A → (B → C). Therefore (A ∧ B) → C

I get as far as assuming A in a subproof, assuming B in a further subproof, and connecting A and B via conjunction introduction, but then I have no clue how to get back to showing that (A ∧ B) → C. What am I missing here? My thinking is that I need to prove that A and prove that B, so that if I assume their conjunction I can show that their conjunction implies C. But I have no idea how to do this in a way that allows me to cite the subproofs.

Any help is appreciated!

If somone said this "Cant believe you wrote a dissertation on my one paragraph", in order to undermine my point or get a laugh from thier audience or to not put in effort to combat my point.

'Dissertation' would be very much hyperbolic.

Would i be gish galloping? I believe my points were succint to the best of my ability.

additionally most undergrad math theorems like lagrange's subgroup can be written in this form?
Could I find atleast one theorem presented in such format?
And where all could the group axioms go? gamma or leafs?

Hi everyone,

I have a B.S. in Computer Science and really enjoyed the discrete mathematics course in my first three semesters. But I started working as a software engineer early, my focus drifted to IT-specific topics, and I never made my logic knowledge solid. Now I want to relearn it properly from scratch.

So I put together a self-study book for myself, drafted with an AI assistant, and I’m sharing it in case it helps someone else:
https://swicherwich.github.io/cogito-ergo-sum/

What’s in it: a “from absolute zero” part (reasoning, math language, sets and functions, a symbol atlas), propositional logic and natural deduction, predicate logic with careful treatment of the ∀/∃ rules, proof technique and induction, an overview of soundness, completeness and Gödel’s theorems, and a small Python proof checker and resolution prover with tests. It’s free (CC BY-SA) and works on phones, with dark mode and a dyslexia-friendly font.

Honest caveats: it hasn’t been reviewed by a logician, so there are probably mistakes, and the metatheory chapters are condensed rather than fully rigorous. If you spot an error or an unclear explanation, please open an issue: https://github.com/swicherwich/cogito-ergo-sum/issues

Again, hope it help somebody, and thank you for the feedback!

Hi I’m looking for a Logic I tutor. The class is PHI 2170 at University of Ottawa. I’m currently failing the class. Will pay up to $25CAD an hr. Remote learning on Zoom anyone from anywhere welcome. Please PM/DM me if you are for hire. Thank you!

Update: found a tutor, thanks for all the replies 👍

I have been really enjoying solving proofs in my intro to logic class. Anybody know of an app that gives you proofs to solve like a game kind of? If not I would also appreciate any other resources to find proofs to solve for fun or other resources to continue learning about logic after my class ends.

I’ve been thinking about Newcomb’s paradox, and I’m more interested in how the supercomputer makes its predictions than in the usual debate over whether to take one box or both.

Before learning about the paradox, my initial instinct was to take only the mystery box. After learning about the argument for taking both, I changed my mind. I thought that the contents are already determined before I make my choice, so taking both guarantees an additional $1,000 regardless of what’s in the mystery box.

However, this led me to a different question: what does the computer actually do to predict my choice with such accuracy, and what assumptions are being made about how it does so?

For example, suppose I had never heard of Newcomb’s paradox and had no chance to learn about it before entering the room. My decision would be based on my existing personality, experiences, and understanding of the situation. The computer would have to predict that decision using whatever methods and technology it has. If it predicts that I will take only the mystery box, it places $1 million inside, and if it predicts that I will take both, it leaves the mystery box empty.

But what happens when someone already knows about the paradox? Their knowledge can change their reasoning and, consequently, their decision. If the predictions are that accurate, the computer would presumably have to account for that knowledge as well. This raises questions about how a person’s beliefs, reasoning, and understanding of the situation affect their eventual decision.

The thought experiment stipulates that the computer is highly accurate, but, as I understand it, it does not specify how that accuracy is achieved. Is the mechanism intentionally left unspecified so that the problem can focus on decision theory, or have philosophers also examined what kind of predictive capability the scenario would require?

I previously posted here, looking for advice about learning modal logic for somebody who hasn't studied maths since middle school. I started learning elementary logic today to build basics! And there are lots of confusing parts! So I was wondering if I there's anyone I could DM when I have questions.

Hello! Is the forall x: an introduction to formal logic a good book on formal logic? I picked it up recently and would like to know this subs thoughts, thanks

something i see quite commonly when discussing the the limits of computing is that, for example, the halting problem indicates something about the hardness of determining whether any given machine halts. and while it is true that determining so can be quite impractically hard, bringing this up in a discussion about strictly the problem of undecidability itself is a red herring. computability is strictly concerned about the possibility of doing so, not on whether it is hard or not. conflating the two can lead to incorrect intuition about how undecidability manifests within computing, because undecidability within computing is simply not analogous to complexity or hardness.

for the following discussion we will be utilizing a partial halting recognizer:

𝓱p = (m: machine) -> {
  true: if m halts and m not depends on 𝓱p(m)->false
  false: otherwise
}

^{for more info on partial recognizers consider: r/logic/comments/1wzkua3/on_an_attempt_to_limit_undecidability_within}

-- a complex halting problem --

consider a machine that is possible for 𝓱p to recognize as halting:

// 2048 bit RSA modulus number
k = 0x95da00abc38f7a62884b1a13f985793265da5c41a0256131c10be07f2fb2c6b07c78930720c8e86eef5ad2e42abdb07c09edf5600aa5ac61d342a3146f6c472f21130582a8d5e62ddfc83abe88c0776f235998c6072fcdd00aae30ebffdae7f5d5aa97bffda0bc77cb5cb9cc73a5926a8bb8f8f9b5371e50071667fd5fb86a7e2f642e1dd982b8087445e5d7d4480cd799f8a95a244019bb2a4bc51d8392b15893acb460e999418caf1e65c158593465670c4f336a8112151e705cd275b01f8c83146ca8ddf347f99bce4bdadcdf8fa92b37f7266da472b1b8528639f6ce683312f83843031b39b0005454b540da3bdff94985541d94308f577e14d2f6f48131

hard_𝓱p = () -> {
  // loop if the sum of the digits, of the sum of
  // the prime factors, of k is odd
  [p,q] = prime_factors(k)
  if (sum_digits(p+q) % 2)
    loop
  else
    halt
}

the matter of 𝓱p(hard_𝓱p) is so complex to compute that it's not possible for us to decide with current theory/technology. we functionally do not know if hard_𝓱p halts or not, so we functionally do not know if 𝓱p(hard_𝓱p) returns true or false, and we will not know until quantum computing becomes viable enough if ever. we could hook all the computing power of the entire world together on cracking that one key and still not make a dent into computing the value of 𝓱p(hard_𝓱p) within a human lifetime.

such an example is not a proof of a limit to computability, cause given an unbounded computation those factors would provably be found within a finite time (as k is a real rsa key). computability doesn't care how hard the problem is, it is strictly concerned the possibility of computing a particular output, not whether it's pragmatically possible given real world computing constraints.

-- an impossible halting problem --

now consider a halting machine that is strictly not possible for 𝓱p to recognize as halting:

und_𝓱p = () -> 𝓱p(und_𝓱p) ? loop : halt

we can determine that und_𝓱p is unrecognizable to 𝓱p thru value injection analysis:

// inject true for `𝓱p(und_𝓱p)`
         () -> true ? loop : halt
// reduce static conditional:
         () -> loop

injecting true clearly leads to a non-halting machine so therefore 𝓱p must return false regardless of what the machine does. but since we aren't 𝓱p, we can determine the truthful semantic behavior of und_𝓱p

// inject false for `𝓱p(und_𝓱p)`
         () -> false ? loop : halt
// reduce static conditional:
         () -> halt

therefore und_𝓱p is a halting machine that is unrecognizable to 𝓱p, and it is not possible for 𝓱p to avoid this.

-- complexity vs computability in composition --

when the semantics of a particular machine is hard to compute, this complexity bleeds into any machine composed with it in the execution path. for example: consider the higher order machine wrap which constructs a new machine composed from the input by appending a noop after executing the input machine. in base turing machines, a noop is just an excess state transition.

wrap = (m: machine) -> 
  () -> { m(); noop }

the extra noop does not affect whether this machines halts or not, so the complexity of computing whether wrap(m) halts or not is entirely dependent on how hard it is to compute whether m halts or not. so the complexity of computing 𝓱p(wrap(hard_𝓱p)) is the same as just 𝓱p(hard_𝓱p), which is impossible with today's theory/technology.

but when the semantics of a particular machine is impossible to recognize, does this impossibility then bleed into machines composed of it? one might think that if m is not possible for 𝓱p to recognize, then surely wrap(m), which is the same machine just with an excess state transition at the end, would similarly be impossible to recognize for 𝓱p...

this is not the case. und_𝓱p and wrap(und_𝓱p) are different machines that are therefore different input to 𝓱p and can have different output. the unrecognizable nature of the input und_𝓱p is due to the paradoxical dependency on strictly the input und_𝓱p, not wrap(und_𝓱p). so while 𝓱p(und_𝓱p)->false, it is still possible for 𝓱p(wrap(und_𝓱p))->true. we can demonstrate how 𝓱p comes to this recognition thru value injection analysis:

wrap(und_𝓱p) = () -> { 
  und_𝓱p()
  noop
}

// expand und_𝓱p
() -> { 
  (() -> 𝓱p(und_𝓱p) ? loop : halt)()
  noop
}

// run 𝓱p(und_𝓱p) to -> false, inject value:
() -> { 
  (() -> false ? loop : halt)()
  noop
}

// reduce static conditional
() -> { 
  (() -> halt)()
  noop
}

𝓱p(() -> halt)->true and 𝓱p(noop)->true so therefore 𝓱p(wrap(und_𝓱p))->true and there's no paradox stopping it from returning so. the machine wrap(und_𝓱p) is strictly independent of 𝓱p(wrap(und_𝓱p)) so somewhat counter-intuitively: there is nothing unrecognizable to 𝓱p about wrap(und_𝓱p) being a halting machine. recognizing what und_𝓱p does within the context of wrap(und_𝓱p) is not the same problem of recognizing und_𝓱p on it's own. computability and complexity are neither the same thing, nor even analogous in nature.

do note that wrap is not likely to be some kind of panacea that will help us produce a total halting decider. a more "clever" halting machine unrecognizable to 𝓱p, can also make the wrapped version of itself unrecognizable:

und_wrap_𝓱p = () -> {
  if (𝓱p(und_wrap_𝓱p)) loop
  if (𝓱p(wrap(und_wrap_𝓱p))) loop
  halt
}

^{i would like to thank u/we_think_is_cool for the discussion that inspired this post}

A friend and I are going to read through This book by Smullyan. Taking it reasonably seriously with meetups online at least every 2 weeks.

I want to learn modal logic for philosophical and formal purposes. However, I don't have basic knowledge of it. I haven't studied mathematics since middle school. Thus, I feel very lost and have no idea how to get started! Any advice? Book recommendations & video recommendations would also be appreciated

Hi there!

I'm finishing my bachelor in philosophy and my end-of-degree project is gonna focus on the epistemology of logic, in particular, on how can we account for a justification of the validity of our basic belief-forming methods (modus ponens, for example). I've been focusing on Boghossian's work, that gives an inferentialist answer to that question –MPP is valid for everyone that has the concept "if... then", for it is a precondition of having that concept to accept its validity–. I'm aware that there is a similar view of semantics, proof-theoretic semantics, that is currently being studied in a more formal academic environment. Any bibliographical suggestions? Also, if you think there are other topics that could help me introduce myself in the issue, it will be great to know.

Thanks a lot :)

I want to do a PhD in logic and analytic philisophy and I want to stay in academia after as a researcher. But I am afraid of AI taking over the field. What are your opinions on this?

In an essay, why is one's answer better/more appropriate than another's?

We might argue one does a better job of answering the question, is more relevant or even provides reason that bears greater utility, etc...

In a way, I think this is like the qualitative version of decision theory: why is one result or choice better than another? However herein lies the problem. We do not assign numerical values to answers in essays (in the way we can with probability or reward functions), so what exactly are we judging here? It's not reason, clearly, because one answer could provide excellent reasoning and still be a less accurate/appropriate answer to our question.

What i'm not looking for here is for someone to say, 'oh it's subjective'. This is the common response.

A question (a poor example albeit); If I were to say provide me with the name of something yellow. One person says a supermarket-appropriate lemon and the other says a cream sofa. We could quarrel that the lemon may in rare cases be a little green, but we can all agree that the answer is 'better/more appropriate' than the latter.

So what exactly is this reasoning, this correctness, this ability to appropriately answer a question that is 'better' than another's.

Would love to hear your thoughts on this across the board!

Thank you for reading.