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)

7
votes
3answers
81 views

mathematical proof vs. first-order logic deductions

For a long time I thought that the standard mathematical proofs, only were an informal or imperfect way of writing the proof in the language of first-order logic. When I say standard mathematical ...
5
votes
4answers
199 views

Is there a possibility that ZFC is inconsistent and, if it is, do we have to throw out our old proofs? [duplicate]

I have learned that ZFC has not been proven consistent, and that further more if one were to start from ZFC and prove ZFC consistent, this would imply that ZFC is not consistent, due to Gödel. A few ...
0
votes
0answers
10 views

Cyclical counting quantifiers

In counting logic, how does one assign a meaning to statements such as "There exists $x$ $y$'s such that there exist $y$ $x$'s such that $x>y$. My mind hurts as I try to imagine how to evaluate ...
-3
votes
0answers
26 views

What are the truth tables for the following logical statements? [on hold]

NOT ($P$ and $Q$) (NOT $P$) or (NOT $Q$) $P$ and (NOT $Q$) (NOT $P$) or $Q$ Also: Is the statement "Some girl is not good at math" the negation of the statement "All girls are good at math?"
2
votes
0answers
17 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
0
votes
1answer
26 views

N-bit-String contains of zeros and one “1” bit [on hold]

Design a circuit contains of only basic logical gates (2 bit gates such as AND, OR, XOR, NAND and NOT gate) and constants: Input: n bit string A[0:n-1] Output: two bits: Y=1 only if all bits are 0 ...
1
vote
1answer
55 views

How to negate: not a limit point (symbolic logic)

