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)

5
votes
1answer
203 views

Anyone encounter these Logic symbols?

These diagrams are equivalent representations of the 2-ary boolean functions. What are the symbols used in the top left diagram? (Source: wikicommons user mate2code)
3
votes
1answer
411 views

Working with negation of quantifiers

How would you prove $\exists x\neg P(x)$ given $\neg \forall xP(x)$ using first-order logic?
2
votes
1answer
98 views

What is the difference between $Γ⊭Φ$ and $Γ⊭¬Φ$?

Did I understand this correctly? $Γ⊨Φ$ ($Φ$ is considered true) $Γ⊨¬Φ$ ($Φ$ is considered false) $Γ⊭Φ$ ($Φ$ is considered neither true nor false) $Γ⊭¬Φ$ ??? Please help me understand. How can ...
-1
votes
2answers
114 views

Applying the compactness theorem

Using a Hilbert system: L is a FOL (First order language) with R, where R is a single binary predicate symbol. Suppse A = ⟨V,E⟩ is a structure for this language domain V = |A|. Suppose also that E = ...
1
vote
2answers
175 views

Formal deduction in first order logic

How do you show that a deduction exist in the Hilbert Proof System, as used in Herbert Enderton, A Mathematical Introduction to Logic. L is a FOL (First Order Language) which contains R, where R is a ...
0
votes
1answer
55 views

Are these 2 expressions tautologies?

