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)

1
vote
1answer
50 views

Consistency of theories

1) Can we express the consistency of a theory $T$ by the formula $\sim\exists x\ (\sim x=x)$? i.e, there is no $x$ such that $x$ does not equal $x$. 2) If so, can we that say that if $T$ is ...
4
votes
0answers
71 views

Can all axioms of mathematical theories be expressed with predicate logic?

The book Roads to Infinity: The Mathematics of Truth and Proof stated that, "All the standard mathematical theories have axioms that can be expressed in predicate logic." Predicate logic generally ...
0
votes
2answers
54 views

Falsehood in a calculus of natural deduction

How does the introduction rule and the elimination rule of falsehood ⊥ look like in a calculus of natural deduction?
1
vote
2answers
119 views

Which should I study first: Logic or set theory?

I'm an undergraduate student in a college of sciences and technics studying maths, physics, computing and some chimestry so we studied elementary materials in logic and set theory. As I am interested ...
1
vote
0answers
55 views

Recommendations for a thorough logic textbook

I'm looking for a (possibly introductory) textbook on logic that covers the motivation behind conventions in logic, like the definition of the implication. Prof. J. Lau has an excellent webpage, ...
4
votes
11answers
2k views

Why every definition is an “iff”-type statement? [duplicate]

Suppose that we are trying to define a mathematical object $M$. The statement of the definition generally takes the form (or some of its equivalent variant), A mathematical object is said to be ...
2
votes
3answers
106 views

Incompleteness in other areas of mathematics

I read in "Apostolos Doxiadis:Uncle Petros and Goldbach's conjecture" that SPOILER ALERT Uncle Petros practically stopped working on Goldbach's Conjecture when he learnt about the Incompleteness ...
0
votes
2answers
22 views

Max 2-sat and clause size

I've seen that Max 2-Sat is NP-complete, are there instances in which every clause has exactly $2$ variables which are $NP$-complete? Or do all such instance need to contain a clause of exactly 1 ...
0
votes
0answers
19 views

How to convert this paradoxical circuit into logical statement?

As you can see, one of inputs of a XOR gate is connected to the output of the same XOR gate. Each time when the output is "true" it influences its input and it makes the gate change output to ...
0
votes
1answer
66 views

Two statements R and S are logically equivalent iff R $\iff$ S is a tautology.

How do prove the following statement: "Two statements R and S are logically equivalent iff R↔S is a tautology. without using a true table.Would I have to use cases? So far I have done so far is that ...
7
votes
1answer
98 views

WLOG and “by symmetry” arguments and the foundations of mathematics

John Harrison's paper Without Loss of Generality raises the interesting point that although "without loss of generality"/"by symmetry" arguments are a common proof technique, there is no corresponding ...
125
votes
3answers
18k views

Why can a Venn diagram for 4+ sets not be constructed using circles?

This page gives a few examples of Venn diagrams for 4 sets. Some examples: Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete ...
0
votes
2answers
113 views

Can all theorems be deduced directly from the ZFC axioms?

I stumbled upon a website called metamath that claims to be able to do this : http://us.metamath.org/mpegif/mmset.html
0
votes
0answers
37 views

Proof of cut elimination

I am reading Proofs and types and am blocked at the proof of cut elimination in sequent calculus (chap 13). I don't see either how the cuts are being pushed up above the preceding steps to the top of ...
1
vote
0answers
27 views

trace calculation of an operator valued matrix

Heyho, i've got problems understanding a certain calculation of the trace of an operator valued matrix right now. We've got the Matrix $T(\lambda)= \begin{pmatrix} A(\lambda) && B(\lambda) ...
2
votes
0answers
20 views

Symbolically formulate the two guard problem so it can be solved by a computer