1.There are few I have seen here. $\forall N(x), \exists x'\in B, (x'\neq x\wedge x'\in E)$. $\forall N(x), \exists x'\in B, (x'\neq x\to x\not\in E)$. $\forall r>0, \exists x'\in N_r(x)\cap E, ...
0
votes
1answer
27 views

most natural formulation of the $\vee$-eliminating rule

There are several (equivalent) ways to formulate the eliminating rule of $\vee$ ("or") Here are two of them: $\begin{array}{c} A\vee B \quad A\vdash C \quad B\vdash C\\ \hline C \end{array}$ ...
1
vote
1answer
32 views

$\kappa$-categoricity in the language of identity

I have the following exercise from Dirk Van Dalen's Logic and Structure: Here with language of identity we mean the language with no extralogical symbols (i.e. no symbols of predicates, functions ...
2
votes
1answer
45 views

Number of non-isomorphic models

Let $C$ be the class of cardinals. Define by recursion $C_0 = C$, $C_\alpha = C_\beta\cup P(C_\beta)$ if $\alpha=\beta+1$ and $C_\alpha = \bigcup_{\beta<\alpha}{C_\beta}$ for limit $\alpha$ (Here ...
1
vote
2answers
19 views

Is there a difference between these statements about natural numbers?

Can i say that $(\forall x \in \mathbb{N}:x^2=x) \vee(\forall x \in \mathbb{N}:x>1)$ is the same statement as:$\forall x \in \mathbb{N}:(x^2=x)\vee(x>1)$ ? If not, why? Thanks.
0
votes
0answers
51 views

proof with 3 quantifiers? [on hold]

Problems: $$∃x ∈ S \text{ s.t. } ∀y ∈ S, ∀z ∈ S, \text{ if } z > y, \text{ then } z ≥ x + y.$$ $$∀x ∈ S, ∃y ∈ S \text{ s.t. } ∀z ∈ S, \text{ if } z > y, \text{ then } z ≥ x + y.$$ What I have ...
4
votes
1answer
96 views

Is Alfred Tarski's Introduction to Logic still helpful for self study?

I am trying to setup a self study path to enhance my knowledge of mathematical logic. I haven't taken a logic course for a few years and my confidence on mathematical proofs is unnerving. I am ...
1
vote
2answers
36 views

Logically Equivalance - Proofs

In terms of logical statements, is ($\exists$n $\in$ N)($\forall$ x $\in$ A)(nx >= 1) equal to ($\forall$x $\in$ A)($\exists$ n $\in$ N)(nx >= 1)? Also consider the following statements $\forall x ...
2
votes
2answers
43 views

Logical Statements - Proofs

Let $f$ be a real-valued function (a function with target space the set of reals). Let $P(x, M)$ stand for $|f(x)| \leq M $, let $N$ be the set of positive real numbers, and let $\mathbb{R}$ be the ...
0
votes
1answer
23 views

Eliminating rule of existential quantifier

Why is the rule $\begin{array}{c} \exists x(\varphi(x))\quad \forall x (\varphi(x)\rightarrow A)\\ \hline A \end{array}$ valid? Why does this rule hold? How can one verify this rule intuitively?
3
votes
2answers
51 views

Intuitionistic Proof of $(a \Rightarrow b) \Rightarrow (\lnot b \Rightarrow \lnot a)$

I'm trying to prove $$(a \Rightarrow b) \Rightarrow (\lnot b \Rightarrow \lnot a)$$ A seemingly natural way to start is by assuming the left side, as well as assuming a. This ends up proving what I ...
2
votes
1answer
27 views

Axiomatizability of the algebra of (a fragment of) calculus

Consider the set $S$ of all infinitely-differentiable functions on the reals. Consider the structure $(S,+,-,*,0,1,Id,D)$, where $+$,$-$, and $*$ are function addition, subtraction and multiplication ...
3
votes
3answers
87 views

Explaining the meaning of equality

I've been tasked with explaining to a group of people what the notion of equality means in mathematics, I've come up with a working explanation, but would appreciate some input, suggestions etc. ...
0
votes
1answer
61 views

Can the solvability of a single Diophantine equation be undecidable (in any sense of the word)?

Apologies in advance for asking the following "philosophical" question, which falls dramatically short of any reasonable standards of mathematical rigour: Is it possible that there should exist a ...
6
votes
1answer
130 views

What proof uses both the Riemann Hypothesis and its negation?

Some time ago I happened to see a proof that was remarkable in that it used both the Riemann Hypothesis and its negation. That is, it considered the two cases: RH is true, and RH is false, obtaining, ...
4
votes
4answers
85 views

Is it possible to assign probability to a set $X$ with $|X|>2^{\aleph_0}$?

Is it possible to assign probability to a set $X$ with cardinality $|X| > 2^{\aleph_0}$? Example would be a set $|X| = 2^{2^{\aleph_0}}$.
1
vote
1answer
55 views

What are the meanings of the various turnstiles

It is easy to find the meanings of $\vdash$ and $\models$ (see this question and Wikipedia) but what of the (triple?) turnstile $\Vvdash$ and the (vertical double?) turnstile $\Vdash$? Do they have a ...
2
votes
4answers
79 views

Non-standard model of $Th(\mathbb{R})$ with the same cardinality of $\mathbb{R}$

Let $\mathfrak{R}= ⟨\mathbb{R},<,+,-,\cdot,0,1⟩$ be the standard model of $Th(\mathbb{R})$ in the language of ordered fields. I need to show that there exists a (non standard) model of ...
-1
votes
0answers
20 views

Logical consequence and resolution rule

Which of this are false? a) If some formula H results from premises D, then H could be derived from D with using (reapetedly) resolution rule. b) If some formula H results from premises D, then we ...
0
votes
1answer
16 views

Replacing a fractional quantity by one in inequalities

I was looking through proofs for the product law for limits and I stumbled upon a very clear one and managed to follow all the steps involving algebra and limits, but, near the end, in the proof, a ...
0
votes
1answer
39 views

Can you write down a chain of derivabilities?

Suppose you have a sentence $A$, from which you can derive $B$, from which you can derive $C$. What is the best way to write this down? I would like to write $$ A \vdash B \vdash C, $$ but I'm not ...
1
vote
2answers
20 views

Convert form form CNF to DNF

i have few question about converting forms to DNF, CNF and from CNF to DNF. 1) How can i convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $ 2) How can i convert this to CNF $(p \wedge q) \vee ...
-1
votes
1answer
51 views

Does $\mathcal{P}(\mathbb{N})$ contain infinite sets?

I know that $\mathcal{P}(\mathbb{N})$ is infinite and uncountable. However, is the power set of the natural numbers considered to contain only finite sets of natural numbers, or infinite ones as well? ...
0
votes
2answers
48 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
8
votes
2answers
144 views

Why do we know that Gödel sentences are true in the standard model of set theory, but do not know if the continuum hypothesis is?

By what methods can we identify sentences that are true in the standard model of set theory, but not in other models? In particular, how do we prove that Gödel sentences are true in the standard ...
2
votes
1answer
69 views

A math puzzle about slow clock