(m=n)↔(n⊕(¬m)) (m≠n)↔(¬(n⊕(¬m)) Is it true? I can need functions that switch like these for my application. But I want to make sure I'm not yielding falsehood. ...
8
votes
6answers
6k views

Is the empty set a subset of itself?

Sorry but I don't think I can know, since it's a definition. Please tell me. I don't think that $0=\emptyset\,$ since I distinguish between empty set and the value $0$. Do all sets, even the empty ...
1
vote
1answer
74 views

Coding a sequence into a natural number by map $f$ with $f(k_1, .., k_n) + f(k_{n+1}, .., k_{2n}) = f(k_1 + k_{n+1}, .., k_n + k_{2n})$

Has anyone discovered a way of coding a sequence of natural numbers into a natural number by map $f$ that has the following property $f(k_1, .., k_n) + f(k_{n+1}, .., k_{2n}) = f(k_1 + k_{n+1}, .., ...
1
vote
1answer
149 views

Truth-teller sentences in automated proof-checking machine

Let M be an automated proof-cheking machine which works for ZFC. Let set A be a set of all "well-formed" mathematical logic sentences. For any x∈A, I think M(x) will work in ZFC. Let sentence m be ...
2
votes
1answer
50 views

Statements true for all n Vs. statements true as n->infty

Let P be a statement. What are the necessary and sufficient conditions for the following statement to be true? (P is true $\forall n \in \Bbb N$)$\implies$(P is true as n$\to \infty$) As background ...
1
vote
0answers
63 views

Direct Proof and Proof by Contradiction [duplicate]

This might seem like a random question but I am wondering can every theorem that can be proved through contradiction be proved directly or vice versa, that is is one a subset of the other or is there ...
0
votes
1answer
90 views

Can a mathematical difference not also imply a disjunction?

Is there a disjunction for every difference? E.g. 2-1=1 which implies a disjunction e.g. the sets 1 and 2 are disjunct. So can there not be any difference that not also implies a disjunction?
4
votes
1answer
98 views

Is this expression true and legal?

I want to write it simple and easy but I'm not sure about precedence A→B & NOT A→ NOT B ↔ NOT A XOR B = 1 I want to express ((A→B) & (NOT A→ NOT B)) ↔ (((NOT A) XOR B)) = 1 Are the two ...
0
votes
1answer
91 views

formal consequences in logic

How can we show that for all $n$, $k$ elements of Naturals, with $n < k$, that $\text{PA} \vdash \underline{n} < \underline{k}$? This is the idea of formal consequences. Also, For all $k$ in ...
2
votes
2answers
100 views

Can argument forms be sound?

So, the definition of a valid argument form is that the truth of the conclusion is guaranteed via the truth of the premises. Soundness is often said to be a valid argument where the premises are true. ...
0
votes
2answers
84 views

Non-isomorphic structures with equal cardinality

Let $\mathfrak{A}=(\mathbb{N},S,0)$ be a structure where $S$ is the sucessor function. Let $\mathfrak{B} =(\mathbb{N}\times \{0\} \cup \mathbb{Z} \times\{1\} ,S, 0)$ with $0 = (0,0)$ and $$ S(k,i) ...
2
votes
3answers
190 views

How can {→,⊕} be complete when {¬,⊕} isn't?

Please provide an example with {→,⊕} that can't be realized with {¬,⊕}. I can't think of what I can't realize with {¬,⊕}. I have a simple model where I think the bottom is more like YES ⊕ NO (and ...
2
votes
1answer
2k views

Any functionally complete sets with XOR?

According to wikipedia, the set {^, ¬} is functionally complete. But is there any 2-set functionally complete set with XOR (e.g. (¬A) ⊕ A is always true). I'm looking for a 2-set functionally ...
0
votes
1answer
50 views

Prove the following “connected” problem

There are $n$ people in the room, some know each other and some don't. If $i$ knows $j$, then $j$ knows $i$. Suppose that for every four different people there exists one who knows the remaining ...
1
vote
2answers
123 views

Need help with solving proposition logic formula, should be a tautology

I have the following formula: $(((p \vee q) \rightarrow r) \wedge (p \rightarrow q))\rightarrow (q\rightarrow r)$ The truth table for this formula shows that this is a tautology. However, I get ...
2
votes
2answers
113 views

Is it true that $((A\rightarrow B)\land(¬A\rightarrow ¬B))↔((¬A) \;\;\text{⊕}\;\; B)$? [closed]

Is $((A\rightarrow B)\land(¬A\rightarrow ¬B))↔((¬A) \;\;\text{⊕}\;\; B)$ true? I found it's true but I don't know what to use it for besides refactoring. How interesting is the statement A→B if not ...
13
votes
2answers
303 views

A sentence false in a field of characteristic $0$ but true in all fields of positive characteristic?

Consider the language $L=\{+,\cdot, 0, 1\}$ of rings. It is easy to show using compactness that if $\sigma$ is a sentence that holds in all fields of characteristic $0$, there is some $N\in \mathbb N$ ...
10
votes
4answers
664 views

How does one show a set of axioms is independent? (of each other?)

I am being asked to show that the groups axioms of existence of an identity, of inverses and of associativity are independent. Does this mean that none of two of them imply the third? That is: do I ...
2
votes
2answers
32 views

Get A⊕(B+1) from A⊕B

I have numbers A,B,C.D. (⊕ is XOR) C = A⊕B D = A⊕(B+1) Is there any way to get D from C, when I do not know A and B? How? Thanks for help!
2
votes
1answer
301 views

Two questions on “Mathematical Logic” by Ebbinghaus, Flum & Thomas

My first question is on the relationship between ZFC and first order logic: "A reader who has been confused by the discussion in this chapter says, "Now I'm completely mixed up. How can ZFC be used as ...
1
vote
1answer
118 views

Cantor's diagonal argument without equality

Trevor Wilson posted an answer while I was preparing an edit to the question. I think Trevor would have given essentially the same answer to the modified question. But, to make things as clear as ...
8
votes
1answer
180 views

Independence results that cannot be established by forcing.

I read the Wikipedia article on Absoluteness recently and found mention of Shoenfield’s Absoluteness Theorem, which states that if $ \phi $ is any $ \Sigma^{1}_{2} $- or $ \Pi^{1}_{2} $-sentence of ...
0
votes
1answer
72 views

L-sentences and spectra [duplicate]

Is there an example of a sentence with spectrum {p|p is prime}? I may need to resort to some theorem of Algebra, but not sure if it will help. Thanks
2
votes
2answers
86 views

Prove Γ ⊢ ¬¬φ is formally provable from Γ ⊢ φ

This is a mathematical logic problem on the Sequent Calculus Γ ⊢ φ Γ ⊢ ¬¬φ (Prove Γ ⊢ ¬¬φ is formally provable from Γ ⊢ φ ) Since "¬¬" is not generated by any of the rules, I have tried to use ...
4
votes
1answer
108 views

Spectrum of elements in a set

Suppose that $X$ is a spectrum. Is $\mathbb{N}\setminus X$ a spectrum? By spectrum, we mean that it is the set containing all natural numbers $n$ s.t. there is a model of $\phi$ with exactly $n$ ...
1
vote
1answer
327 views

Well formed formulas of all mathematical proof

Last week, I asked the "automated proof-checking machine." Many answered that automated proof-checking machine already exists in first-order theory. However I have still question. For the operation ...
4
votes
3answers
257 views

Exercise in propositional logic.

Which of the following arguments is valid? A. If it rains, then the grass grows. The worms are not happy unless it rains. Therefore, If the worms are happy , then the grass grows. B. If the wind ...
3
votes
1answer
95 views

What is the (propositional) logic associated with an orthomodular lattice?

In Quantum Mechanics the space of projections on the associated Hilbert Space of States forms an Orthomodular Lattice. Von Neumann calls this a Quantum Logic. When projections commute they generate a ...
2
votes
2answers
229 views

Help with the proof that an initial proper segment of a sentence can't be a sentence

I'm reading Peter G. Hinman-Fundamentals of Mathematical Logic, I'm new with stuff like proofs, and as newbie I'm not used to proving anything, so I'm jammed in the exercises of the book of the ...
6
votes
5answers
215 views

$\forall m \exists n$, $mn = n$ True or False

Identify if the statement is true or false. If false, give a counterexample. $\forall m \exists n$, $mn = n$, where $m$ and $n$ are integers. I said that this statement was false; ...
3
votes
3answers
934 views

How to Negate These Statements Containing Logical Connectives?

I have a few questions that I am working on, that I supposedly answered incorrectly. I have the following statements that I am charged to express in symbolic form: $f =$ you are a full-time student; ...
0
votes
1answer
47 views

Does the term consistency (for equations) have some logical meaning?

Let $\phi(x_1,...,x_n)$ be a statement about an equality of two expressions having $x_1,...,x_n$ respectively. If there is no $(x_1,...,x_n)$ such that $\phi(x_1,...,x_n)$ is true, we call this ...
1
vote
1answer
198 views

Bijection and Natural elements

I'm trying to establish that the set of $L_{PA}$ terms and $p$ an element of the $N[x_1,\ldots,x_n]$ where $N$ = naturals, for some $n$ in the Naturals are in a bijection. Well, the $L_{PA}$ terms ...
2
votes
1answer
102 views

What would be arithmetic hierarchy of $\Sigma_1^0 \wedge \Pi_1^0$?

What would be arithmetic hierarchy of the form of formula like $\phi \wedge \psi$ where $\phi$ is $\Sigma_1^0$ and $\psi$ is $\Pi_1^0$? Prenex normal form seems to give me no answer for this.
2
votes
1answer
114 views

Are Horn clauses always universally quantified?

I know that the original publication ' Alfred Horn (1951), "On sentences which are true of direct unions of algebras" ' didn't require universal quantification. However, it didn't call these Horn ...
-1
votes
1answer
217 views

Unconventional models and Peano Arithmetic

I'm trying to show that $\mathbb{Z}[x]^+ \models \mathsf{PA}^-$. What are the initial segments of this model?
1
vote
2answers
137 views

Models and Inconsistency.

I’m trying to show that a first-order theory $ T $ is inconsistent if and only if $ T \vdash \varphi $ for every w.f.f. $ \varphi $. I understand that there might be a need to use the axioms for $ ...
1
vote
2answers
161 views

Paradox - What is wrong with this proof that proves a false assertion?

Theorem: Let $a_{n}=a_{n-1}+1, a_1=1$. For any $n$, in order to compute $a_n$, it is necessary to compute $a_i$ for each $i=1,\dots,n-1$, which takes $\Theta(n)$ time. Proof: This is vacuously true ...
2
votes
2answers
138 views

Proving if Boolean Equations are valid

I need to prove algebraically that: $$ab + abc'd + abde' + abc'e + a'b = b$$ $$(wxyz)(wxyz' + wx'yz + w'xyz + wxy'z) = 0$$
26
votes
7answers
1k views

Are there infinite sets of axioms?

I'm reading Behnke's Fundamentals of mathematics: If the number of axioms is finite, we can reduce the concept of a consequence to that of a tautology. I got curious on this: Are there infinite ...
-1
votes
2answers
146 views

How many possible operations are there of arity n? (N-ary) [closed]

Not sure about this one! Can someone please help? Thanks
13
votes
1answer
277 views

Do you need the Axiom of Choice to assert that every real vector space has a norm?

Math people: This question is 95% answered (the first answer) at Does every $\mathbb{R},\mathbb{C}$ vector space have a norm? and Vector Spaces and AC . The questions, answers, and links found there ...
0
votes
1answer
92 views

Computability function - how to express it in set theory/arithmetic hierarchy

Let's say that $f$ is computable function such that for particular inputs $x$ and $y$, $f(x) = 0$ and $f(y) = 0$. If we want to express this in logical form (arithmetic hierarchy formula), what would ...
1
vote
5answers
244 views

There are four possible operations of arity 1. What are they?

I know negation is one but cant think of anything else? I need three more!
1
vote
1answer
102 views

function that cannot be expressed using finite characters

There are functions that cannot be expressed using finite characters. For example while function $x^3$ can be written using finite characters there exists a sequence of cartesian pair, describing ...