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)

0
votes
2answers
107 views

The Adjunction $\_\times A\dashv (\_ )^A$ for Preorders: The Deduction Theorem.

The following is from Turi's Category Theory Lecture Notes. Definition 11.11 Let $A$ be an object of a category $\mathbb{C}$ with binary products. The right adjoint of $\_\times ...
2
votes
1answer
109 views

Showing a Theory $T$ is Substructure Complete

Let $T$ be a (complete and consistent) theory. Suppose $T$ exhibits the following two properties: (1) model-completeness: if $\mathcal{M} \models T$ and $\mathcal{A} \subseteq \mathcal{M}$ s.t. ...
3
votes
0answers
178 views

Relationship between paradoxes in logic and geometry/topology

Though I've been reading for years, this is my first question here. Believe it or not, I've tried the search feature- apologies if this is a duplicate. The main point of this post can be summarized ...
0
votes
1answer
35 views

Question about intransitivity

A relation $\mathrel R$ is intransitivity only if $\mathrel R$ is irreflexive. True or False I think is yes. $\forall x(x\mathrel Rx \wedge x\mathrel Rx) \implies \neg x\mathrel Rx$ Am I ...
2
votes
0answers
96 views

An example of a proof in sequent calculus

I'm reading Gaisi Takeuti, Proof Theory (2nd ed - 1987), and I'm trying with some exercises. See pag.13 : Ex.2.5.2) Prove the following in LK : $(A \supset B) \supset \lnot A \lor B$. In order to ...
1
vote
3answers
183 views

Is it possible to express an if statement in algebra?

In programming languages it is possible to write functions that use if statements that can be plotted on Cartesian coordinates. For example: ...
1
vote
2answers
63 views

How to simplify this using boolean algebra?

My paper is due tomorrow and there is only the last exercise left for me to do. However, I don't have any sufficient notes or examples on how to simplify it. Any help would be appreciated! A'B'C' + ...
13
votes
5answers
760 views

Purpose of the Peano Axioms

Wikipedia says the Peano Axioms are a set of axioms for the natural numbers. Is the purpose of the axioms to create a base on which we can build the rest of mathematicas formally? If this is true ...
1
vote
1answer
48 views

Question about universal quantifier and logic formula

If I have $(\forall u: F(u,v))\implies G(v)$ I can say $(\forall u)[F(u,v)\implies G(v)]$?
6
votes
2answers
179 views

Formalizing proof of Godel sentence's non-provability?

In the question What does it mean for something to be true but not provable in peano arithmetic? Henning Makholm states, "...he [Godel] gave a (formalizable, with a few additional technical ...
6
votes
1answer
108 views

$\forall x\forall y(\dots )$ or $\forall x(\forall y\dots )$.

The sentence that needs translation is this: Everything hates something, but only scientists hates everything. With respect to the first part of the sentence I am fairly certain the correct ...
1
vote
2answers
101 views

How can you really be sure the contradiction didn't spring from the hypothesis?

This question may have a duplicate but I didn't find one. Given a proof by contradiction of a statement like $p \land q \implies r$. Which means (as i understand it): $p \land q \land \lnot r$ is ...
3
votes
1answer
391 views

lambda calculus and category theory

I am not particularly knowledgeable in either lambda calculus or category theory, but I am starting to learn Haskell so I would like to ask: are there connections between category theory and lambda ...
5
votes
1answer
213 views

Foundational theories, their uses, interactions and comparisons?

Until now, I heard that there are some theories for building mathematical objects (or at least it is what it seems to my poor knowledge). Some of these are: Set theory; Logic; Category theory; Type ...
0
votes
1answer
87 views

Propositional logic derivation

Data given : Y value is either 0 or 1 Premises : 1) $(X=Y)$$\iff$ (R $\lor$ S) 2) S $\iff$ $(X=0)$ 2) R $\implies$ $(X=1)$ Result : $(X=1)$ $\implies$ R Can i infer result from premises and ...
2
votes
0answers
74 views

How much arithmetic can Predicative Second-Order EFA do?

As discussed in this MathOverflow question, I'm trying to find what the result would be of applying a Feferman-Scutte-like analysis to the predicativism of Edward Nelson and Charles Parsons, who ...
3
votes
2answers
64 views

show that $\Gamma = Th(A) \cup \{\varphi_n : n \in \omega\}$ is satisfiable

