Questions about logic and 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)

5
votes
1answer
68 views

If a statement holds for all standard models of PA, then does it hold for all models?

Suppose that $\varphi$ is a consequence of every standard model of PA. Then is it provable from PA?
4
votes
2answers
94 views

Is it possible for two non-isomorphic groups to satisfy the same first-order sentences and be equicardinal?

My question is the same as the title. A proof or a counterexample would be nice.
0
votes
0answers
24 views

XOR with multiply operation.

can I do that $((A*5) \oplus A)==A*(5\oplus1)?$ and that $(A \oplus B/2) == ((2*A) \oplus B)$? Thanks.
0
votes
1answer
45 views

What are techniques for proving undecidability or unprovability of a sentence?

I asked a question the other day on how to form logical equivalence between a sentence $\phi$ and two other sentences $\psi$ and $\chi$, such that neither $\psi$ nor $\chi$ were on their own as ...
0
votes
0answers
61 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
2answers
73 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
44 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
4
votes
1answer
59 views

Minimize $(A\land\neg C)\lor(B\land C)$

Is it possible to write following expression with each variable occuring only 1 time and using any of operations $\land\neg\lor\oplus$ ? $$(A\land\neg C)\lor(B\land C)$$
3
votes
1answer
41 views

A question about commutative algebraic theories and free elements on one generator

