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)

4
votes
4answers
316 views

The set of all things. A thing itself?

If the universe is the set of all things. Does it contain itself? In other words is it a thing itself? I know its a stupid question, but it really grinds my gears. Thanks! Edit 8.12 Okey, someone ...
5
votes
2answers
189 views

First-order Euclidean Geometry

I gather that the axiomatisation of Euclidean Geometry, e.g., by Hilbert, can be used with First-order Logic and has good properties. Is it fairly complete in the sense, say, that it proves ...
0
votes
2answers
108 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
110 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
182 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
36 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
102 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
206 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' + ...
14
votes
5answers
793 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
49 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)]$?
1
vote
2answers
452 views

Proofs by contradiction and set theory

I'm having trouble understanding proofs by contradiction. I'm running things by memory and not by understanding what a contradiction is. I'd like to know what we're assuming and how to start. My ...
6
votes
2answers
183 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
429 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
214 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
93 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
76 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
507 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
73 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
109 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
199 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
177 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
163 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
266 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
175 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
50 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
162 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
95 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
97 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
197 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
143 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
109 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
167 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
133 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
101 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
146 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
140 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
226 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
156 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 ...