I am trying to solve this problem from Enderton's book: What i've tried: I see that this problem reduces to show that a set of formulas, say $\Gamma$ is satisfiable using the compactness theorem: ...
2
votes
1answer
456 views

How to prove $2+2=4$ using axioms of real number system?

How to prove $2+2=4$ using axioms of real number system? How do you make sense of the axioms for real number system when you cannot define the operations. You don't give an algorithm to calculate the ...
0
votes
1answer
86 views

Definition of divergence (negation rules)

Some background before my question. A question in my homework is as follows: Using no negative words, say what it would mean for a sequence $\langle a_n \rangle$ to diverge. Our definition of ...
1
vote
2answers
72 views

Rules of Inference

Have a couple of questions... How do I show invalid arguments? If $x$ is a real number such that $x > 1$, then $x^2 > 1$. Suppose that $x^2$ is $> 1$, then $x > 1$. Okay, I know ...
2
votes
1answer
69 views

Relations and equivalence relation

Let $R=\{ (x,y) \vert x=1 \,\, or\,\, y=1 \}$ When I see something written like this to represent "or", I immediately think XOR. But is that necessarily true? This would greatly change the ...
3
votes
1answer
33 views

theory and a logic

The book I am reading (The first course in logic) discusses the difference between a logic and logic. This distinction is quite clear to me. I wonder what is the difference between a theory and a ...
0
votes
3answers
106 views

Converting to NAND only

I've been trying to work this out for days and still can't do it. I have to convert the top equation to NAND only. I've worked out the second line by using Demorgans theorem however doing this would ...
5
votes
1answer
194 views

Explain/illustrate Goedel's theorems and possible implications to non-mathematicians

I am asked to give a talk about (a) mathematical practice, (b) axiomatization, (c) Gödel's theorems and (d) possible antimechanist arguments based on the incompleteness theorems (as mentioned in P ...
0
votes
0answers
29 views

MIU system and Euclidean geometry [duplicate]

I read on Wikipidea that we can view the MIU system (it is a post canonical system) as a formal logic. I noticed that Eucliedean geometry is similar to MIU system in many regards: we also have axioms, ...
0
votes
2answers
58 views

proofs of independence

If we have a first-order theory, do all independence proofs of a certain result in that theory need to use "outside" assumptions? Cant we just enumerate all proofs in that theory and conclude that ...
1
vote
1answer
175 views

Explain mathematical practice and axiomatization to non-mathematicians

I am asked to give a talk about (a) mathematical practice, (b) axiomatization, (c) Gödel's theorems and (d) possible antimechanist arguments based on the incompleteness theorems (as mentioned in P ...
3
votes
1answer
160 views

Problem understanding multiple quantifiers in Predicate Logic

So, my problem is that I have trouble knowing when and why I should write two quantifiers in the front of the whole proposition, rather than one in the front and one within ... If I have "Everyone ...
4
votes
1answer
256 views

Conditional Probability/ Bayes' Theorem puzzle

I always believed that problems on conditional probability could be solved with common logic without using Bayes' theorem (because I cannot understand Bayes' theorem intuitively and I didn't bother ...
0
votes
2answers
173 views

Unable to understand combination of quantifiers and set notation

I know what universal and existential quantifiers are but following is confusing,may be its comibination of set notation and quantifers. What does the following statement means? ...
1
vote
1answer
49 views

A question about infinitary proofs and First Order Peano Arithmetic

In certain proof systems, infinite proofs are allowed; a common example is a version of Induction: Given $\Sigma \vdash \phi(S^n 0)$ for all $n \in \Bbb N$, infer $\Sigma \vdash \forall x ...
2
votes
2answers
160 views

How can we define infinitary proofs?

In the first order logic the usual notion of a formal proof for a sentence $\sigma$ from a theory $T$ is a "finite" sequence ($<\omega$ - sequeance) of sentences which each one of them is a valid ...
7
votes
1answer
113 views

Have mathematical structures equipped with “generalized relations” been considered in a systematic way?

A binary relation on $X$ is basically just a function $X^2 \rightarrow \mathbb{B}$, where $\mathbb{B}$ is the prototypical Boolean algebra $\{0,1\}.$ We can generalize by replacing $\mathbb{B}$ with a ...
5
votes
1answer
94 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
2
votes
3answers
95 views

Element contained within a predicate?? Tattoo error…