Let $T$ denote a commutative algebraic theory with a constant symbol. (We definitely need to assume that $T$ has a constant symbol, otherwise the algebraic theory of idempotent Abelian semigroups is ...
0
votes
3answers
154 views

How do we define equality in real numbers?

How do we define equality in real numbers? I know in logic we define equality by Leibniz's law. $$ \forall x \forall y[x=y \rightarrow \forall P(Px \leftrightarrow Py)] $$ But how do we define the ...
3
votes
0answers
37 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
0
votes
1answer
122 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
2
votes
1answer
100 views

Why didn't Frege succeed in his attempts to reduce mathematics to logic?

My background: Sophomore-level understanding of mathematics and philosophical logic. All the explanations I have found online so far are either far too technical or too simplistic. Thanks in advance ...
0
votes
2answers
83 views

Help with a modal Hilbert-style proof of (□(a>b)&◊(a&c))>◊(b&c)

Can't grasp how it can be proved. To proof just propositional calculus formula (without modal operators) at first seems rather natural to me. Tried the law of importation scheme but it didn't work ...
0
votes
1answer
21 views

Prove or disprove $ \exists x \in S [ p(x) \land q(x)] \iff [\exists x \in S p(x)] \land [\exists x \in S q(x)] $

I proved it as follows. Can anybody tell me if it is correct or wrong? Assume $ \exists x \in S [ p(x) \land q(x)] $ , Let $ x_0 \in S, st [ p(x_0) \land q(x_0)]$ $p(x_0)$ and $ q(x_0) $ Let x ...
1
vote
3answers
86 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
0
votes
0answers
36 views

Model-theory : questions regarding back-and-forth sets

See my previous post for the basic definitions from Jouko Väänänen, Models and Games (2011), page 54-on. See page 64 for : Definition 5.14 Suppose $\mathcal A$ and $\mathcal B$ are ...
2
votes
2answers
45 views

'Algebraic' way to prove the boolean identity $a + \overline{a}*b = a + b$

For me, it is pretty clear that $a + \overline{a}*b = a + b$, because the first $a$ in the or will make sure that if the second term must be 'evaluated', $a$ will ...
1
vote
2answers
44 views

implication versus conjunction correctness in FOL?

I've just started learning FOL and I'm really confused about whether to use conjunction or implications. For example, if I want to represent ...
2
votes
1answer
36 views

Is there a phrase to describe those objects of $\mathbf{C}$ that can be expressed as quotients of the algebra freely generated by $X$?

Let $\mathbf{C}$ denote the category of models of an algebraic theory in $\mathbf{Set}.$ Now suppose $X$ is an object of $\mathbf{Set}$. Is there a traditional phrase used to describe those objects of ...
1
vote
1answer
46 views

Model-theory : questions regarding partial isomorphism

I'm having problems with the first pages of Bruno Poizat, A Course in Model: Theory An Introduction to Contemporary Mathematical Logic (ed or 1985), specifically with local isomorphism and back- and ...
0
votes
1answer
40 views

Decidability…

I'm confused about what my book is saying here. It's a bit long so I have an image of it here (if that's okay?) https://docs.google.com/document/d/1ssy3P06dqSAhREuRbr9PNj6CYYe4_HdcITg1X4kx8PM/edit ...
1
vote
1answer
29 views

What techniques are there to search for first order sentence equivalence?

Suppose we have a first order sentences $\phi$, $\psi$, and $\chi$ such that: $\phi$ $\longleftrightarrow$ ($\psi$ $\land$ $\chi$) And $\phi$ and $\chi$ are known or fixed. How can we search for a ...
1
vote
1answer
54 views

What paradigm of automated theorem proving is appropriate for Principia Mathematica-style formalization?

I am in possession of a book, which, inspired by Russell's Principia Mathematica (PM) and logical positivism, attempts to formalize a specific domain by determining axioms and deducing theorems from ...
7
votes
1answer
155 views

Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
2
votes
2answers
42 views

$(\forall x\in S)P(x)\equiv \forall x(x\in S\Rightarrow P(x))$ What does it mean?

$(\forall x\in S)P(x)\equiv \forall x(x\in S\Rightarrow P(x))\\(\exists x\in S)P(x)\equiv \exists x(x\in S\wedge P(x))$ What I think it means: 1) For all $x$ in $S$, $P(x)$ holds true = for all $x$, ...
1
vote
1answer
32 views

From statement to logic

I have a problem with the modelling of the following statement in propositional logic (warning, I translated it from italian): Martha is not a singer, and she doesn't play violin or flute, but not ...
2
votes
4answers
464 views

What is the truth table for demorgan's law?

From Demorgan's law: $(A \cup B)^c = A^c \cap B^c$ I constructed the truth table as follows: $$\begin{array}{cccccc|cc} x\in A & x \in B & x \notin A & x \notin B & x \in A^c ...
0
votes
2answers
59 views

Finding boolean/logical expressions for truth table + explanation [closed]

I'm having very hard time finding boolean expressions from truth tables. I've also tried many tricks but still can't get through...think you guys can help me with this??...you'll be doing this lil ...
0
votes
1answer
22 views

Simplification of a Disjunctive Normal Form Logic Equation

So I'm fairly new to logic equations and I've been given a pretty big logic equation to simplify and just need a bump in the right direction to figure out where to go. I've been told it's going to be ...
-3
votes
2answers
59 views

check the formulas for satisfiability and validity [closed]

Could perhaps somebody explain me how to define if a formula is valid, satisfiable, or not satisfiable if ...
0
votes
1answer
56 views

particular property and completeness?

I was puzzeling with the almost standard definition of completeness: In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula ...
6
votes
1answer
175 views

What is semantics of “type”? Do “types” of “type theory” semantically differ from “set” of set theory?

"To be of a (certain type)" is a fundamental relationship for ontology and the computer science "ontologies" are in the core of Semantic Web (which is my interest). But I did not encounter a ...
4
votes
3answers
185 views

Simplifying a categorical proof of constructive dilemma

In axiomatic propositional calculus the following axiom schema captures constructive dilemma: $\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$ \begin{equation} (a \lif c) \lif ((b \lif c) ...
1
vote
0answers
47 views

Divisibility is not definable over $\mathbb{N}$ with coprimality relation

I am asked to show that the divisibility relation "|" is not definable over $(\mathbb{N},\perp)$, where "$\perp$" is the coprimality relation. I am pretty sure that I should use the following: ...
1
vote
1answer
70 views

Show that if $L$ is countable and contains a two-place predicate symbol, there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$

We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific ...
1
vote
1answer
47 views

Completeness theorem for intuitionistic logic

Reading from Wikipedia about intuitionistic logic, I am guessing that there is a formal proof system for intuitionistic logic. (Note: My knowledge of intuitionistic logic is almost nil). My ...
1
vote
2answers
39 views

Abelian/Isomorphic logic statement

I don't understand this logic statement. I don't think the context helps at all but I thought i'd include it anyway. $G$ is abelian and $H$ is not abelian, then $G\ncong H$, is the same as: $G$ ...
0
votes
2answers
30 views

Showing that $A \cap X = A$ for all $A$ if and only if $X = S$.

I have the following task: Let $S$ be a nonempty set. All capital letters will denote subsets of $S$. Show that $A \cap X = A$ for all $A$ if and only if $X = S$. This does not seem to true. ...
1
vote
1answer
24 views

Propositional calculus , axiom scheme independence proof

I am studying mathematical logic from Mendelson's "Introduction to mathematical logic" and have difficulty understanding the intuition behind his proof of independence of axiom schemes introduced for ...
1
vote
2answers
47 views

Derivation of Null Quantification in Logic?

I was reading page 10-8 of this: https://faculty.washington.edu/smcohen/120/Chapter10.pdf and I was wondering if the distributive qualities could be derived, e.g. $\forall x (P \lor Q(x)) ...
0
votes
0answers
24 views

Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?

Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
1
vote
1answer
36 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
1
vote
1answer
35 views

Can a predicate in logic operate on something undefined ? Is $P(x)$ true or false for $x$ undefined, where $P$ is a predicate?

Can a predicate in logic operate on something undefined ? Is $P(x)$ true or false for $x$ undefined, where $P$ is a predicate ? To be more concrete: Is $x \le 5$ true or false for $x$ undefined ? ...
-1
votes
1answer
74 views

Mathematical Logic Problems [closed]

True or false(and why): If T is a set of logical sentences which is logically contingent and T' so that T' $\subset$ T, then T' is also logically contingent Prove that $$\phi \lor \psi, \lnot \phi ...
0
votes
1answer
52 views

Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ elementarily nonequivalent structures for $L$?

Let $L$ be a set of specific symbols and $\operatorname{Form}(S)$ be the set of all first-order formulas over $L$. Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ ...
1
vote
1answer
85 views

Arrows-only implication & disjunction in $\mathbf{Set}.$

Just before the truth-arrows in a topos subsection of Goldblatt's "Topoi: A Categorial Analysis of logic," descriptions of the truth functions $\Rightarrow$ and $\smallsmile$ are given in ...
0
votes
2answers
58 views

Ordinal existence

Is there any ordinal $\alpha$ such that $\omega ^ {\omega ^ \alpha} = \alpha$? Could you please suggest me how to even try to solve this?
2
votes
1answer
21 views

Proposition Question

I am trying to translate this into propositional symbols but (for me) it's so complicated. Can someone help me figure this out. "If it rains then I will carry a sharp object and I will start laughing ...
2
votes
1answer
56 views

How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?

I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that ...