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)

2
votes
1answer
69 views

Building math theory on absurd axioms - reducing math to logic

I know similar questions have been asked and i know my terminology might be wrong but I am trying to come to an answer to whether math can be derived from logic. Wikipedia defines logic as use and ...
1
vote
1answer
22 views

Give the following expression in the form of a formula:

Does anybody know how to give the following expression in the form of a formula? Let $P$ be the set of all people, and let $K$ and $M$ be binary predicates on $P$ with the following ...
0
votes
2answers
42 views

Prove by Simple Induction that $12^n − 1$ is divisible by $11$ for each $n \in \mathbb N.$

Since $12^n-1$ is divisible by $11$ for small $n$ cases i.e. $(1,2,3,\ldots$, etc), I want to prove that $12^{n+1} -1$ is also divisible by $11$. what I wrote down: ...
2
votes
2answers
44 views

First order formula defining a predicate which asserts that a set is finite.

Is it possible to define a predicate in the first order language of set theory such that $F(x)$ is true iff $x$ is a finite set? I understand that FOL cannot assert that the domain of discourse is ...
1
vote
1answer
45 views

Propositional language has an independent set of axioms

Let $\mathcal{L}_0$ be the language consisting of all propositional symbols $A_n$, along with all formulas formed by using $\neg$ and $\to$. In other words, it is the smallest set $L$ such that $A_n ...
0
votes
4answers
23 views

propositional logic, does An have to be a numerical expression/equation?