Take the classic two guard riddle (I don't know where the origin of this riddle is, so I'll take the version from http://www.calpoly.edu/~mcarlton/riddles.html): You stand at a fork in the road. ...
3
votes
2answers
85 views

Question about the solution to Unexpected hanging paradox

The following is the unexpected hanging paradox: A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to ...
-1
votes
0answers
20 views

Identity Substitution in Polyadic Singular Sentences

Let the sentence "Yash loves Priya" be symbolized as Lyp. Let the sentence "Priya is Dr.Lingnurkar" be symbolized as p=l. The identity substitution rule is a=b,ϕa,/∴ϕb. In my textbook, ...
5
votes
4answers
259 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 ...
7
votes
4answers
143 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 ...
2
votes
2answers
47 views

What's the meaning of an element that belongs to the same element?

In classical set theory, if I consider that $x$ is an element, which means it is not a set, can I write $x \in x$ ? If yes, what this would mean? Correct me if I am wrong, but I don't need to have ...
2
votes
0answers
26 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
1
vote
2answers
71 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, ...
1
vote
0answers
26 views

The pencils in a box of crayons always have the same color [duplicate]

I retrieved an old math book and I'm delighted to share following exercise. The pencils in a box of crayons always have the same color. Proof by induction on the number $n$ of pencils in the ...
0
votes
1answer
28 views

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

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

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
8
votes
2answers
58 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
0
votes
3answers
56 views

How to convert a truth table to boolean expression?

If I have a huge truth table, it's hard for me to construct an expression. I know a problematic method, the Disjunctive Normal Form. But I found that I cannot reduce the huge expression. ...
2
votes
3answers
119 views

Negation of a logical statement

My question is that when I negate the statement $$(\forall x\in \mathbb{R})( \exists n \in \mathbb{N})(x < 1/n),$$ do I negate all of the statement or just the first part $(\forall x \in ...
42
votes
13answers
14k views

Why is “the set of all sets” a paradox?

I've heard of some other paradoxes involving sets (ie, "the set of all sets that do not contain themselves") and I understand how paradoxes arise from them. But this one I do not understand. Why is ...
1
vote
3answers
74 views

How to prove a logical implication?

Question: Using the Laws of Logic and Rules of Inference, prove that $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$ I just don't know how to apply the Rules of ...
1
vote
5answers
190 views

$(A_1\rightarrow\wedge A_2)$ is not a well-formed formula

Let $A_1,A_2$ be sentence symbols. Could anyone advise me how to prove $(A_1\rightarrow\wedge A_2)$ is not a well-formed formula? Thank you.
2
votes
2answers
72 views

How to translate set propositions involving power sets and cartesian products, into first-order logic statements?

As seen from an earlier question of mine one can translate between set algebra and logic, as long as they speak about elements (a named set A is the same as {x ∣ x ∈ A}). However I've stumbled upon ...
1
vote
2answers
37 views

How to show that $[(p \rightarrow q) \rightarrow r] \Rightarrow [p \rightarrow (q \rightarrow r)]$

To show that $[(p \rightarrow q) \rightarrow r] \Rightarrow [p \rightarrow (q \rightarrow r)]$ without using a truth table. That is, using logical laws.
4
votes
1answer
85 views

Suppose some theory T has countably many axioms, how many models of $T$ are there of cardinality $\aleph_1$,$\aleph_2$,$\aleph_{\omega_1}$?

Setting Let $\mathcal{L} = \{E\}$ where $E$ is a binary relation symbol. Let $T$ be the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes. So we see $T$ has ...
2
votes
1answer
72 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 ...
4
votes
10answers
5k views

How do I prove this statement is tautology without using truth tables?

How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$ I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left ...
0
votes
0answers
15 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 ...
2
votes
0answers
22 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 ...
4
votes
1answer
112 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
1answer
36 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 ...
0
votes
1answer
44 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
2answers
21 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.
1
vote
2answers
39 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
52 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
31 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?
2
votes
4answers
85 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 ...
3
votes
2answers
61 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 ...
3
votes
3answers
90 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. ...
5
votes
1answer
140 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, ...