Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
1answer
32 views

Boolean algebra proof - I don't know why this is valid!

So this is the answer proof I was given, I'm stumped by the final application of the Idempotent law (where does that 1 come from!?) As I understood it a 0 or 1 can only come from a combination of A ...
0
votes
1answer
28 views

Push Down Automata

I've been stuck on this one problem for a couple of days now with no clue on how to complete it. Construct a PDA which accepts precisely the language $\{a^{2n} (bc)^n\mid n \in \mathbb{N}\}$. ...
1
vote
1answer
79 views

Have we found a Turing Machine for which halting/non-halting is unprovable?

The undecidability of the Halting Problem implies that there exist Turing Machines such that you can't prove whether they halt or not in whatever logical system you're using (let's say ZFC)$^1$. Have ...
0
votes
3answers
80 views

'If…then…' and '…if…' and '…only if…' and 'If… only then…' statements?

Suppose you have two statements A and B and "If A then B". I am trying to think of what this implies and alternative ways of writing this. I think "If A then B" = A$\rightarrow$B = "A is ...
2
votes
0answers
21 views

Sufficient conditions for a quotient algebra to be finite?

Here's the set up. I have a finite set of elementary letters, and a finite set of operations on the set and I form the free algebra. For concreteness, let's imagine I have two binary operations ...
1
vote
0answers
35 views

Does $T \models \forall \bar v (\phi(\bar v) \leftrightarrow \forall \bar w \psi(\bar v,\bar w))$ implies this formula?

Finishing the title, Does $$T \models \forall \bar v (\phi(\bar v) \leftrightarrow \forall \bar w \psi(\bar v,\bar w))$$ implies $$T \models \phi(\bar v) \leftrightarrow \exists \bar w \psi(\bar ...
0
votes
0answers
12 views

Adding or multiplying by a constant each time to a set of numbers to obtain desired numbers

Suppose there is a finite set of integers $X = \{x_1,x_2,..,x_n\}$. For each single arithmetic operation, one can only operate on every integer in the set. (For example, we cannot multiply one number ...
3
votes
1answer
34 views

How to prove an equality in a Lindenbaum-Tarski algebra?

Let $\mathscr{L}'= \mathscr{L}\cup \mathscr{C}$ be an extension of the language $\mathscr{L}$ with a new infinite set of constants $\mathscr{C}$, and $T$ be an $\mathscr{L}$ theory. I wish to show ...
0
votes
0answers
46 views

Proof of $(P \to R) \lor (Q \to R)\, is\,equivalent\, to\,(P \land Q) \to R$

I am working through Velleman’s ‘How to Prove It’. This is one of the problems where I am a bit stuck. $(P \to R) \lor (Q \to R)\, is\,equivalent\, to\,(P \land Q) \to R$ I use the Conditional ...
0
votes
1answer
51 views

Question on branches and $\iff$.

For real-valued functions $f$ and $g$ of a real variable $x$, is the statement $$f(x)+ig(x)=0\iff e^{f(x)}(\cos(g(x))+i\sin(g(x)))=1,$$ correct? I'm concerned about the branch when taking the ...
0
votes
0answers
32 views

Formalize “Statement $A$ is the correct explanation of statement $B$”

If I have two statements. Let say Statement $A$ and Statement $B$. What will be the necessary condition or how to write the following conditions mathematically? Statement $A$ is the correct ...
0
votes
1answer
41 views

Iterating proof step

Many books proves theorems by performing one proof step and using this step as a scheme they say by repeating this step $l$ times we prove that... I wonder whether there is some formal meta-theorem ...
1
vote
0answers
32 views

Proof that $\cal K$ is an elementary class iff $\cal K$ is closed under elementary substructures.

Assume $\cal K$ is a pseudo elementary class. I need to prove that $\cal K$ is an elementary class iff $\cal K$ is closed under elementary substructures. Pseudo elementary class is a class of reducts ...
1
vote
1answer
31 views

Consistent recursively axiomatizable theory

This is question 4 page 234 of Enderton's Mathematical Introduction to Logic, section 3.4 on the "Arithmetization of Syntax": Let $T$ be a consistent recursively axiomatizable theory (in a ...
1
vote
1answer
32 views

Does elementary equivalence imply L-equivalence for structure L?

Does elementary equivalence imply L-equivalence for structure L? In the textbook "A Shorter Model Theory" by Wilfrid Hodges, page 39 defines both of these terms but does not tie them together. I was ...
1
vote
1answer
41 views

Why if the antecedent P is false, and the consequence Q true, then the implication P $\Rightarrow$ Q is true? [duplicate]

I know that that's the definition but I wonder why logicians choose that thefinition to be true. It sounds strange to me and I cant make sense of it if someone tell me 'if the sky is red, then I'm ...
1
vote
1answer
34 views

Permutations: Discrete Math

How many permutations are there of the set $(a,b,c,d,e,f,g)$ My Answer: Since there are 7 elements in the set, $7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040$ Am I right?
2
votes
1answer
73 views

Very Simple Model Theory

I'm working through the fifth edition of Dirk van Dalen's 'Logic and Structure' and got stuck in section 4.3 on model theory. Let a structure (of some type) be a tuple $ \mathfrak{A} = (A; R_1, ...
4
votes
0answers
33 views

Proving $\square(\forall v_1\neg\psi(v_1))\rightarrow\forall v_1\neg\psi(v_1)$ for a particular $\psi$.

I have a formula $\psi(v_1)$ that is equivalent in $\mathrm{PA}$ to $$\exists a\exists b\exists c\left[\neg\exists ...
2
votes
1answer
73 views

Did I use axiom of choice in my proof?

I have two different affine open covers for a scheme $X$, say $X = \cup_{i \in I} U_i$ and $X = \cup_{j \in J} V_j$. For each $p \in X$, we know there exist some $i(p)$ and $j(p)$ such that $p \in ...
0
votes
1answer
24 views

Finding smallest set of real numbers according to a property

This is one of the example problem that has been solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x ...
0
votes
1answer
55 views

Let $\tau$ and $\rho$ be tableaus such that $\tau \leadsto \rho$. Prove that $\tau$ is satisfiable if and only if $\rho$ is satisfiable.

I have this definition: Let $\nu$ be any propositional interpretation. Let $b$ be any branch of a tableau. Say that $\nu$ is faithful to b if and only if for every formula, $A$, on the branch, ...
1
vote
1answer
54 views

Construct a calculus which produces exactly all pairs $(S,t)$, such that $free(t)=S$.

Construct a calculus which produces exactly all pairs $(S,t)$, such that $free(t)=S$. This calculus will operate on pairs $(S,t)$, where $S$ is a set of variables and t is a term. I've got an ...
1
vote
1answer
48 views

Logical equivalence please help [duplicate]

I've been stuck on this one problem for a couple of days now with no clue on how to complete it. I need to prove the following logical equivalence: $(\neg P \wedge \neg R) \vee (P \wedge \neg Q ...
1
vote
1answer
59 views

Prove Logical Equivalence [duplicate]

I've been stuck on this one problem for a couple of days now with no clue on how to complete it. I need to prove the following logical equivalence: (¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) is equivalent to ¬R ∧ (Q ...
1
vote
1answer
59 views

What is the difference between Boolean logic and propositional logic?

As far as I can see, they only employ different symbols but they operate in the same way. Am I missing something? I wanted to write "Boolean logic" in the tag box but a message came up saying that if ...
1
vote
1answer
102 views

Unable to prove this simple inference using sequent calculus

In a recent question, I asked if the folowing inference is valid provided that the variable $z$ does not occur free in $\Gamma$ (Note: No restriction regarding whether or not $z$ occurs free in $\phi$ ...
0
votes
1answer
29 views

Give the missing rules for the connective $\vee$. Also give rules for $\rightarrow$ (implication)

Consider the connetives $\neg$, $\wedge$ and $\vee$. Formulated using set-theoretic machinery, the rules for these, except $\vee$, have the form: $$\left\{ B_1,...,B \cup \left\{ \neg \neg \phi ...
1
vote
1answer
40 views

Showing $(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$ by distributive law(s)

I want to show that $$(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$$ by one of the two Distributivity Laws: $$P\wedge(Q\vee R)\equiv(P\wedge Q)\vee(P\wedge R)$$ $$P\vee(Q\wedge R)\equiv(P\vee ...
0
votes
2answers
52 views

Systems without the law of excluded middle

If my understanding is correct (indeed, I think Wikipedia says this same thing) there are systems of logic in which the law of excluded middle does not hold. I can see how in some kind of ...
2
votes
2answers
90 views

embdedding standard models of PA into nonstandard models

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...
4
votes
1answer
42 views

$\kappa$-saturated, $1$-types - $n$-types

Definition. Let $\kappa$ be an infinite cardinal. We say that an $L$-structure $\mathfrak{A}$ is $\kappa$-saturated iff all $1$-types over sets of cardinality less than $\kappa$ are realised in ...
3
votes
0answers
113 views

How should one understand the foundation of set theory?

I have read the answer of Carl Mummert for the question on how to avoid circularity. I would like to ask further as I want to study models of set theory. As I understand, with say assuming the ...
1
vote
0answers
55 views

Is this inference valid?

Is the following inference valid provided that the variable $z$ does not occur free in $\Gamma$ (Note: No restriction regarding whether or not $z$ occurs free in $\phi$ is assumed) ? $${ \Gamma \vdash ...
4
votes
1answer
111 views

No countable models

I want an example of a theory T with finite models of arbitrarily large size but T has no countably infinite model. I know that T has to be uncountable, but couldn't come up with an example. ...
1
vote
0answers
27 views

How to convert conjunction inside disjunction into CNF?

How do I convert something like $$\bigvee_{a\in A} \bigwedge_{i\in L} (x_{i,a} \wedge y_{i,a})$$ into CNF? The $x_{i,a}$ and $y_{i,a}$ are variables.
2
votes
1answer
41 views

In logic, is distributivity part of semantics or syntax?

For an example, consider the statement $A \land (B \lor C)$. The proposition $A$ distributes over $(B \lor C)$, so the statement is logically equivalent to $(A \land B) \lor (A \land C)$ Wikipedia ...
1
vote
1answer
41 views

Logic question involving prime numbers [closed]

Explain why the statement,“$n^2 + 4n + 3$ is a prime” is not true for any integer $n ≥ 1$.
0
votes
1answer
28 views

Induction solution for game of coins

Consider a game in which, initially, there is a pile of n coins placed on a table. There are two players who alternate turns. Each player, on her or his turn, removes either one, two, or three coins ...
1
vote
0answers
39 views

What does the statement “x is a diagram of classical logics” mean?

From the Wikipedia entry on quantum logic A more modern approach to the structure of quantum logic is to assume that it is a diagram – in the sense of category theory – of classical logics (see ...
0
votes
1answer
39 views

Why is that: $P \Rightarrow T$, truth value(P) = ?, but $(P\Rightarrow F) \Rightarrow$ Truth value (P) = F

Why is that: If: P :proposition. T: true statement F: false statement $$P \Rightarrow T $$ In this statement, we can not have for sure the Truth value of P (if P is T or F) , but, in this ...
2
votes
1answer
59 views

Connection between ultrafilters and maximal consistent sets

I have been told by reputable sources that ultrafilters over the set of all formulas in a given logic corresponds to a maximal consistent set of formulas in that logic, and I am trying to wrap my head ...
1
vote
1answer
55 views

Failures of categoricity not related to size?

The paradigmatic cases I know of theories failing to be categorical are cases that seem tied to the language's inability to distinguish between different infinite cardinalities of the theories domain. ...
0
votes
1answer
41 views

are these propositions equivalent, case xor and then?

I have the following sentence that should be converted into logical connectors: Either you eat healthy or you will get sick. One transformation that came into my mind was: ...
2
votes
0answers
47 views

Show there is no elementary extension of $\mathbb{N}$ with an element between $0$ and 1

I have been presented with the follwing question and i want to see if the method i have used works, i have my doubts. We recall that M is an elementary extension of $N= \langle \mathbb{N}; +, ., 0, 1 ...
0
votes
1answer
48 views

Every epimorphism in Sets is split: why is it equivalent to axiom of choice?

Suppose that $f: A \rightarrow B$ is epic in Sets. One can construct a section $s: B \rightarrow A$ of $f$ as follow: Let us define an equivalence relation $R$ on $A$ as follow: $aRa'$ iff $a, a' \in ...
1
vote
0answers
46 views

prove Lindenbaum’s lemma for a countable language

Been reading through some model theory and got to a section on constructing models from syntax and i have been presented with the following problem, sorry for the lack of solution i just have no idea ...
1
vote
1answer
60 views

What does it mean by Proving false

With respect to the recent finding of a bug in a Coq theorem prover in which false was proved, I'm asking this question. As a hobbyist studying maths, I'm ...
0
votes
1answer
18 views

Understanding the conditional in a specific case

The problem given was as follows: Let $f: A \rightarrow B$ be a surjective function. Let us define a relation on A by setting $a_0$ ~ $a_1$ if $f(a_0) = f(a_1)$ Does this definition mean that ...
1
vote
0answers
135 views

Validity of a few FOL formulas

How we can obtain that the following examples (in my book wrote) is logically valid, I) $ \exists y \forall x p(x,y) \to \forall x \exists y p(x,y) $ II) $ \exists x \exists y p(x,y) \to \neg ...