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)

1
vote
3answers
114 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
0answers
29 views

Finding DNF for the given problem (Logic)

I'm struggling to find DNF for the given problem: Whats bugging me, is the last line - I'm seemingly unable to get rid of disjunctions in the first 2nd level parenthesis. Any ideas on what am i ...
1
vote
2answers
61 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' + ...
9
votes
5answers
375 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
44 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
143 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
103 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
95 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 ...
2
votes
1answer
180 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
202 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
66 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
55 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
60 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
281 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
54 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
60 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
63 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
32 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
84 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
171 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
28 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
52 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
158 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 ...
2
votes
1answer
92 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
130 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
99 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
41 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
125 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 ...
6
votes
1answer
101 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
68 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 ...
0
votes
0answers
51 views

The most general unifier (MGU) for a clause with 3 subclauses.

What is the most general unifier (MGU) for this clause $C$: $$C = \neg p(x,y)\vee \neg p(a, f(x))\vee \neg p(f(x),f(y))?$$ My problem is that I can only find an MGU for subclauses 1+2 and 1+3, but ...
2
votes
3answers
78 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
163 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
89 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?
0
votes
0answers
46 views

symbolize and prove.

symbolize and prove The rules used can be found in the following links: * Predicate logic rules * Chellas Rules 1)Dionysius and Pseudo-Dionysius cannot be identical. For Dionysius was a ...
2
votes
1answer
70 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} ...
0
votes
0answers
70 views

How to write Propositional logic equation

Given $n-1$ teams and $m-1$ days, provide a propositional logic equation to illustrate the following: each team can only play 1 home game per day. All possible permutations must be played. I'm not ...
1
vote
1answer
71 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
138 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
95 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
92 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
47 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
130 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 ...
0
votes
0answers
61 views

How to prove a statement that involves max and big theta?

If we have 4 functions. a,b,c,d Considering that a is in Θ(c) and b is in Θ(d) I need to prove that (a + b) is in Θ(max{c, d }). What approach do you recommend? Do I have to prove this ...
3
votes
1answer
112 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
118 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
77 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
67 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
68 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
93 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. ...