Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [logic]

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

0
votes
1answer
8 views

Tautological Equivalence and Transitivity

In propositional logic, let there be three sets of formulas $\Phi, \Phi', \Phi''$ such that $\Phi \Leftrightarrow \Phi'$ and $\Phi' \Leftrightarrow \Phi''$. Can transitivity be used here to deduce ...
0
votes
1answer
10 views

Natural deduction without premises given?

Normally when given a question like $Q \wedge P, R \vdash P \wedge R$ I can do box proof like: $\underline{Q \wedge P}\hspace{5 mm}$ (assumption) $\underline{P \hspace{5 mm} R}\hspace{5 mm}$ ($\...
0
votes
1answer
15 views

How to make an English sentence from a first-order logic formula with unbound variables?

I'll first quote the problem from 'Computability and Logic' by Boolos, Burgess, Jeffrey. 9.3 Consider a language with a two-place predicate P and a one-place predicate F, and an interpretation in ...
0
votes
1answer
11 views

Atomlessness of the Lindenbaum-Tarski $\sigma$-algebra of infinitary language $L_{\omega_1}$

Consider the Lindenbaum-Tarski $\sigma$-algebra $A$ of the infinitary language $L_{\omega_1}$ of propositional calculi. Since $L_{\omega_1}$ has $\omega_1$ propositional variables and allows ...
2
votes
1answer
41 views

Showing two sets of formulas are logically equivalent using induction.

Can someone let me know if my proof is okay for showing the following two sets are logically equivalent (in propositional logic)? I asked this a day or so ago but the post was very long, disorganized, ...
3
votes
2answers
31 views

Is there an (efficient) algorithm to determine whether an equation of two terms in the language of elementary set theoretic operators is an identity?

By elementary set theoretic operations I refer to those which are usually imaged in Venn diagrams -- union, intersection, set difference, etc. In the formulation of my question I included the word ``...
1
vote
2answers
38 views

Help writing the contradiction of this statement

I was given the statement and asked to write it out symbolically and negate it. "Given any integer $n>1$, there is a power of $2$ that is bigger than $n/2$ and less than or equal to $n.$" First, ...
-1
votes
0answers
18 views

Rule C proof (Math logic, Mendelson) [on hold]

The problem concerns the proof of the rule C (3rd ed.), when we get E y(k) C(k) (y(k)) imp A. It is obviously not enough to use just the proposition 2.18 (d), and we shall replace similar formula with ...
1
vote
2answers
29 views

Absorbing bounded quantifiers, formal proof?

Intuitively I get in arithmetic aka the natural numbers that: $\exists n\,\exists m\,(m < n \wedge P(m)) \Leftrightarrow \exists k\,P(k)$ But I am having problems finding a formal proof. What I ...
2
votes
1answer
42 views

Choicelike consequence of compactness

Could someone please elaborate on the proof of Corollary 3.2.? Why does one need a total order *on $F$* if one is just interested in well-ordering each $F_x$ (in order to choose one element)? Also, a ...
2
votes
1answer
71 views

When does $(\square P \land \square Q) \to \square (P \land Q)$ hold?

If all axioms of classical propositional calculus hold and we work in modal logic that is at least K (ie. extremely weak), it is trivial to show $\square(P \land Q) \to (\square P \land \square Q)$. ...
2
votes
1answer
75 views

A constructivist reading of the Church-Turing thesis

I recently asked myself a question concerning a constructivist reading of the Church-Turing thesis. Let us give the latter in the following formulation: put $EC(f)$ for "$f$ is effectively computable" ...
2
votes
0answers
39 views

Terminology for free variables

Suppose you have a proof along the lines of $$\begin{array} {rc} \text{Assume:} & x > 2 \\ & \vdots \\ & \text{Some logic stuff} \\ & \vdots \\ \text{Conclude:} & x > 1 \\ \...
0
votes
1answer
39 views

Is this a proposition?

For $x$ in the set of real numbers If $x^{2} > 0$ then $x > 0$ I am unsure whether this is a proposition. If $x^2 > 0$ is true then $x > 0$ is false and hence the statement is false. If $...
0
votes
1answer
22 views

Clarification on the formalization of tautological consequence

I have a mediocre question. Just to clarify, if a is a tautological consequence of b, then a ∨ b = b? It is assumed that a and b are literals.
1
vote
0answers
38 views

Godelian problems with logic puzzles

It occurs to me that the sort of reasoning common in many logic puzzles (e.g. https://en.wikipedia.org/wiki/Hat_puzzle or https://xkcd.com/blue_eyes.html), the persons involved all trust one another ...
-3
votes
1answer
23 views

What are two logical clauses that when solved together in two different ways lead to two different solutions? [on hold]

Construct an example of two clauses that can be resolved together in two different ways giving two different outcomes
1
vote
0answers
13 views

Definable subsets of a cartesian product of two structures

Below I reproduce a consequence of the Feferman-Vaught theorem, taken from Wilfrid Hodges' book Model Theory: Corollary 9.6.4: Let $L$ be a first-order language, let $A$ and $B$ be $L$-structures ...
-6
votes
0answers
43 views

What's wrong with this assertion of P = NP? [on hold]

I'm not a trained mathematician, but I have a hunch that P and NP are essentially two different views of the same phenomenon. So wondering what could be wrong with this. The essence of my argument is:...
19
votes
7answers
6k views

How can I argue that for a number to be divisible by 144 it has to be divisible by 36?

Suppose some number $n \in \mathbb{N}$ is divisible by $144$. $$\implies \frac{n}{144}=k, \space \space \space k \in \mathbb{Z} \\ \iff \frac{n}{36\cdot4}=k \iff \frac{n}{36}=4k$$ Since any whole ...
0
votes
0answers
18 views

Criterion for $\mathcal L$-structure to be a model of universal theory

Let $T$ be a universal (universally axiomatizable) theory of signature $\mathcal L$ without functional symbols. Let also $M$ to be an $\mathcal L$-structure. Prove that if every finite substructure of ...
0
votes
2answers
22 views

Proving that a set of connectives { # , T } is functionally complete / adequate

I am a little bit stuck trying to prove if a set of logical connectives {#, T} is functionally complete. For the ternary connective # we have; #(a,b,c) = T if there are 2 T's, #(a,b,c) = F otherwise....
2
votes
0answers
35 views

Prove that $\{ \phi \rightarrow(\psi \rightarrow \theta)\} \vdash \phi \wedge \psi \rightarrow \theta$?

Please, can you check is my solution of this problem $\{ \phi \rightarrow(\psi \rightarrow \theta)\} \vdash \phi \wedge \psi \rightarrow \theta$ good? First, I rewrote it like $\{ \phi \rightarrow(\...
34
votes
4answers
4k views

Why isn’t ‘because’ a logical connective in propositional logic?

In simple terms, could someone explain why there is not a logical connective for ‘because’ in propositional logic like there is for ‘and’ and ‘or’? Is this because the equivalent of ‘because’ is the ...
3
votes
2answers
53 views

Proving that first-order formulas can not distinguish sets of a certain size

Consider the set of first-order formulas over the empty signature, i.e. $\mathrm{FO}(\emptyset)$ (with variable set $Var$). The models over this signature are just characterized by their plain carrier ...
2
votes
1answer
40 views

ZF(C): Model or Inner Model

I am quite confused about models of ZF(C) set theory; in particular the wording that is used frequently. I have seen many cases of statements such as "assume $V$ satisfies ZFC" where $V$ is the class $...
0
votes
0answers
34 views

$\neg (\neg A) \rightarrow A$ part of the axioms of propositional logic? [duplicate]

When talking with a mathematics teacher the other day, we discussed these axioms in the context of proving tautologies with semantic tableaux: $(p\to(q\to p))$ $((p\to(q\to r))\to((p\to q)\to(p\to r))...
0
votes
1answer
21 views

Theorem statable in base system but not provable in base system?

On the wikipedia page for proof theory, under the section of reverse mathematics, it is stated that: For each theorem that can be stated in the base system but is not provable in the base system, ...
0
votes
0answers
21 views

Show that a proposition using even number of instance of each variable and $\Leftrightarrow$ is a tautology.

I need to show that given a statement using an even number of each of the variables $X_1,X_2,...,X_{n}$ and bi-implication connective is always a tautology.
1
vote
0answers
20 views

Elementary substructure and existentially closed

Definition. We say that $\mathcal{M} \models T$ is existentially closed if whenever $\mathcal{N} \models T$, $\mathcal{M}\subseteq \mathcal{N}$, and $\mathcal{N}\models \exists x \phi(x, a)$, where $a ...
-2
votes
2answers
32 views

logic - how to convert this formula

I have this formula: $$(X \wedge (Y \rightarrow Z)) \vee \neg(\neg X \rightarrow (Y \rightarrow Z))$$ Is it possible to convert it to this: $$X ↔ (Y → Z)$$ the truth table show that they are ...
0
votes
1answer
36 views

Show that $ \{ (\phi \wedge \psi) \rightarrow \theta \} \vdash \phi \rightarrow(\psi \rightarrow \theta)$

How to show that $ \{ (\phi \wedge \psi) \rightarrow \theta \} \vdash \phi \rightarrow(\psi \rightarrow \theta)$? I tried to do it using deduction theorem and got $\vdash((\phi \wedge \psi) \...
0
votes
2answers
15 views

Showing $\vdash (A\supset (A\supset B)) \supset (A\supset B)$

I am trying to show that $$\vdash (A\supset (A\supset B)) \supset (A\supset B)$$ My approach was to start with $$\begin{align} B, A\supset B, A\supset (A\supset B)\vdash (A\supset B) &\qquad(\...
0
votes
1answer
40 views

How does one formally show that bounded search with some property $R(a,x)$ is computable i.e. $\exists x \in \mathbf N (x < y \to R(a,x) )$?

Everything here is in the L-structure $\mathbb N = (\mathbf N;0,S,+,\cdot,<)$. I was following these notes and got stuck with the lemma 5.1.11 page 84 of paper (88 pdf): In this context we assume ...
2
votes
1answer
23 views

Notation of countable disjunction in infinitary logic

Let $L_{\omega_1}$ be a propositional infinitary language. The subscript $\omega_1$ in $L_{\omega_1}$ indicates that disjunctions and conjunctions of all lengths $<\omega_1$ are allowed. In other ...
2
votes
2answers
84 views

Löwenheim-Skolem and proper class models of ZFC. [duplicate]

Let $N$ be a proper class model of ZFC and $x \subset N$ a set. Show that there is a set $y \in N$ such that $x \subset y$. If $x \subset N$, I think that by the downward's part of Löwenheim-Skolem, ...
3
votes
2answers
31 views

Proof by deduction - implications

Currently trying to explain some maths to a friend. He has taken a statement $x^2 + 4 > 2x$ and tried to prove this is true for all $x$. His proof is $x^2+4>2x \Rightarrow x^2-2x + 4 > 0 \...
1
vote
0answers
51 views

Predicate Logic Hilbert Proof

In the Hilbert proof system for predicate logic, prove that the formula: $\exists x~\big(B(x)\to C(x)\big)\to\big(\forall x~B(x)\to\exists x~C(x)\big)$ I'm awful with Hilbert Proofs and have no idea ...
1
vote
0answers
60 views

Proving that first-order PA is not finitely axiomatizable

I am trying to prove that there is no finite set of first-order sentences that is an axiomatization of PA. My first attempts naturally aimed at showing that for any finite axiomatization of PA, call ...
-2
votes
1answer
22 views

Existence of total order for every set

please prove it from Compactness theorem for propositional logic. Don't assume AC in any form. I mean relation $<$ is total order for $X$ iff trichotomy transitivity irreflexivity are true about $...
1
vote
1answer
31 views

Is $P→(Q∧R)$ the correct answer?

I need to know if $P→(Q∧R)$ is the correct answer to this? $P =$ you can vote $Q =$ you are under 18 years old $R =$ you are from mars Based on the above information, construct the formal-logic ...
-1
votes
0answers
22 views

Expressing definitions as formulas involving quantifiers.

Recall (from calculus) that a function f is increasing if ∀𝑎∀𝑏(𝑎<𝑏⇒𝑓(𝑎)<𝑓(𝑏)). Express the following definitions as formulas involving quantifiers: f is decreasing. f is constant. ...
8
votes
1answer
70 views

A theory which seems to have proof-theoretic ordinal $\omega_1^{CK}$

I'm trying to understand proof-theoretic ordinals, and mistakenly "proved" there's a sound recursive theory of arithmetic with proof-theoretic ordinal $\omega_1^{CK}.$ That's impossible, so where does ...
-1
votes
2answers
41 views

Logical Induction

"Prove that the number of people making an odd number of handshakes is always even." Though it can be easily proved by Induction but I wanted to ask is it correct to state the problem otherwise like "...
0
votes
1answer
56 views

What are the requirements of a mathematical theorem? [on hold]

Most important, I would be interested on the fact that the theorem must be expressed with the least amount of words or requirements in order to be "elegant". I dont know how to describe, but I know it ...
4
votes
4answers
175 views

What is the intuitive explanation of $\exists y \theta(x,y) \to \psi(x)$ is the same to $\forall y ( \theta(x,y) \to \psi(x) )$?

I was studying first order predicate logic and discovered tha: $$\Sigma \vdash (\exists y \theta(x,y)) \to \psi(x)$$ is NOT the same as: $$\Sigma \vdash \exists y ( \theta(x,y) \to \psi(x) )$$ ...
1
vote
2answers
65 views

formulas such that either “$\mathcal{M} \vDash \phi$, then $\mathcal{M} \vDash \psi$” or “$\mathcal{M} \vDash \phi \rightarrow \psi$”

I'd appreciate your help with the following: I am looking for formulas $\phi$ and $\psi$ (in any suitable language $\mathcal{L}$) such that in the following exactly one condition is fulfilled, the ...
0
votes
0answers
27 views

Class of rings with all nilpotent elements is not axiomatizable

Prove that class of rings with all elements being nilpotent is not first order axiomatizable in signature $\{+, \cdot, 0, 1, = \}.$ I need some hints how to approach this problem. All similar ...
0
votes
0answers
29 views

The truth of sentences in first-order logic

I'm studying the subject myself from the book "A Friendly Introduction to Mathematical Logic" and I could not understand a corollary about the sentences saying that: "If D is a sentence in the ...
0
votes
2answers
32 views

Proof for $\lor$ Elim: rule in Soundness Theorem

So far I have been told to assume the line is invalid and then arrive at a contradiction. Suppose the first invalid step derives the sentence $C$ by an application of $\lor$ Elim to the sentences $A\...