You have the misfortune to own an unreliable clock. This one loses exactly 20 minutes every hour. It is now showing 4:00am and you know that is was correct at midnight, when you set it. The clock ...
0
votes
2answers
46 views

If $P$ is true then not $Q$

I'm trying to solve the following problem: "If this sentence is true then tomorrow will not rain". tomorrow will rain tomorrow will not rain the sentence is a paradox What I thought is: $P ...
-2
votes
2answers
42 views

Problem on elementary logic and set theory

Let A and B be sets with B is a subset of A. Prove that A \ (A\B)=B. I start by saying that suppose x is in A \ (A\B). By definition, x is in A and X is not in (A\B) . However, x is not in A\B ...
-5
votes
0answers
21 views

how can we make 20 using onlynand only two 3s and we can use any mathematical function as and when required [closed]

how can we make 20 using onlynand only two 3s and we can use any mathematical function as and when required
0
votes
3answers
38 views

complete the proof for this statement

$$\forall x \in \mathbb{R}, x \neq 0 \implies \frac{1}{x^2\:+3}\:<\:\frac{4}{5}\: $$ I thought of doing the contrapositive but not sure what to do next. $$ \frac{1}{x^{2\:}+3}\:\ge ...
-1
votes
0answers
33 views

Universum, interpretation few question.

i have few questin about predicate logic and interpretation : I have formula like this: 1) $(\forall x: \neg p(x) \vee q(x)) \Leftrightarrow \neg (p(x) \wedge q(x))$ No i must choose is either of ...
1
vote
3answers
65 views

Implies in a truth table, unclear. [duplicate]

In my textbook, we have the following truth table: $P$ true and $Q$ true means that "$P \implies Q$" is true. $P$ true and $Q$ false means that "$P \implies Q$" is false. $P$ false and $Q$ true ...
2
votes
1answer
45 views

define the “optimal” automatic theorem prover

my question is : is it possible to define in some way what should do an "optimal automatic mathematician" ? There are two points of view of an automatic theorem prover / automatic mathematician : ...
0
votes
1answer
27 views

Satisfiable formula only over even structares

In First order Logics, what formula can I cook up, that's satisfiable over all even structures, and only even structures. (even structure means it has an even number of elements in its domain).
0
votes
2answers
35 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
0
votes
0answers
29 views

Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem ...
1
vote
1answer
33 views

Setting Unknowns to 1

Suppose a square formation of troops 50 meters deep is marching with a dog in the middle of its back rank. The dog runs to the front of the formation, turns around instantaneously and runs back to ...
1
vote
2answers
70 views

How to prove that a statement is a theorem using Hilbert's system?

I'm looking for an actual step-by-step way of proving that a statement is a theorem using Hilbert's system. For instance: As can be seen from the above picture, the solution consists in a series of ...
2
votes
1answer
28 views

Derive a formula for the number of small square base pyramids required to create a bigger pyramid?

To quote from the problem statement: "Pyramids are built using smallest pyramids of "level 1", that are used as building blocks for higher levels. Stacking pyramids of "level 1" to create ...
0
votes
0answers
21 views

Formally define replacement operation for rules of replacement

I'm having some trouble formally defining non-uniform substitution the replacement operation for a rule of replacement in propositional logic. Based on the idea of "Non-Uniform Substitution" from here ...
0
votes
0answers
26 views

What is the relationship of the Liar Paradox and Gödel's sentence?

In both cases we get a negative result in a certain sense due to self-reference. Could Gödel's sentence be thought of as a representation of the Liar Paradox in the language of arithmetic? If that is ...
-2
votes
2answers
44 views

Universal instantiation another question why couldn't?

something like this: $ \exists x: p(x) \Rightarrow \forall x: p(x) $ $ \neg \exists x: p(x) \vee \forall x: p(x) $ $ \forall x: \neg p(x) \vee \forall x: p(x)$ So if i use here rule : universal ...
0
votes
0answers
32 views

Skolem normal form - difference form different thinking?

i found two tutorials which transfer this formula to Skolem form: $\forall x \exists y: \neg p(x,y) \vee \forall w \exists z: p(w,z)$ First case 1: $\forall x \exists y: \neg p(x,y) \vee \forall w ...
3
votes
1answer
241 views

Why does the Deduction Theorem use Union?

We have an initial set of premises $S$. We are given or observe or assume sentence(s) $A$ is/are true. We can then prove $B$. Formally, $S \cup \left\{A\right\} \vdash B$. Shouldn't it be an ...