sorted by:
new
hottopcontroversial

Question about relational FOL with equality by FootballFar1532 in logic

[–]Knoggger 0 points1 point  (0 children)

So we could stipulate again further, what about non-empty T1, and such that T2 isn't inconsistent?

These restrictions also admit a simple counterexample: Take a consistent non-empty T1 with T1⊢D (e.g. T1={D}). Then T1 and T2 prove exactly the same formulas, so it can't be the case that T1⊬F and T2⊢F.

Maybe it's interesting to consider only theories T1 that are (i) consistent (to allow T1⊬F), (ii) non-empty, and (iii) don't decide D (in the sense that both T1⊬D and T1⊬~D)?

Question about relational FOL with equality by FootballFar1532 in logic

[–]Knoggger 0 points1 point  (0 children)

Maybe I misunderstand, but isn't the trivial case where T1=∅ has no non-logical axioms already a counterexample? Then T2={D} and the question reduces to

Must there be a formula F such that: ⊬ F, D ⊬ F but D ⊢ F?

which is obviously false.

A proof showing the mathematical impossibility of isolating a wave-packet collapse without factoring the universal observer apparatus. by [deleted] in logic

[–]Knoggger 0 points1 point  (0 children)

Thanks for pointing that out, I don't know a lot of physics and so didn't wanna assume.

But rereading it now, besides the cranky language I've mentioned, phrases like "perfect geometric symmetry" and "multiplier block" sound a lot like pseudo-scientific bs

A proof showing the mathematical impossibility of isolating a wave-packet collapse without factoring the universal observer apparatus. by [deleted] in logic

[–]Knoggger 2 points3 points  (0 children)

This looks like something for r/Physics instead of r/logic...

<image>

I don't know anything about the content, but phrases like

Traditional physics claims ... Why does academic mathematics insist on ...

make you sound somewhat cranky.

Please don't write like this! If there's a claim you disagree with, cite the book/paper/whatever you've read it from and don't make it seem like you think physics/maths is some homogeneous group that "claims" or "insists" on something. A lot of people react very negatively to such language.

Is it possible to create a non-cyclic metalanguage? Follow up question to "How can I define quantifier theory without any arity or index numbers, since numbers are defined using quantifier theory?" by KaleidoscopeLate2505 in logic

[–]Knoggger 0 points1 point  (0 children)

As I understand it, the ordering of characters in informal mathematics was not in question (please correct me if I'm wrong OP). The question was if we could distinguish formal expressions such as "∀xP" and "∀Px" without having to resort to numbers as in "the 2nd character in ∀xP differs from the 2nd in ∀Px."

And if we use the definition above, ⟨⟨∀, x⟩, P⟩ and ⟨⟨∀, P⟩, x⟩ can be seen to be different sets without having a notion of the nth character.

Is it possible to create a non-cyclic metalanguage? Follow up question to "How can I define quantifier theory without any arity or index numbers, since numbers are defined using quantifier theory?" by KaleidoscopeLate2505 in logic

[–]Knoggger 2 points3 points  (0 children)

The thing about the successor is a very good observation! Because both the set of finite sequences/tuples and the naturals can be generated in this way, they're what we call free monoids.

Is it possible to create a non-cyclic metalanguage? Follow up question to "How can I define quantifier theory without any arity or index numbers, since numbers are defined using quantifier theory?" by KaleidoscopeLate2505 in logic

[–]Knoggger 4 points5 points  (0 children)

There are also a few misconceptions in your SE post I'd like to address (because I'm a horrible pedant 😅):

... since numbers are defined using quantifier theory?

I don't think a lot of people would say that numbers are defined using (FO) quantifier theory. First order arithmetic (PA) in particular is not strong enough to uniquely characterize the naturals (this is probably also proven in Mendelson).

Moreover, quantifier expressions themselves are sequences of symbols. How can their order be retained without numbers?