Hey so my friend got a tattoo of logical symbols to translate some quotation, and this friend ended up having a statement of this form contained in the proposition: $\forall y[P(y) \rightarrow (y ...
4
votes
0answers
191 views

Puzzle - zero knowledge proof

I am solving the following problem : I have edge-matching puzzles, where all pieces are squares and the grid has $n$*$n$ format. There is no global image to guide a puzzle solver. Despite the puzzles ...
1
vote
1answer
141 views

A relation, R, is euclidean iff ∀x∀y∀z((Rxy ∧ Rxz) → Ryz). Prove that identity is euclidean.

A relation, R, is euclidean iff ∀x∀y∀z((Rxy ∧ Rxz) → Ryz). Prove that identity is euclidean. I know the euclidean identity is ∀x∀y∀z((x=y ∧ x=z) → y=z). How can I prove this?
2
votes
1answer
83 views

Primitive Recursion Functions (Programs)

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
1
vote
1answer
103 views

How would one prove transitivity in first-order logic?

Here is a problem from Enderton's Mathematical Introduction to Logic: Show that $$\vdash \forall \,x\,\forall\,y\,\forall\,z\,(x = y \rightarrow y = z \rightarrow x = z)$$ One thought I have ...
0
votes
2answers
166 views

Is there a useful application of Peano arithmetic?

If there is, can someone provide an example of how Peano arithmetic can be used to solve a real-world problem? If not, can someone provide an example of any axiomatic system other than ZFC that can ...
4
votes
3answers
119 views

Predicate Logic: Difference between 'who' and 'if' in symbolization

Consider the two sentences: (1) "chessplayers are rich if they are professional" (2) "chessplayers who are professional are rich" and the key: UD: Living things Cx: x is a ...
2
votes
1answer
100 views

Show formulas which are valid according to Brouwer-Heyting-Kolmogorov interpretation [closed]

How can I show, that the following formulae are valid according to Brouwer-Heyting-Kolmogorov interpretation? $(A \land B) \to (B \land A)$ $\neg (A \lor B) \to (\neg A \land \neg B)$ $A \land (B ...
0
votes
1answer
50 views

General Proof/Logic Question About a Limit

Consider some sequence of real numbers $\{a_n\}$. Assume we want to show that it does not have a finite limit. Is this a valid proof technique: Let L be any finite real number. Then proceed to show ...
5
votes
4answers
145 views

Why use the biconditional in the Axiom of Extensionality

I'm studying the Axiom of Extensionality in the following form: $$ \forall a \forall b[\forall x(x\in a\leftrightarrow x\in b)\rightarrow a=b] $$ (where quantification of a,b is restricted to sets ...
3
votes
1answer
137 views

Type Theory (Proof tree)

Suppose $B(x)$ set $(x:A)$ is a family of sets and $D$ is a set. Prove $(\Sigma x:A)B(x) \times D \to (\Sigma x:A)(B(x) \times D)$. Using the so called Curry-Howard correspondence one may ...
5
votes
2answers
214 views

Any inconsistent theory must be complete?

Assume the following definitions: $U$ is the set of all sentences in a language A theory $T$ is complete if $\forall A \in U$, $A \in T$ or ${\sim} A \in T$ or both. A theory is consistent if at ...
2
votes
1answer
146 views

Help with 'If, then'- and 'Only if'-sentences in Predicate Logic

So, I have to ask now, because I've spent so much time on these two translations. My key is Domain: living things Px: x is a pokerplayer Cx: x is a chessplayer Yx: x is ...
1
vote
1answer
76 views

Proof that a statement involving quantifiers is false

I believe that the sentence $\forall x (P(x)\rightarrow \exists y Q(x,y))$ false? Is it sufficient to define: 1) The Domain of $x, y $ 2) The predicates $P(x)$ and $Q(x,y)$ so that for some $x$ ...
3
votes
1answer
72 views

Are these equivalent?

$\forall x \in D, (P(x) \Rightarrow Q(x))$ is equivalent to $(\forall x \in D \cap P,Q(x))$. However, is this also equivalent to $(\forall x\in D)( P(x)\land Q(x))$? If not, what's the difference? ...
0
votes
1answer
162 views

Examples from Kleene's Introduction to Metamathematics [1952] : Intro- and Elimination-rules

Following Prof.Mummert suggestion about the correct application of Intro- and Elimination- rules for quantifiers [pag.98-99]: look at examples 5 and 6 on page 149 of Kleene 1952. Example 5. ...