Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

3
votes
4answers
9k views

How to represent XOR of two decimal Numbers with Arithmetic Operators

Is there any way to represent XOR of two decimal Numbers using Arithmetic Operators (+,-,*,/,%).
-1
votes
1answer
22 views

What's the method of collation in the language of set theory?

I have read about the language of set theory and the thing I noticed is that although the alphabet and rules of formation are usually described, I have yet to see a description of the method of ...
2
votes
2answers
91 views

Weather forecast and probabilities

There are two weather stations, station A and station B which are independent of each other. On average, the weather forecast accuracy of station A is $80\%$ and that of station B is $90\%$. Station A ...
3
votes
2answers
50 views

Multiplicity of real numbers in a tuple with known cardinality decidable?

Given a tuple $(x_1, \ldots, x_n)$ of computable real numbers $x_1, \ldots ,x_n$ and its cardinality $|\{x_1, \ldots x_n\}|=d \leq n$, is it decidable which numbers have which multiplicity? In other ...
3
votes
2answers
562 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. Is it possible to give a formal proof for the above?
0
votes
1answer
31 views

Proof that standard translation of modal formula is equivalent to the FO formula

For example $\varphi:=\lozenge\lozenge p\rightarrow\lozenge p$ defines transitivity and it has a standard translation $St_{x}(\varphi):=\forall P\forall x(\exists y(R(x,y)\wedge \exists x(R(y,x)\wedge ...
0
votes
2answers
39 views

Do we have to write down definitional abbreviations when writing the alphabet for a formal language?

If we want to have new symbols in our language, which are definitional abbreviations for strings of symbols already in our language's alphabet, do we have to add them to that alphabet? For example, ...
0
votes
0answers
19 views

Prove by the definition of convergence that the sequence an converges to 1.

I know the definition of convergence as a sequence an approaches the limit if for every $\epsilon > 0$, there exists $N \in\mathbb N$ such that $|a_n - L| \lt \epsilon$. How do I prove with this ...
2
votes
1answer
199 views

Why does the existence of independent statements not prove consistency?

I've read before that, by the Principle of Explosion, if a theory is inconsistent, then absolutely any statement can be proven within it. Obviously, there are statements which are independent of ZFC ...
0
votes
1answer
37 views

If S = {1/n | n ∈ ℕ}, what is inf(S)? [duplicate]

I believe the answer is 0 but I'm not really sure how to prove it...does it involve using epsilon?
1
vote
0answers
27 views

Can we prove undefinability theorem first (using techniques that are different from Godel's) and then deduce Incompleteness from it?

I asked a related question about the matter here in philosophy platform where it was suggested to ask a modified version of the question on Math.se My question is, Is there any known way to prove ...
2
votes
1answer
70 views

How to formalize a variable-binding operator, such like $\frac{d}{dx}$?

How to formalize a variable-binding operator, such like $\frac{d}{dx}f(x)$? For instance, I think we should treat $\frac{d}{dx}$ as a higher-order function of $x$, returning a function that takes it ...
1
vote
2answers
21 views

Does the fact that a modal operator distributive over disjunction imply that a modal operator is distributive over conjunction?

If L is an arbitrary operator on two propositions p and q: Does L(p $\vee$ q) $\Rightarrow$ Lp $\vee$ Lq imply L(p $\land$ q) $\rightarrow$ Lp $\land$ Lq?
1
vote
2answers
40 views

Validity of $\exists x \forall y: x \le y$ in set of integers and set of natural numbers

If I say $\exists x\in \mathbb{N} $ such that $\forall y \in \mathbb{N},$ $x \leq y$, this is a true statement. I am assuming that the set of natural numbers is defined for $0\leq x < \infty $. ...
1
vote
0answers
75 views

Is this translation into symbols correct?

Me and my friend came up with a cool game - we take turns in taking some mathematical theorem stated in English and turn it into a symbolic statement. The rules are this: you are only allowed to use ...
0
votes
0answers
23 views

Simplest way to say “$\varphi$ is a wff of formal system $\mathbf{F}$”?

What is the simplest way to say "$\varphi$ is a well-formed formula of formal system $\mathbf{F}$" in symbols? The only thing that comes to mind is: $$\varphi \in \mathbf{F}$$ Am I right? I.e., ...
4
votes
1answer
82 views

Why isn't '&' used for logical conjunction?

There is a beautiful and well-established logogram for "and" that is known to virtually every more or less educated person in the world - it's the ampersand '&'. It's completely unambiguous, as ...
0
votes
1answer
40 views

Why include equality in FOL for ZFC?

What are the pros and cons of working with first-order logic with equality for constructing ZFC, when all you have to do is make '$x=y$' a shorthand for: $$'\forall z [z \in x \Leftrightarrow z \in y] ...
0
votes
1answer
25 views

Why to define formulas defined using WFFs as WFFs?

The rules of formation for the language of set theory are the following: If $a$ is a variable and $b$ is a variabe, then $a\,{\in}\,b$ is a WFF. If $P$ is a WFF and $Q$ is a WFF, then ...
1
vote
0answers
36 views

How to denote a variable is an argument to a function.

How would one write "x is an argument to the function f" in set notation. For instance here is a piece of logic I'm trying to write as set notation: For all x where x is an argument to the function ...
0
votes
1answer
28 views

Quantifier in Integer Programming/Logic

It is common to write constraints with something like $x_s \leq y \quad \forall s \in X$ In Integer Programming, where x_s and y is a variable. However my tutor said that this not so absolutly ...
14
votes
4answers
3k views

Proof by Contradiction, Circular Reasoning?

Suppose we wish to prove $P$ implies $Q$. We assume $P$. Proof by contradiction begins by assuming not $Q$, and from these two assumptions, a "contradiction" is derived. Now, sometimes that ...
1
vote
1answer
37 views

Natural Deduction proof: ∀x¬∀y(Pxy→Qxy)⊢∀x∃yPxy

I'm trying to prove the claim ∀x¬∀y(Pxy→Qxy)⊢∀x∃yPxy in a Gentzen-style system. I know that I will have to use universal elimination to derive ¬∀y(Pay→Qay)from ∀x¬∀y(Pxy→Qxy). I would then use ...
0
votes
1answer
34 views

Why can't we quantify over propositional functions/open formulas in first order languages?

The rule of formation concerning quantifiers in first order languages is If $x$ is a variable and $P$ is a WFF, then ${\forall}x(P)$ is a WFF. Apparently we can't quantify over propositional ...
0
votes
1answer
23 views

In ${\forall}x(P)$, is $P$ any WFF or specifically an open one?

One of the rules of formation for the language of set theory is If $x$ is a variable and $P$ is a ${\square}$, then ${\forall}x(P)$ is a WFF The reason I wrote ${\square}$ is that I have heard ...
0
votes
2answers
18 views

Is there a difference between a propositional function and a WFF? [closed]

These two seem the same, are they? I don't see any differences now, but I'd want to know if there are any.
0
votes
0answers
28 views

How to show that $\lnot q \equiv (p \lor q) \rightarrow p$?

How I can show that $\lnot q \equiv (p \lor q) \rightarrow p$ are equivalent using Law of Algebra Propositional ? I applied in this order: $(p \lor q) \implies p$ implication DeMorgan ...
2
votes
1answer
44 views

Is the dominating number $\frak d$ regular?

For a poset $(P, \leq)$ we say a subset $C\subseteq P$ is cofinal if for all $p\in P$ there is $c\in C$ such that $p\leq c$. We set $$\text{cf}(P,\leq) = \min\{|C|: C\subseteq P \text{ and } C \text{ ...
0
votes
1answer
34 views

Any foundational theory of math falls prey to the incompleteness theorems - true or false?

I heard somewhere on the internet once something along the following lines: Any conceivable foundational theory of mathematics (be it ZFC or, if ZFC was found to be inconsistent, some modification ...
3
votes
1answer
56 views

What is the simplest formal system falling prey to Gödel's incompleteness theorems?

What is the the simplest formal system falling prey to Gödel's incompleteness theorems? Is the answer different for the first and second theorems? Is the answer Q for the first theorem and PRA for ...
1
vote
1answer
19 views

Resolution proof involving more than a literal

I want to show that the following clauses are unsatisfiable together using resolution (i.e. obtain a refutation): 1: $\lnot P_1 \lor \lnot P_2$ 2: $P_2 \lor \lnot P_3$ $P_1 \land P_3$ I perform ...
2
votes
1answer
68 views

Why can't we quantify over propositional functions in the ZFC set theory?

What's the difference between saying if $P(y)$ is some propositional function, then we can create an axiom ${\forall}z{\exists}x:(y{\in}x{\iff}y{\in}z{\land}P(y)$ and saying ...
2
votes
1answer
15 views

conditional proposition vs biconditional proposition

So I have been working on college and am currently in a math class. The following question came up and I chose "->" as the answer. This was marked wrong and I challenged the answer but was told this ...
0
votes
1answer
27 views

What does this clause actually mean?

Consider an instance of 2SAT that is given by the following clauses: $\{\lnot x, y\}, \{\lnot y, z\}, \{\lnot z, w\}, \{\lnot w, u\lnot \},\{\lnot u, \lnot x\},\{x, \lnot u\}, \{u, \lnot w\}, \{w, ...
0
votes
2answers
62 views

Does Second-Order Comprehension make second-order ZFC inconsistent due to Russell's Paradox?

When we do set theory, we take our first-order variables to range over all sets. But if we take our second-order variables to range over sets of sets in the range of the first-order variables, then ...
5
votes
3answers
367 views

Prime numbers on a non-standard model

I can't imagine how this is possible: Let $\mathcal{M}$ be a nonstandard model of arithmetic. Show that: There is an element $a\in M$ such that for all prime numbers $p$, we have that $\mathcal{M} ...
0
votes
1answer
33 views

How to make a WFF defining some other WFF?

We have the following symbols: ${\implies},{\land},{\in},{\lnot}.$ Let $a$ be some WFF, e.g. $a{\lor}b$. I want to define it as $b$, which is ${\lnot}({\lnot}a{\land}{\lnot}b)$. How do I write it? ...
2
votes
1answer
381 views

Puzzle : Truant List of Statements

I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question: The $n^{th}$ statement in a list of 100 statements is : "Exactly $n$ of the ...
0
votes
2answers
32 views

How do these two definitions of $a{\implies}b$ agree with each other?

Let $a$ and $b$ be WFFs. One definition of $a{\implies}b$ one can often encounter is "if $a$, then $b$". The other is ${\lnot}(a\,{\land}\,{\lnot}b)$. How do these two agree with each other? For ...
1
vote
1answer
43 views

Does this sketch proof that every formula is equivalent to one in the arithmetical hierarchy work?

In the lecture notes for my course, the arithmetical hierarchy is defined as follows: A formula is $\Sigma_0$ or $\Pi_0$ if every quantifier is bound; A formula is $\Sigma_{n+1}$ if it is of the ...
0
votes
0answers
39 views

How can one formulation of the axiom of extension define set equality and the second one not?

I've seen the claim that there are two ways of writing the axiom of extension. The first one is ${\forall}A{\forall}B({\forall}x(x{\in}A{\iff}x{\in}B)){\iff}A=B$. This one supposedly admits $=$ as a ...
0
votes
1answer
32 views

proof by resolution?

Consider the following sentence: $$[(F \implies P)\vee(D \implies P)] \implies [(F \wedge D) \implies P]$$ I am not too familiar with how to prove by resolution, from what I found online, I need to ...
0
votes
2answers
36 views

finding a formula for a given truth table

How would one proceed in finding a formula from a given truth table without resort to the use of disjunctive normal form and karnaugh maps? For example, given ...
0
votes
1answer
28 views

Statement problems

It was a hot day and four couples drank together 44 bottles of cold drink. Anita had 2, Biva 3, Chanchala 4 and Dipti 5 bottles. Mr. Pannikar drank just as many bottles as his wife, but each of the ...
0
votes
2answers
43 views

How to solve this logic question without going directly to truth tables?

Which of the following equations is equivalent to $(x \lor y) \implies z$? The answer is E - but how can we solve it without using truth tables directly - using little theorems and identities? A: ...
1
vote
2answers
64 views

Why does $a{\iff}b$ mean that $a$ is the definition of $b$?

As an example of what I'm talking about, the axiom of extension $({\forall}A{\forall}B{\forall}x)(x{\in}A{\iff}x{\in} B){\iff}A=B$ is often used as the definition of set equality. Why is defining $a$ ...
0
votes
1answer
38 views

Unary predicate for finite number of values

I am working with automated prover. I am creating a theory, where an unary predicate PR should be true just for several constants, false otherwise. I made following axioms: ...
1
vote
1answer
99 views

$A*$ finite or infinite? (Set theory)

I have a question regarding the following: If $A$ is a set, then by $A*$ we mean the set of all finite rows of elements of $A$. Now suppose $A$ is finite. How big is $A*$, and how can you see ...
-1
votes
0answers
40 views

Does Tennenbaum's Theorem apply to MA+TCO?

I recently asked Does Tennenbaums Theorem apply to Modular Arithmetic?. Based on issues brought up from that question I now want to ask if Tennenbaum's theorem applies to the slightly stronger theory ...