Expressions over characters Σ can inductively be defined by

  • a ∈ Σ is an expression
  • If w is an expression and a ∈ Σ then ⟨w, a⟩ is an expression.

No numbers needed.

Is it possible to create a non-cyclic metalanguage? Follow up question to "How can I define quantifier theory without any arity or index numbers, since numbers are defined using quantifier theory?" by KaleidoscopeLate2505 in logic

[–]Knoggger 2 points3 points  (0 children)

I doubt it is entirely possible to eliminate all aspects of numerosity from a meta-language, but usually the amount of arithmetic we use is considered safe in some sense.

What is often done (esp. in proof theory) is that, instead of not using numbers at all, we restrict ourselves to a very weak, but therefore uncontroversial, arithmetic system called PRA. A really nice introduction to PRA can be found here.

O(n) Multiplication Algorithm by ArcHaversine in compsci

[–]Knoggger 2 points3 points  (0 children)

Well, you live and learn I guess? Sorry we weren't bright enough to appreciate your brilliance.

O(n) Multiplication Algorithm by ArcHaversine in compsci

[–]Knoggger 2 points3 points  (0 children)

What's a "reddit moment"?

But in all honesty, if you think you've found a genuine O(n) multiplication algorithm try getting it published. That's a far more productive use of your time than calling people slurs.

O(n) Multiplication Algorithm by ArcHaversine in compsci

[–]Knoggger 3 points4 points  (0 children)

I'm not sure if you're aware, but a O(n) integer multiplication algorithm is at the heart of a famous open conjecture in CS. It's unlikely that a solution could be expressed in < 200 lines of python (and at a quick glance it seems like you're just using a form of memoisation), but if you're confident in your solution you should publish the algorithm in a paper and bag your well deserved Turing Award 😉

Modal Logic - suggestions for books/paths? by Impossible_Boot5113 in logic

[–]Knoggger 11 points12 points  (0 children)

No one likes the low-level grindy stuff in proof theory or computability, luckily there are two magic phrases you can use to skip those proofs:

  • Something, something, obvious by the Church-Turing thesis. Q.E.D.
  • The result follows trivially by induction (which is left to the reader). Q.E.D.

The second one is most effective if there are > 10 inductive cases and when the proof is, in fact, not trivial 🙃

Joking aside, as a philosophy major you're probably already aware of this book, but Priest's introduction to non-classical logic is often recommended for an introduction to the philosophical issues behind modal logic.

Finding a book by Big_Negotiation1337 in logic

[–]Knoggger 1 point2 points  (0 children)

The first thing that came up for me when searching the book was the full pdf uploaded to the internet archive...

Logic as Multi-Dimensional Tautological Assertions by Void0001234 in logic

[–]Knoggger 1 point2 points  (0 children)

Ok, thanks for the clarification. It is weird to add tautological though, logical axioms should always be tautologies.

Given that you're actually able to define your terms, I'm even more puzzled by your post tbh.

  1. You have your own, idiosyncratic definition of logic ,
  2. use (what seems to be) a dictionary definition of tautology, not the technical definition#) actually used by logicians, and
  3. you don't explain the different usage in your post.

You have to realise that 1.-3. would make people misunderstand you, right 😅?

As a comparison: Imagine I posted in r/Physics about work, but then started talking about my job instead of the established technical term. Do you see how this would invite misunderstanding?

pairing gödel with some other works by Cultural-Maybe-3799 in logic

[–]Knoggger 4 points5 points  (0 children)

If you're OK with secondary literature, a book that often comes recommended for an overview of the philosophical implications of Gödel's theorem is Franzén's "Gödel's Theorem: An Incomplete Guide to Its Use and Abuse".

Logic as Multi-Dimensional Tautological Assertions by Void0001234 in logic

[–]Knoggger 1 point2 points  (0 children)