So if the $propositional$ $symbols$ are $A_{n}$ for all $n$ in the natural numbers, does that mean that our statements are not in terms of sentences with true/false values (which can be represented by ...
2
votes
2answers
102 views

Is constructive proof of non-existence possible

Constructive proof construct(indicates) object that satisfies given predicate. Question is whether one can give constructive proof of non-existence of an object with given property e.g. that every ...
2
votes
3answers
31 views

propositional language. don't understand the definition?

I'm taking a mathematical logic class, and I don't understand this definition of the $propositional$ $language$, as given by my book: "The propositional language $\mathscr{L}_0$ is the smallest set ...
0
votes
0answers
26 views

Is equality the same as equivalence, and if so, how many? [on hold]

In other words, is $(= \vdash \equiv ) \wedge (\equiv \vdash =)$ true? If so, what is $\left|(= \vdash \equiv) \wedge (\equiv \vdash =)\right|$
-1
votes
1answer
35 views

Valid inference or not?

(For some reason I can't write at the bottom). (1) For all real numbers $x$, either $p(x)$ or $q(x)$. (2) $a$ is a real number. (3) [Not sure I understand. Some help would be appreciated.] $$ ...
1
vote
2answers
46 views

What does completeness mean in propositional logic?

During one of the lectures in logic, My prof proved completeness and soundness of Hilbert system of axioms or simple axiom system as in ...
0
votes
0answers
34 views

Proof of Propositional Compactness Theorem

I am going through the proof for the following form of compactness theorem. Statement: If Φ is an unsatisfiable set of propositional formulas, then some finite subset of Φ is unsatisfiable -- ...
2
votes
2answers
87 views

Fixed point combinator and functions with no fixed point

In lambda calculus the fixed point combinator is defined as: It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. At the same time I wonder what is the meaning of ...
0
votes
2answers
24 views

Boolean Algebra Simplification

How do I simplify the following equation? $\newcommand{\pn}{\phantom{\neg}}$ $$\begin{align*} \neg A\pn B \neg C \neg D\\ + \pn A\neg B\neg C\neg D\\ + \neg A\neg B\neg C\pn D\\ + \pn A\pn B\neg C\pn ...
2
votes
3answers
155 views

Difference between completeness and categoricity

I have problems understanding the difference between a categorical theory and a complete theory. My intuition says that every valid complete theory must be categorical. Is it true? Clarification: by ...
1
vote
1answer
27 views

Weakening and Contraction

I saw this site saying weakening is a structural rule where the hypotheses or conclusion of a sequent may be extended with additional members and that contraction is a rule where two equal (or ...
1
vote
1answer
30 views

Trying to wrap my head around the idea of Proving Rule of Cases is a valid arument

I had a question on my assignment today that asked to "Prove that the Rule of Proof by Cases is a valid argument." Based of what I've read, Proof by Cases is valid when all cases produce the same ...
2
votes
0answers
26 views

Need some help with this Cardinality/sets question.

I've got this problem about sets, and cardinality. I don't really understand it other than cardinality is the number of elements within each set, I don't understand a lot of the signs used within the ...
0
votes
1answer
15 views

Logic - Proof with Quantifiers

The question reads: (∀x)(∃y)(x + y ≥ 3) x is an integer and y is a natural number. Let x be an arbitrary integer. Now I'll need to find a y such that x + y ≥ 3. I'll take y = 3 - x. Now, this is ...
1
vote
1answer
38 views

Finding which base number given operations

$$ (35_a + 24_a) * 21_a = 1081_a $$ Which base is the above number? Any advice on how to solve questions like these? I tried making it in to a polynomial: $(3a+5 + 2a+4) * (2a+1) = 108a + 1$ ...
0
votes
3answers
42 views

Having problem with prediate logic

Suppose that the UoD (Universe of Discourse) is {A, B, C, D, E, F, G} which are softwares and I want to make the statement that "At least four softwares have a bug". Let P(x) be the predicate that " ...
0
votes
2answers
30 views

Logic when using two (if/then) statements

Let p , q , and r be the propositions: p: You have the flu. q: You miss the final exam.. r: You pass the course I'm trying to figure out how I would express this proposition in english: (p ---> ...
1
vote
1answer
13 views

An $n+1$-c.e. set which is not $n$-c.e.

A set $X\subseteq \mathbb{N}$ is $n$-c.e. if there is a total recursive guessing procedure $g(x,s)$ so that $$ g(x,0) = 0,\ \lim_s g(x,s) = X(x) $$ and the number of times $g$ changes its mind on a ...
0
votes
3answers
36 views

Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ (in a Boolean algebra)

Suppose X is a Boolean algebra. Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ I suspect this one is not that difficult, but for some reason I can't find the answer. This homework ...
2
votes
1answer
34 views

$\perp \Rightarrow p$ Syntactic Proof

Given the following axioms $$\begin{aligned}&1. p\Rightarrow (q\Rightarrow p)\\&2. [p\Rightarrow (q\Rightarrow r )] \Rightarrow [(p\Rightarrow q)\Rightarrow (p\Rightarrow r)]\\&3. \neg\neg ...
3
votes
3answers
96 views

Syntactically deduce $p\vdash \neg\neg p$

Given the following axioms $$\begin{aligned}&1. p\Rightarrow (q\Rightarrow p)\\&2. [p\Rightarrow (q\Rightarrow r )] \Rightarrow [(p\Rightarrow q)\Rightarrow (p\Rightarrow r)]\\&3. \neg\neg ...
0
votes
1answer
46 views

the set of well formed formulas

Want to prove that W_p is countably infinite where W_p = { Well formed formulas } Additional: Well-formed formulas are expressions in predicate logic that capture the idea of making good grammatical ...
2
votes
1answer
24 views

Adding unary relation symbol within complete theory

I try to prove following problem: Let $T$ be a complete theory over countable language, then $T$ has a model $\mathfrak{A}$ with cardinality $\le 2^{\aleph_0}$ such that for each $\mathfrak{B}\models ...
1
vote
2answers
39 views

prove that a wff is not satisfiable.

for any pair of formulae p1 and p2, if both p1 -> p2 and p1 -> (not p2) are valid then p1 is not satisfiable. Prove by way of contradiction that this is true. My approach was assuming that p1 is ...
1
vote
1answer
34 views

How to prove math theorems in formal logic or at least in the style of natural deduction?

I have become rather interested lately in proofs in mathematics, and I discovered at first to my surprise that they are written in paragraph form using natural language. Although this seemed out of ...
2
votes
2answers
80 views

Are addition and multiplication on naturals algebraically distinguishable?

Suppose (N, +) and (N, *) are the structures of addition and multiplication on N, the natural numbers with 0. Let S be the set of equational identities that hold in (N, +), and let T be the set of ...
0
votes
0answers
22 views

If an open sentence is always true for all values of the variable(s) in it, is it still an open sentence or is it considered a statement?

for example, x + y = y + x and 2(x + 7) = 2x + 14. Could they be considered as statements? also, is it possible a sentence considered as both an open sentence and statement?
-3
votes
1answer
29 views

Is an equation always open sentence? [closed]

I'd like also want to ask are (i) "I am handsome" and (ii) 2(x + 2) = 2x + 4 an open question?
0
votes
3answers
28 views

How would I go about turning english sentences into predicate logic?

I am taking a Discrete Mathematics for Computer Science course and was having some issues figuring this out. I would rather not be given a specific answer, but the steps on how I could solve this. If ...
2
votes
4answers
91 views

Is proof by contradiction “same thing” as $A \rightarrow B$ is true when $A$ is false?

I encountered earlier today a question "Is the proof by contradiction same as that $A \rightarrow B$ is true when $A$ is false?" continued by "Are they related, then? How?" I think the answer is "no, ...
1
vote
4answers
30 views

Predicate and Statement

I was confused on some problems involving predicate. First, there are many different definitions of predicate, the one I learned is "a predicate in one variable is a mathematical sentence involving ...
1
vote
5answers
60 views

Can the logic associative law be applied here?

$\big(p \rightarrow (q \rightarrow r)\big)$ is logically equivalent to $\big(q \rightarrow (p \rightarrow r)\big)$ I am a little confused when dealing with the 'implies' operator $\rightarrow$ and ...
0
votes
1answer
28 views

What is the truth table for the logical expression NOT(NOT(A) OR NOT(B)).

What is the truth table for the logical expression NOT(NOT(A) OR NOT(B)). A B NOT(NOT(A) OR NOT(B)) 0 0 0 1 1 0 1 1 And also what logic ...
2
votes
1answer
38 views

Sets and Logic .. Disproving with counter example

Can anyone please give me an idea to disprove the following with a counterexample: $A , B , C$ are sets. If $A \times C = B \times C$ , then $A = B$. (Here $\times$ is a Cartesian product.) I tried ...
3
votes
2answers
58 views

Is $Th(\mathbb{Z}[x])$ uncountably categorical?

Consider $T=Th(\mathbb{Z}[x])$ in the language $L = \{0,1,+,\times,deg(), \circ\}$ where $0,1,+$ and $\times$ have their usual interpretations, $deg()$ is a unary function symbol which gives the ...
0
votes
1answer
91 views

Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
1
vote
0answers
27 views

Definition of decidable sentence

Let $P(n)$ is a sentence which mentions natural number $n \in \mathbb{n}$ For example, "$n > 5$" or "There is no $n$ such that $3^n+4^n=5^n$ " can be $P(n)$. I want to define a set A as a set ...
4
votes
1answer
78 views

Equivalence between Peirce's law and Excluded Middle in Intuitionistic logic

I'm searching for a intuitionistically valid proof of the formula : $[((P→Q)→P)→P] ↔ (P \lor \lnot P)$ using the "standard" Hilbert-style axiom system from Kleene [1952], for ...
0
votes
1answer
49 views

Why is this relation recursive?

A relation $R \subset \mathbb{N}^d$ is called recursive if there exists a primitive recursive function f with $$ (x_1 ,\dots,x_d) \in R \Leftrightarrow f(x_1,\dots,x_d)=0.$$ In Kurt Gödel's article ...
0
votes
1answer
49 views

What is really a “complete” deductive system for first-order theories.

Given some first-order language and a set of axioms therefrom one still needs to specify a deductive system to turn it into a full-fledged first-order theory. Currently I'm under the following ...
1
vote
0answers
53 views

Is a sentence in $\Pi_1$ true given $Q \vdash \lnot\varphi$?

If $Q \vdash \lnot\varphi$ (Q is the Robinson arithmetic), and if I assume that $\varphi \in \Pi_1$; Can I say that $\varphi$ is a true sentence? My thoughts are that, given that Q is $\Sigma_1$- ...
2
votes
2answers
71 views

Are ideals necessarily definable?

Consider the first-order language of rings. Let $R$ be a ring and $I \subseteq R$ be an ideal. Is $I$ necessarily $\emptyset$-definable? If not, what if we allow parameters from $R$?
1
vote
2answers
38 views

Need help with $(¬p \vee ¬(p\wedge¬q)) \wedge ¬(p \wedge q) ≡¬p$

Hey guys I just need help solving this solution here. Sorry if I didn't type the symbols correctly. My solution so far: $$ (¬p \vee ¬(p\wedge¬q)) \wedge (¬p \vee ¬q)≡ (¬p \vee (¬p \vee q)) \wedge (¬p ...
0
votes
2answers
49 views

Prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ using natural deduction

I want to prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ where $x \notin FV(\psi)$ using natural deduction method. I was able to prove implication from left to ...
0
votes
1answer
19 views

Logical Equivalences Question

This is for a homework problem, so I would prefer bumps or tips in the right direction rather than full answers. I am supposed to show the logical equivalence of $p \leftrightarrow q$ and $(p \land ...