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 ...

learn more… | top users | synonyms (1)

3
votes
5answers
337 views

Can mathematics be traced back to a fundamental system of truths?

I'm not sure exactly how to state this question, or even if it belongs here. Still, I hope you will consider it, as I find it very interesting: Most of the results I've seen in mathematics come from ...
2
votes
1answer
45 views

Equivalent formula in countable structures

Question, if two sentences A & B, are such that for all countable structures M: M⊨A iff M⊨B, and A & B be thus logically eguivalent. But how?! I understand that I have to use ...
0
votes
1answer
83 views

The definition of interpretation in a Kripke model collides with my intuition of what it should do

In Lindröm and Segerberg (2007) exposition of a Kripke model, with frame $F= \langle W,D,R,E,w_0\rangle$, they define an interpretation $I$ as a family of functions $I_w$, where $w$ ranges over ...
2
votes
1answer
71 views

Are all theorems of minimal arithmetic theorems of a given theory?

I am working on some metamathematics revision and the following question came up. Let the theory $R_0$ be axiomatized by the following axiom schemata which hold for all $n,m \in \mathbb{N}$: ...
1
vote
4answers
5k views

Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the ...
3
votes
1answer
66 views

Intuitionistic logic and explicit existence proofs

I have read that to intuitionistically prove a statement of the form $\exists x.\varphi,$ we have to actually describe such an $x$ as an explicit expression (with free variables from $\varphi$, ...
1
vote
1answer
125 views

First Order Logic “More Than One”?

I'm trying to figure out how to express "More than one" in first order logic. What I have so far is: $$\exists S_1 \exists S_2 IsGreen(S_1) \wedge IsGreen(S_2)$$ But that definitely doesn't sound ...
2
votes
1answer
54 views

Logic verification: $x^3$ is irrational, then $x$ is also irrational

Prove, by contraposition, if $x^3$ is irrational, then $x$ is also irrational. Just a verification do I need to show that given $x$ is rational $x^3$ is also rational? Suppose $x \in \mathbb{Q}$ ...
3
votes
1answer
144 views

Theorems that we can prove only by contradiction

While most of the world is fine with proofs performed by contradicting the thesis, direct proofs are sometimes considered more elegant than indirect ones. Those who prefer intuitionism or ...
1
vote
1answer
46 views

Question about the total probability law

Why does $A= (A \cup B) +(A\cup C)$ and not $(A \cap B)+(A \cap C)$? Wouldn't you have to take the intersection to have elements of just $A$ instead of having the elements that $A$ overlaps with? ...
3
votes
2answers
88 views

Epistemic logic: in which worlds are the formulas true?

I have a question regarding the following: I don't get both answers. I thought that question 1 was true in w2, w3, w4. But the answer does not show have w3. Why is that? Because the symbol says ...
2
votes
1answer
33 views

How to quantify a specify amount in logic

I'm looking for a way to specify the number of times an event happens in a Discourse Representation Structure, basically using first order predicate logic. I have the existential and universal ...
2
votes
2answers
602 views

How to explain the power of PA to non-logicians

I plan to give a talk to a group of math PhD students (with no exposure to mathematical logic. I should also mention that I'm certainly no logician, myself) about the incompleteness theorems. I plan ...
1
vote
5answers
74 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
0
votes
0answers
68 views

What do we call functions that are definable by expressions?

Let $X$ denote a model of an algebraic theory $T$. What do we call the functions $f : X^n \rightarrow X$ that are definable by some expression in the language of $T$? e.g. If $S_3$ is the symmetric ...
2
votes
2answers
51 views

What does rule schematic mean?

While I'm studying the mathematical logic, the book says "Each rule of such a calculus either says that certain strings belong to $Z$, or else permits the passage from certain strings ...
0
votes
0answers
107 views

The unique model of cardinal $\kappa$ of a $\kappa$-categorical countable theory is saturated.

Let $T$ be a $\kappa$-categorical ($\kappa \geq \aleph_1$) first-order theory in a countable language $\mathcal L$. I try to prove that its unique (up to isomorphism) model of cardinal $\kappa$ is ...
0
votes
1answer
188 views

Do syllogisms apply to probabilistic statements?

I came across a statement that triggered my logic 101 alarm on another SE site, regarding risk factors for an illness. The statement was similar to this (modified): Favoring green jelly-beans is ...
1
vote
1answer
266 views

What is the definition of “Winning Strategy” in an Ehrenfeucht-Fraïssé game?

I've read many descriptions and applications of a Winning Strategy, as much as many for a Strategy tout court, but when a formal, algebraic definition is called upon, I've found close to no input. I ...
2
votes
1answer
259 views

Some burning questions on First-order logic from an amateur

I'm currently taking an introductory course in Mathematical logic(prerequisites is only advanced calculus) and my lecture notes are based on Enderton's book 'Mathematical Introduction to Logic' ...
1
vote
1answer
115 views

How to prove if two propositions are always true

Let P1 and P2 denote the following propositions: P1="CS is difficult or not many students like CS". P2="If math is easy, then CS is not difficult". Suppose that both P1 and P2 are true, determine if ...
1
vote
1answer
51 views

big o statement prove or disprove (impossible)

This question is harder than it looks folks for all a in the reals and for all b in the reals, [(a <= b) => (n^a is O(n^b))] n^a is O(n^b) if n^a <= cn^b for some n>= n, (n less than or equal ...
1
vote
1answer
149 views

Prove formula in Predicate Logic

Prove the following $$ \vdash A \land (\exists x) (B \rightarrow C) \equiv (\exists x)(B \rightarrow (A \land C)) $$ as long as $ x$ not free in $A$. This is question number 9 chapter 6 in ...
0
votes
1answer
182 views

rewriting quantifiers using propostional expressions

Let the domain of the propositional function P(x) be D={a,b,c}. Express the following quantified statements without using quantifiers but as logical expressions of P(a), P(b) and P(c) using AND, OR, ...
0
votes
1answer
67 views

Clarification about the definition of term algebras

The following definition has been given in this article. A term algebra is an algebra $ \langle \mathcal{S}, \mathcal{G} \rangle $ where every time that $g_\alpha, g_\beta \in \mathcal{G}$ and $$ ...
2
votes
3answers
68 views

Proving $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$.

How do I prove using boolean algebra that $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$? I can see it in the logic table and it is logical, but I can't prove it mathematically.
3
votes
3answers
99 views

#23 on GRE 8767

I am unsure how I would do the work for this question: $S(n)$ is a statement about positive integers $n$ such that whenever $S(k)$ is true, $S(k+1)$ must also be true. Furthermore, there exists some ...
3
votes
1answer
264 views

What is the converse of the triangle inequality?

It's usual when presenting a theorem to also present its converse. Surprisingly, I've never seen the triangle inequality's converse stated. Triangle inequality: If the sides of a triangle are a, b, ...
0
votes
1answer
35 views

Can all cardinal numbers be represented by an ordinal numbers, assuming choice?

Can all cardinal numbers be represented by ordinal numbers, assuming AC? (ZF+AC) If or if not, what would be the proof?
4
votes
0answers
126 views

Logic in closed symmetric monoidal categories; reference request.

Suppose we want an algebraic theory $T$ to be interpretable in any closed symmetric monoidal category $\mathbf{C}.$ I am thinking in particular of the case where $\mathbf{C}$ is the category of models ...
0
votes
1answer
57 views

Propositional Logic Proof [closed]

how to prove this statement using propositional logic. The idea is in my head but i just can't seem to figure it out. Here is the statement : (A->B)^(B->(C->D))^(A->(B->C))->(A->D) This is what i've ...
0
votes
1answer
343 views

What is the use of Tarski-Vaught test?

As title says, what is the use of Tarski-Vaught test? I do understand that it is necessary and sufficient criteria for $N$ to be an elementary substructure of $M$, but beside that I don't see how this ...
1
vote
2answers
68 views

What exactly is $L$-terms in model theory?

I got confused after seeing the inductive definition of $L$-terms in model theory. So I do get that there are variables and constants, and when function $f$ is applied to the term, the resulting thing ...
2
votes
1answer
126 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
0
votes
2answers
98 views

How many Scythians were there?

I was doing a maths test yesterday and the last question on the exam was as follows: $2500$ years ago, a Scythian king called Ariantas ordered every one of his subjects to bring him an arrow head. ...
2
votes
5answers
280 views

Question about definition of binary relation

Wikipedia says: Set Theory begins with a fundamental binary relation between and object $o$ and a set $A$. If $o$ is a member of $A$, write $o \in A $. I thought that a binary relation is a ...
1
vote
1answer
3k views

Simple Equation? [duplicate]

You saw a T-shirt of sh 97, since you don't have cash you borrow sh50 from your dad and sh50 from your Mom. Now you have sh100. You purchase a T-shirt for sh97 and left with sh3.00 change. You return ...
6
votes
3answers
684 views

Give a proof that “p & ~p” implies “q”?

Context: This is not a textbook or homework problem. I was hoping you younger folks could help my tired old brain. "Everybody knows" a contradiction implies anything. What I'm looking for is a ...
2
votes
1answer
123 views

compound proposition logically equivalent

I can not solve this question Find a compound proposition logically equivalent to $p \to q$ using only the logical operator $\downarrow$.
3
votes
1answer
57 views

Can a quasi-identity express that a function $f$ is surjective? And if not, can this be explained by duality?

Consider a first-order theory having a unary function symbol $f$. Then the following quasi-identity expresses that $f$ is injective. $$\forall xy : f(x)=f(y) \rightarrow x=y$$ Alternatively, we can ...
2
votes
2answers
491 views

Prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction

I am trying to prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction. Here is my attempt using JAPE application. ...
1
vote
1answer
299 views

A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
2
votes
1answer
71 views

If $\phi$ is satisfiable and $\mathscr{S}$ is countable, then the set of all models of $\phi$ has the cardinality of the continuum

I have just started reading Chang and Keisler and I'm already stuck in an exercise. Let $\mathscr{S}$ be a countable set of sentence letters (i.e. $\mathscr{S} = \{S_0, S_1, S_2, \dots\}$ or some ...
2
votes
1answer
36 views

choosing elements from the set of sequences in ZFC

In my previous question, I asked about infinite-length formula in ZFC. But I am still confused over following: Suppose you want to build a function from a set of sequences to a set that chooses $n$th ...
4
votes
2answers
203 views

Is infinite-length formula allowed in ZFC?

I am curious whether infinite-length formulas are allowed in ZFC. If it is not, then how does it express the case where infinite number of terms (in ordinary mathematics) are being handled? (Like ...
6
votes
2answers
112 views

Closed form of generating function consisting of power of two binomials

Let $g(x)$ be infinite formal power series and $$g(x) = (1 + x)(1 + x^2)\cdots(1 + x^{2^k})\cdots$$ Show that $(1 - x) g(x) = 1$. My book gives following proof: Using a fact that $(1 - x^k)(1 + ...
0
votes
1answer
206 views

How can I simplify this boolean equation for the multiplexer a little further?

I've obtained a formula through cannonical representation, which is: $$A\cdot \overline{B\cdot S}+A\cdot B\cdot \overline{S}+\overline{A}\cdot B\cdot S+A\cdot B \cdot S$$ And I'm trying to simplify ...
2
votes
1answer
76 views

Do the circle groups have any interesting stand-alone descriptions?

By the circle groups, I mean firstly the circle group $\mathbb{T} \subseteq \mathbb{C}$ of all complex numbers having modulus $1$, and secondly the commutative group $\mathbb{S} = \mathbb{T} \cap ...
0
votes
1answer
59 views

Induction and Implication

The axiom of induction in logical symbols is: $$ \forall P[[P(0) \land \forall k \in N (P(k) \implies P(k+1))] \implies \forall n \in N[P(n)]] $$ If $P(0)$ is true and $P(k)$ is false (therefore ...
7
votes
2answers
344 views

There is a second-order sentence that is valid in standard semantics but not valid in Henkin semantics?

Let $\Sigma^\mathrm{ST}$ be a set of sentences that is valid in standard semantics and $\Sigma^\mathrm{Henk}$ be a set of sentences that is valid in Henkin semantics. Since ...