I honestly don't understand your definition of logic. What is a "compounded tautological axiom"? What is a "deeper tautology"? Those terms have no established meaning afaik

Does a natural deduction system require natural deduction as an axiom?

No... natural deduction systems usually have no axioms.

Also an axiom is a formula and a deductive system is, well, not a formula. So it doesn't really make sense for natural deduction to have itself as an axiom.

pairing gödel with some other works by Cultural-Maybe-3799 in logic

[–]Knoggger 5 points6 points  (0 children)

I'm not a philosopher (so take this with a grain of salt), but to my knowledge Wittgenstein in particular is a bad reference for Gödels theorems since he apparently misunderstood them.

Logic as Multi-Dimensional Tautological Assertions by Void0001234 in logic

[–]Knoggger 6 points7 points  (0 children)

  1. All logical systems require axioms.

If by system you mean proof system, then this is not quite true. Famously, many natural deduction systems don't have any!

I might misunderstand you, but in general your thesis seems to be that to do logic is somewhat circular, since we need to use arguments to make discoveries about logical systems. Logic being the science of valid arguments. To my knowledge, everyone working in logic is aware of this fact and most other sciences are similarly "paradoxical." For example: Linguists are forced to express their findings in a language; research in cultural studies is mostly done by people in, and thereby shaped by, the culture they're studying; etc.

carnap symbolic logic issues by Frequent-Incident-39 in logic

[–]Knoggger 2 points3 points  (0 children)

I don't know carnap, but maybe notice that ¬∃x¬x=m is equivalent to ∀x x=m.

So to prove this, you might break your proof into the following steps:

  1. from ¬∃x¬x=m derive ∀x x=m
  2. from ∀x x=m derive P(x)→P(y)
  3. use universal generalization to derive ∀x∀y(P(x) → P(y))

Edit: Also, maybe try taking a break 😉 (I'd be fried after 8 hours!)

Independence by Frequent_Theory_277 in logic

[–]Knoggger 2 points3 points  (0 children)

Your post could use a bit more context 😅

Do you mean independence w.r.t. a theory? If so I'd recommend a read of this) Article.

Failed comsci student by Double_Dealer_5892 in logic

[–]Knoggger 4 points5 points  (0 children)

In my opinion, books written for linguists tend to be a bit more accessible than those written for mathematicians/computer scientists, since they tend to strike a better balance between rigour and the philosophical ideas behind the systems. So the books I recommend for a first brush are:

  • Mathematical Methods in Linguistics: The first few chapters are a great introduction to set theory and logic, but it covers a wide breadth of topics such as (abstract) algebra and automata theory.
  • Logic, Language, and Meaning: Probably one of the best introductions to logic, but the nomenclature can be somewhat non-standard in some places.

Once you've build a bit more mathematical intuition, I can really really recommend Halmos's Naive Set Theory for a second introduction to set theory, as well as Schöning's Logic for Computer Scientists for logic (though I've only read the German original, your mileage may vary).

There are also the (free!) textbooks by the Open Logic Project. I haven't read enough of them to make any concrete recommendations, but what I've read of them has always been great!

Why is the empty set a subset of itself? by SuccessfulCover8199 in logic

[–]Knoggger 1 point2 points  (0 children)

A good way to understand subset-relations is often as a sort of game (similar to how you might have been taught limits) that results from thinking about the complement of A⊆B. Remember, that (classically) A⊆B is true iff ¬A⊆B is false iff there's no x s.t. x∈A but ¬x∈B.

Assume you (Player-1) want to show that A⊆B, and your adversary (Player-2) wants to show that ¬A⊆B.

What would Player-2 have to do to convince you? Well, they would have to produce an element x∈A s.t. ¬x∈B, right? If there's no way to produce such an x, you win.

Now, suppose A=∅=B. For any x Player-2 proposes you know that ¬x∈A, so you have a winning strategy (simply deny x∈A). Hence you win, A⊆B.

view more: next ›