3
$\begingroup$

I try to express the following statements in first order logic:

  1. X is a subset of Y.
  2. A set can be uniquely characterised by its elements.
  3. The power set p(X) contains all subsets of X.
  4. A set X is the union of all its subsets containing just one element.

Thus far I managed:

  1. $\forall x \in X \Rightarrow x \in Y$
  2. $X=Y \Leftrightarrow (\forall x \in X \Rightarrow x \in Y \land \forall y \in Y \Rightarrow y \in X)$
  3. $ x \in p(X) \Leftrightarrow (\forall y \in x \Rightarrow y \in X) $

However now I don't know to express the 4th problem via FOL.

I tried: $ X = \cup x.(\forall z \in X \exists t. z \in t \land t = x \land z \not \in \forall y. y \neq t)$

If possible I would also like to convert 3. in an expressing $p(X)$ with $=$ rather than $\Leftrightarrow$

Any form of constructive comments are welcome. Thanks in advance.

EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

$ X = \underset{|x| = 1, x \subset X} \cup \Leftrightarrow \forall y \in X \exists x . (y \in x \land \lnot \exists z .(z \lnot = x \land y \in z) ) $

On the LHS of $\Leftrightarrow $ I simply tried to express the property given in the problem above and on its RHS I tried to express this property in terms of FOL.

$\endgroup$
4
  • $\begingroup$ The usual language of set theory includes only two relations: equality and set containment ($\epsilon$). That mean that you have to tell us how you represent the operation of set union. $\endgroup$ Mar 19, 2017 at 15:30
  • $\begingroup$ This is not a question for us, it is a question for your instructor. $\endgroup$ Mar 19, 2017 at 15:46
  • $\begingroup$ The instructors are not reliable, they may answer anytime between 1 day to two weeks. Thus I try to do as much as possible by myself, then try to rely find material other sources online and if nothing helps, I post here. $\endgroup$
    – Imago
    Mar 19, 2017 at 15:49
  • $\begingroup$ Unfortunately we are not able to help you cope with your instructors. You can try contacting a TA. $\endgroup$ Mar 19, 2017 at 15:52

1 Answer 1

1
$\begingroup$

It might be useful to take a look at the ZFC axioms. The existence of one element sets is guaranteed by the Axiom of pairing.

The axiom of pairing says that given $A$,$B$ sets, one can construct a third set $C = \{A, B\}$. Formally: $$ \forall A. \forall B. \exists C.\forall D. (D \in C \iff D = A ~\lor~ D = B) $$

A singleton set is just the pairing $\{A,A\} = \{A\}$.

The axiom of union says that for any set $A$ there is a set $U$ whose elements are exactly the elements of the elements of $A$. That is:

$$ \forall A. \exists U. \forall c. (c \in U \implies \exists D.(c \in D ~ \land ~ D \in A)) $$

A set $X$ is the union of all its subsets containing just one element.

Let's look at some example, let $X = \{a, b\}^\star$ be a set, take $X^\prime = \{\{a\},\{b\}\} $, which is also a set by the axiom of pairing. By the axiom of union there exists a set $\cup X^\prime$ such that:

$$ \cup X^\prime = \{a,b\} = X$$

So you can look at the Union Axiom and try to modify to fit your problem, you have to make a union on a set of singleton sets, which means you have to find a way to define $X^\prime$.

$\star$: I'm assuming $a$ and $b$ are also sets.


EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

Well, from your previous answers it seems you're only allowed to use basic operations like membership and equality, if more stuff is allowed you can literally just write something that looks like natural language while still being formal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.