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
13 views

Valid Formula in First Order Logic

I am a little confused about the validity of first order logic formulas. How we can using formal notation to prove the following is VALID? $ \exists x \exists ...
0
votes
1answer
22 views

Is an infinite, recursive predicate valid?

Consider the following predicate: $$P(x) =\ "True\ and\ P(x)"$$ Does it make sense to claim that $P(x)$ is true $\forall x$? Specifically, Consider the case where, instead of a boring $True$, you ...
3
votes
3answers
95 views

Are there two meanings to induction?

I've seen mathematical induction in two forms. First form: It seems that if $P(0)$ holds and $\displaystyle ...
0
votes
1answer
27 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
22 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
70 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
73 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
20 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
27 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
11 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
31 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
44 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
49 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
30 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
26 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
22 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
29 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
28 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
36 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
31 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
64 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, ...
-1
votes
2answers
35 views

Math Question - If it takes x hours to do this using x things, how long does it take.. type of question [on hold]

A soccer club owns five identical mowers. It takes 10 hours to mow the grass of the soccer field using two of the mowers. How long does it take to mow the grass of the same field using all five ...
4
votes
0answers
30 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
71 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
20 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
38 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
46 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
46 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
53 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
57 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
89 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
23 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
39 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
51 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
82 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
35 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 ...
2
votes
0answers
96 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
48 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
104 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. ...
-2
votes
0answers
50 views

please help me to undrestanding my qestiones? [on hold]

and other quetion The subset [0; 1] of the real line is a complete lattice, but it is not algebraic.why?
1
vote
0answers
23 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 ...
-5
votes
0answers
28 views

Proof theory and the generalized Riemann hypothesis [closed]

Is there a way to disprove the following? CONJECTURE: Let χ be a Dirichlet character modulo q. Let ɛ be a positive number with 0 < ɛ < ½. Let T be a positive number > 10. Then within ZF, where ...
1
vote
1answer
37 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
25 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
38 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 ...
1
vote
1answer
56 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 ...
0
votes
0answers
23 views

Boolean Algebra Combinational Circuit [closed]

I'm trying to solve the following circuit: There is $a$ number greater than zero that is written with n binary numbers: $$(x_{n-1} x_{n-2} \cdots x_1 x_0)_{\text{base }2}$$ Design a ...
1
vote
1answer
53 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. ...